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

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

Java

FF6のボス戦の曲は最高です。

D

作業をかなり妨害されたわけですが、前回の記事で性能測定した定数時間のselectをsbvjに実装したので、以下で公開します。

http://code.google.com/p/sbvj/

sbvj-0.0.2.jarをダウンロードして、インポートするだけで使えます。

以下のような感じで使えます。

static void constantTimeSelect() {
	int sbvSize1 = 1000;
	SuccinctBitVector sbv1 = new SuccinctBitVector(sbvSize1);
	for ( int i = 0; i < sbvSize1; i++ ) {
		if ( 0 == (i % 10) ) {
			sbv1.setBit(i, 1);
		}
	}
	
	sbv1.build(BuildType.SELECT_FOR_ONE_IN_CONSTANT_TIME);
	
	long select = sbv1.getSelect(5, 1);
	
	System.out.println( "select: " + select );
	
	int sbvSize2 = 1000;
	SuccinctBitVector sbv2 = new SuccinctBitVector(sbvSize2);
	for ( int i = 0; i < sbvSize2; i++ ) {
		if ( 0 == (i % 10) ) {
			sbv2.setBit(i, 0);
		} else {
			sbv2.setBit(i, 1);
		}
	}
	
	sbv2.build(BuildType.SELECT_FOR_ZERO_IN_CONSTANT_TIME);
	
	select = sbv2.getSelect(5, 0);
	
	System.out.println( "select: " + select );
}

結果は、以下のようになります。

select: 50
select: 50

次回はちょっとした解説を書いてみようと思います。