2010年7月29日木曜日

高速な復元抽出の直感的な説明

先日@niamさんと@tsubosakaさんのつぶやきを見てて,確率{pi}で復元抽出するWalker's alias methodというものを知りました.たまたま,今日,復元抽出する用事があったので,思い出して調べた次第.私も昔同じことをやろうとして,O(log n)でいけるからまぁいいやと思っていたのですが,このアルゴリズムだとO(1)でいけます.

解説はこのあたりのブログを参照.
さて,私は理解力が足りなくてこのあたりの説明を読んでもなんでこれでいいのかさっぱりわからなかったので,絵に描いて理解しました.確率{pi}で復元抽出するためには,piに比例した面積の図形を壁に貼ってダーツをすればいいのです.{0.1, 0.05, 0.3, 0.1, 0.45}だったとします.するとこんなの.

まさか毎回ダーツ投げさせる訳にもいかないので,randを呼びます.でも,これでは何がうれしいのかわかりません.四角形にしてみましょう.

ちょっとうれしさがわかってきました.rand.nextDouble()の値が,たとえば0.2から0.4の間なら橙にすればよいのです.このおおざっぱな0.2ずつの区間のことをここではブロックとでも読んでおきましょう.ところが,0から0.2の間ならどうでしょう.3色もあります.もっと詰まっていたら.やっぱり2分探索が必要な気がします.そこで,一つのブロックの中に高々2種類しかないような区切り方はできないでしょうか.できます.これができれば1回比較すればよいだけです.ブロックをnこ(ここでは5個)用意すれば可能です.こんな感じ.
randが0から0.2なら,つまり5倍してintにキャスとして0だったら,もう一度0.1以上か否かチェックして,以下なら青,以上なら橙を返せばOK.このブロックを作ってるのがWalker's alias algorithmです.まず,piをn倍したものをqiとします.qi < 1のものに一つずつブロックを割り当てます.図だと,青赤緑.次に,残った qi > 1のものはqi < 1が消費したブロックのあまりにとりあえず詰めていき,1以下になったら新しいブロックに割り当てます.橙は青と赤のあまりに詰めたところで1以下になったので,新しいブロックをもらいました.灰は残りに割り当てて完了.割り当て数はn個,上記の方法なら各ブロックごとに新しいブロックを一つずつしか消費しないので,最大でもn個ブロックがあれば十分なことがわかります.保存すべき情報は,各ブロックごとに境界となっている位置,2種類の色です.片方の色はインデックスと一致させておけばよいので,境界ともう一方の色だけ覚えればよいのでした.

ちょっとあまりに見事な方法だったので記事にしてみました.

0 件のコメント:

コメントを投稿