String.prototype.indexOfって結構速いみたい

こんなSuffixArray（ハッシュ使ってるけど）を作ってみた。

suffixarray.js

function SuffixArray(str) {
  var
  i, c, sa = {};
  this.str = str;

  for (i = 0; c = str.charAt(i); i++) {
    (sa[c] || (sa[c] = [])).push(i);
  }
  this.sa = sa;
}

SuffixArray.prototype.search = function (word, start) {
  if (!word) return 0;
  start = start || 0;

  var
  i,
  is = this.sa[word.charAt(0)], l = (is || []).length;

  for (i = 0; i < l; i++) {
    if (is[i] >= start && this.str.substr(is[i], word.length) === word) return is[i];
  }
  return -1;
}

SuffixArrayって言うとバイナリサーチが一般的な気がするけど、バイナリサーチよりハッシュの方が速い（し書くのが楽）に決まってるのでハッシュで書いてみた。（JavaScriptのオブジェクトをハッシュと呼んでいいのか？）

で、String.prototype.indexOfと、ついでにString.prototype.search(正規表現版indexOf)で速度を比較してみる。
jsPerfというのがあるのを知ったので、そこでやってみた。

ここにあります↓。
String.prototype.indexOf vs String.prototype.search(RegExp) vs my SuffixArray · jsPerf

結果は、

という感じです。Opera 17って何だよ、って感じですが中身は八割ぐらいChromeなのでChromeだと思えばいいはずです。

これ、長いほど速いみたいなので、indexOfが一番速いということになります。しかもSuffixArrayより倍以上速いです。

うーん、indexOfって線形探索じゃないんだろうな…。

ちなみにFirefoxでもほぼ同じ結果でした（時間は八倍ぐらいかかりましたが）