Deep BlueVBScriptWMIPHPC语言JavaScriptWindows API路由器Windows函数Python

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 次去取得之前储存的结果。


http://ken.gw.to/