問題

memoize 函式是一個高階函數 (higher-order function)，它接收一個函式作為輸入，並返回該函式的 memoized（儲存結果的）版本。

被記憶過後的函式就會快取 (cache) 每個已經計算過的值，並在之後接收到相同輸入時返回快取結果。這可以顯著提高涉及複雜處理/顯著延遲且重複被同樣參數調用的函式的性能。

function memoize(func: Function, resolver): Function: Function;

resolver 是讓開發者自定義快取的 key 的函式，如果不提供，則預設為 (...args) => args.join('_')。

fibonacci 就是一個非常經典的例子，由於其計算過程是指數級的，因此在計算較大的數字時，將會非常花時間，所以是非常適合使用 memoize 來優化的例子。

如果在這裡有不太清楚 fibonacci 的話，可以參考 cs61a - measuring efficiency 的 lecture。

function fibonacci(n) {
  console.log(`I'm calculating fibonacci(${n})`)

  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

範例

當 fibonacci 在使用 memoize 後的結果，可以看到第二次呼叫 fibonacci(20) 時，不會再執行計算，而是直接返回快取的結果。

const memoizedFibonacci = memoize(fibonacci)

console.log(memoizedFibonacci(20)) // I'm calculating fibonacci(20)...
console.log(memoizedFibonacci(20)) // No log, return immediately

練習區

了解問題後，讀者們可以嘗試先寫下思路，再到下方的練習區域實際寫出程式碼。也可以移除 test 檔內的 skip 來測試追問題是否正確。

import { add } from './add';

describe('add', () => {
  test('Commutative Law of Addition', () => {
    expect(add(1, 2)).toBe(add(2, 1));
  });
});

追問

1. 是否可以支援清除快取 (cache)？

const memoizedFibonacci = memoize(fibonacci)

console.log(memoizedFibonacci(20)) // I'm calculating fibonacci(20)...
console.log(memoizedFibonacci(20)) // No log, return immediately

memoizedFibonacci.cache.clear()

console.log(memoizedFibonacci(20)) // I'm calculating fibonacci(20)...

筆者思路

1. 決定用來快取的資料結構，例如 object, map, set ..., 在這裡，筆者選擇用 Map，因為 Map 能夠有效地存儲各種類型的鍵。
2. 創建雜湊值 (hash key)，這裡先簡單的使用 args.join('_') 來創建。
3. 如果在快取中找不到鍵，則計算值。
4. 如果已經在快取中，則是回傳存儲值。

筆者解答

基礎版

function memoize(func, resolver = (...args) => args.join('_')) {
  let cache = new Map()

  return (...args) => {
    const hashkey = resolver(...args)

    if (!cache.has(hashkey)) {
      const result = func.apply(this, args)
      cache.set(hashkey, result)
    }

    return cache.get(hashkey)
  }
}

export { memoize }

追問版

function memoize(func, resolver = (...args) => args.join('_')) {
  let cache = new Map()

  const memoized = (...args) => {
    const hashkey = resolver(...args)

    if (!cache.has(hashkey)) {
      const result = func.apply(this, args)
      cache.set(hashkey, result)
    }

    return cache.get(hashkey)
  }

  memoized.cache = cache
  return memoized
}

相關題目

1. bigfronend - generic memoize function