記憶術(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ù)增加“記憶”功能叉寂。