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

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

Java

さて、前回に引き続き高速なrank実装を検討してみます。

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

rankの定義は以下でした。

rank( B, pos, b )

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

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

前回の記事で明らかになったことは、

ブロックの管理領域のサイズとアクセス性能はトレードオフ

ということでした。

ブロックサイズをSBとして、ビットベクトルに付与すると、

  • アクセス性能は、LBよりも良い
  • 管理領域のサイズは、LBよりも大きい

という特徴があります。

ブロックサイズをLBとして、ビットベクトルに付与すると、

  • アクセス性能は、SBよりも悪い
  • 管理領域のサイズは、SBよりも小さい

という特徴があります。

つまり、SBとLBともに一長一短の性質を持っていることがわかります。

このような状況の時、よく取られる手法があります。
それは、ハイブリッドです。
ハイブリッドすることにより、お互いの短所を補うのです。
ハイブリッドという言葉で最も有名なのは、ハイブリッドカーですよね。
ハイブリッドカーは、ガソリンエンジンの効率が最も悪い「発進時」と「加速時」を電気モーターに任せることで効率を良くしています。
また、電気モーターは電気が必要であるという欠点がありますが、この点は、走行時のエネルギーを充電することで回避しています。

今回のケースもSBとLBをハイブリッドすることでお互いの短所を補うことができます。
まず、SBとLBをハイブリッドした図を以下に示します。

f:id:ryokkie:20120225133738p:plain

とても簡単ですね。
ハイブリッドという言葉が申し訳ないような気がしてくるくらい簡単ですね。
でも、意外と効果があって、きちんとお互いの短所を補います。

まず、SBの短所ですが、それはブロック数が多くなるため、管理領域のサイズが大きくなるということでした。
上記の図だけを見ると、SBとLBのブロック数自体には、変化がないため、あまり意味がないように感じるかもしれません。
しかし、LBとハイブリッドすることにより、以下のようなメリットがあります。

  • 1つのブロックに必要な領域をint型(4バイト)からbyte型(1バイト)に減らすことが可能

さて、何を言っているのでしょうか?
以下に図を示します。

f:id:ryokkie:20120225155124p:plain

つまり、SB単体で利用している場合だと、先頭からの累計値なので、SBの最後の値を保持できるだけのサイズが必要ということです。
仮に、SBの管理範囲=32bitだとした場合に、320000000サイズのビットベクトルが存在した場合、10000000個のSBが必要で、最後の要素であるSB[9999999]の値が取り得る最大値は、

320000000 - 32 = 319999968

となります。つまり、一つのSBに4バイト必要となります。
SB配列の後半の方は、4バイトでも良いですが、SB配列の先頭の方は、

SB[0]=0
SB[1]=32
SB[2]=64
・・・

なので、4バイトも必要ないわけです。
つまり、SB配列の前半の方の各要素の4バイトの中で、3バイトは完全に無駄なわけです。
1バイトで管理できるなら1バイトで管理した方がサイズが小さくなって有利です。
これを実現するために、LBを利用します。
以下の図を見てください。

f:id:ryokkie:20120225162605p:plain

どうでしょうか?
LBを使うことで、SBは、LB内のrankの累積値で済むので、最大値は96となり、1バイトで済むことがわかります。
つまり、仮に、SBが1000個あるとしたら、4バイトで管理していた時は、

1000 * 4 = 4000

となり、4000バイト必要だったのですが、1バイトの管理にすることで、

1000 * 1 = 1000

となるので、1000バイトで済むことがわかります。

つまり、3000バイト(75%)も節約できるのです。
これは、SB配列のサイズが大きくなればなるほど顕著になります。

LBとのハイブリッドによって、SB配列の短所であったブロックの管理領域のサイズが大きくなるのを改善できました。
また、LBもSBとのハイブリッドによって、アクセス性能の問題が改善できます。
というのも、LBで範囲を特定した後、ビットベクトルのLBの範囲すべてを探索するのではなく、SBを使ってビットベクトルの探索範囲をさらに特定できるので、効率的に探索することができます。

LBとSBのハイブリッドによって、ブロックの管理領域のサイズを抑えつつ、アクセス性能も高速にすることができました。

次回は、LBとSBのハイブリッド構造によって、高速化したrankをJavaで実際に実装してみます。

最後に上記のハイブリッドの説明は参考にしている本と全く関係のない私の解釈に基づくものなので、間違っていたらごめんなさいと断っておきます。
まぁ、イメージと直観で理解する私のようなタイプの人には役立つのではないでしょうか。