Memoization 說穿了就是「把算過的結果記下來」:同一組參數第二次進來,直接回傳快取值,不再重算。
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 次都是它自己在重算早已算過的值。
用閉包藏一份快取即可:
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 次只是去快取裡把先前存好的結果拿出來。
realazy 在文章裡給過一版通用實作,核心想法是「參數與結果一一對應的雜湊表」。但它有問題:直接把參數拼成字串當鍵,一旦參數裡含物件或陣列就無法保證唯一,像 [221,3] 與 [22,13] 這種組合會撞在一起。
先沿用雜湊表:
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 是引擎實作的類陣列物件,不是真陣列,得先轉一次。另外,原本的簽名還帶了方法名與上下文引用(fib.fib_memo = Memoize('fib_memo', fib)),實際上 currying 之後用 this 就能拿到上層物件,所以可以直接傳函式引用:fib.fib_memo = Memoize(fib.fib_memo)。
看似嚴密了,然而陣列之所以能當物件屬性名,是因為它被轉成字串處理:
var a = [1,2,{yy:'0'}];
var b = [1,2,{xx:'1'}];
var obj = {};
obj[a] = "111";
obj[b] = "222";
for( var i in obj )
alert( i + " = " + obj[i] ); //只會彈出"1,2,[object Object] = 222",obj[a] = "111"被覆蓋了
所以跟字串拼接其實沒有本質差別。
function Memoize(fn){
var cache = {}, args = [];
return function(){
for( var i=0, key = args.length; i < key; i++ ) {
if( equal( args[i], arguments ) )
return cache[i];
}
args[key] = arguments;
cache[key] = fn.apply(this, arguments);
return cache[key];
};
}
不再依賴雜湊鍵,而是把參數與結果分放在兩個清單裡,每次先遍歷參數清單比對,找到對應的索引再去結果清單取值。比較用的 equal:
function equal( first, second ){
if( !first || !second || first.constructor != second.constructor )
return false;
if( first.length && typeof first != "string" )
for(var i=0, l = ( first.length > second.length ) ? first.length : second.length; i<l; i++){
if( !equal( first[i], second[i] ) ) return false;
}
else if( typeof first == 'object' )
for(var n in first){
if( !equal( first[n], second[n] ) ) return false;
}
else
return ( first === second );
return true;
}
千萬不要直接用 == 比較 arguments 與快取陣列,那比的是記憶體參考,不是內容。
代價是速度:遞迴比對本身影響不大,但快取項目一多,每次都遍歷參數清單就很沒效率(求第 80 以上的 Fibonacci 數,在 Firefox 3 與 Safari 3 上約需 40ms)。
Oliver Steel 的〈One-Line JavaScript Memoization〉用極短的行內函式風格解決問題:
function Memoize(o, p) {
var f = o[p], mf, value;
var s = function(v) {return o[p]=v||mf};
((mf = function() {
(s(function(){return value})).reset = mf.reset;
return value = f.apply(this,arguments); //此處修改過,允許接受參數
}).reset = s)();
}
用法:
var fib = {
temp: function(n){
for(var i=0;i<10000;i++)
n=n+2;
return n;
}
}
Memoize(fib,"temp"); //讓fib.temp緩存返回值
fib.temp(16); //執行結果:20006,被緩存
fib.temp(20); //執行結果:20006
fib.temp(10); //執行結果:20006
fib.temp.reset(); //重置緩存
fib.temp(10); //執行結果:20010
參數型別單純且固定,用雜湊表最快;參數可能是物件或陣列,就用平行清單加深度比對,寧可犧牲一點速度換正確性;若函式幾乎不帶參數、或只需要「算一次就好」的語意,Oliver Steel 那版最省事,而且還附帶 reset() 方便重設。