1. 導入

JavaScriptのArray.indexOf()メソッドは、配列中である値が出現する位置が何番目かを、ループを書かずに調べることができる大変便利なメソッドで、私自身、一途にこのメソッドばかり使っていたのですが、先日以下の2つの問題に気づいてしまいました。
  1. 比較的最近追加されたメソッドで、IE8以前では対応していない
  2. forループで探すより3倍程度遅い
1つ目の問題は、Mozilla Developer Networkのリファレンスに含まれるArray.indexOfの項目に対処法が書いてありますので、そちらを参照していただくとして、このエントリーでは2つ目の問題について調査を行います。また、Array.indexOf()の代替となる高速なコードを提示します。

2. 実験の準備

まず、Array.indexOf()と速度を比較するために以下のような定義したindex()を用意しました
var index = function (arr, val)
{
	for (var i=0; i<arr.length; i++) {
		if (arr[i] === val)
			return i;
	}

	return -1;
}
検索用のデータとして、0から(dataSize-1)の連番が格納された配列dataを使用しました。この実験では、データサイズdataSizeは10または1,000を用いています。また、速度測定のための繰り返し回数numIterationは、dataSizeに対応してそれぞれ10,000,000または100,000を用いています。

比較のための検索用ルーチンは以下のように定義しました。ここで、targetは検索対象の値で、dataにおける最初の要素と最後の要素、即ち0と(dataSize-1)をそれぞれ用いました。

1. Array.indexOf()
-- 普通にArray.indexOf()を使う場合です。無名関数呼び出し(function () { ... })()で各変数をローカル化しています。
(function () {
	var target = dataSize - 1; // または target = 0

	for (var j=0; j<numIteration; j++) {
		data.indexOf(target);
	}
})();

2. index()
-- 上で定義した関数です。
(function () {
	var target = dataSize - 1; // または target = 0

	for (var j=0; j<numIteration; j++) {
		index(data, target);
	}
})();

3. forループ
-- 単純にforループした場合です。
(function () {
	var target = dataSize-1; // または target = 0

	for (var j=0; j<numIteration; j++) {
		for (var i=0; i<data.length; i++) {
			if (data[i] === target)
				break;
		}
	}
})();

4. forループ + if-in
-- forループの中でi番目の要素が存在するかどうかを調べています。これはArray.indexOf()の実装の模倣です。
(function () {
	var target = dataSize-1; // または target = 0

	for (var j=0; j<numIteration; j++) {
		for (var i=0; i<data.length; i++) {
			// ここで、dataにi番目の要素が存在するかif-in文で調べている
			if (i in data && data[i] === target)
				break;
		}
	}
})();

5. forループ@グローバル領域
-- 無名関数呼び出し(function () { ... })()によるローカル化を行わず、グローバル領域で処理する場合です。
target = dataSize - 1; // または target = 0

for (var j=0; j<numIteration; j++) {
	for (var i=0; i<data.length; i++) {
		if (data[i] === target)
			break;
	}
}

これらの処理に掛かった時間をミリ秒単位でそれぞれ測定しました。なお、繰り返し自体にかかる時間として、以下の処理にかかる時間も測定し、実験結果から差し引いています。
(function () {
	for (var j=0; j<numIteration; j++) ;
})();

実験に使用したブラウザはMac版のGoogle Chrome 26.0、Firefox 20.0及びSafari6.0.4です。

3. 実験の結果

比較の結果は次の通り。

データ10個, 繰り返し10,000,000回の場合の速度比較 (ミリ秒)
ルーチン検索対象ChromeFirefoxSafari
Array.indexOf()最後の要素85821062243
Array.indexOf()最初の要素331362473
index()最後の要素310312357
index()最初の要素10512650
forループ最後の要素220216556
forループ最初の要素192747
forループ + if-in最後の要素58263703213
forループ + if-in最初の要素58252304
forループ＠グローバル領域最後の要素696286933
forループ＠グローバル領域最初の要素8921103

データ1,000個, 繰り返し100,000回の場合の速度比較 (ミリ秒)
ルーチン検索対象ChromeFirefoxSafari
Array.indexOf()最後の要素59514141803
Array.indexOf()最初の要素439
index()最後の要素208159316
index()最初の要素222
forループ最後の要素203157561
forループ最初の要素110
forループ + if-in最後の要素56432843145
forループ + if-in最初の要素822
forループ＠グローバル領域最後の要素673269924
forループ＠グローバル領域最初の要素433

