首頁 >web前端 >js教程 >JavaScript學習筆記之函數記憶

JavaScript學習筆記之函數記憶

韦小宝原創: 2018-01-25 11:03:041597瀏覽

這篇文章主要介紹了JavaScript學習筆記之函數記憶，小編覺得挺不錯的，現在分享JavaScript源碼給大家，也給大家做個參考。對JavaScript有興趣的一起跟隨小編過來看看吧

本文講解函數記憶與菲波那切數列的實現，分享給大家，具體如下

##定義

函數記憶是指將上次的計算結果快取起來，當下次呼叫時，如果遇到相同的參數，就直接傳回快取中的資料。

舉例：

function add(a, b) {
  return a + b;
}

// 假设 memorize 可以实现函数记忆
var memoizedAdd = memorize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数，第二次调用时，从缓存中取出数据，而非重新计算一次

原理

#實作這樣一個memorize 函數很簡單，原理上只用把參數和對應的結果資料存到一個物件中，當呼叫時，判斷參數對應的資料是否存在，存在就傳回對應的結果資料。

第一版

我們來寫一版：

// 第一版 (来自《JavaScript权威指南》)
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)
  }
}

我們來測試一下：

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

console.time(&#39;use memorize&#39;)
for(var i = 0; i < 100000; i++) {
  memoizedAdd(1, 2, 3)
}
console.timeEnd(&#39;use memorize&#39;)

console.time(&#39;not use memorize&#39;)
for(var i = 0; i < 100000; i++) {
  add(1, 2, 3)
}
console.timeEnd(&#39;not use memorize&#39;)

在Chrome 中，使用memorize 大約耗時60ms，如果我們不

使用函數記憶，大約耗時1.3 ms 左右。

注意

什麼，我們使用了看似高大上的函數記憶，結果卻更加耗時，這個例子幾乎有 60 倍呢！

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

要注意的是，函數記憶只是一種

程式技巧，本質上是犧牲演算法的空間複雜度以換取更優的時間複雜度，在客戶端JavaScript 中程式碼的執行時間複雜度往往成為瓶頸，因此在大多數場景下，這種犧牲空間換取時間的做法以提升程序執行效率的做法是非常可取的。

第二版

因為第一版使用了join 方法，我們很容易想到當參數是物件的時候，就會自動呼叫toString 方法轉換成[Object object]，再拼接

字串作為key 值。我們寫個demo 驗證一下這個問題：

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 函數是如何實現的：

// 第二版 (来自 underscore 的实现)
var memorize = function(func, hasher) {
  var memoize = function(key) {
    var cache = memoize.cache;
    var address = &#39;&#39; + (hasher ? hasher.apply(this, arguments) : key);
    if (!cache[address]) {
      cache[address] = func.apply(this, arguments);
    }
    return cache[address];
  };
  memoize.cache = {};
  return memoize;
};

從這個實作可以看出，underscore 預設使用function 的第一個參數作為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

肯定是有問題的，如果要支援多參數，我們就需要傳入hasher 函數，自定義儲存的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，參數是物件的問題也可以解決，因為儲存的是

物件序列化後的字串。

適用場景

我們以斐波那契數列範例：

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

我們會發現最後的count 數為453，也就是說fibonacci 函數被呼叫了453 次！也許你會想，我只是循環到了10，為什麼就被呼叫了這麼多次，所以我們來具體分析下：

當執行fib(0) 時，調用1 次

當執行fib(1) 時，呼叫1 次

當執行fib(2) 時，相當於fib(1) + fib(0) 加上fib(2) 本身這一次，共1 + 1 + 1 = 3 次

當執行fib(3) 時，相當於fib(2) + fib(1) 加上fib(3) 本身這一次，共3 + 1 + 1 = 5 次

當執行fib(4) 時，相當於fib(3) + fib(2) 加上fib(4) 本身這一次，共5 + 3 + 1 = 9 次

當執行fib(5) 時，相當於fib(4) + fib(3) 加上fib(5) 本身這一次，共9 + 5 + 1 = 15 次

當執行fib(6) 時，相當於fib(5) + fib(4) 加上fib(6) 本身這次，共15 + 9 + 1 = 25 次

當執行fib(7) 時，相當於fib(6 ) + fib(5) 加上fib(7) 本身這次，共25 + 15 + 1 = 41 次

當執行fib(8) 時，相當於fib(7) + fib(6)加上fib(8) 本身這次，共41 + 25 + 1 = 67 次

當執行fib(9) 時，相當於fib(8) + fib(7) 加上fib(9)本身這次，共67 + 41 + 1 = 109 次

當執行fib(10) 時，相當於fib(9) + fib(8) 加上fib(10) 本身這一次，共109 + 67 + 1 = 177 次

所以執行的總次數為：177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次！

如果我們使用函數記憶呢？

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

我們會發現最後的總次數為12 次，因為使用了函數記憶，呼叫次數從453 次降低為了12 次!

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

從 0 到 10 的結果各儲存一遍，應該是 11 次吶？咦，那多出來的一次是從哪裡來的？

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

也許你會覺得在日常開發中又用不到fibonacci，這個例子感覺實用價值不高吶，其實，這個例子是用來表明一種使用的場景，也就是如果需要大量重複的計算，或大量計算又依賴先前的結果，便可以考慮使用函數記憶。而這種場景，當你遇到的時候，你就會知道的。

JavaScript學習筆記之函數記憶

相關文章