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

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

Java

今週は、出張も多く、なかなかまとまった時間も取れず、実装が遅れてしまいました。
一応、出張先でコーディングぐらいは終わらせようとEclipseの環境をコピーしてノートパソコンに入れてみたけど、自宅が64bitのWindowsを使っていて、ノートパソコンが32bitのWindowsだったので、動きませんでした。

なので、まぁ、一週間ぐらい空いてしまいましたが、続きをやりたいと思います。

今回からは、性能測定です。
メインはselectですが、rankも測定してみようと思います。

性能測定のために、実験条件を設定します。

まず、私の環境です。

実験条件の参考にさせてもらったのは以下の論文です。

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

次に、ビットベクトルの条件を以下のようにします。

  • ビットベクトルの1の割合が全体の1%(疎なビットベクトル)
  • ビットベクトルの1の割合が全体の3%
  • ビットベクトルの1の割合が全体の10%
  • ビットベクトルの1の割合が全体の25%
  • ビットベクトルの1の割合が全体の50%
  • ビットベクトルの1の割合が全体の75%
  • ビットベクトルの1の割合が全体の90%(密なビットベクトル)

つまり、疎なビットベクトルであっても密なビットベクトルであっても性能にあまり差があってほしくないので、7種類のビットベクトルで測定することにしました。

次に、ビットベクトルの長さの条件を以下のようにします。

  • 2^10 〜 2^30

2^32までやるとビットベクトルの構築が遅すぎるのでこうしました。

次に、rank操作とselect操作の実行回数です。
ランダムな要求を10^7=1000万回実行する時間を計測したいと思います。

さて、次回は、この実験条件で実際に実験を行って、結果を分析したいと思います。