まず、いずれのブラウザでもArray.indexOf()メソッドがindex()関数と比べて明らかに遅いことが見て取れます。これは先程紹介したMDNリファレンスのArray.indexOfの項目にある、"ECMA-262 第 5 版で定められたアルゴリズムと等価"なコードが示すように、検索対象の配列の各要素が実際に存在するかどうか調べる作業を始めとして、汎用性の高めるための処理を行なっているためだと推測できます。実際、(Firefoxではそれほどの違いがないのが謎ですが、) ChromeとSafariの「forループ + if-in」の速度はかなり遅くなっていることが分かります。

index()とforループを比較した場合、ChromeとFirefoxでは繰り返し回数が多くなると関数呼び出しのオーバーヘッドが顕在化することが分かります。しかしながら、その差は1000万回のループに対して僅かに90ミリ秒程度なので、よほど繰り返しindex()関数を呼び出さない限りは問題にならないと考えられます。実際、10万回のループでは関数呼び出しのオーバーヘッドがほとんど確認できません。一方、Safariにおいては関数呼び出しによるオーバーヘッドは見られず、むしろ関数化することによって最後の要素を検索した場合に大きく高速化していることが分かります。Safariの最適化が関数に強いのかもしれません。

また、グローバル領域でforループを行った場合、いずれのブラウザでも(特にChromeとSafariでは)、処理速度は低下しています。こちらの記事の引用によれば、最適化されたインデックスが作られるローカル変数と比べて、グローバル変数は常に名前で参照されることから、値の読み出しに時間がかかるそうです。

4. 実用的なコードの提示

ベンチマークの結果に基づいて次のような関数を作成しました。
var index = (function (undefined)
{
	var f;

	return function (arr, val, from)
	{
		if (from !== undefined) {
			if (from < 0) {
				f = from + arr.length;

				if (f < 0)
					return -1;
			}
			else {
				f = from;
			}
		}
		else {
			f = 0;
		}

		for (var i=f; i<arr.length; i++) {
			if (arr[i] === val)
				return i;
		}

		return -1;
	}
})();

// 使い方
var targetArray = ['あ', 'い', 'う', 'え', 'お'];
console.log(index(targetArray, 'い')); // -> 1
console.log(index(targetArray, 'い', 2)); // -> -1 -- 前から3番目の'う'から検索するため
console.log(index(targetArray, 'お', -2)); // -> 4 -- 後から2番目の'え'から検索する
戻り値として、第一引数で指定した配列の中に、第二引数と一致する要素が見つかった場合は、最初に見つかったものの要素番号、見つからなかった場合は-1を返します。基本的にArray.indexOf()メソッドと同様に使えますが、第一引数として指定する配列が歯抜け状態だと思い通りに動作しない可能性があります。具体的には、配列の各要素に一つでも抜けがある場合、Chrome上でなぜかArray.indexOf()メソッドよりも遅くなります。第三引数で検索を開始する要素の番号を指定できます。負の値を指定することで最後の要素からの位置で検索開始位置を設定できます。

(function (undefined) { ... })()という、undefinedを引数とする匿名関数を使用しているのは、undefinedが間違いなく未定義を意味するようにするおまじないです。というのも、JavaScriptにおいてundefinedはただの変数に過ぎず、ユーザーが後から上書きできるため、安全にundefinedを使うにはこのような工夫が必要なのです (参考)。普通は上書きしないでしょうが、この匿名関数には変数fをもつクロージャの役割ももたせていて、どのみち定義することになるので、ついでに引数としてundefinedも書いておきました。わざわざクロージャにしているのは、Firefox (20.0)の最適化にクセがあり、このように書かないとFirefoxでの速度がArray.indexOf()程度にまで低下してしまうためです。具体的には、実験から外面的に推測する限り、Firefoxは変数を代入した段階では参照のみを保持し、実際に値が変更された時に初めて変数を定義するという、いわゆる遅延評価により最適化しているようなのですが、この変数定義が発生した場合に計算速度が大幅に低下しているということのようです。それを回避するため、予めクロージャ内に定義した変数fでワンクッション置くことで、高速化しています。

