竹内関数をメモ化とか遅延で高速化してみた

最近、自作の プログラミング言語 を作っていて、ベンチマークを取るためにいくつかの言語で 竹内関数 を書いてみました。
そこで調べている中で、結果をメモ化したり遅延評価したりすることで高速化させることができると知ったのでJavaScriptで書いてみた次第です。

##まずは下ごしらえ

環境は以下の通りです。

• Intel Core i3 1.8GHz
• node.js v0.10.5 64bit

で、次の様なユーティリティーを書いてみました。

tak-util.js

/**
 * ベンチマーク用関数
 * @param {Number} n 実行する回数
 * @param {Function} fun 測定する関数
 * @return {Object} averageに平均が、resultsに各結果が入ったオブジェクト
 **/
function bench(n, fun) {
  var
  i,
  start, finish, average,
  results = [];
  for(i = 1; i <= n; i++) {
    console.log('start : %d', i);
    //process.hrtimeでナノ秒を取得できる
    start = process.hrtime();
    fun();
    //process.hrtimeに引数を渡すとその差を返す
    finish = process.hrtime(start);
    console.log('finish : %d', i);
    //[秒, ナノ秒]という形式の配列なのでナノ秒に変換
    results.push(finish[0] * 1e9 + finish[1]);
  }
  average = results.reduce(function(a,b) {
    return a + b;
  }) / n;
  return {
    results: results,
    average: average,
  };
}

コメントちゃんと書いたので見てください。

##定義通りの場合

コードはこんな感じです。

tak-simple.js

/**
 * 定義通りの竹内関数
 **/
function simpleTak(x, y, z) {
  return x <= y ? y :
    simpleTak(simpleTak(x - 1, y, z),
              simpleTak(y - 1, z, x),
              simpleTak(z - 1, x, y));
}

定義通りすぎて言うことがありませんね…。

実際に実行してみます。

• tak(13,7,0)の場合

benchmark : simple tak(13,7,0) : 10 times
1 : 0.848564657 seconds
2 : 0.84946041 seconds
3 : 0.846620912 seconds
4 : 0.850074494 seconds
5 : 0.849625192 seconds
6 : 0.847950572 seconds
7 : 0.848873124 seconds
8 : 0.845893361 seconds
9 : 0.847051968 seconds
10 : 0.847635833 seconds
average : 0.8481750523 seconds

大体0.8秒ってところでしょうか。素でも速いです。

• tak(15,5,0)の場合

benchmark : simple tak(15,5,0) : 10 times
1 : 27.27188912132 seconds
2 : 27.27261219555 seconds
3 : 27.2710481851 seconds
4 : 27.27377410339 seconds
5 : 27.27219512001 seconds
6 : 27.27109614298 seconds
7 : 27.27095988127 seconds
8 : 27.27129093939 seconds
9 : 27.27283837469 seconds
10 : 27.27099590527 seconds
average : 27.271869996897 seconds

って遅！　270秒…、四分半も待たされるとは…。
竹内関数恐るべしです。
そして、これがどう高速になっていくのか楽しみです。

##メモ化した場合

x,y,zの値をキーにしてオブジェクトに結果をメモ化して、一度計算した値を二度計算しないようにすることで高速化を諮ります。

コードにするとこうなる。

tak-memo.js

/**
 * 結果をメモ化した竹内関数
 */
function memoTak(x, y, z) {
  var
  memo = {},
  tak = function(x, y, z) {
    if([x, y, z] in memo) return memo[[x, y, z]];
    return memo[[x, y, z]] = x <= y ? y :
          tak(tak(x - 1, y, z),
              tak(y - 1, z, x),
              tak(z - 1, x, y));
  }
  return tak(x, y, z);
}

見事にJavaScriptの変態を利用してみました。
念のために書いておくと、JavaScriptのオブジェクトのキーには文字列しか用いることができません。なので cached[[x,y,z]] のような呼び出しは実質的には cached['' + [x,y,z]] のようにキーとなる値を文字列に変換します。
今回はそれを体よく利用しました。

結果のところは…。

• tak(13,7,0)の場合

benchmark : cached tak(13,7,0) : 10 times
1 : 0.004029464 seconds
2 : 0.001785805 seconds
3 : 0.002380503 seconds
4 : 0.001236721 seconds
5 : 0.00123387 seconds
6 : 0.001223036 seconds
7 : 0.001720235 seconds
8 : 0.001174002 seconds
9 : 0.001174571 seconds
10 : 0.001252116 seconds
average : 0.001721032 seconds

0.001秒…。風のように結果が表示されたぜ…。
定義通りと比べて700倍以上は高速になってるわけですか…。

