歡迎加入QQ討論群258996829
蘋(píng)果6袋
麥子學(xué)院
Javascript學(xué)習(xí)之函數(shù)記憶詳解
發(fā)布時(shí)間：2017-09-07 19:32 回復(fù):0 查看:2271 最后回復(fù)：2017-09-07 19:32
定義
函數(shù)記憶是指將上次的計(jì)算結(jié)果緩存起來(lái)，當(dāng)下次調(diào)用時(shí)，如果遇到相同的參數(shù)，就直接返回緩存中的數(shù)據(jù)。
舉個(gè)例子：
function
add(a, b) {
return a + b;
}
//
假設(shè)
memorize
可以實(shí)現(xiàn)函數(shù)記憶
var
memoizedAdd =
memorize(add);
memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) //
相同的參數(shù)，第二次調(diào)用時(shí)，從緩存中取出數(shù)據(jù)，而非重新計(jì)算一次
原理
實(shí)現(xiàn)這樣一個(gè) memorize
函數(shù)很簡(jiǎn)單，原理上只用把參數(shù)和對(duì)應(yīng)的結(jié)果數(shù)據(jù)存到一個(gè)對(duì)象中，調(diào)用時(shí)，判斷參數(shù)對(duì)應(yīng)的數(shù)據(jù)是否存在，存在就返回對(duì)應(yīng)的結(jié)果數(shù)據(jù)。
第一版
我們來(lái)寫(xiě)一版：
//
第一版
(
來(lái)自《
JavaScript
權(quán)威指南》
)
function
memoize(f) {
var cache = {};
return
function(){
var key = arguments.length + Array.prototype.join.call(arguments, ",");
if (key
in cache) {
return cache[key]
}
else
return cache[key] = f.apply(
this, arguments)
}
}
我們來(lái)測(cè)試一下：
var add =
function(a, b, c) {
return a + b + c
}
var memoizedAdd = memorize(add)
console.time('use memorize')
for(
var i = 0; i < 100000; i++) {
memoizedAdd(1, 2, 3)
}console.timeEnd('use memorize')
console.time('not use memorize')
for(
var i = 0; i < 100000; i++) {
add(1, 2, 3)
}console.timeEnd('not use memorize')
在 Chrome
中，使用
memorize
大約耗時(shí)
60ms
，如果我們不使用函數(shù)記憶，大約耗時(shí)
1.3 ms
左右。
注意
什么，我們使用了看似高大上的函數(shù)記憶，結(jié)果卻更加耗時(shí)，這個(gè)例子近乎有 60
倍呢！
所以，函數(shù)記憶也并不是萬(wàn)能的，你看這個(gè)簡(jiǎn)單的場(chǎng)景，其實(shí)并不適合用函數(shù)記憶。
需要注意的是，函數(shù)記憶只是一種編程技巧，本質(zhì)上是犧牲算法的空間復(fù)雜度以換取更優(yōu)的時(shí)間復(fù)雜度，在客戶(hù)端 JavaScript
中代碼的執(zhí)行時(shí)間復(fù)雜度往往成為瓶頸，因此在大多數(shù)場(chǎng)景下，這種犧牲空間換取時(shí)間的做法以提升程序執(zhí)行效率的做法是非常可取的。
第二版
因?yàn)榈谝话媸褂昧?/span> join
方法，我們很容易想到當(dāng)參數(shù)是對(duì)象的時(shí)候，就會(huì)自動(dòng)調(diào)用
toString
方法轉(zhuǎn)換成
[Object object]
，再拼接字符串作為 key
值。我們寫(xiě)個(gè)
demo
驗(yàn)證一下這個(gè)問(wèn)題：
var propValue =
function(obj){
return obj.value
}
var memoizedAdd = memorize(propValue)
console.log(memoizedAdd({value: 1})) // 1console.log(memoizedAdd({value: 2})) // 1
兩者都返回了 1
，顯然是有問(wèn)題的，所以我們看看
underscore
的
memoize
函數(shù)是如何實(shí)現(xiàn)的：
//
第二版
(
來(lái)自
underscore
的實(shí)現(xiàn)
)
var memorize =
function(func, hasher) {
var memoize =
function(key) {
var cache = memoize.cache;
var address = '' + (hasher ? hasher.apply(
this, arguments) : key);
if (!cache[address]) {
cache[address] = func.apply(
this, arguments);
}
return cache[address];
};
memoize.cache = {};
return memoize;
};
從這個(gè)實(shí)現(xiàn)可以看出，underscore
默認(rèn)使用
function
的第一個(gè)參數(shù)作為
key
，所以如果直接使用
var add =
function(a, b, c) {
return a + b + c
}
var
memoizedAdd =
memorize(add)
memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6
肯定是有問(wèn)題的，如果要支持多參數(shù)，我們就需要傳入 hasher
函數(shù)，自定義存儲(chǔ)的
key
值。所以我們考慮使用
JSON.stringify
：
var memoizedAdd = memorize(add,
function(){
var args = Array.prototype.slice.call(arguments)
return JSON.stringify(args)
})
console.log(memoizedAdd(1, 2, 3)) // 6console.log(memoizedAdd(1, 2, 4)) // 7
如果使用 JSON.stringify
，參數(shù)是對(duì)象的問(wèn)題也可以得到解決，因?yàn)榇鎯?chǔ)的是對(duì)象序列化后的字符串。
適用場(chǎng)景
我們以斐波那契數(shù)列為例：
var count = 0;
var fibonacci =
function(n){
count++;
return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (
var i = 0; i <= 10; i++){
fibonacci(i)
}
console.log(count) // 453
我們會(huì)發(fā)現(xiàn)最后的 count
數(shù)為
453
，也就是說(shuō)
fibonacci
函數(shù)被調(diào)用了
453
次！也許你會(huì)想，我只是循環(huán)到了
10
，為什么就被調(diào)用了這么多次，所以我們來(lái)具體分析下：
當(dāng)執(zhí)行 fib(0)
時(shí)，調(diào)用
1
次
當(dāng)執(zhí)行 fib(1)
時(shí)，調(diào)用
1
次
當(dāng)執(zhí)行 fib(2)
時(shí)，相當(dāng)于
fib(1) + fib(0)
加上
fib(2)
本身這一次，共
1 + 1 + 1 = 3
次
當(dāng)執(zhí)行 fib(3)
時(shí)，相當(dāng)于
fib(2) + fib(1)
加上
fib(3)
本身這一次，共
3 + 1 + 1 = 5
次
當(dāng)執(zhí)行 fib(4)
時(shí)，相當(dāng)于
fib(3) + fib(2)
加上
fib(4)
本身這一次，共
5 + 3 + 1 = 9
次
當(dāng)執(zhí)行 fib(5)
時(shí)，相當(dāng)于
fib(4) + fib(3)
加上
fib(5)
本身這一次，共
9 + 5 + 1 = 15
次
當(dāng)執(zhí)行 fib(6)
時(shí)，相當(dāng)于
fib(5) + fib(4)
加上
fib(6)
本身這一次，共
15 + 9 + 1 = 25
次
當(dāng)執(zhí)行 fib(7)
時(shí)，相當(dāng)于
fib(6) + fib(5)
加上
fib(7)
本身這一次，共
25 + 15 + 1 = 41
次
當(dāng)執(zhí)行 fib(8)
時(shí)，相當(dāng)于
fib(7) + fib(6)
加上
fib(8)
本身這一次，共
41 + 25 + 1 = 67
次
當(dāng)執(zhí)行 fib(9)
時(shí)，相當(dāng)于
fib(8) + fib(7)
加上
fib(9)
本身這一次，共
67 + 41 + 1 = 109
次
當(dāng)執(zhí)行 fib(10)
時(shí)，相當(dāng)于
fib(9) + fib(8)
加上
fib(10)
本身這一次，共
109 + 67 + 1 = 177
次
所以執(zhí)行的總次數(shù)為：177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453
次！
如果我們使用函數(shù)記憶呢？
var count = 0;
var fibonacci =
function(n) {
count++;
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
fibonacci = memorize(fibonacci)
for (
var i = 0; i <= 10; i++) {
fibonacci(i)
}
console.log(count) // 12
我們會(huì)發(fā)現(xiàn)最后的總次數(shù)為 12
次，因?yàn)槭褂昧撕瘮?shù)記憶，調(diào)用次數(shù)從
453
次降低為了
12
次
!
興奮的同時(shí)不要忘記思考：為什么會(huì)是 12
次呢？
從 0
到
10
的結(jié)果各儲(chǔ)存一遍，應(yīng)該是
11
次吶？咦，那多出來(lái)的一次是從哪里來(lái)的？
所以我們還需要認(rèn)真看下我們的寫(xiě)法，在我們的寫(xiě)法中，其實(shí)我們用生成的 fibonacci
函數(shù)覆蓋了原本了
fibonacci
函數(shù)，當(dāng)我們執(zhí)行
fibonacci(0)
時(shí)，執(zhí)行一次函數(shù)，
cache
為
{0: 0}
，但是當(dāng)我們執(zhí)行
fibonacci(2)
的時(shí)候，執(zhí)行
fibonacci(1) + fibonacci(0)
，因?yàn)?nbsp;
fibonacci(0)
的值為
0
，
!cache[address]
的結(jié)果為 true
，又會(huì)執(zhí)行一次
fibonacci
函數(shù)。原來(lái)，多出來(lái)的那一次是在這里！
多說(shuō)一句
也許你會(huì)覺(jué)得在日常開(kāi)發(fā)中又用不到 fibonacci
，這個(gè)例子感覺(jué)實(shí)用價(jià)值不高吶，其實(shí)，這個(gè)例子是用來(lái)表明一種使用的場(chǎng)景，也就是如果需要大量重復(fù)的計(jì)算，或者大量計(jì)算又依賴(lài)于之前的結(jié)果，便可以考慮使用函數(shù)記憶。而這種場(chǎng)景，當(dāng)你遇到的時(shí)候，你就會(huì)知道的。
來(lái)源：SegmentFault
您還未登錄，請(qǐng)先登錄
熱門(mén)帖子
- iDev 全平臺(tái)開(kāi)發(fā)者大會(huì)門(mén)票免費(fèi)送！限量10張！
- 蘋(píng)果Mac Pro垃圾桶 最低配的ME253CH
- 本人想買(mǎi)個(gè)蘋(píng)果電腦搞開(kāi)發(fā)，哪位大俠指點(diǎn)下
- 求助：failable initializer 'init(name:)' cannot override a non-failable initializer
- 為慶祝Swift發(fā)布1個(gè)月，雨燕社區(qū)正式上線(xiàn)。
- 在UITextFeild里輸入數(shù)據(jù)，這個(gè)數(shù)據(jù)怎么做加減乘除？
- Swift 高仿喜馬拉雅FM
- 要成為自由職業(yè)者？先要學(xué)會(huì)蘋(píng)果的Swift哦
- 用swift實(shí)現(xiàn)的調(diào)用系統(tǒng)相機(jī)，相冊(cè)的DEMO
- 關(guān)于嵌入式引用\()