JavaScriptでメモ化

ネットがつながってないころに書こうと思ったネタ。ちょっと鮮度古めですが。

404 Blog Not Found:再帰再考の小飼氏のメモ化関数をみて、「へぇー」と思う一方で「実装とか適用方法がなんかJavaScriptぽくない」、もとい「Perlぽい」と思ったので、自分でも書いてみました。

Function.prototype.memoize = function() {
  var func = this;
  var cache = {};
  return function() {
    var k = new Array(arguments.length);
    for(var i=0,argc=arguments.length;i<argc;i++) {
      k[i] = arguments[i];
    }
    return (k in cache) ? cache[k] : (cache[k] = func.apply(this,k));
  }
}

使い方はこう。

function fib(n) {
  return (n<3) ? 1 : fib(n-1) + fib(n-2);
}
fib = fib.memoize();

あるいはこう。

var fib = function() { return (n<3) ? 1 : fib(n-1) + fib(n-2); }.memoize();

ちょっとJavaScriptぽさがアップしたでしょう？

まあ、実際にやっていることはほぼ変わらないのですが、Functionのプロトタイプに関数を追加するようにしています。元の小飼氏バージョンにはローカルに定義された関数に適用できない欠点がありましたが、この方法ならそれも可能になります。