[译文]更快的javascript memoization

memoization虽然并不是什么新鲜事，但确实是一个非常有用的技术手段来缓存函数的计算结果，例如冗长的查找或昂贵的递归计算。

基本的原理是，如果你可以判断在一次运算之前，程序已经完成依赖一组特定的输入值的计算，那么计算结果可以直接返回，而不需重复计算一次。

memoization可以帮助优化的一些问题包括：递归、高速缓存的canvas动画和更一般意义上的重复计算。

实现memoization

memoization这个概念在JavaScript编程语言诞生之前就有了，但我们可以简单地认为它是记忆输入特定值的一个函数的结果。

当我们说“记忆”，意思是利用一种缓存存储的特定输入计算输出的结果。如果一个特定的函数执行后又有相同的输入，记住结果而不重新计算是非常必要的。很多时候，用一个简单的数组缓存，使用hash或map会更好。

在大多数JavaScript实现的memoization中，我发现是这么实现的：在一个内部函数采用签名或散列索引存储的结果。

一个简单易读的memoization实现如下图所示，这是由zepto.js作者Thomas Fuchs所写：

Function.prototype.memoize = function(){
    var self = this, cache = {};
    return function( arg ){
      if(arg in cache) {
        console.log('Cache hit for '+arg);
        return cache[arg];
      } else {
        console.log('Cache miss for '+arg);
        return cache[arg] = self( arg );
      }
    }
  }

function fooBar(a){ ... }
var memoFooBar = fooBar.memoize();
memoFooBar(1); // 计算后返回结果
memoFooBar(1); // 直接返回缓存结果
memoFooBar(2); // 计算后返回结果

大多数开发人员更喜欢让缓存结果在闭包函数外，而Thomas Fuchs直接添加Function原型性属性memoize，缓存结果在闭包内，如上面的cache变量。

Thomas Fuchs的方法被认为是最佳实践，还可以尽可能避免代码冲突。

一个更快的实现？

一些具体改进：参数类型判断，不通过typeof来确定是否对object参数进行JSON序列化，或者使用更可靠Object.prototype.toString.call()。想要知道的更多，请猛戳这里。

除此之外，大部分的代码是自解释的。参数是一个函数，强制转换为一个JavaScript数组，hash作为一个序列化后的key值，fn.memoize是缓存的结果集。

/*
* memoize.js
* by @philogb and @addyosmani
* with further optimizations by @mathias
* and @DmitryBaranovsk
* perf tests: http://bit.ly/q3zpG3
* Released under an MIT license.
*/
function memoize( fn ) {
    return function () {
        var args = Array.prototype.slice.call(arguments),
            hash = "",
            i = args.length;
        currentArg = null;
        while (i--) {
            currentArg = args[i];
            hash += (currentArg === Object(currentArg)) ? 
            JSON.stringify(currentArg) : currentArg;
            fn.memoize || (fn.memoize = {});
        }
        return (hash in fn.memoize) ? fn.memoize[hash] : 
        fn.memoize[hash] = fn.apply(this, args);
    };
}

现在你会发现这个实现是利用自定义函数属性，我之前说如果可能的话，应该避免这么做。但我为什么选择向你展示这个实现而不是遵循最佳实践？

我收集了一些我认为是更健壮的memoization实现，当我使用jsPerf测试他们的时候，上面的代码性能表现的比其他要更好些。

我很惊讶的发现，进行双重检查测试，叫其他人review和测试输出，但就目前的结果看来，这是一个更好的memoization实现。

jsPerf测试结果说明这是一个更快的实现，我自己的离线测试得出结论，至少2倍于其他实现的性能。

现在让我们看下memoization在优化方面的应用。

测试

菲波那契数列

你会发现很多memoization实现例子使用了众所周知的斐波纳契数列来演示如何优化递归问题。
斐波纳契数列看起来有点像这个:1、1、2、3、5、8、13、21、34 …

每个数字出现在它的两个数字的总和。因此你可推算第20个数字是什么。

下面你将看到斐波纳契数列计算基本功能的实现，依赖于递归为了生成正确的结果。

function fib( x ) {
    if(x < 2) return 1; else return fib(x-1) + fib(x-2);
}

/*console profiling test*/
var fibTest = memoize(fib);
//first call
console.time("non-memoized call");
console.log(fibTest(20)); //varies (eg.10946)
console.timeEnd("non-memoized call");

