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

更新時(shí)間：2011年10月27日 10:12:22 作者：

函數(shù)可以用對(duì)象去記住先前操作的結(jié)果，從而能避免無(wú)謂的運(yùn)算，這種優(yōu)化被稱為記憶（Memoization）。JavaScript 的對(duì)象和數(shù)組要實(shí)現(xiàn)這種優(yōu)化是非常方便的。

比如說(shuō)，我們想要一個(gè)遞歸函數(shù)來(lái)計(jì)算 Fibonacci 數(shù)列。一個(gè) Fibonacci 數(shù)字是之前兩個(gè) Fibonacci 數(shù)字之和。最前面的兩個(gè)數(shù)字是 0 和 1。

復(fù)制代碼代碼如下:

 
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 

這樣是可以工作的，但是它做了很多無(wú)謂的工作。 Fibonacci 函數(shù)被調(diào)用了 453 次。我們調(diào)用了 11 次，而它自身調(diào)用了 442 次去計(jì)算可能已經(jīng)被剛計(jì)算過(guò)的值。如果我們讓該函數(shù)具備記憶功能，就可以顯著地減少它的運(yùn)算量。

我們?cè)谝粋€(gè)名為 memo 的數(shù)組里保存我們的儲(chǔ)存結(jié)果，儲(chǔ)存結(jié)果可以隱藏在閉包中。當(dāng)我們的函數(shù)被調(diào)用時(shí)，這個(gè)函數(shù)首先看是否已經(jīng)知道計(jì)算的結(jié)果，如果已經(jīng)知道，就立即返回這個(gè)儲(chǔ)存結(jié)果。

復(fù)制代碼代碼如下:

 
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; 
}(); 

這個(gè)函數(shù)返回同樣的結(jié)果，但是它只被調(diào)用了 29 次。我們調(diào)用了它 11 次，它自身調(diào)用了 18 次去取得之前儲(chǔ)存的結(jié)果。
以上內(nèi)容來(lái)自:http://demon.tw/programming/javascript-memoization.html

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

復(fù)制代碼代碼如下:

 
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)作鍵來(lái)用，不過(guò)要注意函數(shù)里的arguments是js解釋器實(shí)現(xiàn)的一個(gè)特殊對(duì)象，并不是真正的數(shù)組，所以要轉(zhuǎn)換一下……
ps: 原來(lái)的參數(shù)包括方法名稱和上下文引用：fib.fib_memo = Memoize(‘fib_memo', fib)，但實(shí)際上currying生成的函數(shù)里可以用this直接引用上層對(duì)象，更復(fù)雜的例子可以參考John Resig的makeClass，所以我改成直接傳函數(shù)引用：fib.fib_memo = Memoize(fib.fib_memo)
這樣寫(xiě)看上去似乎很靠譜，由參數(shù)組成的數(shù)組不是唯一的么。但實(shí)際上，數(shù)組之所以能作為js對(duì)象的屬性名稱來(lái)使用，是因?yàn)樗划?dāng)作字符串處理了，也就是說(shuō)如果你給函數(shù)傳的參數(shù)是這樣：(1,2,3), cache對(duì)象就會(huì)是這個(gè)樣子：{ “1,2,3″: somedata }，如果你的參數(shù)里有對(duì)象，比如：(1,2,{i:”yy”})，實(shí)際的鍵值會(huì)是：”1,2,[object Object]“，所以這跟把數(shù)組拼接成字符串的方法其實(shí)沒(méi)有區(qū)別……
示例：

復(fù)制代碼代碼如下:

 
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] ); //只會(huì)彈出"1,2,[object Object] = 222"，obj[a] = "111"被覆蓋了 

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

復(fù)制代碼代碼如下:

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

可以完全避免上述問(wèn)題，沒(méi)有使用hash的鍵值對(duì)索引，而是把函數(shù)的參數(shù)和結(jié)果分別緩存在兩個(gè)列表里，每次都先遍歷整個(gè)參數(shù)列表作比較，找出對(duì)應(yīng)的鍵名/ID號(hào)之后再?gòu)慕Y(jié)果列表里取數(shù)據(jù)。以下是比較數(shù)組的equal方法：

復(fù)制代碼代碼如下:

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

千萬(wàn)不要直接用==來(lái)比較arguments和args里的數(shù)組，那樣比較的是內(nèi)存引用，而不是參數(shù)的內(nèi)容。
這種方法的速度很慢，equal方法其實(shí)影響不大，但是緩存的結(jié)果數(shù)量多了以后，每次都要遍歷參數(shù)列表卻是很沒(méi)效率的（求80以上的fibonacci數(shù)列，在firefox3和safari3上都要40ms左右）
如果在實(shí)際應(yīng)用中參數(shù)變動(dòng)不多或者不接受參數(shù)的話，可以參考Oliver Steel的這篇《One-Line JavaScript Memoization》，用很短的函數(shù)式風(fēng)格解決問(wèn)題：

復(fù)制代碼代碼如下:

 
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); //此處修改過(guò)，允許接受參數(shù) 
}).reset = s)(); 
} 

示例：

復(fù)制代碼代碼如下:

 
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); //執(zhí)行結(jié)果：20006，被緩存 
fib.temp(20); //執(zhí)行結(jié)果：20006 
fib.temp(10); //執(zhí)行結(jié)果：20006 
fib.temp.reset(); //重置緩存 
fib.temp(10); //執(zhí)行結(jié)果：20010 