[JavaScript]二分探索のベンチマーク

今作っているWebサービスで、とりあえず仮の仕様ということで線形探索を多用していたのですが、リリースに向けて、可能な部分は二分探索を使うように改良しました。理屈の上から言えば、O(n) が O(log₂n)になるわけで、当然速くなったものと考えて、実際には検証していませんでした。

ここ数日、少し余裕が出来たので、ちょっとベンチマークを取って見ました。それぞれ、100万回ループして、かかった時間を計っています。各ブラウザのバージョンは、Firefox 12.0、IE 9.0.8112.16421 64-bit Edition、Google Chrome 18.0.1025.168 m、Opera 11.62、OSは Windows7 64bit、マシンは i7-2600 です。

Array.prototype.binarySearch = function( val ){
	var low = 0;
	var high = this.length - 1;
	var middle;

	while( low <= high ){
		middle = ( low + high ) / 2 | 0;

		if( this[middle] == val )
			return middle;
		else if( val < this[middle] )
			high = middle - 1;
		else
			low = middle + 1;
	}
	return -1;
}

Array.prototype.linearSearch = function( val ){
	var length = this.length;
	for( var i = 0; i < length; i++ ){
		if( this[i] == val )
			return i;
	}
	return -1;
}

var array = new Array();
for( var i = 0; i < 100; i++ ){ array[i] = i; }

var start = new Date().getTime();

var result, r;

for( var i = 0; i < 1000000; i++ ){
	r = Math.random() * 100 | 0;
	result = array.linearSearch( r );
	//result = array.binarySearch( r );
}

var end = new Date().getTime();

alert( end - start  );

 要素数100

	Firefox	IE9	Chrome	Opera
linear search	102	756	99	162
binary search	99	723	89	164

要素数100程度ではあまり変わらないという結果でした。
線形探索が遅いと言っても、平均すれば n / 2 で済むわけですから n が小さいうちはそれなりに速いですね。

と、言いますか、最近のPCは本当に速いので、100万回ループしてようやく数ミリから数十ミリ秒という誤差レベルの違いしか出ません。

そこで、今度は要素数1000でやってみました。

要素数1000

	Firefox	IE9	Chrome	Opera
linear search	919	11118	2198	2192
binary search	138	1017	123	219

さすがに、今回は無視しがたい差が出ました。
ただ、問題のWebサービスでは個々の要素数が3桁を超えることはそうない（それ以上が必要な場合はデータベースを使う）と思われるので、ソートのコストも考えると線形探索で十分だったのかも知れません。
むしろ、パフォーマンスに最大の影響を与えるのはやはりDOM操作なので、そこの最適化に注力するのが賢明なようです。