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

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

Java

さて、今回は、rankの実装を行っていこうと思います。

まず、ナイーブな誰でも思いつく実装をしてみます。

rankの定義は以下でした。

rank( B, pos, b )

また、rank操作は、以下でした。

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

なので、Javaでのメソッドを以下のようにします。

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

ここで、posをpTargetPosとし、bをpBitとしました。
ビットベクトルは、クラス内にメンバとして持っているので、引数に与えていないです。

本当にシンプルなrankの実装をやってみます。

私は、以下のように書きました。

public long getNaiveRank( final long pTargetPos, final int pBit ) {
		
	long rank = 0;
		
	// 引数チェックを行う。
	checkArgsTargetPosAndBit( pTargetPos - 1, pBit );
		
	// 愚直にビットベクトルの先頭からビットの数を数える。
	for ( long i = 0; i < pTargetPos; i++ ) {
			
		// iの位置に立っているビットを取り出す。
		int wordPos = (int) ( i / WORD_BIT_SIZE );
		int pos = (int) (i % WORD_BIT_SIZE);
		int word = this.mBitVector[wordPos];
		word = 1 & ( word >> pos );
			
		if ( pBit == word ) {
			++rank;
		}
	}
		
	return rank;
		
}

前回までに示したprint()メソッドを改造して実現してみました。

やっていることは、とても簡単で、pTargetPosまでのビットの数を真面目に先頭から数えているだけです。
非常に簡単に実現できます。

次に、Mainクラスを以下のようにしました。

public class BitVectorMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		// ビットベクトルを生成する。
		BitVector bv = new BitVector( 10 );
		
		// ビットをセットする。
		bv.setBit(0, 1);
		bv.setBit(5, 1);
		bv.setBit(6, 1);
		bv.setBit(7, 1);
		bv.setBit(9, 1);
		
		// 構築したビットベクトルを表示する。
		bv.print();
		
		// rank1
		System.out.println( "rank: " + bv.getNaiveRank(4, 1) );
		System.out.println( "rank: " + bv.getNaiveRank(7, 1) );
		System.out.println( "rank: " + bv.getNaiveRank(10, 1) );
		
		// rank0
		System.out.println( "rank: " + bv.getNaiveRank(4, 0) );
		System.out.println( "rank: " + bv.getNaiveRank(7, 0) );
		System.out.println( "rank: " + bv.getNaiveRank(10, 0) );
		
	}

}

前回の記事でイメージとして示したビットベクトルを実現してみました。

実行した結果は、以下のようになります。

    0-   31:10000111010000000000000000000000
rank: 1
rank: 3
rank: 5
rank: 3
rank: 4
rank: 5

rankの機能としての実現は、これで問題ないのですが、性能面を考えると全く役に立ちません。
もちろんビットベクトルの数が小さいうちはこれでも良いのですが、大きくなると問題になります。

実際に性能を測ってみましょう。

1000万個の要素を持つビットベクトルを準備して、最後の要素に1をセットして、そこまでに出現する0の数を数えるgetNaiveRankメソッドの実行時間を計測してみます。

Mainクラスは以下のようにしました。

public class BitVectorMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		// ビットベクトルを生成する。
		BitVector bv = new BitVector( 10000000 );
		
		bv.setBit(9999999, 1);
		long totalTime = 0;
		for ( int i = 0; i < 100; i++ ) {
			long prevTime = System.nanoTime();
			bv.getNaiveRank(10000000, 0);
			long postTime = System.nanoTime();
			long elapsedTime = postTime - prevTime;
			totalTime += elapsedTime;
		}
		double averageTime = (double) totalTime / (double) 100;
		System.out.println( "平均時間(sec): " + (averageTime / (double) ( 1000 * 1000 * 1000)) );
		
	}

}

ちなみに私の環境は、

  • CPU: Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
  • MEM: 16GB
  • Java7

です。

まぁまぁハイスペックだと思います。

上記のMainクラスを実行すると、以下のような結果となりました。

平均時間(sec): 0.02850799799

平均で0.03秒だなんてまぁまぁ速いじゃないかと思いますが、100回実行すると3秒もかかります。
ランダムアクセスを何度も行うような処理の中では遅すぎて使えません。

実際、参考にしている本でも遅すぎて使えないと書いてあります。
改良した時の比較のために、わざわざやってみたわけです。

では、次回は、rank操作の高速化を行っていきます。