読者です 読者をやめる 読者になる 読者になる

Storing a Sparse Table with O(1) Worst Case Access Timeを読んだ

技術

タイトルのとおりです。以下の論文を読みました。

Storing a Sparse Table with O(1) Worst Case Access Time

[1,m]の自然数の集合に対するサイズnの部分集合があった場合にqが部分集合に含まれるどうかを知りたい、という問題を考えます。この操作をmembership(q)と書きます。

単純に部分集合に含まれる数をソートして並べた場合、データサイズは数を入れる箱(セル)がn個あればよいです。しかしmembership(q)をやるには二分探索が必要なので時間計算量がO(log n)かかります。

これに対して提案手法はデータサイズが高々セル6n個になるかわりにO(1)でmembership(q)ができます。要素数nの部分集合に対して普通の(完全ではない)ハッシュ関数を用意して、衝突した数の集合に対して完全ハッシュを用意する。という仕組みです。

せっかくなのでPythonでどのくらいのサイズになるのか試してみました。

論文の後ろの方で完全ハッシュを指すアドレスを幾つかのベースアドレスとそこからの相対アドレスにわけるという、よくある感じのやつをやってデータサイズを実質セルn + o(n)個にしているのですが、そのへんはCでやらないとめんどいので今回はスルーです。

github.com

以下、m=10009からn=300の部分集合をランダムに作って必要なセル数を確認する、を10回繰り返すサンプルです。-hでヘルプが見られます。セル数は3n前後になっているようです。

$$ python sample.py
Success. block size: 940
Success. block size: 921
Success. block size: 978
Success. block size: 963
Success. block size: 887
Success. block size: 1021
Success. block size: 970
Success. block size: 940
Success. block size: 943
Success. block size: 953