JavaScript Closure 的運用: Memoization

JavaScript: The Good Parts ch4 後半提到 Closure 後, 一堆例子都滿有趣的, 4.15 提到 Memoization 的實作技巧。用遞迴的好處是寫起來直覺, 缺點是有可能重覆算算過的值而跑得過慢。像費氏數列就是很好的例子。Memorization 指用個 table 記住之前遞迴算過的值, 藉此減少不必要的遞迴。

上回練習寫 Memorization 已是高中的事了, 那時用 C 練程式競賽, 不過 C 沒有恰當的 scope 維護方式, Memorization 寫起來較醜一些, 表格得存在全域變數或函式內的靜態變數。JavaScript 配合 Closure 很漂亮地解決表格的 scope 問題, 以下是參考書上的範例練習寫的碼, 幾乎長得一樣啦。

var memorizer = function(memo, fundamental) {
    var shell = function (n) {
        if (memo[n] === undefined) {
            memo[n] = fundamental(shell, n);
        }
        return memo[n];
    };
    return shell;
};

var fib = memorizer([0, 1], function(shell, n) {
    return shell(n - 1) + shell(n - 2);
});

var factorial = memorizer([1], function(shell, n) {
    return n * shell(n - 1);
});

fib(5); // 5
fib(10); // 55
factorial(10); // 3628800

memorizer 的第二個參數的函式得多加一個 "shell" 欄位, 讓 memorizer 產生暫時的函式 shell, 再將它傳進目標函式, 這樣 fib /  factorial 裡用的 shell 就是有 memorization 效果的函式了。

初看的時候腦筋會打結吧, 看懂後覺得很有意思。