JavaScript中的高阶内部记忆不起作用

Question

语境.

Memoization是一种在递归函数上运行的函数技术,具有重叠调用,旨在通过使用内部缓存来优化时间性能,该内部缓存会记住先前已使用参数的结果.典型的用例是斐波那契函数.下面显示了该功能的非记忆和记忆版本以及用于计时目的的辅助功能:

function time (fn) {
   return function () {
      var before = Date.now();
      var result = fn.apply(this, arguments);
      var after  = Date.now();
      return {
         value : result,
         time  : after - before
      };
   };
}
var fib = function (n) {
   if (n < 2) return n;
   else return fib(n-1) + fib(n-2);
};
var mfib = function (n) {
   var cache = {};
   var memoizefib = function (n) {
      if (n < 2) return n;
      else {
         var k1 = JSON.stringify(n-1);
         var k2 = JSON.stringify(n-2);
         var v1 = k1 in cache ? cache[k1] : (cache[k1] = memoizefib(n-1));
         var v2 = k2 in cache ? cache[k2] : (cache[k2] = memoizefib(n-2));
         return v1 + v2;   
      }
   };
   return memoizefib (n);
};

如果现在我们测试我们的函数,我们意识到memoization大大减少了执行时间:

(function test (n) {
   var tfib  = time(fib);
   var tmfib = time(mfib);
   console.log(tfib(n));  // -> { value: 433494437, time: 5780 }
   console.log(tmfib(n)); // -> { value: 433494437, time: 1 }    
})(43);

问题.

正如在函数式编程中经常发生的那样,当在更高阶处应用时,memoization成为一种有用的工具,以允许定义memoize可以转换为泛型函数的函数fn.类似于下一个的典型解决方案可以在Web上找到[1] [2] [3]:

function memoize (fn) {
   var cache = {};
   return function () {
      var args  = [].slice.call (arguments); 
      var key   = JSON.stringify(args);
      return key in cache ?
         cache[key] :
         cache[key] = fn.apply(this, args); (1)
   };
}

1. fn.js - http://eliperelman.com/fn.js
2. 下划线 - http://underscorejs.org
3. 关于Memoization的Addy Osmani - http://addyosmani.com/blog/faster-javascript-memoization

题.

然而,令人惊讶的是这些解决方案都不起作用 围绕代码旋转之后.我认为问题出在(1)中,因为递归它不会应用于memoized版本,fn而是fn应用于原语,因此memoization只应用一次.这是我的结果:

(function test (n) {
   var tfib  = time(fib);
   var tmfib = time(memoize(fib));
   console.log (tfib(n));  // -> { value: 433494437, time: 5768 }
   console.log (tmfib(n)); // -> { value: 433494437, time: 5723 } :(   
})(43);

似乎在Javascript中不可能以更高的顺序应用此技术.我对吗？有没有人有任何解决方案或替代代码来获得更高阶的记忆功能？

Answer 1

有趣的问题.为什么不把这个功能记忆到自己身上呢？

function factorial(n) { return n ? n * factorial(n-1) : 1; }

// simple memoization with one argument and console reporting
function memoize(fn) {
    var cache = {};
    return function(x) {
        if (x in cache) { console.log('retrieved value from cache for', x); }
        return x in cache ? cache[x] : cache[x] = fn.apply(this, arguments);
    };
}

// redefine factorial to be its memoized version
factorial = memoize(factorial);

完成此操作后,factorial现在将调用其memoized版本.

> factorial(6)
720
> factorial(7)
retrieved value from cache for 6
5040

将此应用于您的案例(无需mfib):

(function test (n) {
   var tfib  = time(fib);
   console.log(tfib(n));
   fib = memoize(fib);         // <-- memoize on top of itself
   var tmfib = time(fib);
   console.log(tmfib(n));
})(30);

结果:

Object {value: 832040, time: 714} 
Object {value: 832040, time: 22} 

请注意,此解决方案非常适用于单个递归计算中使用的"内部存储器",而不仅仅是对上述因子情况中的函数的其他外部调用.通过使用memoized版本重新定义函数,现在对memoized函数进行内部递归调用.这说明了从714到22的戏剧性时间的改善.