文章

前端面試手寫練習 - memoize

文章發表於

問題

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));
  });
});

Open browser consoleTests

追問

  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
如果您喜歡這篇文章,請點擊下方按鈕分享給更多人,這將是對筆者創作的最大支持和鼓勵。