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

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

Java

さて、実装を続けていきます。

BitVectorクラスに以下の2つのメソッドを用意します。

public void buildForFastRank() {
...
}
public long getRank( final long pTargetPos, final int pBit ) {
...
}

buildForFastRankメソッドは、ビットベクトルにビットをセットした後に、高速なrank用にLBとSBを付与します。
ある程度想像がついている人もいるかと思いますが、LBとSBのブロックは、スタティックです。
動的な更新はやれなくもないですが、効率的ではないです。
(ビットベクトルの先頭のビットを変更する場合を考えるとわかります。)
あくまで、rank操作を高速化する目的のものです。

このような理由もあり、ビットベクトルに値を設定した後に、buildForFastRankメソッドを実行する必要があります。

getRankメソッドは、getNaiveRankメソッドと引数は同じです。
また、機能も同じです。
ただ、実装はかなり高速です。

まずは、buildForFastRankメソッドから実装してみます。

/**
 * 
 * <p>
 * rankを高速化する管理情報を付与するメソッドである。
 * getRankメソッドを実行する前に実行する必要がある。
 * </p>
 * 
 */
public void buildForFastRank() {
	// SB配列のサイズを計算する。
	// SBサイズとWORDサイズが一致しているので、必ず割り切れるはず。
	long sbArraySize = this.mBitSize / SB_BIT_SIZE;
	// LB配列のサイズを計算する。
	long lbArraySize = 0;
	if ( 0 == ( this.mBitSize % LB_BIT_SIZE ) ) {
		lbArraySize = this.mBitSize / LB_BIT_SIZE;
	} else {
		lbArraySize = (this.mBitSize / LB_BIT_SIZE) + 1;
	}
		
	assert( ((long) Integer.MAX_VALUE) >= sbArraySize );
	assert( ((long) Integer.MAX_VALUE) >= lbArraySize );
		
	// SB配列を確保する。
	this.mSBArray = new byte [ (int) sbArraySize ];
		
	// LB配列を確保する。
	this.mLBArray = new long [ (int) lbArraySize ];
		
	long lbRank = 0;
	int lbIndex = 0;
	int sbRank = 0;
	for ( int i = 0; i < sbArraySize; i++ ) {
		if ( 0 == (i % 8) ) {
			// LB配列の要素に値を代入する。
			lbRank += (long) sbRank;
			lbIndex = i / 8;
			this.mLBArray[ lbIndex ] = lbRank;
				
			// SB配列の要素に値を代入する。
			sbRank = 0;
		}
			
		// 事前条件
		assert( 0 <= sbRank && 256 > sbRank );
		this.mSBArray[ i ] = (byte) sbRank;
		sbRank += getWordRankFromTable( this.mBitVector[ i ] );
	}
}

現在のビットベクトルのサイズに応じて、LB配列とSB配列の数を決定しています。
今回は、1つのSBが管理するビットサイズをWORDのサイズと同じ32としたので、必ず割り切れます。
また、1つのLBが管理するビットサイズを256としました。

これは、以下の論文に基づいています。

Practical Implementation of Rank and Select Queries
Rodrigo Gonzalez, Szymon Grabowski, Veli Makinen, Gozalo Navarro, In Poster Proceedings Volume of 4th Workshop on Efficient and Experimental, 2005.

今回のような2段階のブロックで管理する方法が紹介されていますが、LB=256とし、SB=32とした場合が最も性能が良かったということでした。
ビットベクトルのサイズが非常に大きい場合は、1段階のブロックで管理する方が良い場合もあるみたいなのですが、キャッシュの影響が大きいらしく、少し使いづらいようなので、バランスの良い2段階の方法を採用しました。
まぁ、そもそもJavaなので、キャッシュ効率とかを気にしすぎても仕方ないかなと。
ただ、こればっかりは、実験してみないとわかりませんが、今回はあまり気にしないこととしました。

さて、高速なrankのためのこの領域のサイズを見積もっておきましょう。
ビットベクトルのサイズをNとして、N=2^32(2の32乗)の場合を考えます。
まず、ビットベクトルに必要な領域は、当然のことながら、2^32bitです。
N=2^32なのですから当たり前ですね。
バイトで考えると、

2^32 / 8 = 2^32 / 2^3 = 2^29バイト

ですね。

次に、LBの領域を考えます。
LB=256なので、以下の個数の配列が必要なことがわかります。

2^32 / 256 = 2^32 / 2^8 = 2^24個

また、2^32までの値を格納するので、LB配列の型としては、2^32の値を格納できるint型、もしくはlong型が必要となります。
int型で管理する場合は、符号ありなので、実際は、2^31までしか表現できないので、少し工夫が必要です。
これはまた別の機会に考えてみます。
今回は、最も簡単にlong型で保持することとしました。

つまり、LB配列の領域として以下のバイト数が必要となることがわかります。

2^24 * 8 = 2^24 * 2^3 = 2^27バイト

これは、元のビットベクトルのサイズが、2^29なので、元のビットベクトルに対して、以下の領域が必要となることがわかります。

2^27 / 2^29 =  2^-2 = 1 / 2^^2 = 0.25 = 25%

最後に、SBの領域を考えます。
SB=32なので、以下の個数の配列が必要になることがわかります。

2^32 / 2^5 = 2^27個

また、SBは、255までの値が格納できれば良いので、SB配列の型としては、2^8を格納できるbyte型が必要となります。
しかし、byte型は符号ありなので、実際は、127までしか表現できません。
ただし、領域は、1バイト分存在するので、byte型で値を格納し、値を取り出す時に符号なしに戻すこととします。
具体的には、以下のようなメソッドを使います。

/**
 * 
 * <p>
 * 符号ありのbyte型の値から符号なしのbyte型の値を得るメソッドである。
 * </p>
 * 
 * @param pValue 符号ありのbyte型の値
 * @return 符号なしのbyte型の値
 */
private int getUnsignedByteValue( final byte pValue ) {
	return (((int) pValue) & 0xff);
}

つまり、SB配列の値が必要となった時にだけ、int型で取り出すことで、符号なしの1バイトの値として扱います。

このような理由からSB配列の領域として以下のバイト数が必要になることがわかります。

2^27 * 1 = 2^27バイト

これは、元のビットベクトルのサイズが、2^29なので、元のビットベクトルに対して、以下の領域が必要となることがわかります。

2^27 / 2^29 =  2^-2 = 1 / 2^2 = 0.25 = 25%

つまり、LB配列とSB配列の領域として、ビットベクトルのサイズの50%を使うということになります。
ここで、LB配列の型をint型とすると、ビットベクトルのサイズに対して37.5%となります。
これは、設計次第で変更可能です。
つまり、ビットベクトルのサイズとして、2^32以下の値しか考慮しないのであれば、int型で管理する方が効率が良いわけです。
今回は、実装を少しサボって、long型としておきます。

さて、次回は、getRankメソッドを実際に実装します。