JavaScriptでメモ化関数（つづき）

前回5/6に紹介したメモ化関数についてちょっと補足。

メモ化した関数を別の名前にしてしまうと、下記のような再帰的な関数fibはそれ自体は高速化されない。２回目以降に同じ引数をもつときだけ高速化されるに過ぎない。

function fib(n) {
  return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}
var fib2 = memoize(fib, null);
var v = fib2(100);
// ほぼ永久に計算が終わらない。

再帰の途中結果もメモ化すれば高速化されるので、メモ化関数を別名にせず、単純に同じ名前にすればよい。

var fib_org = fib;
fib = memoize(fib_org, null);
var v = fib(100);
// v=354224848179262000000 が一瞬で計算される。

ここで、memoize()関数は以下のもの：

// memoize: a general-purpose function to enable a function to use memoization
//   func: the function to be memoized
//   context: the context for the memoized function to execute within
//   Note: the function must use explicit, primitive parameters (or objects
//     that generate unique strings in a toString() method)
function memoize (func, context) {
  function memoizeArg (argPos) {
    var cache = {};
    return function () {
      if (argPos == 0) {
        if (!(arguments[argPos] in cache)) {
          cache[arguments[argPos]] = func.apply(context, arguments);
        }
        return cache[arguments[argPos]];
      }
      else {
        if (!(arguments[argPos] in cache)) {
          cache[arguments[argPos]] = memoizeArg(argPos - 1);
        }
        return cache[arguments[argPos]].apply(this, arguments);
      }
    }
  }
  // JScript doesn't grok the arity property, but uses length instead
  var arity = func.arity || func.length;
  return memoizeArg(arity - 1);
}