Days on the Moon

「IT戦記 - JavaScript で遅延評価」より。遅延評価といえばたらいまわし関数と相場が決まっている、ような気がする。

function tak(x, y, z) {
  return (x <= y) ? y : tak(tak(x - 1, y, z),
                            tak(y - 1, z, x),
                            tak(z - 1, x, y));
}

これを元記事に従って書き直すとこうなる。

// from http://d.hatena.ne.jp/amachang/20061204/1165180769
Function.prototype.lazy = function () {
  return { valueOf: this };
};

function takL(x, y, z) {
  return (x <= y) ? y :
    takL(takL(x - 1, y, z),
         takL(y - 1, z, x),
         function () { return takL(z - 1, x, y); }.lazy());
}

print(takL(10, 5, 0));

だが、Wikipedia で遅延評価の項を見てみると計算結果をキャッシュしておかなくてはいけないようだ。なのでキャッシュの仕組みを取り入れてみる。

Function.prototype.delayed = function () {
  var self = this, args = arguments, value = undefined, forced = false;
  return {
    valueOf: function () {
      if (!forced) {
        value = self.apply(null, args);
        forced = true;
      }
      return value;
    }
  };
};

function takD(x, y, z) {
  return (x <= y) ? y :
    takD(takD(x - 1, y, z),
         takD(y - 1, z, x),
         takD.delayed(z - 1, x, y));
}

print(takD(10, 5, 0));

lazy のようにワンクッション入れるのは嫌だ、キャッシュもなくていいという場合は、変形が多くなるが関数式だけでも事足りる。

function takF(x, y, fz) {
  return (x <= y) ? y :
    takF(takF(x - 1, y, fz),
         takF(y - 1, fz(), function () { return x; }),
         function () { return takF(fz() - 1, x, function () { return y; }); });
}

print(takF(10, 5, function () { return 0; }));

ついでにメモ化版。

function takM(x, y, z) {
  var item = x + "," + y + "," + z; // [x, y, z].join() より速い
  return (item in takM.memo) ? takM.memo[item] :
    takM.memo[item] = (x <= y) ? y : takM(takM(x - 1, y, z),
                                          takM(y - 1, z, x),
                                          takM(z - 1, x, y));
}
takM.memo = {};

print(takM(10, 5, 0));

そして各たらいまわし関数の速度比較。SpiderMonkey のシェルで試してみると takF がもっとも速く、ついで takL に takD、大きく差を開けて takM という結果になった。ブラウザ上では安定した結果が得られなかったものの、takF、takL、takD が総じて速く、takM はその 2～3 倍時間がかかった。

まとめると、JavaScript でのたらいまわしに限って言えば、関数式を使い評価を遅らせることが速度向上に大きく貢献している。そしてその際計算結果をキャッシュしておくかどうかはあまり関係ないようだ。メモ化はそれに比べれば遅いものの、何もしない場合と比べれば月とスッポンの差がある。

ちなみに、JScript ではなぜかそのままメモ化するよりもメモ化を汎用化したほうが速かった。

Function.prototype.memoize = function () {
  var self = this, memo = {};
  return function () {
    var item = Array.prototype.join.apply(arguments);
    return (item in memo) ? memo[item]
                          : memo[item] = self.apply(this, arguments);
  };
};

function takMG(x, y, z) { // same as tak
  return (x <= y) ? y : takMG(takMG(x - 1, y, z),
                              takMG(y - 1, z, x),
                              takMG(z - 1, x, y));
}
takMG = takMG.memoize();