Subscribed unsubscribe Subscribe Subscribe

Python, web, Algorithm 技術的なメモ

技術的なメモを書いていきます.pythonistaを目指しています.

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

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

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_mapkeyハッシュ値を計算しmapsの サイズに収まるようなindexを算出します(ここでは衝突は 考慮していません).算出されたindexを用いて要素をmapsに追加します. 衝突が起こらないと考えれば,addO(1)となります.

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

まとめ

今回は,二分探索の実装例,ハッシュテーブルの実装例を簡単に 紹介しました.

アルゴリズムの実装をする事がアルゴリズムを理解するための近道だと 思います.アルゴリズムを自分で実装し各言語にデフォルトで付随しているアルゴリズムと 計算量を比較することでアルゴリズムの重要性が身にしみたりします.

Reference