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

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

Java

Combined SamplingとRRRを結合してみた。

以下にあります。

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

BuildTypeにCS_RRRを指定すると動きます。

t:63
s:63 × 32 = 2016
selectのサンプリング間隔:4096

としました。

性能は、以下ぐらいです。

CPU : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
メモリ : 16GB
OS : Windows7 64bit

bit vector size : 2^28

rank
Density(5%)  : 0.46(micro sec)
Density(10%) : 0.49(micro sec)
Density(20%) : 0.54(micro sec)

select
Density(5%)  : 0.56(micro sec)
Density(10%) : 0.56(micro sec)
Density(20%) : 0.59(micro sec)

まぁまぁ、安定して速くなった気がする。
もちろん、性能だけを求めるなら、元のビットベクトルを保持したPlain Typeのデータ構造の方が高速です。
この実装の利点は、rankとselectの性能を維持しつつ、元のビットベクトルが不要なので、サイズを小さくできるというところでしょう。
特に、accessとrankしか不要なら、rankのサンプリングだけしておけば良いと思います。