遞迴是拖慢腳本速度的常見兇手之一。遞迴層數一多,瀏覽器就會越跑越慢,最後跳出「腳本失控」的提示,甚至直接當掉。上一節談過用 memoization 來優化計算數值的遞迴函式,但 memoization 並非萬靈丹——不是所有遞迴都能靠快取救回來。本文要談的就是這些情況,以及解法:把遞迴改寫成迭代。
需要先說明的是,本文結尾給的方案並非最終答案,還得和「優化迴圈」那一節的技術一起用,才能得到最好的效果。
【原文】Speed up your JavaScript, Part 3
【作者】Nicholas C. Zakas
【譯者】明達
以下是對原文的整理
在這個系列的第二篇裡,我簡短介紹過如何用 memoization 取代過多的遞迴呼叫。memoization 會快取先前算出來的结果,如此一來就不必重算。對以遞迴計算的函式來說這招非常有效。我當時用的 memoizer 出自 Crockford,主要用在回傳整數的遞迴運算;但並非所有遞迴都回傳整數,所以我們需要一個更通用的版本。
function memoizer(fundamental, cache) {
cache = cache || {};
var shell = function(arg) {
if (! (arg in cache)) {
cache[arg] = fundamental(shell, arg);
}
return cache[arg];
};
return shell;
}
這個版本與 Crockford 原版有幾點差異。首先參數順序對調了:原函式放在第一位,快取物件放第二位且為選填(不是每個遞迴都需要初始值)。其次,我把快取從陣列改成物件,這樣就能處理回傳值不是整數的情況。而在 shell 函式中,我用 in 運算子判斷參數是否已在快取裡,這比檢查型別是否為 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 次。對結果集合嚴格定義的遞迴演算法來說,memoization 幾乎是無敵的。然而確實還有很多遞迴不適合這招。
我在學校時的一位教授始終堅持:任何用遞迴的地方,只要有需要,都能改用迭代。遞迴與迭代其實經常互為補位,尤其在對方出問題的時候。把遞迴轉為迭代的技巧與語言無關,而這對 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);
}
// 遞迴版的合併排序
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() 都會再產生兩次遞迴呼叫。這個演算法不適合 memoization,因為每個結果只算一次、用一次,快取起來也沒意義。用 mergeSort() 處理 100 個元素的陣列,總共會呼叫 199 次;1000 個元素則是 1999 次。
這時候的解法就是把遞迴改寫成迭代,也就是引入迴圈:
// 迭代版的合併排序
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([]); // 以備元素數量為奇數
for (var lim = len; lim > 1; lim = (lim + 1) / 2) {
for (var j = 0, k = 0; k < lim; j++, k += 2) {
work[j] = merge(work[k], work[k + 1]);
}
work[j] = []; // 以備元素數量為奇數
}
return work[0];
}
這個版本用一連串迴圈取代遞迴。合併排序的第一步是把陣列拆成單元素陣列,這裡很明確地做了這件事,而不是靠遞迴隱晦完成:work 一開始被初始化為一堆單元素陣列的集合,迴圈中每次合併兩個陣列並把結果放回 work,最後排序結果就從 work[0] 取回。
整個實作完全沒有遞迴,卻一樣完成了這個演算法。代價是引入了相當多迴圈,而迴圈次數取決於元素數量,所以可能還得搭配上一篇文章談過的技術來處理這些額外開銷。
總結基本原則:任何時候使用遞迴都該謹慎。memoization 與迭代是兩條替代路線,最直接的收益,大概就是不用再看到那個「腳本失控」的提示框了。