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

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

Java

さて、前回の記事で設定した実験条件で、rank操作とselect操作の性能を測定してみました。

まず、rank操作の結果をグラフにしたものを以下に示します。

f:id:ryokkie:20120328003859p:plain

1%となっているのは、ビットベクトルの密度です。
この結果から、rank操作の性能が2^25あたりからビットベクトルの密度に関係なく、急速に性能が劣化しているのがわかります。
劣化の原因ははっきりとはわからないですが、おそらくキャッシュの影響だと思います。参考文献でも同じような性能特性だったと思うので、そういうものなのでしょう。
ただまぁ、劣化しているのは事実ですが、2^30の時に1000万回も実行して0.3秒なので、十分に高速です。
それでも性能の劣化を気にする人は、別の実装を行うか、2^25よりも大きなビットベクトルを作らない方が良いかもしれません。

次に、select操作の結果をグラフにしたものを以下に示します。

f:id:ryokkie:20120328003900p:plain

この結果からビットベクトルの密度にselect操作の性能が影響されていないことがわかります。
また、select操作は、2分探索であるため、ビットベクトルのサイズに性能が依存することがわかります。

さて、ここまでで、長かった簡潔ビットベクトルの説明を終わりにしたいと思います。
もちろん、まだまだ追求したいこともあります。
例えば、O(1)の定数性能のselect操作を実装してみたいというのもあります。
ただし、それらは、簡潔ビットベクトルのソースをブラッシュアップする過程でやっていき、実装できれば、記事を追加するというようにしたいと思います。

ビットベクトルから簡潔ビットベクトルまでしっかりと説明したのには理由があります。
それは、LOUDSを利用した簡潔TRIEを実装するためです。
私が最初に設定したゴールは、Java版のLOUDSを利用した簡潔TRIEを実装し、オープンソースとして公開することです。
なので、次回からは、Javaで簡潔TRIEを書いていこうと思います。