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

Javaで簡潔ビットベクトル(33)

Java

先日、RRRの完備辞書をリリースしましたが、ちょっと実装を間違えていたこともあり、性能がちゃんと出ていませんでした。修正したので、再度、アップロードします。

https://code.google.com/p/sbvj/

ざっくりとrankの性能を測定すると、以下ぐらいです。

Bitmap Size  : 2^28
Density(5%)  : 0.3(micro sec)
Density(10%) : 0.3(micro sec)
Density(20%) : 0.3(micro sec)

参考にした論文は、以下です。

Fast, Small, Simple Rank/Select on Bitmaps
Gozalo Navarro, Eliana Providel, SEA'12, 2012.

上記の論文の方法と同じ実装になりましたが、さらに高速化する方法があります。論文の2つ目の方法のCombined Samplingを利用します。これは、なるほどよくできていると思いました。まず、rank値とselect値をサンプリングして保持しておきます。ここまでは、多くの既存の手法と同じです。ただし、rank値の計算にサンプリングしたrank値だけでなく、サンプリングしたselect値を使います。また、select値の計算にサンプリングしたselect値だけではなく、サンプリングしたrank値を使います。つまり、今までは、rankとselectの両方とも互いに独立した補助データ構造が必要だったのでサイズが大きくなりがちでしたが、Combined Samplingは、それを解決した補助データ構造です。rankは、性能がそれほど改善するわけではないのですが、サイズが小さくなります。また、selectには、かなり恩恵があり、性能もサイズも改善します。

Combined Samplingのおもしろいところは、これだけではなく、RRRの実装も改善します。「On the fly」なRRRの実装でサイズは改善したけど、selectの性能が改善しない問題をサンプリングしたselect値を利用することで改善することができます。ただし、わずかにサイズは増えます。現状、「On the fly」なRRRの実装では、サンプリングしたrank値の2分探索で実装しているので、どうしても性能は不利です。なので、サンプリングしたselect値と対応するクラスのインデックスの復元位置を持つことで、性能アップが期待できます。論文の最後にそれらしいことが数行ぐらい書いてあります。

岡野原さんのrsdicは、このような実装になっているのではないかと推測しています。
ソースは見ないことにしているのでわからないですが・・・。