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

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

Java

さて、前回に引き続き、selectの実装をしていきます。
もう定義は書かないですが、わからなくなったら前回の記事を見てください。

前回の記事で、高速なrank操作用のブロックを使って、2分探索でselectを計算するという戦略にしました。
ただ、rankの場合は、O(1)の定数時間で操作が完了するのですが、selectの場合は、2分探索なので、O(log(N))の時間がかかってしまいます。
ここで、Nはざっくりと言うとブロックの数です。
だいたい高速ですが、rankに比べるとやはり遅くなります。

selectが2分探索にならざるを得ない理由をもう少し整理してみます。

まず、前回と同じような以下のようなrankのために付与した1の累計値を保持するブロックを持つビットベクトルBを考えます。

+-------0th-------+-------1th-------+-------2th-------+-------3th-------+
|        0        |        2        |        6        |        6        |
+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| 0 0 1 0 0 0 0 1 | 0 0 0 0 1 1 1 1 | 0 0 0 0 0 0 0 0 | 1 0 1 0 0 0 0 1 |
+-----------------+-----------------+-----------------+-----------------+

このとき、

rank( B, 10, 1 ) = 2

というrank操作の場合、10の位置がどのブロックに含まれているのかは、ブロックサイズがわかっていれば、ダイレクトに特定することができます。
例えば、今回は、ブロックサイズが8なので、

10 / 8 = 1

となり、1番目のブロックに存在することがすぐにわかります。
しかし、select操作では、それができません。
これは、select操作は、ビットベクトルの1の配分によって、特定すべきブロックが変化するからです。

例えば、さきほどのビットベクトルの場合では、特定すべきブロックは、1番目のブロックとなり、select操作の結果は、以下のようになります。

select( B, 2, 1 ) = 12

しかし、ビットベクトルB'が以下のようなものだとすると、

+-------0th-------+-------1th-------+-------2th-------+-------3th-------+
|        0        |        2        |        2        |        2        |
+------0-7th------+-----8-15th------+-----16-23th-----+-----24-31th-----+
| 0 0 1 0 0 0 0 0 | 0 0 0 0 0 0 0 1 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 1 |
+-----------------+-----------------+-----------------+-----------------+

特定すべきブロックは、3番目のブロックとなり、select操作の結果は、以下のようになります。

select( B', 2, 1 ) = 31

このようにビットベクトルの1の配分によって特定するべきブロックが変わります。
一方、rank操作の場合は、特定するブロックはビットベクトルの1の配分に影響されません。
ただし、rank操作の結果は、変わります。
例えば、

rank( B, 10, 1 ) = 2
rank( B', 10, 1 ) = 1

という2つのrank操作が特定するブロックは、両方とも1番目のブロックなので、ビットベクトルによって特定するブロックは変わりません。
しかし、結果は、2と1で異なっています。

このような特徴からrank操作用のブロックを利用したselect操作は、求めるブロックをダイレクトに特定できないため、ブロックの値を利用して、2分探索を行い、ブロックを特定する必要があります。

つまり、O(1)の定数時間アクセスを行うselect操作を実現するには、rank操作用のブロックをそのままでは使えないということになります。
select操作用の定数時間アクセスを行うデータ構造は、2分探索版のselect操作を作成してから作成しようと思います。

さて、次回は、今回書く予定だったselect操作用の表引きについて解説したいと思います。