概要
この記事はUniversity of Colorado Boulder MS-DSのCS Pathway 1つ目である、DTSA 5501 Algorithms for Searching, Sorting, and Indexing の講義メモである。
Courseraで公開されているカリキュラムの時系列に沿って記述していく。
コースの目的
アルゴリズムの設計と分析の基本（ビッグO記法/ビッグΩ記法/ビッグΘ記法）に加えて、配列のソート、優先度付きキューなどのデータ構造、ハッシュ関数、bloom filter、count-min sketch、文字列照合などについて学ぶ。
指定テキスト
CLRSこと "Introduction to Algorithms 3rd edition"（邦訳は『世界標準MIT教科書 アルゴリズムイントロダクション 第3版』近代科学社）
本講義では総合版の1章、6章、7章、9章、10章、11章を参照する。
本講義だけなら分冊第1巻だけで足りるようだが、その他のコースを受講するなら分冊第2巻も購入するか、総合版を買うのを個人的に薦める。
Statistics Pathwayから進んだとしても本講義群はコア科目のため、動的計画法と貪欲アルゴリズムを学ぶ際に第2巻の内容を学ぶ。
CLRSの章末問題の解答はこちらで公開されている。
指定テキストがない場合は、イリノイ大学の Jeff Erickson教授が公開しているテキストが参考になる。
講義の前提条件
- 数学的背景
アメリカのSTEM教育を受けている大学1年生レベルの数学- 集合と関数
- 対数と指数
- 等差数列と等比数列の合計
- 確率論
- プログラミングの背景
- Pythonの基本的な制御構造：条件分岐、forループ、再帰
- 関数
-
listとdict class
モジュール1
モジュール1の概要
- 挿入ソートについて
- 漸近表記
- 最悪の場合の複雑さを定義する
- マージソートと二分探索を学習する
挿入ソート
講義ビデオやテキストの通りなので、真新しく感じる内容もないだろうから割愛。
漸近表記
情報技術者試験でよく出てくるビッグ$O$記法が有名か。
| 漸近記法 | 意味 | 例 | 備考 |
|---|---|---|---|
| $O$ | 計算量の上限 | $5n^2 + 3n +1 = O(n^2)$ | 最大の計算時間を表す $5n^2 + 3n +1 = O(n^4)$も意味は薄れるが、$n^4$よりも計算量が大きくならないという意味で正しい |
| $\Omega$ | 計算量の下限 | $5n^2 + 3n +1 = \Omega(n^2)$ | 最小の計算時間を表す $5n^2 + 3n +1 = \Omega(n)$も意味は薄れるが、$n$よりも計算量が小さくならないという意味で正しい |
| $\Theta$ | 計算量の上限と下限 | $5n^2 + 3n +1 = \Theta(n^2)$ | $O$と$\Omega$をかけ合わせた概念 理想的な入力でも最悪な入力でも、計算量はこの程度だと見積もれる |
この講義では多くの場合$\Theta$を用いている。
二分探索
講義ビデオやテキストの通りなので、真新しく感じる内容もないだろうから割愛。
マージソート
講義ビデオやテキストの通りなので、真新しく感じる内容もないだろうから割愛。
講義内容とは重ならないが、マルチスレッドのマージソートアルゴリズムを書いてみたい。
モジュール2
モジュール2の概要
- データ構造の必要性とプログラミングでの利用例
- 最小/最大ヒープとその影響について
- 挿入/削除の正確性と実行時間の分析
- ヒープで効率的に解決できる問題と、ヒープが最適ではない問題
- ハッシュテーブルのデータ構造と構成
- ヒープとハッシュテーブルの違いと、ハッシュテーブルの利用シーン
動的配列
リスト自体はポインタだということを、Pythonだけ利用していると忘れがちになる。
リストとは、そのリスト用に予約されているメモリ内の領域にすぎない。Cなどでは自分で領域を確保するため、この動きを理解しやすい。
データを挿入するとき、目的の位置に値を挿入した後でリストの後の要素は1つずつ後ろへずらす必要がある。
同様にデータを削除するとき、目的の値を削除した後でリストの後の要素は1つずつ前へずらす必要がある。
この2つの操作はデータ量が大きくなるほど計算量も膨大になっていく。
もしも確保していたメモリ領域を使い切った状態で値を追加しようとするなら、メモリ領域の再配置が必要になる。この際、古い領域から新しい領域へ値のコピーが発生する。
辞書ならどうなるだろうか。
辞書はキーに対して値が関連付けられる。キーは一意の値であり、同じキーを2つの値に関連付けることはできない。
キーはハッシュテーブルを利用して実装されている。ハッシュテーブルは後述する。
辞書は値の参照先を保存したものなので、データ構造自体の計算量は少ない。その代わり、参照先に実際の値が格納されているため、リストと比べるとメモリを多く必要とする。
ヒープデータ構造
ヒープは木構造だが、リストで表現できる。
$i$番目の要素の左側の子は$2i$番目の要素であり、右側の子は$2i + 1$番目の要素であり、$j$番目の要素の親は$j \div 2$(切り捨て) 番目の要素である。
最小ヒープでは、すべての親ノードが子ノードの値より小さいまたは等しい状態になっている。たとえば [2, 3, 5, 7, 4, 9, 5] は最小ヒープである。
最大ヒープではその逆で、すべての親ノードが子ノードの値より大きいまたは等しい状態になっている。
バブルアップとバブルダウン
次のリストはどうであろうか。[2, 4, 7, 6, 5, 6, 8, 9, 10]
7は6より大きいため、最小ヒープ違反が起きている。ここで6をひとつ上の階層に移動させて7と入れ替えれば違反は消える。
このようなスワップ操作をバブルアップと呼ぶ。
もしも1回の操作で最小ヒープ違反が解消しない場合は、再帰的にバブルアップを繰り返す。
ヒープから要素を削除した場合、その位置に空きができる。
再度上記のヒープから、4を削除する。
1. [2, 6, 6, 5, 7, 8, 9 ,10]
2. [2, 6, 6, 5, 7, 8, 9, 10]
3. [2, 5, 6, 9, 6, 7, 8, 10]
4. [2, 5, 6, 9, 6, 7, 8, 10]
実際には3と4の間で空白データは存在しないため、3の時点で最小ヒープ違反が解消されて4の形になっている。
ハッシュテーブル
Pythonの辞書はハッシュテーブルである。代表的なハッシュテーブルとは表（多次元配列）である。
あるハッシュ関数にキーを入力したとき、ある数で割った余りの値（モジュロ）と同じインデックスに値が存在しない場合、そのキーに対する値オブジェクトのポインタがリストに追加される。
次に同じハッシュ関数に別のキーを入力し、同じモジュロが出現したとき、リストの最後へ該当する値オブジェクトのポインタを追加する。
モジュール3
モジュール3の概要
- クイックソートアルゴリズムの理解と実装
- クイックセレクトアルゴリズムの理解と実装
- クイックソートおよびクイックセレクトアルゴリズムの実行時間評価
クイックソートアルゴリズムの理解
マージソートを行う場合、一時リストを用意する必要があり、それは多くの配列を扱うなら非常にコストが高くつく。
クイックソートは分割統治法である。
配列$A$をソートするとき、ピボットとなる値を決める。
このピボットをパーティションとして、以下のように分割する。
a. ピボットよりも小さい値をすべて含んだ部分配列
b. ピボット
c. ピボットよりも大きい値をすべて含んだ部分配列
a, b, cの部分配列がそれぞれソート済みであれば、a + b + cでソート済みの配列が得られる。
クイックソートは以上を再帰的に繰り返す。
- ピボットを選ぶ。
- 配列のパーティショニングをし、ピボットよりも小さい値の部分配列と大きい値の部分配列に分割する。
- 2つの部分配列でクイックソートを再帰的に呼び出す。
クイックセレクトアルゴリズムの理解
ある配列から$k$番目に小さい要素を探すとする。
クイックソートを行えば $\Theta(n \log n)$で見つかるが、ソートする必要はない。
このときクイックセレクトアルゴリズムを用いると$\Theta(n^2)$で$k$番目の要素を見つけることができる。
- ピボットを決定する。
- 部分配列に分け、パーティションの位置を求める。
- ピボットが$k$番目より左にあれば$k$番目の要素はピボットより右にあるため、次の探索開始地点をピボットの右隣からとする。
ピボットが$k$番目より右にあれば$k$番目の要素はピボットより左にあるため、次の探索終了地点をピボットの左隣までとする。 - 1~3を繰り返す。
- ピボットの位置が$k$番目になったら終了する。
モジュール4
復習中
モジュール5
最終試験
51.87％。試験範囲は講義内容全体から広く。
提出して採点された後、1度だけ10分間の見直し再提出の機会が得られる。制限時間に引っかからなければ再挑戦して点数を上乗せできるだろう。
私は操作方法がよく分からず、修正しないまま再提出をした。
最終試験は受験しなくても講義全体で80％得点していればB評価となりクリアできる。
しかしクイズや課題が満点なら83％となるため、最終試験で4割ほど取ればA評価になる。
成績
92.30点（A）
感想
講義について
評価されるクイズは何度でも挑戦できる。
今まで私が受けてきたCourseraコースと違い、8時間あたり3回制限がないため総当りさえできてしまうのが難点。
poorな英語力でも字幕と板書のおかげで理解しやすい。
古典的なアルゴリズムばかり扱っているのかと思いきや、Count-Min Sketchという2003年発明・2005年論文発表というクイックソートなどと比べれば新しいアルゴリズムも扱っていて面白さを感じた。
課題について
採点アルゴリズムに難があり、様々なソートアルゴリズムの実装が課題なのにlist_.sort()が使えてしまう問題があった。どうやらipynb上で合格できるコードなら何でも通ってしまうようだ。
課題そのものは基本情報技術者試験（持ってないけど）でも扱っているものから先述の比較的新しいアルゴリズムの実装まで幅広い。
採点はされないがアルゴリズムに対する考察軸も与えてくれているので、深く学びたければSlackやフォーラムを利用して議論するとより面白みが深まる。
参考資料
Coursera: Algorithms for Searching, Sorting, and Indexing
Thomas H.Cormen 他 著, 浅野哲夫 他 訳（2013）『世界標準MIT教科書 アルゴリズム イントロダクション［総合版］第3版』近代科学社
Aditya Y.Bhargava著, 株式会社クイープ監訳（2017）『なっとく！ アルゴリズム』翔泳社