记忆（memoization）在JavaScript中的应用

Posted by & filed under Programming.

函数可以用对象去记住先前操作的结果，从而能避免无谓的运算。这种优化被称之为记忆，英文叫做memoization。关于memoization可以参见维基百科的解释。JavaScript的对象和数组要实现这样的优化是非常方便的，比如说，我们要递归计算著名的fibonacci数列，一个fibonacci数字是之前两个fibonacci数字之和，最前面两个数字是0和1.

var fibonacci = function (n) {
    return n <2 ? :fibonacci(n-1) + fibonacci(n - 2);
};
for(var i = 0; i <= 10; i++) {
    document.writeln('//' + i + ":" + fibonacci(i));
}

这样的算法是可以工作的，但本身做了很多无谓的运算。fibonacci函数被调用了453次。我们调用了11次，而自身调用了442次去计算可能已经计算过的值。如果我们让该函数具备记忆功能就可以显著减少运算量。
我们在一个名为memo的数组中保存我们的存储结果，存储结果可以隐藏在闭包中。当我们的函数被调用时，这个函数首先看是否已经知道存储结果，如果已经知道，就立即返回这个存储结果。

var fibonacci = function () {
    var memo = [0,1];
    var fib = function (n) {
        var result = memo[n];
        if(typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        };
        return result;
    };
     return fib;
}();

这个函数返回同样的结果，但只被调用了29次，我们调用了它11次。他自身调用了18次去取得之前的存储结果。运算效率大约提升了93%，可见记忆这种优化的能力是非常强大的。PHP语言中也可以使用闭包创造类似的记忆优化算法。

Leave a Reply

  • (will not be published)