JavaScript - Memoization 記憶函式

tags: JavaScript Event Loop 讀書會

什麼是 Memoization ?

記憶函式 ( Memoization ) 是一種優化程式技巧，把需要大量計算 ( 長遞歸、長迭代操作 ) 的函式將其參數與結果緩存 ( Cache )，若調用記憶函式且給予相同參數時，不須經過計算程序，直接回傳相同結果。

沒有 Cache 機制的程式

假設有一個工人，這位工人需要去倉庫拿工具 ( getTool ) 來完成他的工作 ( task ) :

function getTool (task) {
    console.log('前往倉庫拿取工具')
    return task + '工作完成'
}

但我們會發現，如果工人做同樣的工作 ( task )，他仍然會不斷跑去倉庫拿取工具 :

Day 1：工人 ( 小明 ) 第一天修理大水管，跑到倉庫拿工具。

Day 2：工人 ( 小明 ) 第二天繼續修理大水管，還是跑到倉庫拿工具。

Day 3：工人 ( 小明 ) 第三天繼續修理大水管，還是跑到倉庫拿工具

( 小明 OS : e04，給我工具箱 ! )。

身為哆啦工具夢的我們，來實現小明的願望吧 !

讓我們把拿取工具 ( getTool ) 過程優化 :

function getTool (todoTask) {
    const doneCache = {} // 已經做過同樣的工作 cache
    return function () {
        // 工作內容
        const taskContent = JSON.stringify(arguments)
		
        // 如果已經有做過同樣的工作
        if (doneCache[taskContent]) {
            return doneCache[taskContent] // 直接回傳工具對應的工作內容
        }
        // 如果工具箱沒有工作所需要的工具
        else {
            // 工作結果
            const doTaskResult = todoTask.apply(this, arguments)
            // cache 儲存工作結果，並回傳
            doneCache[taskContent] = doTaskResult
            return doTaskResult
        }
    }
}

然後訂定小明一個工作流程 :

const work = getTool((task) => {
    console.log('前往倉庫拿工具')
    return task + ': 已完成工作'
})

如此一來，當小明做同樣的工作，他就知道已經有拿過工具，直接執行工作內容就可以了 !

但是當小明每天做不同的工作，他還是得回去倉庫拿給西 ( 工具 ) :

設計一個 Momoized Function

每個功能函式都要寫成 Memoized Function 太麻煩，不妨設計一個 Memoize 工具函式吧 !

const memoize = (func) => {
    const cache = {}
    return (...args) => {
        const key = JSON.stringify(args)
        if (!(key in cache)) {
            cache[key] = func(...args)
        }
        return cache[key]
    }
}

Memoization 使用時機

• 當函式需要消耗大量效能來運算 ( Expensive function calls, heavy computations )。
• 經常會需要將前一次的值再次帶入的遞迴函式 ( Recursive function )。

Memoization 需注意的問題

Cache 雖然可以優化執行效能，但 Cache 也會因處理大量資料 ( 有很多不同的資料 ) 時，占用大量記憶體且不會釋放，因此 Memoization 也是一把雙面刃，需要注意使用時機。

Vue 也有相同的機制

Vue 也有提供給我們選擇使用 Memoization 或者不使用，也就是 Computed 及 Methods 方法。computed 帶有 Cache 機制，也就是在 Computed 它是屬於 Memoization，這也是為什麼 computed 都要求一定要 return 結果，否則會報錯，而 methods 就沒有 Cache 了，每次呼叫 Methods 的方法時都會重新執行。

此外，主流框架對於 Virtual DOM 渲染基本上都有 Cache 的機制，因此可以時常看見對於效能好的裝置來說，瀏覽有使用 Framework 的網頁時，整體網頁瀏覽較為順暢，但若是效能或記憶體容量較差的裝置來說，瀏覽使用 Framework 的網頁時常會有跑不動 ( Lag ) 的感覺。

---

Memoization 運用在 Fibonacci ( 費波那契數列 )

費波納契數列 ( Fibonacci Sequence ) 指的是 :

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

建立一個 Fibonacci 查詢函式

// n 為查詢費波那契數列第幾筆的值
const fibonacci = n => {
    return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
}

除了 n = 1、n = 2 的情況外，可以觀察每個 fibonacci 計算出來的值都是前兩個 fibonacci 相加的結果，也就是

fibonacci(n) === fibonacci(n - 1) + fibonacci(n - 2)

Time Complexity 時間複雜度

然而，利用這種初步的遞迴函式演算法是屬於 O(n^2)，也就是當 n 的值愈大，運算所花費的時間會呈指數 ( 爆炸性 ) 成長 :

fibonacci(3) // 執行 3 次函式
fibonacci(5) // 執行 9 次函式
fibonacci(7) // 執行 25 次函式
fibonacci(10) // 執行 109 次函式
fibonacci(20) // 執行 13259 次函式
fibonacci(30) // 執行 1664079 次函式
fibonacci(99) // 你不會想試的

圖片來源：Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

Memoized Fibonacci

我們可以用上面設計的 Momoized Function 來封裝 fibonacci :

const memoize = (func) => {
    const cache = {}
    return (...args) => {
        const key = JSON.stringify(args)
        if (!(key in cache)) {
            cache[key] = func(...args)
        }
        return cache[key]
    }
}

const fibonacci = memoize((n) => {
    return n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
})

Reference

JavaScript Memoization 故事介紹

JavaScript記憶（Memoization）函數

實現 JavaScript 的 Memoization

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