アルゴリズムの学習の一環としてCourseraの "Algorithms, Part I" を完了した。
先日アルゴリズムに関する学習教材を探していた折、同講座に関する満足の声を見かけたのでやってみることにした。（英語のレビューは上記ページに載っている）
- Courseraで高評価な「Algorithms, Part I」を使った社内勉強会を開催しています - Hatena Developer Blog
- Coursera Algorithm Part I を受講し終えた - /var/log/kmb.log
- Coursera Algorithms PartⅠを受講しました | Futurismo
時間はかかったが全課題を及第点以上で完了できた!!
"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ページ超のなかなか重そうなやつ）をベースにしている。
セジウィック：アルゴリズムC 第1〜4部 ―基礎・データ構造・整列・探索―
- 作者:ロバート セジウィック
- 発売日: 2018/03/01
- メディア: Kindle版
英語字幕は全編にわたって存在する。ちなみに日本語字幕は一部講座のみにしか存在しないのであてにしないほうがよい。
ボリューム
公式には "Approx. 53 hours to complete" と書かれている。自分の場合は57.5時間かかった。
「動画を見る -> 課題を解く」
のシンプルな構成を素直にやったわけではなく、
「動画を見る -> 英語or内容が理解できなければ巻き戻す -> 理解できた内容をノートに書く -> 課題を解く」
のように丁寧に学習した。課題は平均して6.5時間ぐらいで終えたと思う。((各週に用意された課題1つ解く目安が8時間とあるので課題だけでも8 * 5 = 40時間かかる計算のようだ))
私とJavaとIntelliJ
課題はすべて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
盤面にランダムに穴を空けていったとき、何回の操作でpercolationが発生するかをモンテカルロ法で求める。
Week 2: Stack, Queue, 基礎的なソートアルゴリズム
StackとQueueという基本的なデータ構造の解説。
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalidにも書いたのだが、基本的なデータ構造のインタフェースと性能を知るだけでなく内部実装の違いを学べるのが面白い。
課題
双方向キューのDequeとRandomizedDequeの実装を行う。
インタフェースを理解したうえでリストで実装するか、配列で実装するかなどを考慮する。
また、配列で実装する場合には性能要件を満たすためにresizeの実装を工夫する必要がある。
Week 3: Mergesort, Quicksort
主要なプログラミングの内部でも多く使われているマージソートとクイックソートに関しては詳細な解説があった。
重複キーが存在するケースの性能や安定ソートの問題に触れたり、データ型の定義とソート処理ロジックの分離（ソート条件ごとのComparatorを用意する）など。
クイックソートの応用で重複するデータを検査せずに分割を完了することができるDijkstra's 3-way partitioningなど、発展的な内容も一部あった。
課題
平面内にあるn個の点から4つ以上の点を接続するすべての線分を見つける課題。パターン認識の基礎。
まずBruto forceで解いて、次にソートを上手く利用して高速化するよう促される。
安定ソートの問題に直面する。
Week 4: Priority Queue, Symbol Tableの基礎
Stack, Queueと違い、追加順ではなく最小または最大の要素をremoveするPriority Queueを扱う。内部実装の解説でヒープについても触れる。
ヒープの要素が整列される様子がアニメーションで解説されるのだが、Sedgewick先生がピーターの法則に言及していたのが面白かった。
課題
スライドパズルをPriority Queueを使って解く。
これはなかなか難しかった。基本的には幅優先探索なのだが、各盤面がどれだけゴールに近いかを評価して高速化を図るのが工夫のしどころ。
このように評価関数（ヒューリスティック関数という）を導入する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." という言葉はグッときた。
課題
平面上で最も近い点を求めたり、図形の中にどの点が含まれているかを検出する。
この課題では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年内には終えるぞ!!
