JavaScript Memoization：讓函數(shù)也有記憶功能

chanvy 2008-11-20

展開全文

Source: http://www./2008/04/27/javascript_memoization/

Author: YY in Limbo 混沌?？裣?/div>

realazy在blog上給出了一個JavaScript Memoization的實現(xiàn)，Memoization就是函數(shù)返回值的緩存，比如一個函數(shù)參數(shù)與返回結(jié)果一一對應(yīng)的hash列表，wiki上其實也有詳細解釋，我不細說了，只討論一下具體實現(xiàn)的問題，realazy文中的代碼有一些問題，比如直接用參數(shù)拼接成的字符串作為查詢緩存結(jié)果的key，如果參數(shù)里包括對象或數(shù)組的話，就很難保證唯一的key，還有1樓評論里提到的：[221,3]和[22,13]這樣的參數(shù)也無法區(qū)分。

那么來改寫一下，首先還是用hash表來存放緩存數(shù)據(jù)：

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];
};
}

嗯，區(qū)別是直接把數(shù)組當(dāng)作鍵來用，不過要注意函數(shù)里的arguments是js解釋器實現(xiàn)的一個特殊對象，并不是真正的數(shù)組，所以要轉(zhuǎn)換一下……

ps: 原來的參數(shù)包括方法名稱和上下文引用：fib.fib_memo = Memoize(’fib_memo’, fib)，但實際上currying生成的函數(shù)里可以用this直接引用上層對象，更復(fù)雜的例子可以參考John Resig的makeClass，所以我改成直接傳函數(shù)引用：fib.fib_memo = Memoize(fib.fib_memo)

這樣寫看上去似乎很靠譜，由參數(shù)組成的數(shù)組不是唯一的么。但實際上，數(shù)組之所以能作為js對象的屬性名稱來使用，是因為它被當(dāng)作字符串處理了，也就是說如果你給函數(shù)傳的參數(shù)是這樣：(1,2,3), cache對象就會是這個樣子：{ “1,2,3″: somedata }，如果你的參數(shù)里有對象，比如：(1,2,{i:”yy”})，實際的鍵值會是：”1,2,[object Object]”，所以這跟把數(shù)組拼接成字符串的方法其實沒有區(qū)別……

示例：

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"被覆蓋了

直接用參數(shù)作為鍵名的方法不靠譜了…………換一種方法試試：

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];
};
}

可以完全避免上述問題，沒有使用hash的鍵值對索引，而是把函數(shù)的參數(shù)和結(jié)果分別緩存在兩個列表里，每次都先遍歷整個參數(shù)列表作比較，找出對應(yīng)的鍵名/ID號之后再從結(jié)果列表里取數(shù)據(jù)。以下是比較數(shù)組的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;
}