加速你的 JavaScript，第 3 部分
遞歸是快速運行腳本的敵人。過多的遞歸會導致瀏覽器停止或意外退出，因此必須解決 JavaScript 中的一個嚴重性能問題。在本系列的第 2 部分中，我簡要介紹了通過記憶化處理函數中過多的遞歸。記憶是一種緩存先前計算的值的技術，這樣它們就不需要重新計算了；當遞歸函數進行這樣的計算時，記憶化非常有用。我介紹的 memoizer 是 Crockford 的，主要用於返回整數的遞歸函數。當然，所有遞歸函數都不返回整數。更通用的 memoizer() 可以創建函數來處理任何類型的遞歸函數：
function memoizer(fundamental, cache){
cache = cache || {}
var shell = function(arg){
if (!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(shell, arg)
}
return cache[arg];
};
return shell;
}
這個版本的函數與 Crockford 的有點不同。首先，參數的順序被顛倒了，原來的函數作為第一個參數和一個可選的 cache 對像作為第二個參數。並非所有遞歸函數都以初始信息為種子，因此使該參數可選是有意義的。在內部，我將緩存數據類型從數組更改為對象，這使得該版本適用於返回非整數結果的遞歸函數。 shell 內部 函數，我使用的是 hasOwnProperty() 方法來查看參數是否已經有一個 cache 入口。如果值的類型不是 undefined，這比測試更安全 自 undefined 是一個有效的返回值。與前面的斐波那契示例的用法示例：
var fibonacci =
memoizer(function (recur, n) {
return recur(n - 1) + recur(n - 2);
}, {"0":0, "1":1});
再次調用 fibonacci(40) 導致只有 40 次調用原始函數，而不是 331,160,280。記憶化非常適合具有嚴格定義的結果集的遞歸算法。但是，還有其他遞歸算法不適合通過記憶進行優化。
我在大學的一位教授堅持認為，如果有必要，使用遞歸編寫的任何東西也可以使用迭代編寫。事實上，當一個問題被視為一個問題時，遞歸和迭代通常被認為是彼此的補救措施。無論編程語言如何，將遞歸算法轉換為迭代算法的技術都是相同的；然而，在 JavaScript 中的重要性更大，因為執行環境的資源非常有限。考慮一個典型的遞歸算法，例如合併排序。在 JavaScript 中，可能會這樣寫：
function merge(left, right){
var result = [];
while (left.length > 0 && right.length > 0){
if (left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
//recursive merge sort algorithm
function mergeSort(items){
if (items.length == 1) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
調用mergeSort() 數組上的函數返回按正確順序排序的項目數組。請注意，對於每次調用 mergeSort() 有兩個遞歸調用。該算法不會從記憶中受益，因為每個結果只計算一次，因此緩存結果無濟於事。如果您要調用 mergeSort() 在一個有 100 個項目的數組上，總共有 199 個調用； 1,000 項數組將導致 1,999 次調用。這種情況下的解決方案是將遞歸算法轉換為迭代算法，也就是引入一些循環（算法來源：List Processing:Sort Again, Naturally）：
//iterative merge sort algorithm
function mergeSort(items){
if (items.length == 1) {
return items;
}
var work = [];
for (var i=0, len=items.length; i < len; i++){
work.push([items[i]]);
}
work.push([]); //in case of odd number of items
for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
for (var j=0,k=0; k < lim; j++, k+=2){
work[j] = merge(work[k], work[k+1]);
}
work[j] = []; //in case of odd number of items
}
return work[0];
}
合併排序算法的這種實現使用一系列循環而不是遞歸來對數組進行排序。由於合併排序首先將一個數組分解為幾個單項數組，因此此方法顯式地執行此操作，而不是通過遞歸調用隱式地執行此操作。 work array 最初是一個單項數組的數組。循環允許一次合併兩個數組，將結果放回 work 大批。當函數完成其工作時，結果存儲在 work 的第一個位置 並被退回。在這個版本的歸併排序中，沒有遞歸。但是，它確實會根據數組中的項目數引入大量循環，因此可能值得重新審視第 2 部分中討論的技術來處理額外的開銷。
底線：始終注意 JavaScript 中的遞歸。記憶和迭代是避免過度遞歸和長時間運行腳本對話框的兩種方法。
翻譯
- 中文（簡體）
