記憶術(shù)一詞是我在《高階Perl》一書(shū)中看到的累颂，書(shū)中介紹了如何利用Perl語(yǔ)言的閉包特性給子程序添加記憶功能，從而減少計(jì)算量凛俱；是一種用空間換時(shí)間的優(yōu)化方法紊馏。
Fibonacci 函數(shù)
斐波納契（Fibonacci ）數(shù)列以如下被以遞歸的方法定義：F(1)=1，F(xiàn)(2)=2, F(n)=F(n-1)+F(n-2)（n>2蒲犬，n∈N*）朱监；而Fibonacci 函數(shù)就是以數(shù)列下標(biāo)為參返回?cái)?shù)列值的函數(shù)。
在javascript中定義的Fibonacci 函數(shù)如下：
function Fibonacci(i){
if(i>2) return Fibonacci(i-1) + Fibonacci(i-2);
return i;
}
上面這個(gè)函數(shù)原叮，你如果敢在瀏覽器的開(kāi)發(fā)者工具的控制臺(tái)中運(yùn)動(dòng)Fibonacci(100)赫编，瀏覽器就敢卡死。因?yàn)檫@個(gè)運(yùn)算的數(shù)量級(jí)太大了奋隶。下面以Fibonacci(10)為例看一下計(jì)算量：
Fibonacci(10) = Fibonacci(9)+Fibonacci(8);
Fibonacci(9)=Fibonacci(8)+Fibonacci(7);
Fibonacci(8)=Fibonacci(7)+Fibonacci(6);
……
這樣一直運(yùn)算下去擂送，你會(huì)發(fā)現(xiàn)很多Fibonacci數(shù)被重得計(jì)算了多次。效率被這些重復(fù)的計(jì)算拖了后腿唯欣。
加了緩存后的Fibonacci 函數(shù)
var fibCache = [0,1,2];
function Fibonacci(i){
if(fibCache[i]) return fibCache[i];
return (fibCache[i] = Fibonacci(i-1) + Fibonacci(i-2));
}
通過(guò)上面的代碼優(yōu)化后团甲，你再運(yùn)行Fibonacci(100),結(jié)果瞬間就顯示在控制臺(tái)上了。
更優(yōu)的緩存方案
上面的優(yōu)化后的Fibonacci函數(shù)已經(jīng)達(dá)到了優(yōu)化的目的黍聂。但是這種編輯方式有幾個(gè)缺點(diǎn)：
- 暴露在全局作用域的 fibCache躺苦，可能會(huì)被其他代碼污染
- 如果有大量需要加“記憶術(shù)”的函數(shù)，需要針對(duì)不同的函數(shù)增加“記憶術(shù)”代碼产还。
- 緩存功能代碼與函數(shù)的功能邏輯代碼混雜在一起匹厘。
我們不如寫(xiě)一個(gè)能給普通函數(shù)添加“記憶術(shù)”的函數(shù)：
function fnCache(fn){
var cache = {};
return function(str){
return cache[str] || (cache[str] = fn(str));
}
}
之后就可以很輕松的改造各個(gè)需要添加“記憶術(shù)”的函數(shù)了。還以Fibonacci函數(shù)為例脐区，我們需要在定義Fibonacci函數(shù)的下放加入一些代碼愈诚，如下：
function Fibonacci(i){
if(i>2) return Fibonacci(i-1) + Fibonacci(i-2);
return i;
}
Fibonacci = fnCache(Fibonacci);
或者按如下方式改造Fibonacci函數(shù)：
var Fibonacci = fnCache(function (i){
if(i>2) return Fibonacci(i-1) + Fibonacci(i-2);
return i;
});
如此，在其他地方調(diào)用該函數(shù)的代碼不用做任何的修改牛隅，并且函數(shù)也已經(jīng)被加了“記憶”功能炕柔。
對(duì)“記憶術(shù)”的進(jìn)一步改造
上面的增加“記憶”功能的函數(shù)有一個(gè)明顯的缺點(diǎn)，就是只能支持一個(gè)參數(shù)媒佣。下面對(duì)其進(jìn)行改造匕累，使之支持多個(gè)參數(shù)的情況；
function fnCache(fn){
var cache = {};
return function(){
var str = Array.prototype.join.call(arguments,",");
return cache[str] || (cache[str] = fn.apply(null,arguments));
}
}
arguments 中存儲(chǔ)的調(diào)用當(dāng)前函數(shù)時(shí)所參數(shù)的實(shí)參列表默伍，無(wú)法你的函數(shù)原型中是否有對(duì)應(yīng)接收實(shí)參的形參欢嘿。它是一個(gè)類(lèi)數(shù)組的對(duì)象衰琐，但不是數(shù)組×侗模可以使用 Array.prototype.join.call(arguments,","); 這樣羡宙，把它當(dāng)作一個(gè)數(shù)組一樣完成鏈接功能。關(guān)于apply的介紹可以參考你不知道的JavaScript基礎(chǔ)：call And apply掐隐。
并非所有函數(shù)都適合加緩存
是的狗热，并非所有函數(shù)都適合加緩存，下面就列舉幾種不適合加緩存的函數(shù)：
- 參數(shù)中有非基本數(shù)據(jù)類(lèi)型（String,Number,Boolean,null,undefined）時(shí);由于fnCache函數(shù)在使用Object的鍵名做緩存的索引虑省，所以所有的參數(shù)都要被轉(zhuǎn)換成字符串斗搞。想像一下兩個(gè)包括不同屬性的對(duì)象轉(zhuǎn)換成字符串后都是"[object Object]"，如此后一個(gè)對(duì)象會(huì)使用前面已經(jīng)執(zhí)行過(guò)計(jì)算的對(duì)象得到的緩存結(jié)果慷妙。這顯示不是你想要的。
- 當(dāng)執(zhí)行函數(shù)不僅僅是為了得到返回值時(shí)允悦；比如打印日志的函數(shù)膝擂。
- 當(dāng)需要對(duì)返回的結(jié)果對(duì)象進(jìn)行操作時(shí)；當(dāng)?shù)谝淮畏椿匾粋€(gè)對(duì)象時(shí)隙弛，同時(shí)做了緩存后架馋，你對(duì)返回的對(duì)象進(jìn)行的操作同樣會(huì)在下一次返回緩存對(duì)象中有所體現(xiàn)。除非你明確這就是你想要全闷，否則不要對(duì)這樣的函數(shù)增加“記憶”功能叉寂。
