プログラミングをしていると、ある配列から特定の数値や文字列を含んだデータを取り出す場面に直面するはよくあると思いますが、どのようにデータを探索するかによってパフォーマンスに大きく影響します。
データ探索の方法として、JavaScriptであれば、indexOf関数という便利な関数があるので、それを使用する方が多いかもしれません。

しかし、indexOf関数はデータを取り出すのに時間がかかるという評判もあるため、今回は幾つかの定番アルゴリズムの中から高速にデータを取り出す事ができる手法を確認したいと思います。

定番の探索アルゴリズム

リニアサーチ（線形探索法）

リニアサーチはその名前の通り、一直線に配列を探索する方法です。
先頭から順番に（もしくは末尾から順番に）データを取り出して探索しますので、非常にシンプルな方法ですが、データ量に比例して探索時間も長くなります。

コードでは以下のようになります。

function linearSearch ( list, num ) {
  var index = -1;
  for( var i = 0, len = list.length;i < len;i++ ) {
    if( list[i] === num ) {
      index = i;
      break;
    }
  }
  return index;
}

var dataList = [100, 30, 29, 349, 19, 47, 55];
var targetIndex = linearSearch( dataList, 19 );
console.log(targetIndex); //->4

バイナリサーチ（二分探索法）

バイナリサーチは配列を繰り返し半分に分割して探索範囲を狭めていき、対象データを探索する方法です。
前提条件として、配列の中身は昇順もしくは降順で並んでいる必要がありますが、探索アルゴリズムの中では比較的高速な探索方法です。

コードでは以下のようになります。

function binarySearch ( list, num ) {
  var index = -1;
  var head = 0;
  var tail = list.length;

  while( head <= tail ) {
    var center = Math.floor(( head + tail ) / 2);
    var centerVal = list[center];

    if( centerVal === num ) {
      index = center;
      break;
    }
    if( centerVal < num ) {
      head = center + 1;
    }else {
      tail = center - 1;
    }
  }
  return index;
}

var dataList = [10, 20, 30, 45, 55, 60, 73, 80, 100];
var targetIndex = binarySearch( dataList, 45 );
console.log(targetIndex); //->3

ハッシュ探索法

ハッシュ探索法はいわゆる一発でデータを取り出せるようにデータを並び替える方法です。
データに対して特定の計算式を施して並び替える必要があるため、並び替えの処理に時間を要しますが、データを取り出す際には高速なため、データ量が多い場合に効果を発揮します。

コードでは以下のようになります。

function makeHashList ( list ) {
  var hashList = list.reduce(function(directory, value, index) {
    directory[value] = (directory[value] || []).concat(index);
    return directory;
  }, {});
  return hashList;
}
function hashSearch (list, num) {
  var index = -1;
  if(num in list) {
    index = list[num];
  }
  return index;
}

var dataList = [100, 200, 50, 20, 90, 150, 20];
var hashList = makeHashList(dataList);
var targetIndex = hashSearch( hashList, 20 );
console.log( targetIndex ); //->3,6

各アルゴリズムの速度を検証してみる

上記で紹介した３つのアルゴリズムにJavaScriptのindexOf関数を加えた４つの探索方法を使って、大量のデータを探索してみます。探索回数の増加に伴う探索速度の増減を把握するために以下の条件で検証を行いました。

• 特定の配列からランダムな数値を探索し、対象の数値が格納されているインデックス値を取得できるまでの時間を計測する
• 各アルゴリズムで探索対象の配列内の数値、長さ、探索するランダムな数値は同一のものを使用する
• ハッシュ探索の配列のみ探索対象の配列をランダムにソートし、他の配列は昇順の並びとする

データを変更すると探索時間も変動しますが、概ね以下のような結果となりました。

探索アルゴリズムごとの計測時間結果（ミリ秒）

探索回数	100	1000	10000	100000
IndexOf関数	3	14	87	217
リニアサーチ	2	24	148	358
バイナリサーチ	1	1	2	23
ハッシュ探索法	0	25	54	75

検証結果からも分かる通り、100回の探索回数程度であれば各アルゴリズムでの探索時間に大差はないものの、indexOf関数は遅い結果となりました。
また、探索回数が1000〜3000回を超えた辺りからindexOf関数やリニアサーチよりハッシュ探索の方が高速に探索できる事がわかります。
バイナリサーチは配列が昇順（もしくは降順）で並んでいる必要があるものの圧倒的に早いですね。

という事で、大量のデータから探索する場合はハッシュ探索やバイナリサーチを使いましょう！

※ただし、上記の結果は特定の探索データに基づいた一例にすぎないので、必ず上記のような結果とならない事をご了承ください。