Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
187
Help us understand the problem. What is going on with this article?
@alucky0707

配列を高速に探索するTips

More than 5 years have passed since last update.

[追記]気づいたらいつの間にか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);

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

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のオブジェクトのキーは文字列のみなのでオブジェクトに対してこの方法を使うことはできません。[/追記]

187
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
alucky0707
ウィルキンソンジンジャエールを片手にコードを書く人。JavaScriptぐらいしかまともに書けない…。東京都内の工業高校に通うザコ学生。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
187
Help us understand the problem. What is going on with this article?