二分探索法とハッシュテーブル

二分探索法とハッシュテーブルの実装例

今Think Complexityでアルゴリズムと複雑系について勉強しています．今回は，自分の勉強を兼ねてThinkComplexity(chap3)で勉強した

二分探索
ハッシュテーブル

について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！

Binary Search（二分探索）の実装

pythonでのBinary Searchの実装方法を2つ紹介します．

例えば，私たちが英語の辞書から単語を探す時に使っているのが Binary Searchです．Binary Searchでは最初から逐次的に調べるのでなく，真ん中から探索を開始し，探している単語がそれより後か前かを調べ，前なら前半を調べ，後なら後半を調べる．この作業を繰り返すことで目的の単語を探索する方法のことを Binary Searchと呼びます．この計算量はO(logn)です．ただし，使用するリストがソートされている事が事前条件です．従って，ソートと探索の計算量はO(nlogn) + O(logn)でO(nlogn)になるかと思います．詳しい説明は色々なところでされていると思うので，説明はこれくらいにして，Pythonでの実装例を紹介します．

下記のコードにある関数bisection()はpythonのモジュールであるbisect を使って実装した例で，関数binary_search() は地道にアルゴリズム通り実装した例です．両関数ともtargetとしている要素がリストにあればそのインデックスを返し，なければNoneを返します．

bisection()では，挿入点を探し挿入点のインデックスを返すbisect_leftを使います．リストt内でのtargetの挿入点をbisect_leftより算出しiに代入します．t[i]がtargetでない場合Noneを返します．また，targetが存在しない場合はtのサイズより大きな値を返すのでその場合もNoneを返します．

binary_search()では初めに，tのサイズをhiに格納します．またlo<hiになると探索を終了します．それ以外は要素をtargetと比較し，前半または後半の中間に位置するインデックスの値を用い再帰的に探索します．

Hashtables(ハッシュテーブル)の実装例

最後に，簡単なHashtableの実装例を紹介します．ハッシュテーブルはとても高速で，探索，挿入，削除の計算量はconstant(定数)です．つまりO(1)です．pythonでは辞書がhashtableです．

hashtableの理解を深めるために一度辞書型のことは忘れて，簡単なhastableの実装を紹介します．（衝突の事は考えません）

下記のコードにあるクラスLinearMapは要素の追加にリストのappendを使っているため計算量はO(1)ですが，getではitemsを走査しているためO(n)となります．（nはitemsの要素数）

続いて，BetterMapクラスは100個のLinearMapを要素として持ちます． BetterMapではインスタント時にO(n)の計算量が掛かります．要素の追加では，find_mapでkeyのハッシュ値を計算しmapsのサイズに収まるようなindexを算出します（ここでは衝突は考慮していません）．算出されたindexを用いて要素をmapsに追加します．衝突が起こらないと考えれば，addはO(1)となります．

最後に,HashMapクラスはLinearMapを2個要素としてもつBetterMapを保持し，要素を追加してサイズが大きくなるたびにリサイズします．リサイズするたびに計算量は一時的に増えますが，n回要素を追加したときのトータルコストは 2n-2となります．そのため1回の操作は2n-2/n = 1 - 2/n となり，計算量がO(1)となります．これで計算量が定数のハッシュテーブルが完成です．実際のhashtableではこれに衝突した時の処理を追加しないといけません．