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

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

Java

定数時間のselectを実装してみようと思い、以下の論文の手法を実装してみた。

Fast Computation of Rank and Select Functions for Succinct Representation.
Joong Chae NA, et al., IEICE, 2009.

前回の性能測定と同様の条件で、性能測定を行ってみた。
「simple」というのが、以前、紹介したrank用のブロックを2分探索して求めるselectの性能です。
「kim」というのが、上記の論文のAlgorithm2を使って求めるselectの性能です。
測定した結果を以下に示します。

f:id:ryokkie:20120513230642p:plain

グラフから定数時間で、selectが実行できていることがわかります。
2^24ぐらいから性能が劣化しているのは、内部でrankを使っているため、rankの性能の劣化によるものだと推測されます。
2^24まではrankの性能の劣化がないため、定数時間で実行できていることがわかります。

さて、次は、64bitアーキテクチャに最適化した実装をやってみようと思います。