實現 JavaScript 的 Memoization

函數式程式設計（Functional Programming）是近年來越來越被軟體開發者常提及的話題，許多人討論它時，不外乎說其就是在程式設計中引入了數學方法，彷彿有神奇又高深的理論加持一般。事實上，對於一般開發者而言，函數式程式設計比較通俗且直接的好處，就是讓開發者可以在「函數」的層面和維度，進行邏輯或是效能上的優化。所以說，比起命令化的執行程式、管理物件，怎麼去設計和管理函數這件事，就是函數式程式設計所關心的重點。

JavaScript 這語言在設計上，天生就支援 first-class function，這代表函數在 JavaScript 是一種資料型態，可以被當成普通物件傳遞、處理，這讓開發者在使用 JavaScript 時可以時不時引入 Functional Programming 的技巧和概念。

本文將介紹 Functional Programming 中大量被使用的 Memoization 機制，然後我們如何在 JavaScript 中引入並實地使用它，無論你會不會 Functional Programming，這都是一個可以常用於日常開發中的優化技巧。

Memoization 是什麼？

用一般程式開發的說法就是快取（Cache）機制，只不過 Memoization 是針對「函數」進行快取。快取的好處在於我們只要執行過一次工作後，之後在執行相同工作前，就能提前知道執行結果為何，所以我們可以不用「真正的」去執行工作，而直接取用執行結果就好，可大量提升程式執行的效能。

同樣快取概念套用在函數上，若我們給予特定「輸入（Input）」到一個函數中，而該函數會回傳一個特定的「輸出（Output）」，理論上函數執行一次後，下次再使用這個函數時，只要「輸入」和過去一樣，我們就能提前知道結果。

而這樣對函數進行的快取機制，就是所謂的 Memoization。

只能使用在純函數

你可能會聽一些人說，只有「純函數」才能引入快取機制，然後開始討論數學上所謂函數的定義，然後你就聽到昏了，後面在講什麼你就都聽不進去了。

但如果撇除函數的數學定義，若白話來說，能被快取的東西，就是能被預測的東西，這代表函數的執行結果也要能被預測，也就是一樣的輸入值，就會有一樣的輸出結果。

所以，如果一個函數每次執行，代入的輸入值一樣，但回傳結果卻是可能不一樣，這就不是一個純函數，像是取亂數的函數就屬此類，我們無法對其引入快取機制，而且也沒有任何引入的意義。

從一個簡單的函數開始

要實現 Memoization 之前，我們得先創造一個有用的函數，然後才能討論怎麼快取它。現在假設我們有一個函數，專門用來查詢一個資料陣列，我們會這樣設計：

const getData = (records, id) => {

    // 找到指定的 element 並回傳
    return records.find((data) => {
    
        // 找到指定的 ID 就回傳 true
        return (data.id === id);
    });
};

// 想像這是一個有上萬筆資料的陣列
const list = [ ... ];

// 取得 list 裡 id 為 helloId 的資料
let data = getData(list, 'helloId');

創造一個函數，專門查詢特定陣列

如果我們想要創造一個函數，專門查詢 list，則可以運用 JavaScript 中的 .bind() ，來綁定 list 並創造出一個新的函數來使用：

// 以舊的 getData 為基礎創造一個新的函數，綁定 caller 和第一個代入參數
const newGetData = getData.bind(this, list);

// 執行新的函數時只需要代入尚未被綁定的參數即可
let data = newGetData('helloId');

註：有興趣者可以延伸搜尋 Functional Programming 的「柯里化（Currying）」相關資料。

設計函數的快取機制

我們可以自己設計一個閉包（Closure）來實現函數的快取機制，簡單來說就是利用 JavaScript 的 Object 來建立一個 key-value pair 的快取。而 key 就使用函數的「輸入（Input）」，value 則是函數的執行「輸出（Output）」。

const memoize = (fn) => {
    // 將快取資料存放在閉包裡的記憶體
    const cache = {};

    return (arg) => {
        // 先檢查是否有快取，如果沒有就執行原始函數並快取其結果
        if (cache[arg] === undefined)
            cache[arg] = fn(arg);

        // 回傳執行結果
        return cache[arg];
    };
};

// 對函數套用 Memoization 機制，會得到一個新的函數
const improvedGetData = memoize(newGetData);

// 這個新的函數使用方法和舊的一樣
let data1 = improvedGetData('helloId');

// 第二次執行同樣函數，並帶同樣參數時，就是直接從快取記憶體中取得結果
let data2 = improvedGetData('helloId');

被我們設計出來的 memoize() 是通用的方法，可以應用在其他函數中，只要其他函數也有這樣的需求，又符合純函數的條件，是可以直接以 memoize() 包裝，受惠於快取機制。

你應該要注意的問題

Memoization 這樣的快取機制，雖對執行效能上有所有好處，但最直接的問題就是會佔用記憶體，如果我們的程式處理的資料量很大，就可能會佔用非常大量的記憶體而不會釋放。

所以在某些函式程式語言中， Memoization 甚至支援快取資料數量的限制，如果你有需求，可以自己試著增加這樣的設計。

效能評估？

至於增加快取後的效能如何呢？這邊準備了一個簡單的測試「Memoization Testing」，分別為原始函數執行的效能，以及引入 Memoization 機制後的效能，你可以試著跑跑看。

第一次的執行上效能差不多，但若「同個函數+同樣輸入值」執行兩次後，原始函數的執行效能就會開始明顯與有快取機制的函數有所差距。

後記

物件導向大家都很會玩了，可以開始玩玩不同維度的優化和技巧，其實相當有趣。:-P