index()だと変数と名前が衝突してしまう可能性があって嫌だという人は、以下のように適当な名前のオブジェクトの要素として定義すればよいでしょう。これによってオーバーヘッドが発生しなくはないですが、関数呼び出しのオーバーヘッドの方がずっと大きいので問題になりません。
var MyLib = {};
MyLib.index = (function (undefined) { /* 中略 */ })();

// 使い方
var targetArray = ['あ', 'い', 'う', 'え', 'お'];
console.log(MyLib.index(targetArray, 'い')); // -> 1

ちなみに、
Array.prototype.index = (function (undefined)
{
	var f;

	return function (val, from)
	{
		if (from !== undefined) {
			if (from < 0) {
				f = from + this.length;

				if (f < 0)
					return -1;
			}
			else {
				f = from;
			}
		}
		else {
			f = 0;
		}

		for (var i=f; i<this.length; i++) {
			if (this[i] === val)
				return i;
		}

		return -1;
	}
})();

// 使い方
var targetArray = ['あ', 'い', 'う', 'え', 'お'];
console.log(targetArray.index('い')); // -> 1
このように書けば、Array.indexOf()メソッドとほぼ同じ書式でアクセスできますが、任意の配列に対してfor-in文による検索を行った場合に、配列の各添字(0,1,2,...)に加えてindexも引っかかってしまいますので注意が必要です。(そもそもfor-in文はオブジェクトに対して使うもので、配列に対して使うべきものではありませんが(参考)、JavaScript以外には配列に使える言語もありますので、無意識に使ってしまってバグを作るかもしれません。)　なお、上記のコードにおいて Array.prototype.index の部分を Array.prototype.indexOf に書き換える、すなわちArray.indexOf()メソッドに上書きした場合は、Array.prototype.indexOfはfor-in文から隠蔽されるように設計されているため引っ掛かりませんが、もともと存在するArray.indexOf()メソッドは当然使えなくなります。おすすめしません。

以下、改変前の文章を置いておきます。

ベンチマークの結果に基づいて次のような関数を作成しました。
var index = function (arr, val, first)
{
	if (arguments.length >= 3) {
		for (var i=first; i<arr.length; i++) {
			if (arr[i] === val)
				return i;
		}
	}
	else {
		for (var i=0; i<arr.length; i++) {
			if (arr[i] === val)
				return i;
		}
	}
	return -1;
}
第 一引数として指定する配列が歯抜け状態だと思い通りに動作しない可能性があります。具体的には、配列の各要素に一つでも抜けがある場合、Chrome上で なぜかArray.indexOf()メソッドよりも遅くなります。第三引数で検索を開始する場所を指定できますが、Array.indexOf()でで きるようなマイナスの値の指定はできません。これは3行目の直後に if (first < 0) { ... } を置いた瞬間、たちどころに処理速度が5倍(Chrome)または3倍(Firefox)遅くなることを確認したためです。forループの外なのでなぜこ んなに遅くなるのか理解できませんが(おそらく最適化上の都合があるのでしょう)、事実として遅くなるので諦めました。

また、FireFoxの場合で、
(function () {
	for (var j=0; j<numIteration; j++) {
		index(data, 999, 500);
	}
})();
(function () {
	for (var j=0; j<numIteration; j++) {
		index(data, 999);
	}
})();
このように書くと順当に前者が後者より約二倍高速に動作しますが、
(function () {
	for (var j=0; j<numIteration; j++) {
		index(data, 999);
	}
})();
(function () {
	for (var j=0; j<numIteration; j++) {
		index(data, 999, 500);
	}
})();
このように書くとなぜか後者が前者より約10倍遅くなります。おそらく最適化の不具合でしょう。index(data, 999)をindex(data, 999, 0)に書き換えれば後者が先ほどの20倍高速化(つまり正常な動作)されますので、第三引数を1箇所でも使う場合は他の箇所でも第三引数を指定するほうが安全かもしれません。なお、Chromeではこのような現象は起こりません。

この辺りの謎は解明され次第報告したいと思います。

タグ ：
#JavaScript
#調査
#indexOf