アルゴリズム の学習の一環としてCourseraの "Algorithms, Part I" を完了した。
www.coursera.org
先日アルゴリズム に関する学習教材を探していた折、同講座に関する満足の声を見かけたのでやってみることにした。（英語のレビューは上記ページに載っている）
時間はかかったが全課題を及第点以上で完了できた!!
"Algorithms, Part I" とは何か
Princeton大学がCourseraで公開している、アルゴリズム に関する講座である。Part I, IIの2つの講座があり、Part Iでは基本的なデータ構造、ソート、および検索アルゴリズム を扱う。本記事ではPart Iの話をする。*1
コースの説明には "This course covers the essential information that every serious programmer needs to know" という強い言葉が書かれており、今すぐやれと煽られている気がしてくる。
この講座の公開は2012年頃とのことだが実に基礎的な領域を扱っているので教材としての価値は2020年でも全く衰えていなさそうだ。むしろ半世紀を超えてなお現役だったりするアルゴリズム たちを学ぶことで、廃れることなく有用な知識とは何であるかということを改めて考えさせられる。
無料
この講座は動画の視聴〜課題の採点まですべて無料。ただし修了証明書の発行はなし。
満足度がすごく高いのでお金を払いたいぐらいなのだが…。
講師
動画の講師はRobert Sedgewick先生。講座内容はセジウィック 本（英語圏 ではアルゴリズム 解説の定番書とのこと。600ページ超のなかなか重そうなやつ）をベースにしている。
英語字幕は全編にわたって存在する。ちなみに日本語字幕は一部講座のみにしか存在しないのであてにしないほうがよい。
ボリューム
公式には "Approx. 53 hours to complete" と書かれている。自分の場合は57.5時間かかった。
「動画を見る -> 課題を解く」
のシンプルな構成を素直にやったわけではなく、
「動画を見る -> 英語or内容が理解できなければ巻き戻す -> 理解できた内容をノート に書く -> 課題を解く」
のように丁寧に学習した。課題は平均して6.5時間ぐらいで終えたと思う。((各週に用意された課題1つ解く目安が8時間とあるので課題だけでも8 * 5 = 40時間かかる計算のようだ))
課題はすべてJava で提出する。
5年以上Java から離れて過ごしてきたので不安だったが、IntelliJ IDEA Community Editionとプロジェクトファイルが提供されるので環境構築で躓くことはなかった。format on saveとか、findbug on compileとかも入っていた。
課題を解く上で要求されるJava 自体の知識というのはほとんどなく、条件分岐やオブジェクト指向 など一般的なプログラミングの知識があればあとはJava の記法を調べてコードに落とし込むだけだった（まぁそれでいらいらすることもあるのだが…）。実装対象のクラス名やpublic API は指示があるし（従わないと採点不可になる）、Iterator やComparetorなどで込み入った実装をする際には記法のサンプルが提示されている。
動画内でのセジウィック 先生の解説もJava ベースだが、こちらもJava の練度が理解を大きく左右するような箇所は殆どなかったと思う。
良かった点
実践的で頭を使う課題
Week 6を除きすべての週に課題が用意されており、これが非常に良かった。解説したアルゴリズム をそのまま記述しろというようなお勉強ぽい内容は少なく、「現実世界ではこのような問題を解くのにアルゴリズム が使われるぞ」というのを実感できる内容が多かった。
また、API デザインを変えずに内部実装の工夫で高速化や効率化を測る工夫が求められるのも良い。現実でもそういうシーンがしばしばある、と語っておられた。
ナイーブな実装では要求するパフォーマンスを満たせ無いことが多い。採点では何よりも正しく実装することへの配点が大きいものの、パフォーマンスやメモリ使用量に関するペナルティでもしばしば減点される。
ちなみに課題採点は完全に自動化されておりいつでも何度でも提出ができるし、ローカルで実行可能なテストデータも提供される。
（どんなに質の高い講義動画であってもずっとPCの前で話を聞くだけだと眠くなってしまうので手を動かす課題のほうが面白いというのもある）
解説が丁寧
科学的なパフォーマンスの解析に焦点をあてる、とコースの説明に書いてあるのだが予想以上に丁寧だった。
ざっくりとした計算量オーダーを見積もって終わるのではなく最悪実行時間、償却実行時間、期待実行時間それぞれについて時間を割いているので知っているつもりのアルゴリズム の違う側面が見えたりする。
応用事例に広く触れている
学ぶ内容は基礎だが、各種データ構造とアルゴリズム の応用事例に触れていることが多く、全体的に応用への強い意識を感じる。
たとえばStackの利用シーンとしてJVM , エディタのUndo, ブラウザのバックボタン, コンパイラ における関数呼び出しの管理を挙げたり、Priority QueueについてはイベントドリブンなシミュレーションやゲームAIの話になったり。
全6週をおさらい
学んだ内容を軽くおさらい。
解法までは書いていないが課題についても触れるので一切の事前情報なしに挑戦したい人は一番下の「まとめ」まで飛ばしてほしい。
Week 1: Union-Find, アルゴリズム の解析
前半ではUnion-Findを扱う。要素のグループ分けを木構造 で管理するデータ構造です…みたいなことを言われてもフーンという感じだが、この講座では「Quick Find -> Quick Union -> 改良版Quick Union」の順に実装を詳解し、アルゴリズム の問題点の指摘から計算量の劇的な改善に至るまでを俯瞰する。
「コンピュータの速度がいかに早くなろうともアルゴリズム の強力さは一切失われず、それどころか、扱うデータや人々の性能への期待が増え続けるのでより重要にさえなっていく…」というようなことをSedgewick先生がたびたび言うのだが、冒頭からそれを言葉でなく心で理解できるようにしている講座設計が非常に良かった。
課題
講義で解説したUnion-Findはライブラリとして提供されるので、それを利用してpercolationを扱う課題。*2
https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php より引用
盤面にランダムに穴を空けていったとき、何回の操作でpercolationが発生するかをモンテカルロ法 で求める。
Week 2: Stack, Queue, 基礎的なソートアルゴリズム
StackとQueueという基本的なデータ構造の解説。
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid にも書いたのだが、基本的なデータ構造のインタフェースと性能を知るだけでなく内部実装の違いを学べるのが面白い。
課題
双方向キューのDequeとRandomizedDequeの実装を行う。
インタフェースを理解したうえでリストで実装するか、配列で実装するかなどを考慮する。
また、配列で実装する場合には性能要件を満たすためにresizeの実装を工夫する必要がある。
Week 3: Mergesort, Quicksort
主要なプログラミングの内部でも多く使われているマージソート とクイックソート に関しては詳細な解説があった。
重複キーが存在するケースの性能や安定ソートの問題に触れたり、データ型の定義とソート処理ロジックの分離（ソート条件ごとのComparatorを用意する）など。
クイックソート の応用で重複するデータを検査せずに分割を完了することができるDijkstra 's 3-way partitioningなど、発展的な内容も一部あった。
課題
平面内にあるn個の点から4つ以上の点を接続するすべての線分を見つける課題。パターン認識 の基礎。
https://coursera.cs.princeton.edu/algs4/assignments/collinear/specification.php より引用
まずBruto forceで解いて、次にソートを上手く利用して高速化するよう促される。
安定ソートの問題に直面する。
Week 4: Priority Queue, Symbol Tableの基礎
Stack, Queueと違い、追加順ではなく最小または最大の要素をremoveするPriority Queueを扱う。内部実装の解説でヒープについても触れる。
ヒープの要素が整列される様子がアニメーションで解説されるのだが、Sedgewick先生がピーターの法則 に言及していたのが面白かった。
課題
スライドパズル をPriority Queueを使って解く。
https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/specification.php より引用
これはなかなか難しかった。基本的には幅優先探索 なのだが、各盤面がどれだけゴールに近いかを評価して高速化を図るのが工夫のしどころ。
このように評価関数（ヒューリスティック 関数という）を導入するA*アルゴリズム 自体は知っていたのだが、ほんの少し関数をいじるだけで実行速度が段違いになるというのは手を動かさないとなかなかイメージできなかったので良い演習になった。
Week 5: Balanced Search Tree, Geometric Applications of BSTs
テーマはBST全般だが、この講座の白眉であるRobert Sedgewick先生が研究していた赤黒木の解説が遂に来る。
実際、赤黒木の解説は力が入っていると感じた。他の動画はたいてい10~20分なのに赤黒木の説明動画だけ35分もある（確かに木の操作とか説明に時間がかかる内容ではあるが）。
Sedgewick先生が赤黒木の論文を書いたのが1979年、大学の講義で赤黒木を扱う中で2007年にさらに改良された実装を見つけたという話と、"there are simple algorithms still out there waiting to be discovered and this is one of them that we're going to talk about." という言葉はグッときた。
課題
平面上で最も近い点を求めたり、図形の中にどの点が含まれているかを検出する。
https://coursera.cs.princeton.edu/algs4/assignments/kdtree/specification.php より引用
この課題ではKd-treeというデータ構造を用いる。このデータ構造は講義の動画を見るだけではあまり理解できなかったのだが、実際に課題でアルゴリズム を書く中でようやく理解できた。
また、一見すると木構造 とは関係なさそうな平面や立体上の問題も木構造 に落とし込むことで強力なアルゴリズム を活かすことができるという学びもあった。
Week 6: Hash Table, Symbol Tableの応用
最終週の主な内容はHash Table。衝突回避の方法としてSeparate chainingとLinear probingの両方を学んだり、Hash TableとBSTのどちらを使うべきかを考察したり、脆弱なハッシュ関数 が起こした過去の問題などについても触れた。
最後のSymbol Tableの応用では現実のアプリケーションとの関連を解説。ここはこれまでの内容を深堀りするのではなく事例紹介という感じ。
最終週の課題はなくてちょっと寂しかった。
まとめ
「アルゴリズム の基礎をしっかり学びたい」という自分の要求に照らし合わせると素晴らしい教材だった。
すでに学んだ経験がある人の復習に適しているかはわからないが、理解度を試すためにプログラミング課題に挑戦してみるのは面白いと思う。
真面目にやると50時間以上かかるボリュームがあるので怖気づくが、「コンピュータサイエンス を専攻した人はこのレベルの内容を学部4年間で修了している」と思えば追いつくには時間をかけるしかない。短期間で知識を身に付けるには単に量をこなすだけではなく質も大事なのでこうした有用な教材に積極的に挑戦していきたい。
より発展的な内容にフォーカスする "Algorithms, Part II" にはまだ着手していないが2020年内には終えるぞ!!
