核心要點
程序經常浪費時間調用反復重新計算相同結果的函數。對於遞歸函數和數學函數尤其如此。斐波那契數生成器就是一個完美的例子。斐波那契數列是一系列整數，從零和一開始，其中每個值都是數列中前兩個數字的和。根據此定義，前十個斐波那契數是：0、1、1、2、3、5、8、13、21、34。從編程的角度來看，第 nth 個斐波那契數通常使用以下函數遞歸計算。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}此函數對於較小的“n”值運行良好。但是，隨著“n”的增加，性能會迅速下降。這是因為兩次遞歸調用重複了相同的工作。例如，要計算第 50 個斐波那契數，必須調用遞歸函數超過 400 億次（確切地說為 40,730,022,147 次）！更糟糕的是，計算第 51 個數字需要將這項工作幾乎完全重複兩次。如果函數記住它之前計算的內容，則可以減輕重複工作的問題。
記憶化基礎
記憶化是一種編程技術，它試圖通過緩存函數先前計算的結果來提高函數的性能。因為 JavaScript 對象的行為類似於關聯數組，所以它們是充當緩存的理想選擇。每次調用記憶化函數時，其參數都用於索引緩存。如果數據存在，則可以返回它，而無需執行整個函數。但是，如果數據未被緩存，則執行函數，並將結果添加到緩存中。
在下面的示例中，原始斐波那契函數被重寫為包含記憶化。在此示例中，自執行匿名函數返回一個內部函數 f()，該函數用作斐波那契函數。當返回 f() 時，它的閉包允許它繼續訪問“memo”對象，該對象存儲其所有先前結果。每次執行 f() 時，它首先檢查是否存在當前“n”值的結果。如果存在，則返回緩存值。否則，執行原始斐波那契代碼。請注意，“memo”是在 f() 之外定義的，以便它可以在多次函數調用中保留其值。回想一下，原始遞歸函數被調用了超過 400 億次才能計算出第 50 個斐波那契數。通過實現記憶化，此數字下降到 99。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}處理多個參數
在前面的示例中，函數接受單個參數。這使得實現緩存相當簡單。不幸的是，大多數函數需要多個參數，這會使緩存的索引變得複雜。要記憶化具有多個參數的函數，緩存必須變成多維的，或者必須組合所有參數以形成單個索引。
在多維方法中，緩存成為對象的層次結構，而不是單個對象。然後，每個維度都由單個參數索引。以下示例為斐波那契函數實現了一個多維緩存。在此示例中，該函數接受一個附加參數“x”，它什麼也不做。每次調用函數時，代碼都會檢查“x”維度是否存在，如果不存在則對其進行初始化。從那時起，“x”維度用於緩存“n”值。結果是函數調用 fibonacci(“foo”, 3) 和 fibonacci(“bar”, 3) 不被視為相同的結果。
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();多維緩存的替代方法是單個緩存對象，該對象由函數所有參數的組合索引。在這種方法下，參數被轉換為數組，然後用於索引緩存。每個函數都有一個名為“arguments”的內置對象，其中包含傳入的參數。 “arguments”是一種稱為類數組對象的類型的對象。它類似於數組，但不能用於索引緩存。因此，它必須首先轉換為實際數組。這可以使用數組 slice() 方法完成。然後可以使用數組表示來索引緩存，如前所示。以下示例顯示瞭如何實現此目的。請注意，附加變量“slice”被定義為對數組 slice() 方法的引用。通過存儲此引用，可以避免反復計算 Array.prototype.slice() 的開銷。然後使用 call() 方法將 slice() 應用於“arguments”。
var fibonacci = (function() {
var memo = {};
function f(x, n) {
var value;
memo[x] = memo[x] || {};
if (x in memo && n in memo[x]) {
value = memo[x][n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[x][n] = value;
}
return value;
}
return f;
})();緩存對象參數
此處介紹的記憶化方案不能很好地處理對象參數。當對像用作索引時，它們首先被轉換為字符串表示形式，例如“[object Object]”。這會導致多個對象錯誤地映射到同一個緩存位置。可以通過在索引之前對對象參數進行字符串化來糾正此行為。不幸的是，這也會減慢記憶化過程。以下示例創建一個通用記憶化函數，該函數將對像作為參數。請注意，對象參數使用 JSON.stringify() 進行字符串化，以便創建緩存的索引。
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}自動記憶化
在所有前面的示例中，函數都被顯式修改以添加記憶化。也可以在根本不修改函數的情況下實現記憶化基礎結構。這很有用，因為它允許函數邏輯與記憶化邏輯分開實現。這是通過創建一個實用程序函數來完成的，該函數將函數作為輸入並對其應用記憶化。以下 memoize() 函數將函數“func”作為輸入。 memoize() 返回一個新函數，該函數在“func”周圍包裝緩存機制。請注意，此函數不處理對象參數。為了處理對象，需要一個循環，該循環將分別檢查每個參數並根據需要進行字符串化。
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();局限性
在實現記憶化時，必須記住以下幾點。首先，通過存儲舊結果，記憶化函數會消耗額外的內存。在斐波那契示例中，額外的內存消耗是無限的。如果內存使用量是一個問題，則應使用固定大小的緩存。與記憶化相關的開銷也可能使它不適用於執行速度很快或執行頻率低的函數。
記憶化最大的限制是它只能自動應用於引用透明函數。如果函數的輸出僅取決於其輸入，並且不會產生任何副作用，則該函數被認為是引用透明的。對引用透明函數的調用可以用其返回值替換，而不會改變程序的語義。斐波那契函數是引用透明的，因為它完全取決於“n”的值。在下面的示例中，函數 foo() 不是引用透明的，因為它使用全局變量“bar”。由於“bar”可以在 foo() 之外修改，因此無法保證返回值對於每個輸入值都保持不變。在此示例中，對 foo() 的兩次調用返回的值為 2 和 3，即使傳遞給兩次調用的參數相同也是如此。
var fibonacci = (function() {
var memo = {};
function f(x, n) {
var value;
memo[x] = memo[x] || {};
if (x in memo && n in memo[x]) {
value = memo[x][n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(x, n - 1) + f(x, n - 2);
memo[x][n] = value;
}
return value;
}
return f;
})();需要記住的事項
關於在 JavaScript 中實現記憶化的常見問題解答 (FAQ)
記憶化是一種在 JavaScript 和其他語言中用於優化計算機程序的編程技術。此技術涉及存儲昂貴的函數調用的結果，並在再次出現相同的輸入時重用它們。這可以通過避免不必要的計算來大大提高程序的性能。在處理遞歸函數或使用相同參數重複調用的函數的情況下，它特別有用。
在 JavaScript 中，記憶化通過創建緩存來存儲函數調用的結果來工作。當調用函數時，該函數首先檢查給定輸入的結果是否已在緩存中。如果是，則函數返回緩存的結果，而不是再次執行計算。如果結果不在緩存中，則函數執行計算，將結果存儲在緩存中，然後返回結果。
當然，讓我們考慮一個計算數字階乘的簡單函數示例。如果沒有記憶化，該函數看起來像這樣：
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}使用記憶化，我們可以通過存儲先前函數調用的結果來優化此函數：
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();雖然記憶化可以顯著提高 JavaScript 程序的性能，但它並非沒有局限性。記憶化的一個主要缺點是它可能會消耗大量內存，尤其是在將大量數據存儲在緩存中時。如果管理不當，這可能會導致性能問題。此外，僅當多次使用相同參數調用函數時，記憶化才有效。如果函數輸入始終不同，則記憶化不會提供任何性能優勢。
記憶化在與純函數一起使用時最有效。純函數是一個始終返回相同輸入的相同結果並且不會產生任何副作用的函數。如果函數依賴於外部狀態或產生副作用，則對其進行記憶化可能會導致意外結果。因此，雖然從技術上講你可以在 JavaScript 中對任何類型的函數使用記憶化，但它最適合純函數。
為具有多個參數的函數實現記憶化可能有點複雜，但這絕對是可能的。一種方法是將參數轉換為可以用作緩存中鍵的字符串。這是一個例子：
function fibonacci(n) {
if (n === 0 || n === 1)
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}是的，有一些庫和工具可以幫助在 JavaScript 中進行記憶化。例如，流行的 JavaScript 實用程序庫 Lodash 提供了一個 _.memoize 函數，可以輕鬆記憶化函數。同樣，Ramda 庫提供了一個 R.memoizeWith 函數，允許你指定自定義緩存鍵函數。
可以通過簡單地重置緩存對象來清除記憶化函數中的緩存。這是一個例子：
var fibonacci = (function() {
var memo = {};
function f(n) {
var value;
if (n in memo) {
value = memo[n];
} else {
if (n === 0 || n === 1)
value = n;
else
value = f(n - 1) + f(n - 2);
memo[n] = value;
}
return value;
}
return f;
})();是的，記憶化在 React 等 JavaScript 框架中非常有用。例如，React 提供了一個 React.memo 函數，可用於記憶化組件。這可以通過防止不必要地重新渲染組件來幫助提高性能。
記憶化是一種強大的優化技術，但它並不總是最佳解決方案。在某些情況下，其他優化技術（例如去抖動和節流）可能更合適。關鍵是要了解程序的特定需求和約束，並選擇合適的優化技術。
以上是在JavaScript中實施備忘錄的詳細內容。更多資訊請關注PHP中文網其他相關文章！
