Author: YY in Limbo 混沌?？裣?/div>
realazy在blog上給出了一個(gè)
JavaScript Memoization的實(shí)現，Memoization就是函數返回值的緩存，比如一個(gè)函數參數與返回結果一一對應的hash列表，wiki上其實(shí)也有
詳細解釋，我不細說(shuō)了，只討論一下具體實(shí)現的問(wèn)題，realazy文中的代碼有一些問(wèn)題，比如直接用參數拼接成的字符串作為查詢(xún)緩存結果的key，如果參數里包括對象或數組的話(huà)，就很難保證唯一的key，還有1樓評論里提到的：[221,3]和[22,13]這樣的參數也無(wú)法區分。
那么來(lái)改寫(xiě)一下，首先還是用hash表來(lái)存放緩存數據：
- 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];
- };
- }
嗯，區別是直接把數組當作鍵來(lái)用，不過(guò)要注意函數里的arguments是js解釋器實(shí)現的一個(gè)特殊對象，并不是真正的數組，所以要轉換一下……
ps: 原來(lái)的參數包括方法名稱(chēng)和上下文引用：fib.fib_memo = Memoize(’fib_memo’, fib)，但實(shí)際上currying生成的函數里可以用this直接引用上層對象，更復雜的例子可以參考John Resig的makeClass，所以我改成直接傳函數引用：fib.fib_memo = Memoize(fib.fib_memo)
這樣寫(xiě)看上去似乎很靠譜，由參數組成的數組不是唯一的么。但實(shí)際上，數組之所以能作為js對象的屬性名稱(chēng)來(lái)使用，是因為它被當作字符串處理了，也就是說(shuō)如果你給函數傳的參數是這樣：(1,2,3), cache對象就會(huì )是這個(gè)樣子：{ “1,2,3″: somedata }，如果你的參數里有對象，比如：(1,2,{i:”yy”})，實(shí)際的鍵值會(huì )是：”1,2,[object Object]”，所以這跟把數組拼接成字符串的方法其實(shí)沒(méi)有區別……
示例：
- 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"被覆蓋了
直接用參數作為鍵名的方法不靠譜了…………換一種方法試試：
- 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的鍵值對索引，而是把函數的參數和結果分別緩存在兩個(gè)列表里，每次都先遍歷整個(gè)參數列表作比較，找出對應的鍵名/ID號之后再從結果列表里取數據。以下是比較數組的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;
- }
千萬(wàn)不要直接用==來(lái)比較arguments和args里的數組，那樣比較的是內存引用，而不是參數的內容。
這種方法的速度很慢，equal方法其實(shí)影響不大，但是緩存的結果數量多了以后，每次都要遍歷參數列表卻是很沒(méi)效率的（求80以上的fibonacci數列，在firefox3和safari3上都要40ms左右）
如果在實(shí)際應用中參數變動(dòng)不多或者不接受參數的話(huà)，可以參考Oliver Steel的這篇《One-Line JavaScript Memoization》，用很短的函數式風(fēng)格解決問(wèn)題：
- 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ò)，允許接受參數
- }).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
