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

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

Java

rank操作の高速な実装について検討してみます。

まずは、復習としてrankの定義から始めます。

rankの定義は以下でした。

rank( B, pos, b )

また、rank操作とは、以下のような内容でした。

ビットベクトルBとして、b=(0 or 1)がposまでに出現する数を求める操作

また、問題は、

posの値に依存しないような実装

でした。

参考にしている本では、ビットベクトルをブロック単位で分割し、各ブロックで、そのブロックまでのrank値を保持しておくことで、高速なアクセスを実現します。
私なりの解釈を図にしてみます。
今回は、ブロックを4として、ビットベクトルにブロック配列を付与してみました。

f:id:ryokkie:20120222022108p:plain

どうでしょうか?
先頭の要素から順にアクセスせずとも、ブロック管理したrank値の配列を使うことで、rank値を簡単に取得できていることがわかるでしょうか?
この情報を付与したことで、ブロック配列分の容量が必要になりましたが、ビットベクトルの最後の方のrankも高速に求めることができます。
つまり、posの値が大きくてもrankを求める性能は劣化しなくなりました。

ここで、ブロック配列の容量について計算してみましょう。
例えば、今回のように4bitごとにrank値の累積値を保存する場合、ビットベクトルのサイズを4bitずつ分割したサイズが必要です。
ビットベクトルのサイズを1024とすると、

1024 / 4 = 256

となるので、1個4バイトのint型で管理すると、

256 * 4 = 1024

となるので、1024バイト必要なことがわかります。

ここで、仮に、ビットベクトルのサイズを1073741824(1024 * 1024 * 1024=1G)とすると、1GBの管理領域が必要となります。

つまり、アクセスを高速にした代わりに、管理領域が必要になったわけですが、管理領域のサイズはけっこう大きいわけです。

これはけっこう問題なので、管理領域を小さくすることを考えてみます。
管理ブロックを4bit単位ではなく、256bit単位にすればどうでしょうか?
つまり、管理ブロックのサイズを相対的に大きくするわけです。
ここで、区別のために、4bit単位のブロックを相対的に小さいということで、SB(Small Blockの略)とします。
また、256bit単位のブロックを相対的に大きいということで、LB(Large Blockの略)とします。

では、ブロックサイズが256bitの時に必要なrankの管理領域のサイズを計算してみましょう。
ビットベクトルのサイズを1024とすると、

1024 / 256 = 4

となるので、1個4バイトのint型で管理すると、

4 * 4 = 16バイト

となるので、管理領域は16バイトで済むことがわかります。
管理ブロックを2倍の512にすると、管理領域は8バイトで済むことがわかります。
つまり、管理ブロックの1つのサイズを大きくすればするほど、管理領域のサイズが小さくなることがわかります。

しかし、ここでも問題が発生します。
仮に、512bit単位でブロック管理するようにした場合、ブロックの境界付近の位置のrank値を求める場合、512回分ビットベクトルを探索しないといけません。
この部分は線形探索になってしまうので、性能に影響します。
4bit単位での管理に比べて、アクセス性能は劣化してしまいます。

rankの管理領域のサイズとアクセス性能の問題はトレードオフになっていて、なかなか難しい問題です。
ブロック管理におけるブロックサイズごとの特徴を図にまとめてみました。

f:id:ryokkie:20120225103512p:plain

さて、次回は、rankの管理領域のサイズとアクセス性能のトレードオフをうまく解決する方法を説明しようと思います。