DIV CSS 佈局教程網

用記憶函式(memoization)加速遞迴:以 Fibonacci 為例
編輯:關於JavaScript     

遞迴優雅,但代價是重複計算。經典的 Fibonacci 就是最容易被數字規模壓垮的例子。

問題:重複計算的災難

var fibonacci = function (n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

這段程式看起來乾淨俐落,但只要 n 大一點,瀏覽器就會卡死。原因是它在計算過程中會大量重複拜訪同一個節點——fibonacci(30) 內部其實把 fibonacci(28) 算了兩次、fibonacci(27) 算了三次,越往下指數級膨脹。

解法:把算過的結果記下來

JavaScript 強大的陣列與函式閉包,讓「記憶已計算的結果」變得非常容易。下面這個小小的通用記憶器,任何遞迴函式都能套用:

var memoizer = function (memo, fundamental) {
    var shell = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fundamental(shell, n);
            memo[n] = result;
        }
        return result;
    };
    return shell;
};

兩個參數分工明確:memo 是初始的記憶表(已知答案),fundamental 是真正負責計算的基礎函式。而 shell 是包在外面的守門人:先查 memo,命中就直接回傳;沒命中才呼叫 fundamental 計算,算完立刻寫回 memo。

最妙的是它把 shell 自己當參數傳給 fundamental,於是基礎函式內部的遞迴呼叫也會經過同一道守門關卡——記憶因此能一路貫穿整棵遞迴樹。

使用方式

// 傳入初始已知項 [F(0), F(1)] = [0, 1]
var fibonacci = memoizer([0, 1], function (shell, n) {
    return shell(n - 1) + shell(n - 2);
});

// 同理,階乘的初始項是 [0!, 1!] = [1, 1]
var factorial = memoizer([1, 1], function (shell, n) {
    return n * shell(n - 1);
});

呼叫方式與原本的遞迴幾乎相同,但速度從指數級降為線性級——原本算不完的 n,現在瞬間完成。

這個模式為什麼優雅

它把「怎麼算」與「算過的別再算」這兩件關注點徹底分離。基礎函式只專心寫遞迴關係式,效能優化完全交給外層的 memoizer 處理,兩邊都不必為對方妥協。這正是高階函式的典型價值。

有兩個實作上的限制值得注意:其一,typeof result !== 'number' 這個判斷意味著它只適用於回傳數值的函式,若結果可能是物件或 NaN 就會誤判;其二,記憶表會無限成長,長時間運行的應用可能需要加上容量上限或改用 WeakMap 之類的機制。

ES6 之後也可以直接用 Map 實作同樣的效果,語意比陣列更清楚,也不受索引必須為整數的限制。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved