はてなアプリケーションエンジニアの 
id:shiba_yu36 です。
最近自分が基礎的でずっと廃れなさそうな分野であるアルゴリズムを少しずつ学びたいと考えていました。しかし、アルゴリズムはあまりにも基礎分野のため、モチベーションをずっと保ち続けられるかという不安もありました。そこで周りの人も巻き込むことでモチベーションを保ち続けたいと思い、社内で勉強会を開催したいと考えました。
勉強会の教材を選定していたところ、Courseraで「Algorithms, Part I」という非常に高評価な教材を見つけることが出来たので、最近はこの教材をみんなで集まって見ながら議論をするという体裁で社内勉強会を開催しています。実際にやってみると、社内勉強会という形式を取ったのも良く、さらにこの教材を利用したことも良かったと感じています。
少しずつ社内勉強会で講義を進めていき、ようやく半分のWeek3まで終わりました。教材が非常に良かったこともあるので、今回は半分終わった区切りとして、この教材がどのようなものであるか、社内勉強会をどのように行っているか、この教材の前半でどのようなことが学べるかについてまとめてみたいと思います。
CourseraのAlgorithms, Part Iというコースについて
Webサイトは以下の場所で公開されています。このコースはアルゴリズムを基本から学ぶというテーマのものです。半分ほど受けた感想として、以下のような特徴があると感じています。
- アルゴリズムの基礎の基礎から説明してくれるため、前提知識が特に必要ない
- アルゴリズムの分野の教材にしては、講義の説明が非常に分かりやすい
- 基礎といっても、よくあるアルゴリズム入門の教材にあるような簡単な紹介程度に留まらず、そのアルゴリズムやデータ構造の性質や応用についても解説があり、示唆に富んでいる
- エンジニアなら誰でも知っているようなスタックやソートの講義ですら、非常に学ぶことが多い
実際にこのコースの講義内容を見ると、前半だけではスタック・キュー、挿入ソート、マージソート、クイックソートくらいのテーマで講義が進んでいくため、パッと見た感じではあまり学ぶことがなさそうに見えます。しかし、実際に受けてみるとその講義内容は単なるアルゴリズムの紹介に留まらず、そのデータ構造やアルゴリズムの特性は何か、実装にどのようなパターンがありえるか、実装ごとにどのような課題がありどうやって解決できるか、時間計算量やメモリ使用量をどう計算するか(計算量の証明などもある)、その他関連する話題に何があるかなどなど、自分が思っていた以上に学びの多い内容となっていました。
後半になると入門書ではあまり触れられていないアルゴリズムについて学ぶことができます。例えば優先度付きキュー、シンボルテーブル、バランス木などがテーマとなっています。MySQLではインデックスをB+ツリー(バランス木の一種)で実装していたり、ソートを優先度付きキューで行ったりしているので、後半も学ぶことでミドルウェアの実装がなぜこのようになっているか理論を知ることができそうです。
また、前提知識が特に必要がなく、講義内容もアルゴリズムの分野の内容としては分かりやすいことも助かります。勉強しようと思った時に、最初から難しい話をされてもモチベーションが下がるので、継続的に学習するためにもこのような特徴はありがたいです。
コースの評価も非常に高く、1400件近くのレビューが付いているにも関わらず、平均の点数は5点中4.9点となっています。これまで受けたアルゴリズムの講義の中で一番良いというコメントも多いです。実際半分受けてみると、この高評価もうなずける内容となっていました。
社内勉強会の形式
今のところ以下のような形式で行っています。- 特に事前に準備はしなくて良い
- 適当に日程調整して、その日にみんなで一緒にコースのビデオを見る
- ビデオを見ながら、分からない部分や気になったところは議論をし、理解を深めていく
アルゴリズムという分野はなかなかすぐに応用する場所を見つけるのが難しい分野です。それでも継続的に学習をするためにも、出来るだけハードルを下げておきたいと考え、事前準備などは一切せずにビデオを一緒に見て議論する程度にしてみました。
このハードルが非常に低い形式でやってみても、自分の分からなかったところを他の人に説明してもらえたり、議論によってさらに深い理解が得られたりと、一人で学習するよりも効果が高いと感じています。
Week1〜Week3で学べること
ここからはAlgorithms, Part Iの前半で学べる内容について簡単にまとめていきたいと思います。Week1 Union-Findアルゴリズムとアルゴリズムの解析
Week1ではある要素とある要素がつながっているかを判定するというタスク(Union-Find)を題材に、まず非常に簡単なアルゴリズムから始め、その問題点を検討し、さらに改善したアルゴリズムを検討し、...というような流れで講義が進みます。Union Findについては 以下の記事でもまとめました。
この講義を受けることで、あるタスクをこなすためのアルゴリズムを変えることで速度が大きく変わるというアルゴリズムの力について実感することができます。また、アルゴリズムをどのように設計していくかや、時間計算量・メモリ使用量の考え方、またUnion-Findというアルゴリズムがどのように応用可能かなどについても学ぶことができます。ちょっとした変更で速度が数十倍も変わるのを感じられるのは非常に面白いです。
また講義の後半ではアルゴリズムの時間計算量の詳しい解析や、メモリ使用量の解析などについて触れられます。ここについては最初難しいと感じたら飛ばしても良いかなと思います。
Week2 スタックとキュー・基本的なソート
Week2では前半でスタックとキューのデータ構造について、後半で基本的なソートについて解説されます。
スタックの講義では、いつもよく見るLinked-Listによる実装と、Resizing Arraysという配列を使った実装の両方を見て、それぞれの特徴について知ることができます。特にResizing Arrayという考え方はいろいろな場所で使われている考え方(例えばgolangのsliceの実装など)なので、なぜそのような実装が行われているのかの理論を知ることができます。さらに追加として同じような構造であるキューについても学べます。
Queueからランダムに取り出せるRandomized Queueというデータ構造が面白そうだったので、以下のブログで実装してみています。
スタックの応用の部分も非常に面白く、社内では二つのスタックを使うだけで計算式から答えを計算できる操車場アルゴリズムについて議論が起こりました。操車場アルゴリズムについては、以下の記事でも言及しています。
後半のソートの講義では、基本的なソートとして選択ソート・挿入ソート・シェルソートについて学ぶことができます。一つずつのソートについて説明しながら、そのソートの特徴と問題点について議論が進み、さらに次のソートアルゴリズムで解決できないかという流れで進むため、そのソートが生まれた理由についても学習できます。ソートのイメージの動画もあるので分かりやすくなっています。特に挿入ソートはソートのタスクにおいてかなり重要なポジションにいる(クイックソートやマージソートの高速化に使われる)ので、特性を理解しておくと役立ちます。
その他にも次の内容も学べます。
- ソート可能とはどういうことか
- 部分的にソートされている時の挿入ソートの速度について
- シャッフルのアルゴリズムについて
応用では、点の集合があった時に線を引く事でそれらを全て囲むような最小の点集合を求めるというConvex hullというタスクをソートで解決するというものが面白かったです。
Week3 マージソートとクイックソート
Week3では前半でマージソートについて、後半でクイックソートについて解説されます。
前半のマージソートの章では、nlog(n)でソートが行えるマージソートについて、その特徴や計算量の証明を知ることができます。さらにマージソートを高速化するようなテクニック(メモリアクセスを減らす、小さい配列には挿入ソートを組み合わせるなど)にも言及されています。他にも、なぜ比較ソートの時間計算量はnlog(n)までしか減らせないのかについても解説されていました。
個人的にはマージソートはその特徴から考えると、ファイルを使ってソートしたいときでも扱いやすいということに気づけたのが非常に勉強になりました。この特性を知ったことで、なぜMySQLがソートする際にメモリに収まらなかったときはマージソートを利用しているのか、その背景について学ぶことができました。MySQLのソートについて調査したことは、以下の記事にまとめています。
後半のクイックソートの章では、プログラミング言語でデフォルトで提供されるソートの実装によく使われているクイックソートについて、その特徴やいかにしてさらに高速化するのかについて、非常に詳しく解説されます。こちらも今まで普通のアルゴリズムの教科書に載っていて知っているような内容を遥かに超えた知識を解説してくれていました。正直Week1~Week3までの中で一番難しい講義でしたが、全員で議論してなんとか乗り切りました。
特に印象に残ったのは以下の課題について議論が進んだところです。
- クイックソートは最悪ケースでn^2の時間計算量がかかる。非常に大きい配列でこの最悪ケースの入力が与えられた場合、システムが止まってしまう。システムで提供するソートの場合、どんな入力がやってきても止まることのないよう実装する必要があるが、どのようにすれば良いか。
- 最初にshuffleするとか、いくつかピックアップしてその中間値を使うとか、方法がいくつかある
- 重複のあるデータがたくさんあるような配列(例: 1,2,3のみで構成される100万の長さの配列)をどのように効率的に処理できるよう実装するか
- 3-way partitioningという手法がある
まとめ
このように少しずつではありますが、エンジニアリングの基礎分野であるアルゴリズムについて、Courseraの「Algorithms, Part I」という教材を利用して社内で勉強会を開催しています。社内で何人かで集まって勉強会をすることで、モチベーションも保ちやすく、また議論によって深く理解できるようになっていると感じています。「Week1〜Week3で学べること」で少し触れたとおり、この教材の前半で触れられている内容は確かにエンジニアなら誰でも知っているような基本的なアルゴリズムを題材にしています。しかし、それぞれのアルゴリズムが単なる手法の解説に留まらず、特性や問題点、応用にも踏み込んでいることが、他の教材とは一線を画しています。数年エンジニアとして仕事をしている人でも勉強になるような内容になっていると感じます。平均の点数が4.9点となっているのも頷けます。
Week4からは優先度付きキュー、シンボルテーブル、バランス木など、さらに実践的であまりちゃんと勉強したことのないようなアルゴリズムが解説されるので、非常に楽しみにしています。これからも少しずつ勉強会を進めていきたいです。
このようにCourseraの「Algorithms, Part I」の教材は非常におすすめです。是非周りの人を巻き込んで勉強会を開催してみるとどうでしょうか。
