【力扣】2623. 記憶函數——函數轉換

一、題目

請你編寫一個函數 fn，它接收另一個函數作為輸入，并返回該函數的 記憶化 后的結果。

記憶函數 是一個對于相同的輸入永遠不會被調用兩次的函數。相反，它將返回一個緩存值。

你可以假設有 3 個可能的輸入函數：sum 、fib 和 factorial 。

• sum 接收兩個整型參數 a 和 b ，并返回 a + b 。假設如果參數 (b, a) 已經緩存了值，其中 a != b，它不能用于參數 (a, b)。例如，如果參數是 (3, 2) 和 (2, 3)，則應進行兩個單獨的調用。
• fib 接收一個整型參數 n ，如果 n <= 1 則返回 1，否則返回 fib (n - 1) + fib (n - 2)。
• factorial 接收一個整型參數 n ，如果 n <= 1 則返回 1 ，否則返回 factorial(n - 1) * n 。

示例 1：

輸入：
fnName = "sum"
actions = ["call","call","getCallCount","call","getCallCount"]
values = [[2,2],[2,2],[],[1,2],[]]
輸出：[4,4,1,3,2]
解釋：
const sum = (a, b) => a + b;
const memoizedSum = memoize(sum);
memoizedSum (2, 2);// "call" - 返回 4。sum() 被調用，因為之前沒有使用參數 (2, 2) 調用過。
memoizedSum (2, 2);// "call" - 返回 4。沒有調用 sum()，因為前面有相同的輸入。
// "getCallCount" - 總調用數： 1
memoizedSum(1, 2);// "call" - 返回 3。sum() 被調用，因為之前沒有使用參數 (1, 2) 調用過。
// "getCallCount" - 總調用數： 2

示例 2：

輸入：
fnName = "factorial"
actions = ["call","call","call","getCallCount","call","getCallCount"]
values = [[2],[3],[2],[],[3],[]]
輸出：[2,6,2,2,6,2]
解釋：
const factorial = (n) => (n <= 1) ? 1 : (n * factorial(n - 1));
const memoFactorial = memoize(factorial);
memoFactorial(2); // "call" - 返回 2。
memoFactorial(3); // "call" - 返回 6。
memoFactorial(2); // "call" - 返回 2。 沒有調用 factorial()，因為前面有相同的輸入。
// "getCallCount" -  總調用數：2
memoFactorial(3); // "call" - 返回 6。 沒有調用 factorial()，因為前面有相同的輸入。
// "getCallCount" -  總調用數：2

示例 3：

輸入：
fnName = "fib"
actions = ["call","getCallCount"]
values = [[5],[]]
輸出：[8,1]
解釋：
fib(5) = 8 // "call"
// "getCallCount" - 總調用數：1

提示：

• 0 <= a, b <= 105
• 1 <= n <= 10
• 1 <= actions.length <= 105
• actions.length === values.length
• actions[i] 為 “call” 和 “getCallCount” 中的一個
• fnName 為 “sum”, “factorial” 和 “fib” 中的一個

二、解決方案

1、概述

此問題要求你編寫一個修改所提供函數的函數，使所提供的函數只有在沒有傳遞參數的情況下才會被調用。如果之前已傳遞過這些參數，它應返回之前的輸出而且無需調用所提供的函數。這種類型的優化稱為 記憶化，是 高階函數 的一個極其重要的示例。

為了具體說明記憶化，以下是沒有記憶化的一些代碼示例。

let callCount = 0;
const add = (a, b) => {callCount += 1;return a + b;
}add(2, 2); // 4
console.log(callCount); // 1
add(2, 2); // 4
console.log(callCount); // 2
add(2, 2); // 4
console.log(callCount); // 3

不出所料，每次調用add時都會增加 callCount。

然而，如果我們應用 記憶化：

let callCount = 0;
const add = (a, b) => {callCount += 1;return a + b;
};
const memoizedAdd = memoize(add);memoizedAdd(2, 2); // 4
console.log(callCount); // 1
memoizedAdd(2, 2); // 4
console.log(callCount); // 1
memoizedAdd(2, 2); // 4
console.log(callCount); // 1

就可以看到callCount僅在第一次調用memoizedAdd時增加。每次后續傳遞 (2, 2) 時，記憶化邏輯會檢測到這些參數以前已傳遞，并立即返回緩存的值 4，而不調用 add。

避免添加兩個數字顯然算不上什么巨大的優化，但可以想象如果是對一個復雜的多的函數進行記憶化，會給性能帶來多大的提升。

1.1純函數

值得注意的是，記憶化 僅對 純函數 有效。純函數的定義為：給定相同的輸入，始終返回相同的輸出，并且沒有任何副作用的函數。

