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

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

Java

疎なビットベクトルのaccessとrankとselectをサポートしようとして、久しぶりに実装しようとしていたら、かなり追加しにくい感じになってたので、ソースをリファクタリングして、メソッドを整理しました。

定数時間のselectですが、

  • 0のみの定数時間(1は、log(n))
  • 1のみの定数時間(0は、log(n))
  • 0と1の定数時間(フルセット)

というように整理しました。ちなみに、どれを選択してもrankは定数時間です。

以下で公開しています。

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

疎なビットベクトル用の簡潔データ構造は、今週中にアップロードしたいと思います。