前言

這篇文章會藉由範例讓你了解 Memoization，讓程式碼執行更有效率。

Memoization 是什麼?

它就只是一種觀念，並非具體的東西，這個觀念是把函式計算後得到的回傳值暫存起來，下次要使用相同參數調用函式時可以馬上回傳結果。在做一些繁重的計算時可以使用它。

另外要注意的是有加上 Memoization 函式必須保持純粹(pure)，一樣的傳入參數要輸出一樣的結果。

範例 1

在此範例中，我們來加上 Memoization 機制讓遞迴執行更有效率。

沒有加上 Memoization

以下是費伯那西數列的程式碼:

const fib = (n) => n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

程式很簡單易懂，但執行效率可就沒那麼迅速了...
由下面的截圖可以知道，要計算到第 45 項費伯那西數就要花費到 9 秒鐘了，更大的數字肯定要花更多時間。

時間複雜度

在提出優化解法前，我們先來分析一下這段程式的時間複雜度。

因為 fib(n)在作遞迴時，只要 n > 2 就是 fib(n - 1) + fib(n - 2) 的結果，n <= 2 則回傳 1，所以我們可以先初步這樣列出算式: T(n) = T(n-1) + T(n-2) + 1。

而 T(n-1) = T(n-2) + T(n-3)，所以我們可以得到 T(n-1) = T(n-2) + T(n-3) + T(n-3) + T(n-4)。

再進一步拆解，變成 T(n-1) = T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6)。

從上面的推論畫出樹狀結構，可以看到每往下一層都是以 2 的次方去增加元素，由此可知為時間複雜度 O(2^n)。

            n
         /     \
       n-1     n-2     # 2^1
      /  \    /   \
    n-2  n-3 n-3 n-4   # 2^2
   /   \
 n-3 n-4               # 2^3
 / \ / \
...............        # 2^(n - 1)

加上 Memoization

接著來做改良，幫 fib 函式多加一個 cache 陣列參數，它會透過閉包的特性儲存之前計算過的費伯那西數，並在每個函式呼叫時當做參數傳遞，就可以不用重複計算。

這邊也帶到 Dynamic Programming 動態規劃法的概念，像上面的優化就是 DP 的一個範例，也就是 DP = 拆分(divide & conquer)和儲存(memoization)

const fib = (n, cache = []) => {
  if (n === 0) return 0;
  if (cache[n]) return cache[n];

  let result;
  result = n <= 2 ? 1 : fib(n - 1, cache) + fib(n - 2, cache);
  cache[n] = result;
  return result;
}

從截圖可以發現執行時間縮短到只剩 0.2 多秒 !!! 是不是變快很多 !? 而且時間複雜度也變成了 O(n)。

使用注意

Memoization 雖然對執行效能上有所有好處，但缺點就是會佔用記憶體，像上面的 cache 陣列記錄了之前計算過的費伯那西數。

所以如果程式處理的資料量較大時，就可能會佔用大量的記憶體，此時可以試著做快取資料量的限制。

範例 2

這個範例用來 cache 計算過的正方形面積，使用閉包 + 高階函式的觀念實作，一樣將之前計算過的值放到 cache 物件裡面。

const getSquareArea = (length) => length * length;

const memorize = (fn) => {
  let cache = {};
  
  return (...args) => {
    const n = args[0];
    if (n in cache) {
      console.log('use cache');
      return cache[n];
    } else {
      console.log('call function');
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}

const memorizedGetSquare = memorize(getSquareArea);

console.log(memorizedGetSquare(3));
console.log(memorizedGetSquare(3));
console.log(memorizedGetSquare(4));
console.log(memorizedGetSquare(4));

執行結果如下:

練習題 LeetCode 2623. Memoize

現在，讀者可以應用自己目前所學，去解看看這道題目喔~

其他補充

1. Lodash 也有實作 Memoization 相關的函式 - _.memoize(func, [resolver])。
2. React.memo、useMemo、useCallback 也有使用到 Memoization 的觀念，去避免元件重複渲染。

參考資料 & 推薦閱讀

[演算法] Fibonacci：善用 cache 和 Memoization 提升程式效能

Computational Complexity of Fibonacci Sequence