配列の値をマップに置き換えて検索する方法は実際どれくらい速いのか検証

alucky0707 さんの 配列を高速に探索するTips で紹介されている、配列を一旦オブジェクトに置き換えて検索する方法は実際どれくらい速いのか検証。

検証方法

1. 0 ～ <指定したサイズ - 1> を要素に持つ配列を生成して、ランダムにソート
2. ランダム配列の各要素をキーに持つオブジェクトを生成
3. 0 ～ 10000 の間でループを回し、ループカウンターの値を indexOf() とオブジェクトのキーの両方で検索
4. それぞれの検索に要した時間の平均を計算して出力

環境

ブラウザ

• Firefox 26.0
• Google Chrome 31.0.1650.63 m
• Internet Explorer 10.0.9200.16650

検証

indexOf() を使う方法

要素数	Chrome	Firefox	IE
10,000	0.0093 ms	0.1882 ms	0.0367 ms
100,000	0.0811 ms	0.2052 ms	0.3648 ms
1,000,000	0.8065 ms	-	3.5679 ms
10,000,000	8.1802 ms	-	-

マップに詰め替えてキー検索する方法

要素数	Chrome	Firefox	IE
10,000	0 ms	0.0009 ms	0.0001 ms
100,000	0 ms	0.001 ms	0.0003 ms
1,000,000	0 ms	0.0011 ms	0.0004 ms
10,000,000	0 ms	-	0.0005 ms

※「-」はブラウザが応答しなくなった（おそらくランダムソートの途中で死んだっぽい）。

やはり、ハッシュによる検索なので要素数に関係なく一瞬で終わる。

ただ、そうなると問題は、配列をマップに置き換えるのにどれくらい時間がかかるのか、という点。
この時間が indexOf() 検索する時間よりかかっていたら意味が無い。

配列→マップへの変換にかかる時間

要素数	Chrome	Firefox	IE
10,000	0.32 ms	0.28 ms	0.36 ms
100,000	1.25 ms	2.77 ms	2.63 ms
1,000,000	44.77 ms	29.55 ms	26.35 ms

※試行回数は 100 回。

これらの数字を信じるとすると、配列を検索して指定した値が入っているかどうか確認する場合、次の表に挙げる回数以上検索する場合に限り、配列をマップに置き換えてからキー値で検索した方が速いということになる。

要素数	Chrome	Firefox	IE
10,000	34回	1回	10回
100,000	15回	13回	7回
1,000,000	56回	-	7回

なんか数値が怪しい気がするけど、とりあえず結構早い段階からマップに置き換えたほうが速くなるっぽい。

結論

つまり、 1, 2 回しか検索しないなら indexOf を使ったほうが速いが、何十回も検索するならマップに置き換えてキー検索した方が速いっぽいという、当然といえば当然の結論が出た。

まぁ、「理論的には早くなるはず」と思いつつも若干半信半疑になっていたので、実際に数値を見て安心できたという点で意味はあるのではないかと。。。

実装

var ARRAY_SIZE = 100000;

var randomSortArray = createRandomSortArray(ARRAY_SIZE);

var average = new Average();
var time;
var contains;

time = measureTime(function() {
    contains = toSearchValueFunction(randomSortArray);
});

console.log('[toSearchValueFunction] ' + time + ' ms');

for (var i=0; i<10000; i++) {
    time = measureTime(function() {
        randomSortArray.indexOf(i);
    });
    
    average.push('indexOf', time);
    
    time = measureTime(function() {
        contains(i);
    });
    
    average.push('contains', time);
}
console.log('[indexOf]  ' + average.get('indexOf') + ' ms');
console.log('[contains] ' + average.get('contains') + ' ms');

function createRandomSortArray(size) {
    var array = [];
    
    for (var i=0; i<size; i++) {
        array.push(i);
    }
    
    array.sort(function() {
        return Math.random() - 0.5;
    });
    
    return array;
}

function toSearchValueFunction(array) {
    var map = {};
    
    for (var i=0; i<array.length; i++) {
        map[array[i]] = i;
    }
    
    return function(value) {
        return (value in map);
    };
}

function measureTime(process) {
    var start = new Date();
    process();
    var end = new Date();
    
    return end.getTime() - start.getTime();
}

function Average() {
    var _holder = {};
    
    this.push = function(name, value) {
        if (!(name in _holder)) {
            _holder[name] = {
                sum: 0,
                cnt: 0
            };
        }
        
        _holder[name].sum += value;
        _holder[name].cnt++;
    };
    
    this.get = function(name) {
        return _holder[name].sum / _holder[name].cnt;
    };
}