實現 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

留言

張貼留言

這個網誌中的熱門文章

有趣的邏輯問題:是誰在說謊

Web 技術中的 Session 是什麼?

淺談 USB 通訊架構之定義(二)

淺談 USB 通訊架構之定義(一)

Reverse SSH Tunnel 反向打洞實錄