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

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

Java

さて、以下の2種類のrank操作を行うメソッドを実装しました。

  • getNaiveRankメソッド
  • getRankメソッド

それぞれのメソッドの実行性能を測定したいと思います。

以下のようなMainクラスを用意して実際に性能を測定してみました。

public class BitVectorMainForMeasureRankPerformance {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		for ( int multiple = 10; multiple <= 30; multiple++ ) {
		
			// ビットベクトルのサイズ
			long bitVectorSize = (long) Math.pow(2, multiple);

			// getRankメソッド: true
			// getNaiveRankメソッド: false
			boolean flag = true;
			BitVector bv = new BitVector( bitVectorSize );

			// ビットを設定しておく。
			for ( long i = 0; i < bitVectorSize; i++ ) {
				if ( 0 == ( i % 10000 ) ) {
					bv.setBit(i, 1);
				}
			}

			if ( flag ) {
				// 定数時間でビットベクトルに対してrankを実行するための前処理を行う。
				bv.buildForFastRank();
			}

			long rank = 0;
			long naiveRank = 0;
			
			long prevRankTime = System.nanoTime();
			for ( int i = 0; i < 100; i++ ) {
				
				// 高速なrank
				rank = bv.getRank(bitVectorSize, 1);
				
			}
			long postRankTime = System.nanoTime();
			long elapsedRankTime = postRankTime - prevRankTime;
			
			long prevNaiveRankTime = System.nanoTime();
			for ( int i = 0; i < 100; i++ ) {
				
				// ナイーブなrank
				naiveRank = bv.getNaiveRank(bitVectorSize, 1);
				
			}
			long postNaiveRankTime = System.nanoTime();
			long elapsedNaiveRankTime = postNaiveRankTime - prevNaiveRankTime;
			
			System.out.println( "2^" + multiple );

			System.out.println( "rank: " + rank );
			System.out.println( "合計時間(sec): " + (elapsedRankTime / (double) ( 1000 * 1000 * 1000 )) );
			System.out.println( "合計時間(millisec): " + (elapsedRankTime / (double) ( 1000 * 1000 )) );
			System.out.println( "合計時間(microsec): " + (elapsedRankTime / (double) ( 1000 )) );
			System.out.println( "合計時間(nanosec): " + elapsedRankTime );
			
			System.out.println( "naiveRank: " + naiveRank );
			System.out.println( "合計時間(sec): " + (elapsedNaiveRankTime / (double) ( 1000 * 1000 * 1000 )) );
			System.out.println( "合計時間(millisec): " + (elapsedNaiveRankTime / (double) ( 1000 )) );
			System.out.println( "合計時間(microsec): " + (elapsedNaiveRankTime / (double) ( 1000 * 1000 )) );
			System.out.println( "合計時間(nanosec): " + elapsedNaiveRankTime );
			
			System.out.println();
			
		}
		
	}

}

ビットベクトルのサイズを2のべき乗として、2^10〜2^30までのサイズのビットベクトルを用意して、それぞれのビットベクトルに対して10000の区切りごとに1を立てておきます。
そして、最後の位置までのrank値を計算するのに各メソッドがどれぐらいの時間がかかったかを計算しています。
また、各メソッドの実行時間は、平均で求めるために、100回の実行を行った時の平均時間を測定しています。

実行した結果をグラフ化したものを以下に示します。
今回は、millisec単位でグラフ化してみました。

f:id:ryokkie:20120304222721p:plain

グラフを重ねる必要はなかったのですが、今回は、重ねてみました。

getNaiveRankメソッドは、予想通りのグラフで、ビットベクトルのサイズが大きくなると、性能が落ちていきます。
getRankメソッドは、定数オーダーなので、横一線のグラフを想定していたのですが、そのようなグラフにはなりませんでした。
実装が悪かったのかもしれないですし、Javaの特性かもしれません。
ただし、ビットベクトルのサイズに性能が依存していないというのはわかるかと思います。

やはり、めんどうでも可視化しておくといろいろなことがわかりますね。

getNaiveRankメソッドは全くいらないような気もしてきますが、ビットベクトルのサイズが十分に小さく、頻繁にビットベクトルが変更されるような場合は、使えるのではないでしょうか。
逆に、一旦、構築してしまえば、後は、アクセスしかしないような場合は、やはりgetRankメソッドを使う方が良いでしょう。

ようやくrankの説明を終えることができました。

次回は、select操作について検討していきたいと思います。