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

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

Java

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

まだ、実装していないgetRankメソッドを実装します。

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

getNaiveRankメソッドと引数は同じですが、buildForFastRankメソッドによって構築された管理領域を使います。

私は、以下のように実装しました。

/**
 * 
 * <p>
 * SBとLBという2つのブロックによってアクセスを高速化したrankを実装したメソッドである。
 * 指定した位置までに出現するビットの数を返す。
 * </p>
 * 
 * @param pTargetPos 位置
 * @param pBit ビット
 * @return 指定した位置までに出現するビットの数
 */
public long getRank( final long pTargetPos, final int pBit ) {
	long rank = 0;
		
	// 引数チェックを行う。
	checkArgsTargetPosAndBit( pTargetPos - 1, pBit );
		
	long pos = pTargetPos - 1;
		
	// LBを使って、累積値を計算する。
	int lbIndex = (int) ( pos / LB_BIT_SIZE );
	rank += this.mLBArray[ lbIndex ];
		
	// SBを使って、累積値を計算する。
	int sbIndex = (int) ( pos / SB_BIT_SIZE );
	// 符号なしのbyte型の値を得る。
	rank += getUnsignedByteValue( this.mSBArray[ sbIndex ] );
		
	// 残りを表引きする。
	int restPos = (int) ( pos % SB_BIT_SIZE );
	rank += getWordRankFromTable( this.mBitVector[ sbIndex ] & MASK_TABLE[ restPos ] );
		
	if ( 0 == pBit ) {
		// 反転させる。
		rank = pTargetPos - rank;
	}
		
	return rank;
}

前回、説明するのを忘れていたのですが、getWordRankFromTableメソッドは、以下のようなメソッドです。

/**
 * 
 * <p>
 * 32bitのWORDから1のrank値を計算するメソッドである。
 * </p>
 * 
 * @param pValue 32bitのビットベクトル
 * @return 32bitのビットベクトル内の1のrank値
 */
private int getWordRankFromTable( final int pValue ) {
	// 32bit分のrank値を計算する。
	return RANK_TABLE[ (pValue >> 24) & 0xff ]
			+ RANK_TABLE[ (pValue >> 16) & 0xff ]
			+ RANK_TABLE[ (pValue >> 8) & 0xff ]
			+ RANK_TABLE[ pValue & 0xff ];
}

getRankメソッドは、LB配列とSB配列を使って、指定した位置が含まれる32bitの範囲をダイレクトに特定し、その中をマスキングした値で表引きします。
この処理によって、rankの値をO(1)で取得することができます。
配列の値を添え字指定で取り出すようなものですね。

今までの説明をコード化しただけですので、それほど難しくないと思います。

LB配列とSB配列は、1の数しか保持していないので、0のrank値を求める時に困りそうですが、求める位置までの1のrank値を求めれば、0のrank値は以下のようにすれば計算できます。

0のrank値 = rank値を求める位置 - 1のrank値

簡単ですね。

buildForFastRankメソッドとgetRankメソッドを利用することにより、1と0のrank値を定数オーダーで求めることができるようになりました。

次回は、性能評価を行ってみようと思います。