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

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

Java

さて、今回は、前回の記事で説明していないgetWordSelectメソッドについて、説明してます。

getWordSelectメソッドは、32bitのビットベクトルから指定した数の1が出現する位置を返します。
32bitのビットベクトルにselectが実行できると考えてもらえれば良いです。
ただし、32bit内のビットベクトルに対するselect操作は、表引きで行うので高速です。

では、私の実装を以下に示します。

private int getWordSelect( final int pValue, final int pRestBitNum ) {
	
	int select = 0;
	
	int restBitNum = pRestBitNum;
	
	// 32bitを8bitで区切った数を取得する。
	int octetNum = (int) (WORD_BIT_SIZE / BYTE_BIT_SIZE);
	int num = 0;
	// 8bit単位にループする。
	while ( num < octetNum ) {
		int shift = num * 8;
		// 8bit単位に1のrank値を取得する。
		int rank = RANK_TABLE[ (pValue >> shift) & 0xff ];
		
		int rest = restBitNum - rank;	
		if ( 0 >= rest ) {
			// 求めたいselect値が存在する8bit範囲が特定されたので、ループを終了する。
			break;
		}
		
		// 求めたいselect値よりも8bitのrankの方が小さい場合は、その8bitには、求めたいselect値がないので、継続してループする。
		restBitNum = rest;
		
		num++;
	}
	
	// 探索した8bit分の位置には、select値がなかったので、その位置分selectに加算する。
	select += num * 8;
	
	// 最後に、求めたいselect値が存在する8bitを表引きする。
	select += SELECT_TABLE[ (pValue >> (num * 8)) & 0xff ][restBitNum - 1] - 1;
	
	return select;
	
}

処理の流れは以下のようになります。

  1. 8bit単位にrank値を使って、求めるselect値が含まれる8bitの範囲を特定する。
  2. 特定した8bit内を表引きで求める。

それほど難しくない処理ですね。
なので、解説は行いません。

さて、次回は、今回まで説明してきて、実際に実装した2分探索版select操作の性能を測定してみようと思います。
また、高速に8bitのselect値を求めるための表引き用のテーブルとして2次元配列版を利用していましたが、1次元配列版も試してみて、それぞれの性能を測定してみようと思います。
性能が良い方を採用しようと思います。