//let's see how much better memoization fares..
console.time("memoized call");
console.log(fibTest(20)); 
//0ms in most cases (if already cached)
console.timeEnd("memoized call");

jsPerf 测试

这次jsPerf测试中，比较了早些时候的五组记忆实现(包括Underscore.js中的记忆实现)。从BrowserScope结果你可以看到的性能差异(对于这个特定的测试)表明我的实现的性能更好，尤其是在Chrome和Firefox。

注1:如果你有兴趣比较实际被访问和命中缓存的性能而不是返回值的，这个测试可以在这里找到。
注2:测试我之前所有实现与直接调用fib(N)的平均查询时间大约有70%的改善。在后面，我们将更仔细地看看这个。


如果我们认为这是(现在)一个更优的记忆实现，一个显而易见的问题是为什么，还有更好的吗？

为什么这么快？

自定义函数实例 VS 独立的变量

就理论而言，让缓存作为函数实例上的属性(而不是在一个单独变量)，属性查找时间会更短。而我猜测函数实例属性和外部独立对象属性的查找时间差异可以忽略不计。当然基于这一理论我们可以看看是否确实存在明显的差别(jsPerf测试)。

奇怪的是，结果却相反。使用一个单独的变量的属性查找更快，Chrome，Firefox和Opera浏览器都表现如此。

回顾一下代码

看另一个版本的实现，没有额外的类型检查。我们可以看到，多数的memoization的实现逻辑在最后的三元表达式返回函数：

function memoize( f ) {
  return function () {
      var args = Array.prototype.slice.call(arguments);
      //we've confirmed this isn't really influencing
      //speed positively
      f.memoize = f.memoize || {};
      //this is the section we're interested in
      return (args in f.memoize)? f.memo[args] :
                     f.memoize[args] = f.apply(this, args);
  };
}

值得你注意的一件事是：在其他的解决方案中实现cache的逻辑都明显的复杂，比如一些不必要的条件检查。

尽我所知，这是这个版本性能更好的原因。

还有更快的吗？

在我看来，检查参数的类型很有必要，序列化也相当重要。但是，如果你觉得过犹不及，一个更简单的解决方案如下：

• 不做类型检查
• 在memoization的实现本身内部显示调用函数，而不是通过参数传递
• 只接受一个参数而不是很多(在某些情况下能很好的运行)

看JSConf版本代码：

function memoize( param ){
    if (!memoize.cache) {
        memoize.cache = {};
    }
    if (!memoize.cache[param]) {
        var result = fib(param); //custom function
        memoize.cache[param] = result;
    }
    return memoize.cache[param];
}

jsPerf测试比较的结果猛戳这里。正如你所看到下面的结果，JSconf的实现在所有浏览器中性能更好。

或许你对直接调用fib(N)的性能也比较感兴趣，可以猛戳这里。直接调用fib(N)(蓝色)，前文的完整实现(Memoize2红色)、JSConf版本(Memoize7橙色)。结果如下图：

你也许对两种变体的memoize.js会感兴趣。
第一类：紧凑的实现(缓存 + memoizer表达式)，函数自定义属性。
第二类：当你不想定义内部属性，利用外部缓存 + memoizer表达式。

在下图在jsPerf图表可以看到，这几个例子的性能水平大致相当。你可以自由选择你感觉最舒服的实现风格，但请记住，这些紧凑版本只是推荐简单的单参数场景。复杂的逻辑，建议看前面给出的完整实现。

// compact memoizer
function memoize1(param) {
   this.memoize = this.memoize || {};
   return (param in this.memoize) ? 
   this.memoize[param] : this.memoize[param] = fib(param);
}

// usage: memoize1(25);


// using an external cache
var memCache = {};
function memoize2(param, cache) {
   cache = cache || {};
   return (param in cache) ? cache[param] : 
   cache[param] = fib(param);
}

// usage: memoize2(25, memCache)


// stoyan's memoizer
function memoize3(param) {
   if (!memoize3.cache) {
       memoize3.cache = {};
   }
   if (!memoize3.cache[param]) {
       var result = fib(param); //custom function
       memoize3.cache[param] = result;
   }
   return memoize3.cache[param];
}

// usage: memoize3(25)