JavaScript中如何實(shí)現(xiàn)函數(shù)記憶與菲波那切數(shù)列-創(chuàng)新互聯(lián)

這篇文章將為大家詳細(xì)講解有關(guān)JavaScript中如何實(shí)現(xiàn)函數(shù)記憶與菲波那切數(shù)列，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

站在用戶的角度思考問題，與客戶深入溝通，找到安鄉(xiāng)網(wǎng)站設(shè)計(jì)與安鄉(xiāng)網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、申請(qǐng)域名、網(wǎng)頁空間、企業(yè)郵箱。業(yè)務(wù)覆蓋安鄉(xiāng)地區(qū)。

具體如下

定義

函數(shù)記憶是指將上次的計(jì)算結(jié)果緩存起來，當(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ù)。

第一版

我們來寫一版：

// 第一版 (來自《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)
  }
}

我們來測(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ù)記憶也并不是萬能的，你看這個(gè)簡(jiǎn)單的場(chǎng)景，其實(shí)并不適合用函數(shù)記憶。

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

第二版

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

var propValue = function(obj){
  return obj.value
}

var memoizedAdd = memorize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1

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

// 第二版 (來自 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

肯定是有問題的，如果要支持多參數(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)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

如果使用 JSON.stringify，參數(shù)是對(duì)象的問題也可以得到解決，因?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，也就是說 fibonacci 函數(shù)被調(diào)用了 453 次！也許你會(huì)想，我只是循環(huán)到了 10，為什么就被調(diào)用了這么多次，所以我們來具體分析下：

當(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 次吶？咦，那多出來的一次是從哪里來的？

所以我們還需要認(rèn)真看下我們的寫法，在我們的寫法中，其實(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)?fibonacci(0) 的值為 0， !cache[address] 的結(jié)果為 true，又會(huì)執(zhí)行一次 fibonacci 函數(shù)。原來，多出來的那一次是在這里！

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

關(guān)于“JavaScript中如何實(shí)現(xiàn)函數(shù)記憶與菲波那切數(shù)列”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

文章題目：JavaScript中如何實(shí)現(xiàn)函數(shù)記憶與菲波那切數(shù)列-創(chuàng)新互聯(lián)
文章位置：http://muchs.cn/article12/dpjggc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、手機(jī)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、虛擬主機(jī)、網(wǎng)站策劃、域名注冊(cè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)