JavaScript 记忆（Memoization）

函数可以用对象去记住先前操作的结果，从而能避免无谓的运算，这种优化被称为记忆（Memoization）。JavaScript 的对象和数组要实现这种优化是非常方便的。

比如说，我们想要一个递归函数来计算 Fibonacci 数列。一个 Fibonacci 数字是之前两个 Fibonacci 数字之和。最前面的两个数字是 0 和 1。

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

for (var i = 0; i <= 10; i += 1) {
    document.writeln('// ' + i + ': ' + fibonacci(i));
}

// 0: 0
// 1: 1
// 2: 1
// 3: 2
// 4: 3
// 5: 5
// 6: 8
// 7: 13
// 8: 21
// 9: 34
// 10: 55

这样是可以工作的，但是它做了很多无谓的工作。 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 次去取得之前储存的结果。

随机文章:

1. EditPlus注册机及其算法
2. 利用53端口的OpenVPN免费上网
3. VBS的一个BUG
4. Python，又见Python
5. VBS任意进制转换（实现PHP的base_convert函数）

这篇文章发布于 2011年06月8日，星期三，14:43，归类于 程序设计。 您可以跟踪这篇文章的评论通过 RSS 2.0 feed。 您可以留下评论，或者从您的站点trackback。