配列を高速に探索するTips #JavaScript

[追記]気づいたらいつの間にか50ストックを超えていました。みなさんありがとうございます。[/追記]

どうも、Opera Nextに（色んな意味で）驚きを隠せないあらっきぃです。

大抵の場合はArray#indexOfで事足りるんだけど、時々高速に配列に要素が存在するか調べたくなることがあります。

例えばこんな風に、要素数100000の配列があったとします。

var
arr = (function(len) {
  var
  i,
  arr = [];
  for(i = 0; i < len; i++) arr.push(~~(Math.random() * len));
  return arr;
})(1000000);

この配列に999983（1000000以下の最大の素数）が含まれているか調べるには、通常こう書きます。

var
search_num = 999983;
if(arr.indexOf(search_num) !== -1) {
  //要素があった場合
} else {
 //要素が無かった場合
}

（CoffeeScriptのin演算子もArray#indexOfを呼びますね）

ですが、このArray#indexOfは単純なリニアサーチ（線形探索）なので、最悪要素数に比例した時間がかかります。なので、複数回呼ぶ場合は速度においてネックになります。

ソートされていればバイナリサーチでもいいのですが、あいにくこの配列はソートされていそうにもありませんし（ボゴソート的確率でソートされていることはありますが…）、バイナリサーチを書くのは正直面倒です。

そこで、JavaScriptの全てとも言えるオブジェクトを使って、こんな風に書いてみることにしました。

var
arrTable = arr.reduce(function(m, a, i) {
  m[a] = (m[a] || []).concat(i);
  return m;
}, {});
if(searchNum in arrTable) {
  //要素があった場合
} else {
  //要素が無かった場合
}

はい、ハッシュ法です（まあJavaScriptのオブジェクトをハッシュ法で実装しなきゃいけないという法律があるわけでもないので、もしかしたら二分探索かもしれませんが…）。
戯言は無視しましょう。

この方法を使うと、ハッシュテーブルを作るのには要素数に比例した時間がかかりますが、探索時間自体は（理論上）定数時間で終わることになります。
つまり、Array#indexOfを使っていた時には五回の探索で5000000のコストが掛かっていたわけですが、ハッシュ法だと1000005になるわけです。約五分の一です。すごい。

しかも、

console.log(arrTable[searchNum]);

のようにすれば、配列中の要素のある位置が全て求まるように実装しました。便利ですね。

最後に、この探索をコンポーネントにしておきたいと思います。

search.js

var
Search = (function() {

  /* constructor */
  function Search(arr){
    if(!(this instanceof Search)) return new Search(arr);
    this._arr = arr;
    this._createTable();
  }

  var
  /* member */
  proto = Search.prototype = {
    _arr: null,
    _table: null,
  };

  /* private */
  proto._createTable = function() {
    this._table = this._arr.reduce(function(m, a, i) {
      m[a] = (m[a] || []).concat(i);
      return m;
    }, {});
  };

  /* public */
  proto.has = function(a) {
    return a in this._table;
  };

  proto.index = function(a) {
    return this._table[a] || [];
  };

  proto.search = function(a) {
    return this.index(a).reduce(function(m, i) {
      m.push(this._arr[i]);
      return m;
    }, []);
  };

  return Search;
})();

[追記]ちなみに、コメント欄でも触れられていますが、JavaScriptのオブジェクトのキーは文字列のみなのでオブジェクトに対してこの方法を使うことはできません。[/追記]