Subscribed unsubscribe Subscribe Subscribe

Python, web, Algorithm 技術的なメモ

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

FIFOとBFSの改良

FIFOとBFSの改良

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

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

FIFOの実装例

FIFO(First In First Out)とは名前の通り最初に入ったものが 最初に出るような処理の事を指します.例えば,コンビニでレジに 並んでいる時は最初に並んだ人が最初に支払いを済ます事ができ, 後から来た人は後ろで順番が来るのを待ちます.このような 処理をFIFOと呼び,これを実装しているデータ構造をqueue(キュー) と呼びます.pythonではcollectionsdeque (deckと発音します)でFIFOの役割を果たす事ができます.(*1) deque(double-ended queue)は両端キューと呼ばれ,両端(先頭・末尾) から要素の追加・削除ができるキューです.追加・削除の 計算量はO(1)と高速です.dequeFIFOを実現する場合, pop()の変わりにpopleft()を使用します.

*1listでも同じように振る舞うことは出来ますが,pop(0)の計算量はO(n)なので,dequeを使用することを勧めます.

次に,FIFOを辞書型で実装した例を紹介します.

このコードでは,appendで新しい値を格納しnextinをインクリメント します.popではnextoutkeyとして要素を返し削除します. 最後にnextoutをインクリメントして次にpopされる時は,次に追加 された要素を返すようにします.このFIFOは辞書を利用しているため, 追加・削除ともに計算量は定数O(1)となります.

BFSの改良

BFS(Breadth-first search)の詳細はこの記事 をご覧下さい.

まず,下記のコードをご覧下さい.ここではbfsメソッドが前回紹介した BFSの実装で,better_bfsが今回改良したBFSとなります.改良することにより 下図のように計算量がO(n^2)からO(n)となりました.

前回のBFSのアルゴリズムではworklistclosedlist構造を 使用していました.list構造のlist.pop(0)O(n)です. pop(0)n回ループするなかに処理があるのでO(n^2)となります. さらに,vs = [v for v in vs if...] の処理がO(n)掛かるとすると合計でO(n^2+n^2)つまりO(n^2)も 掛かっていました.

対して,dequepopleftO(1)となります.worklistdequeに代えpopの計算量をO(1)にします.次にclosedsetに代え,vs = [v for v in vs if ...]の部分を取り払う事で 全体としてO(n)となります.

実際に比較してみると一目瞭然です.青いラインが改良前 (previous bfs)で, 緑のラインが改良後(better bfs)となります. ここではnがノードの数で,timeが処理に掛かった時間を表しています.

このようにデータ構造を変えるだけで, 計算量を大幅に抑える事ができます.

f:id:samuraiT:20140303222549p:plain ノードの数`n = 0 ~ 1000`

f:id:samuraiT:20140303222650p:plain上の図をズームした時の図(`n = 0 ~ 700`)

まとめ

今回は,FIFOの実装とここで 紹介したbfsの再実装を行う事でデータ構造・アルゴリズムを 少し変え効率が良くなる事を紹介しました.

reference