FIFOとBFSの改良
FIFOとBFSの改良
今Think Complexity
chap4)で勉強した
について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！
FIFOの実装例
FIFO(First In First Out)とは名前の通り最初に入ったものが
最初に出るような処理の事を指します．例えば，コンビニでレジに
並んでいる時は最初に並んだ人が最初に支払いを済ます事ができ，
後から来た人は後ろで順番が来るのを待ちます．このような
処理をFIFOと呼び，これを実装しているデータ構造をqueue（キュー）
と呼びます．pythonではcollectionsのdeque
（deckと発音します）でFIFOの役割を果たす事ができます．(*1)
deque(double-ended queue)は両端キューと呼ばれ，両端（先頭・末尾）
から要素の追加・削除ができるキューです．追加・削除の
計算量はO(1)と高速です．dequeでFIFOを実現する場合，
pop()の変わりにpopleft()を使用します．
＊1listでも同じように振る舞うことは出来ますが，pop(0)の計算量はO(n)なので，dequeを使用することを勧めます．
次に，FIFOを辞書型で実装した例を紹介します．
このコードでは，appendで新しい値を格納しnextinをインクリメント
します．popではnextoutをkeyとして要素を返し削除します．
最後にnextoutをインクリメントして次にpopされる時は，次に追加
された要素を返すようにします．このFIFOは辞書を利用しているため，
追加・削除ともに計算量は定数O(1)となります．
BFSの改良
BFS(Breadth-first search)の詳細はこの記事 をご覧下さい．
まず，下記のコードをご覧下さい．ここではbfsメソッドが前回紹介した
BFSの実装で，better_bfsが今回改良したBFSとなります．改良することにより
下図のように計算量がO(n^2)からO(n)となりました．
前回のBFSのアルゴリズムではworklistとclosedにlist構造を
使用していました．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)も
掛かっていました．
対して，dequeのpopleftはO(1)となります．worklistをdequeに代えpopの計算量をO(1)にします．次にclosed
をsetに代え，vs = [v for v in vs if ...]の部分を取り払う事で
全体としてO(n)となります．
実際に比較してみると一目瞭然です．青いラインが改良前
（previous bfs）で，
緑のラインが改良後(better bfs)となります．
ここではnがノードの数で，timeが処理に掛かった時間を表しています．
このようにデータ構造を変えるだけで， 計算量を大幅に抑える事ができます．
ノードの数`n = 0 ~ 1000`
上の図をズームした時の図（`n = 0 ~ 700`）
まとめ
今回は，FIFOの実装とここで 紹介したbfsの再実装を行う事でデータ構造・アルゴリズムを 少し変え効率が良くなる事を紹介しました．
reference
