JavaScript學(xué)習(xí)筆記之函數(shù)記憶

本文講解函數(shù)記憶與菲波那切數(shù)列的實(shí)現(xiàn)，分享給大家，具體如下

定義

函數(shù)記憶是指將上次的計(jì)算結(jié)果緩存起來，當(dāng)下次調(diào)用時，如果遇到相同的參數(shù)，就直接返回緩存中的數(shù)據(jù)。

舉個例子：

原理

實(shí)現(xiàn)這樣一個 memorize 函數(shù)很簡單，原理上只用把參數(shù)和對應(yīng)的結(jié)果數(shù)據(jù)存到一個對象中，調(diào)用時，判斷參數(shù)對應(yīng)的數(shù)據(jù)是否存在，存在就返回對應(yīng)的結(jié)果數(shù)據(jù)。

第一版

我們來寫一版：

我們來測試一下：

在 Chrome 中，使用 memorize 大約耗時 60ms，如果我們不使用函數(shù)記憶，大約耗時 1.3 ms 左右。

注意

什么，我們使用了看似高大上的函數(shù)記憶，結(jié)果卻更加耗時，這個例子近乎有 60 倍呢！

所以，函數(shù)記憶也并不是萬能的，你看這個簡單的場景，其實(shí)并不適合用函數(shù)記憶。

需要注意的是，函數(shù)記憶只是一種編程技巧，本質(zhì)上是犧牲算法的空間復(fù)雜度以換取更優(yōu)的時間復(fù)雜度，在客戶端 JavaScript 中代碼的執(zhí)行時間復(fù)雜度往往成為瓶頸，因此在大多數(shù)場景下，這種犧牲空間換取時間的做法以提升程序執(zhí)行效率的做法是非常可取的。

第二版

因?yàn)榈谝话媸褂昧?join 方法，我們很容易想到當(dāng)參數(shù)是對象的時候，就會自動調(diào)用 toString 方法轉(zhuǎn)換成 [Object object]，再拼接字符串作為 key 值。我們寫個 demo 驗(yàn)證一下這個問題：

兩者都返回了 1，顯然是有問題的，所以我們看看 underscore 的 memoize 函數(shù)是如何實(shí)現(xiàn)的：

從這個實(shí)現(xiàn)可以看出，underscore 默認(rèn)使用 function 的第一個參數(shù)作為 key，所以如果直接使用

肯定是有問題的，如果要支持多參數(shù)，我們就需要傳入 hasher 函數(shù)，自定義存儲的 key 值。所以我們考慮使用 JSON.stringify：

如果使用 JSON.stringify，參數(shù)是對象的問題也可以得到解決，因?yàn)榇鎯Φ氖菍ο笮蛄谢蟮淖址?/p>

適用場景

我們以斐波那契數(shù)列為例：

我們會發(fā)現(xiàn)最后的 count 數(shù)為 453，也就是說 fibonacci 函數(shù)被調(diào)用了 453 次！也許你會想，我只是循環(huán)到了 10，為什么就被調(diào)用了這么多次，所以我們來具體分析下：

當(dāng)執(zhí)行 fib(0) 時，調(diào)用 1 次

當(dāng)執(zhí)行 fib(1) 時，調(diào)用 1 次

當(dāng)執(zhí)行 fib(2) 時，相當(dāng)于 fib(1) + fib(0) 加上 fib(2) 本身這一次，共 1 + 1 + 1 = 3 次

當(dāng)執(zhí)行 fib(3) 時，相當(dāng)于 fib(2) + fib(1) 加上 fib(3) 本身這一次，共 3 + 1 + 1 = 5 次

當(dāng)執(zhí)行 fib(4) 時，相當(dāng)于 fib(3) + fib(2) 加上 fib(4) 本身這一次，共 5 + 3 + 1 = 9 次

當(dāng)執(zhí)行 fib(5) 時，相當(dāng)于 fib(4) + fib(3) 加上 fib(5) 本身這一次，共 9 + 5 + 1 = 15 次

當(dāng)執(zhí)行 fib(6) 時，相當(dāng)于 fib(5) + fib(4) 加上 fib(6) 本身這一次，共 15 + 9 + 1 = 25 次

當(dāng)執(zhí)行 fib(7) 時，相當(dāng)于 fib(6) + fib(5) 加上 fib(7) 本身這一次，共 25 + 15 + 1 = 41 次

當(dāng)執(zhí)行 fib(8) 時，相當(dāng)于 fib(7) + fib(6) 加上 fib(8) 本身這一次，共 41 + 25 + 1 = 67 次

當(dāng)執(zhí)行 fib(9) 時，相當(dāng)于 fib(8) + fib(7) 加上 fib(9) 本身這一次，共 67 + 41 + 1 = 109 次

當(dāng)執(zhí)行 fib(10) 時，相當(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ù)記憶呢？

我們會發(fā)現(xiàn)最后的總次數(shù)為 12 次，因?yàn)槭褂昧撕瘮?shù)記憶，調(diào)用次數(shù)從 453 次降低為了 12 次!

興奮的同時不要忘記思考：為什么會是 12 次呢？

從 0 到 10 的結(jié)果各儲存一遍，應(yīng)該是 11 次吶？咦，那多出來的一次是從哪里來的？

所以我們還需要認(rèn)真看下我們的寫法，在我們的寫法中，其實(shí)我們用生成的 fibonacci 函數(shù)覆蓋了原本了 fibonacci 函數(shù)，當(dāng)我們執(zhí)行 fibonacci(0) 時，執(zhí)行一次函數(shù)，cache 為 {0: 0}，但是當(dāng)我們執(zhí)行 fibonacci(2) 的時候，執(zhí)行 fibonacci(1) + fibonacci(0)，因?yàn)?fibonacci(0) 的值為 0， !cache[address] 的結(jié)果為 true，又會執(zhí)行一次 fibonacci 函數(shù)。原來，多出來的那一次是在這里！

也許你會覺得在日常開發(fā)中又用不到 fibonacci，這個例子感覺實(shí)用價(jià)值不高吶，其實(shí)，這個例子是用來表明一種使用的場景，也就是如果需要大量重復(fù)的計(jì)算，或者大量計(jì)算又依賴于之前的結(jié)果，便可以考慮使用函數(shù)記憶。而這種場景，當(dāng)你遇到的時候，你就會知道的。

相關(guān)推薦：

JavaScript函數(shù)綁定用法解析

javascript函數(shù)的節(jié)流throttle與防抖debounce詳解

實(shí)例講解JavaScript函數(shù)綁定用法

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com