• tak(15,5,0)の場合

benchmark : cached tak(15,5,0) : 10 times
1 : 0.004467934 seconds
2 : 0.00357218 seconds
3 : 0.001740761 seconds
4 : 0.001696287 seconds
5 : 0.002223133 seconds
6 : 0.001609049 seconds
7 : 0.001605058 seconds
8 : 0.001717383 seconds
9 : 0.001610759 seconds
10 : 0.001676901 seconds
average : 0.002191945 seconds

な、なんだって…。
さっきはあれだけ待たされた結果が一瞬で返ってきました。
定義通りと比べて12800倍？？
高速すぎて目が回りそうです。

ちなみに上のコードを少し変えるとわかりますが、竹内関数の解を求めるために必要な引数のパターンの数は、tak(13,7,0)は256通り、tak(15,5,0)の場合は342通りでした。これはこれで興味深いです。

##遅延した場合

評価を遅延してるというより、計算を遅延してる感じになります。Schemeでいうpromise、でしょうか？

コードにするとこうなる。

tak-lazy.js

/**
 * 遅延版竹内関数
 */
function lazyTak(x, y, z) {
  var
  lazy = function(fn) {
    var
    result,
    forced = false;
    //暗黙の型変換を利用するのでvalueOfを持ったオブジェクトを返す。
    return {
      valueOf: function() {
        if(!forced) {
          result = fn();
          forced = true;
        }
        return result;
      },
    };
  },
  tak = function(x, y, z) {
    if(x <= y) return +y;
    return tak(
      tak(x - 1, y, z),
      tak(y - 1, z, x),
      lazy(function(){return tak(z - 1, x, y);}));
  };
  return tak(x, y, z);
}

変数名に forced とかつけられてる辺りからSchemeの影響がうかがえます。

それはそれとして、コードの解説です。
lazy 関数は、関数を引数に取って、その関数の結果が必要となるまで評価しないオブジェクトを返す関数です。（日本語難しいところですし、ECMA-262を読みながら書いてるわけではないので間違ってるか知れません）
それを、遅延版の tak 関数では第三引数に適用しています。
なぜ第三引数のみなのでしょうか？　考えてみればすぐにわかると思います。
竹内関数では、値を返すためには x と y の比較をしなければいけません。つまり、 x と y は結果が必ず必要とされるため遅延する意味がないのです。
対して、第三引数 z の場合は、少なくとも x <= y が正であったときには必要とされないはずです。
なので、第三引数だけ遅延しておけば十分なわけです。

これで本当に速くなるのか？　半信半疑で実行してみます。

• tak(13,7,0)の場合

benchmark : lazy tak(13,7,0) : 10 times
1 : 0.000188729 seconds
2 : 0.000034211 seconds
3 : 0.000025088 seconds
4 : 0.001525802 seconds
5 : 0.000013684 seconds
6 : 0.000014825 seconds
7 : 0.000013684 seconds
8 : 0.000013684 seconds
9 : 0.000012544 seconds
10 : 0.000013115 seconds
average : 0.000185537 seconds

速っ！！
全くもたつきがありませんでした。0.0001秒…、もはや人間の観測できる領域を超越しましたね…。

ちょっと言葉が出てきませんが、次行きます。

• tak(15,5,0)の場合

benchmark : lazy tak(15,5,0) : 10 times
1 : 0.00019044 seconds
2 : 0.00003193 seconds
3 : 0.001436285 seconds
4 : 0.000018246 seconds
5 : 0.000014254 seconds
6 : 0.000013684 seconds
7 : 0.000013684 seconds
8 : 0.000012544 seconds
9 : 0.000013685 seconds
10 : 0.000011973 seconds
average : 0.000175673 seconds

え…。なんでこっちの方が若干速いの…。
衝撃的すぎる。遅延版竹内関数の前ではtak(13,7,0)もtak(15,5,0)も誤差のレベルでしかないわけか…。（何度か測りなおしても、双方の速度はどんぐりの背比べ状態でした）

どうしてこんなに速くなったのか、は少しコードを変更して遅延させたものを計算する必要が何回出てきたかを見れば分かると思います。
で、その結果なんですが、tak(13,7,0)の場合も、tak(15,5,0)も遅延させたものを一度も計算していないことが分かります。
つまり、竹内関数が再帰的に呼び出されたときの第三引数は全く意味がないというわけです。

面白いなー、竹内関数。

最後に、このベンチマークに使ったコードは Gist に置いておきました。
上のGistを持ってきて、コマンドラインで、

$ node tak.js simple 13 7 0

などとするとベンチマークが取れるようにしてあります。暇な人は遊んでみてください。