例如，假設你嘗試記憶化不純的函數 Date.now，它返回自Unix時間戳以來的當前時間（以毫秒為單位）。

const getCurrentTimeMemoized = memoize(Date.now);getCurrentTimeMemoized(); // 1683784131157
getCurrentTimeMemoized(); // 1683784131157
getCurrentTimeMemoized(); // 1683784131157

getCurrentTimeMemoized 第一次調用時會正確返回當前時間。但每次后續調用時，它都會錯誤地返回和第一次相同的值。

類似的，假設你有一個具有副作用的函數，如將數據上傳到數據庫。

function uploadRow(row) {// 上傳邏輯
}const memoizedUpload = memoize(uploadRows);
memoizedUpload('Some Data'); // 成功上傳
memoizedUpload('Some Data'); // 什么都不會發生

第一次調用memoizedUpload時，數據將正確上傳到數據庫，但每次后續調用都不會再得到新的結果。

事實上，你只能在純函數上應用此優化，這也是盡可能使函數純粹的一個很好的理由。

2、在Web開發中的記憶化用途

記憶化有無數的用途，在這里我們討論其中一些典型案例。

2.1緩存網站文件

大型網站通常由許多 JavaScript 文件組成，在用戶訪問不同頁面時會動態下載這些文件。有時會采用一種模式，其中文件名基于文件內容的哈希值。這樣，當 Web 瀏覽器請求已經在之前請求過的文件名時，它可以從磁盤上本地加載文件，而不必重新下載它。

（1）React 組件

React 是一個非常流行的用于構建用戶界面的庫，尤其適用于單頁面應用程序。其核心原則之一是將應用程序分解為單獨的 組件。每個組件負責渲染應用程序HTML的不同部分。

例如，你可能有一個組件如下：

const TitleComponent = (props) => {return <h1>{props.title}</h1>;
};

上面的函數將在每次父組件渲染時調用，即使title沒有更改。通過在其上調用 React.memo，可以提高性能，避免不必要的渲染。

const TitleComponent = React.memo((props) => {return <h1>{props.title}</h1>;
});

現在，TitleComponent 只有在title發生變化時才會重新渲染，從而提高了應用程序的性能。

（2）緩存 API 調用

假設你有一個函數，用于向API發送網絡請求以訪問數據庫中的鍵值對。

async function getValue(key) {// 數據庫請求邏輯
}
const getValueMemoized = memoize(getValue);

現在，getValueMemoized 將僅為每個鍵進行一次網絡請求，可能大大提高性能。需要注意的是，由于getValue是異步的，它將返回一個 Promise 而不是實際值。對于這種用例，這實際上是最理想的，因為即使在第一次請求返回值之前調用兩次，它仍然只會進行一次網絡請求。

記憶化網絡請求的一個潛在缺點是數據陳舊的風險。如果數據庫中與特定鍵關聯的值發生更改，記憶化函數可能仍然返回舊的緩存結果，使用戶無法看到更新。

處理這種情況的幾種方法：

1. 始終向API發送請求，詢問值是否已更改。
2. 使用WebSocket訂閱數據庫中值的更改。
3. 為值提供 過期時間，以使用戶至少不會看到太過時的數據。

你可以在 此處 了解有關 HTTP 緩存的更多信息。

3、算法中的記憶化

記憶化的一個經典應用是在 動態規劃 中，將問題分解為若干子問題。這些子問題可以表示為函數調用，其中許多函數調用多次且使用相同的輸入，因此可以進行優化。

動態規劃極大提高效率的一個經典示例是計算斐波那契數。

function fib(n) {if (n <= 1) return n;return fib(n - 1) + fib(n - 2);
}
fib(100); // 耗時多年

上面的代碼非常低效，時間復雜度為 O(1.6 n )（1.6是黃金比率）。

但是，通過不再使用相同的輸入兩次調用 fib，我們可以在 O(n) 的時間內計算斐波那契數。

const cache = new Map();
function fib(n) {if (n <= 1) return n;if (cache.has(n)) {return cache.get(n);}const result = fib(n - 1) + fib(n - 2);cache.set(n, result);return result;
}
fib(100); // 幾乎立即解決

我們是否可以只是調用了fib的第一個實現，然后在其上寫了memoizedFib = memoize(fib);以獲得相同的性能優化？不幸的是，不能。fib 的原始實現引用了自身（未記憶化版本）。因此，如果調用 memoizedFib(100)，緩存只會添加一個鍵（100），仍然需要數年時間才能計算。這是 JavaScript 的一個基本限制（Python 沒有此問題）。

4、專業實現的考慮

4.1處理任意輸入

