Javaで簡潔ビットベクトル(28) - 気ままなブログ疎なビットベクトルのaccessとrankとselectをサポートしようとして、久しぶりに実装しようとしていたら、かなり追加しにくい感じになってたので、ソースをリファクタリングして、メソッドを整理しました。 定数時間のselectですが、 0のみの定数時間(1は、log(n)) 1のみの定数時間(0は、log(n)) 0と1の定数時間(フルセット) というように整理しました。ちなみに、どれを選択してもrankは定数時間です。 以下で公開しています。 https://code.google.com/p/sbvj/ 疎なビットベクトル用の簡潔データ構造は、今週中にアップロードしたいと思います。
HyperLogLogで遊ぶ - Negative/Positive Thinking
