JavaScript Memoization 让函数也有记忆功能
2024-05-06 14:23:16
供稿：网友
比如说，我们想要一个递归函数来计算 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://demon.tw/programming/javascript-memoization.html
realazy在blog上给出了一个JavaScript Memoization的实现，Memoization就是函数返回值的缓存，比如一个函数参数与返回结果一一对应的hash列表，wiki上其实也有详细解释，我不细说了，只讨论一下具体实现的问题，realazy文中的代码有一些问题，比如直接用参数拼接成的字符串作为查询缓存结果的key，如果参数里包括对象或数组的话，就很难保证唯一的key，还有1楼评论里提到的：[221,3]和[22,13]这样的参数也无法区分。
那么来改写一下，首先还是用hash表来存放缓存数据：
代码如下:
function Memoize(fn){
var cache = {};
return function(){
var key = [];
for( var i=0, l = arguments.length; i < l; i++ )
key.push(arguments[i]);
if( !(key in cache) )
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}
嗯，区别是直接把数组当作键来用，不过要注意函数里的arguments是js解释器实现的一个特殊对象，并不是真正的数组，所以要转换一下……
ps: 原来的参数包括方法名称和上下文引用：fib.fib_memo = Memoize(‘fib_memo', fib)，但实际上currying生成的函数里可以用this直接引用上层对象，更复杂的例子可以参考John Resig的makeClass，所以我改成直接传函数引用：fib.fib_memo = Memoize(fib.fib_memo)
这样写看上去似乎很靠谱，由参数组成的数组不是唯一的么。但实际上，数组之所以能作为js对象的属性名称来使用，是因为它被当作字符串处理了，也就是说如果你给函数传的参数是这样：(1,2,3), cache对象就会是这个样子：{ “1,2,3″: somedata }，如果你的参数里有对象，比如：(1,2,{i:”yy”})，实际的键值会是：”1,2,[object Object]“，所以这跟把数组拼接成字符串的方法其实没有区别……
