這是 Nicholas 討論如何避免腳本失控系列的第二篇,主題是重構巢狀迴圈、遞迴,以及那些在函式內部一次做太多事的函式。核心思路和上一節 chunk() 的例子一致:如果幾個操作之間沒有特定順序、彼此也不相依,就可以用非同步的方式分批執行,既能減少單次執行量,也能避免讓瀏覽器卡死。本文另外也介紹了用 memoization 取代遞迴的做法。
【原文標題】Speed up your JavaScript, Part 2
【原文作者】Nicholas C. Zakas
上週我在〈too much happening in a loop〉中談了 JavaScript 執行時間過長的第一個原因。類似的情況也會出現在函式上——函式也可能因使用不當而過載,通常是因為內部迴圈太多、遞迴太深,或者只是塞了太多不相干卻必須一起做完的操作。
迴圈過多常以巢狀形式出現,這種程式會一直佔住 JavaScript 引擎直到跑完。最經典的例子莫過於氣泡排序。由於 JavaScript 內建了 sort(),實務上不必自己寫,但我們可以藉它理解巢狀迴圈吃資源的癥結所在:
function bubbleSort(items) {
for (var i = items.length - 1; i >= 0; i--) {
for (var j = i; j >= 0; j--) {
if (items[j] < items[j - 1]) {
var temp = items[j];
items[j] = items[j - 1];
items[j - 1] = temp;
}
}
}
}
你應該記得,氣泡排序是效率最低的排序法之一:n 個元素要做 n 平方次運算。元素一多,時間就很可觀。內層迴圈本身很單純,只是比較與交換,真正的問題在執行次數——這會讓瀏覽器異常,最直接的结果就是那個腳本失控的警告框。
幾年前 Yahoo 研究員 Julien Lecomte 寫過一篇〈Running CPU Intensive JavaScript Computations in a Web Browser〉,說明如何把龐大的 JavaScript 運算切成小塊。其中一個例子就是把氣泡排序拆成多個步驟,每步只遍歷陣列一次。我在他的基礎上做了些修改,思路相同:
function bubbleSort(array, onComplete) {
var pos = 0;
(function() {
var j, value;
for (j = array.length; j > pos; j--) {
if (array[j] < array[j - 1]) {
value = array[j];
array[j] = array[j - 1];
array[j - 1] = value;
}
}
pos++;
if (pos < array.length) {
setTimeout(arguments.callee, 10);
} else {
onComplete();
}
})();
}
這個函式借助一個非同步管理器完成了氣泡排序,每次遍歷陣列前先停一下。排序結束後會觸發 onComplete() 通知呼叫方資料已備妥。它用的技巧和 chunk() 一樣:把行為包進匿名函式,再把 arguments.callee 交給 setTimeout() 達到重複呼叫的目的,直到排序完成。若你想把巢狀迴圈拆成小步驟以解放瀏覽器,這個寫法值得參考。
類似的問題還有過深的遞迴。每一層額外的遞迴呼叫都會佔用更多記憶體,拖慢瀏覽器;更麻煩的是,你可能在警告框出現之前就把記憶體耗光,導致瀏覽器無回應。Crockford 曾在部落格深入討論過這件事,他用的例子是遞迴產生斐波那契數列:
function fibonacci(n) {
return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
};
依 Crockford 的說法,執行 fibonacci(40) 會重複呼叫自身 331,160,280 次。避免遞迴的方案之一是 memoization——把上次的結果記下來。他介紹了這個函式,可為處理數值的函式加上這項能力:
function memoizer(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;
};
接著把它套用到斐波那契產生器:
var fibonacci = memoizer([0, 1],
function(recur, n) {
return recur(n - 1) + recur(n - 2);
});
此時再呼叫 fibonacci(40),只會重複呼叫 40 次,改善幅度非常可觀。memoization 的原理一句話說完:同樣的結果,你不必算第二次。可能會再用的結果就存起來,總比重算快。
最後一個讓函式變慢的原因前面提過:函式裡塞了太多內容,通常是這種開發模式造成的:
function doAlot() {
doSomething();
doSomethingElse();
doOneMoreThing();
}
這裡要執行三個函式。請注意,它們彼此並不相依,只是需要在某個時機逐一執行。同樣可以用類似 chunk() 的方式來排程,而不會鎖住瀏覽器:
function schedule(functions, context) {
setTimeout(function() {
var process = functions.shift();
process.call(context);
if (functions.length > 0) {
setTimeout(arguments.callee, 100);
}
}, 100);
}
schedule 有兩個參數:要執行的函式陣列,以及 this 所屬的上下文物件。函式陣列以佇列方式運作,計時器每次觸發就取出最前面的一個執行:
schedule([doSomething, doSomethingElse, doOneMoreThing], window);
很希望各家 JavaScript 函式庫都內建類似這樣的排程機制。YUI 在 3.0 就引入了 Queue 物件,可以透過計時器連續呼叫一組函式。
不管現有技術能幫我們把複雜流程切得多細,對開發者而言,理解並定位腳本失控的瓶頸仍然很重要。無論是迴圈太多、遞迴太深還是其他原因,你現在應該都知道該怎麼處理了。但也別忘了,這裡提到的技術與函式只是拋磚引玉,實務上你該依情境調整,才能發揮最大效果。