之所以僅假設將 3 個具體的函數作為參數傳遞，都具有數值輸入，是有原因的。這是因為數字具有唯一的字符串表示，使緩存邏輯更簡單。如果函數可以傳遞任意輸入，你將需要比僅將輸入直接轉換為字符串更復雜的方法。考慮解決 2630. 記憶函數 II，它需要更通用的方法。

4.2內存管理

由于你可以無限次地調用函數并傳遞不同的輸入，因此可能會耗盡內存。實施一些機制來限制緩存大小非常重要。一種方法是使用Least Recently Used（LRU）緩存。你可以在 2630. 記憶函數 II 的底部相關信息。

方法 1：使用 Rest/Spread 語法 + JSON.stringify()

在 JavaScript 中，你可以使用rest語法訪問所有參數作為數組。然后，可以將參數數組展開以將其傳遞回函數。

由于參數是數字數組（即有效的 JSON），將它們轉換為字符串鍵的便捷方式是使用 JSON.stringify()。

1. 初始化一個用于新的記憶化函數的緩存對象。
2. 每次調用記憶化函數時，將傳遞的參數轉換為字符串。
3. 檢查鍵是否已存在于緩存中。如果是，則立即返回關聯的值。
4. 否則，調用提供的函數，將輸出放入緩存，并返回輸出。

function memoize(fn) {const cache = {};return function(...args) {const key = JSON.stringify(args);if (key in cache) {return cache[key];}const functionOutput = fn(...args);cache[key] = functionOutput;return functionOutput;}
}

方法 2：使用參數語法

JavaScript 還允許你使用特殊的arguments變量訪問傳遞的參數。

使用arguments變量時需要注意以下幾點：

1. 它不能與箭頭函數一起使用，而是引用任何包含非箭頭函數的封閉函數。
2. 雖然arguments類似于數組，但實際上是一個類似 數組的可迭代 對象。像循環遍歷它和訪問索引一樣的操作會按預期工作。但是，調用push和join等方法不會起作用。
3. 在處理可變參數時，通常最佳實踐是使用rest語法，而arguments主要用于較舊的代碼庫。

function memoize(fn) {const cache = {};return function() {// 將參數轉換為字符串let key = '';for (const arg of arguments) {key += ',' + arg;}if (key in cache) {return cache[key];}const functionOutput = fn(...arguments);cache[key] = functionOutput;return functionOutput;}
}

方法 3：基于數字約束進行優化 + Function.apply

將參數轉換為字符串是一個相對昂貴的操作。因為根據問題的約束，永遠不會有超過兩個參數，參數永遠不會大于 100,000，所以我們可以避免將它們轉換為字符串。

假設你有兩個數字a和 b，并且希望將它們轉換為一個唯一的數字，使得沒有其他值的a和b映射到相同的數字。你可以使用公式 key = a + (b * 100001)。

我們還可以使用Function.apply方法調用提供的函數。它的第一個參數是this上下文，我們可以將其設置為 null，因為提供的函數不引用 this。第二個參數是要傳遞給函數的參數。

function memoize(fn) {const cache = new Map();return function() {let key = arguments[0];if (arguments[1]) {key += arguments[1] * 100001;}const result = cache.get(key);if (result !== undefined) {return result;}const functionOutput = fn.apply(null, arguments);cache.set(key, functionOutput);return functionOutput;}
}

方法4：一行代碼

為了展示 JavaScript 提供的一些語法，以下是一種一行代碼的解決方案。讓我們看看代碼的不同部分，以了解它是如何工作的。

1. var memoize = (fn, cache = {}) => (...args) => 定義了 memoize函數，它接受兩個參數：一個函數 fn 和一個可選的緩存對象 cache。由于永遠不會傳遞第二個參數，cache將始終設置為一個空對象 {}。memoize 函數繼續返回另一個函數，它接受任意數量的參數。
2. ?? 這是Nullish合并運算符。僅當左側的第一個操作數不為null或undefined時，它才會返回左側的第一個操作數。否則，它將返回右側的第二個操作數。
3. cache[args.join()] 將參數轉換為逗號分隔的字符串，并返回與該鍵關聯的值。如果值不存在，則返回 undefined（導致函數返回右側的值）。
4. (cache[args.join()] = fn(...args)) 將緩存中的鍵設置為提供的函數的輸出。然后返回該值。如果存在緩存未命中，將執行此代碼。

var memoize = (fn, cache = {}) => (...args) => cache[args.join()] ?? (cache[args.join()] = fn(...args))

5、復雜度分析

以下分析適用于所有方法。

設 N 為以前調用函數的次數。

• 時間復雜度：O(1)。每次調用記憶化函數時，只執行一次字典查找。
• 空間復雜度：O(N)。在最壞的情況下，需要存儲之前的所有參數。