Hatena::ブログ(Diary)

hogehoge @teramako RSSフィード

 

2014-04-03

String repeat のアルゴリズムとパフォーマンス

ES6になると、String.prototype.repeatのメソッドが追加されるわけだが、そのアルゴリズムとパフォーマンスを追ってみている。

ES6 String.prototype.repeat の仕様では以下の様な感じでシンプルな書き方をしている。

  • countが 0 より小さい、または 無限大である場合は RangeError
  • count 0 ならば、空文字列
  • そうでない場合は、count回、文字列を繰り返して連結する

単純に実装すれば、以下の様な感じで済む。

String.prototype.repeat = function (count) {
  if (count < 0 || !Number.isFinite(count))
    throw new RangeError();
  var result = "",
      str = this;
  for (var i = 0; i < count; ++i) {
    result += str;
  }
  return result;
};

他にも配列を作ってjoinする方法も考えつく

String.prototype.repeat = function (count) {
  var arr = new Array(count),
      str = this;
  for (var i = 0; i < count; ++i) {
    arr[i] = str;
  }
  return arr.join("");
};
String.prototype.repeat = function (count) {
  return (new Array(count + 1)).join(this);
}

しかし、これらは結局、count回繰り返す処理であり、ループ数が線形的に増加し非効率である。

スピードを求めるならループ数の一次的増加は悪である。

もう少し工夫をしよう。

Firefox(SpiderMonkey)の初期実装

細かいチェックを省くと概ね以下の様な実装であった

String.prototype.repeat = function (count) {
  if (count === 0)
    return "";
  var str = this,
      result = str;
  for (var i = 1; i <= count / 2; i *= 2) {
    result += result;
  }
  for (; i < count; i++) {
    result += str;
  }
  return result;
};
  • 2, 4, 8 ... と 2のべき乗で収まる範囲の回数までは、結果となる値自身を積み上げていく
    • 512回なら 9回のループ、1024回なら10回のループで済む
  • あまりは、単純ループで追加していく

というアルゴリズムであった。

最初のループでは高速道路に乗った気分で気持よく進み、256, 512, 1024 などの綺麗な数値だと速攻で処理される。しかし、1023回などになると、512回までは気持ちよく進んだ後に2番めのループで511回もループするはめになってスピードが極度に下がってしまう。

修正された実装

落差の激しいアルゴリズムだった実装が次の変更で改善される

String.prototype.repeat = function (count) {
  var result = "",
      str = this;
  for (;;) {
    if (count & 1) {
      result += str;
    }
    count >>= 1;
    if (count) {
      str += str;
    } else {
      break;
    }
  }
  return result;
};

わけがわからない…

が、ビット演算をしているので2進数で考えてみたらなんとなく見えてきた。

13回ほどのリピートを考えてみる。13は 1101(2) である。ビットが立っているところでstr += strで積み上げた文字列をresultに追加して行こうという処理である。

結果、ループ数は2進数の桁分で済む。

すばらしい…、自分のような凡俗にはとても思いつかないアルゴリズムだ。感動した。


一方、Chrome(V8)の実装

そうなると、V8エンジンでの実装が気になり始める。もっと凄いことをしているのでは!?

String.prototype.repeat = function (count) {
  var elements = new Array(count),
      str = this;
  for (var i = 0; i < count; i++) {
    elements[i] = str;
  }
  return elements.join("")
};

なんか…とても残念でした。

次に期待することにしましょう。

パフォーマンス

そんなこんなを思いながら、書いてみた jsperf

いろいろ試行錯誤していたので、綺麗なグラフではないけど、String.prototype.repeatにおけるFirefox(SpiderMonkey)の優秀さ/Chrome(V8)の残念さ、1024リピートという綺麗な数値での爆速さがうかがい知れる感じで面白いと思う。

2014-03-27

2014-03-15

Firfox 30(Nightly)で ES6的な ArrayComprehension,GeneratorComprehension が実装された

書くのが1週間ほど遅れた。

var arry = [for (value of iteratableObject) value]; // ArrayComprehension
/* ==
(function() {
  var list = [];
  for (let value of iteratableObject) {
    list.push(value);
  }
  return list;
}());
*/

var gene = (for (value of iteratableObject) value); // GeneratorComprehension
/* ==
(function *() {
  for (let value of iteratableObject) {
    yield value;
  }
}());
*/

基本的な構文は上記のような感じ。コメント部に書いたのに近いコードを短縮して書けると思えば良いと思う。

for-of 部分は続けて書けるし、if () によるフィルタリングも可能

var list = [
  ["a", "b"],
  ["c", 10],
  "d",
];

[for (child of list) for (v of child) if (typeof v === "string") v].join("/");
// "a/b/c/d"
[for (child of list) if (Array.isArray(child)) for (v of child) if (typeof v === "string") v].join("/");
// "a/b/c"

Mozilla既存のArrayComprehension, GeneratorComprehension

ES6に入る前からMozilla JavaScript 1.8[developer.mozilla.org]からこれらがあり、ES6も当初はこの構文だった。

[v for (value1 of iteratableObject) for (v of value1)];

最初に最終的に取られる値を指定した後に for-of を書くような感じだった。

ただ、これだと評価の順が混乱しやすい。

     [v for (value1 of iteratableObject) for (v of value1)];
// 1.     >--実行---------------------->
// 2.                                     >--実行-------->
// 3. 値

という順番が正しいのだが、以下の方が自然にも思える。

     [v for (v of value1) for (value1 of iteratableObject)];
// 1.                     >--実行------------------------>
// 2.     >--実行------->
// 3. 値

で、結局、現在の下記の様な順番の方が自然だよね、という話になったと記憶している(あやふやだが)

     [for (value1 of iteratableObject) for (v of value1) v];
// 1. >--実行------------------------>
// 2.                                  >--実行--------->
// 3.                                                    値

現状のFirefoxでは、既存の構文もES6の構文も両方サポートしている。拡張機能内などでは、既存構文が使われているのでしばらくは両方サポートの状態が続くと思う。