|
影響JavaScript性能的另外一個(gè)殺手就是遞歸，在上一節(jié)中提到采用memoization技術(shù)可以優(yōu)化計(jì)算數(shù)值的遞歸函數(shù)，但memoization不是萬能的，不是所有的遞歸函數(shù)都可以用memoization技術(shù)優(yōu)化，本文介紹了這些情況，并介紹了解決辦法，就是將遞歸轉(zhuǎn)換為迭代，同時(shí)需要注意，本文末尾介紹的方案不是最終的方案，還需要和上一節(jié)優(yōu)化循環(huán)的方案綜合起來才能達(dá)到最佳效果。
【原文】Speed up your JavaScript, Part 3
【作者】Nicholas C. Zakas
【譯文】http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
【譯者】明達(dá)
以下是對(duì)原文的翻譯：
遞歸是拖慢腳本運(yùn)行速度的大敵之一。太多的遞歸會(huì)讓瀏覽器變得越來越慢直到死掉或者莫名其妙的突然自動(dòng)退出，所以我們一定要解決在JavaScript中出現(xiàn)的這一系列性能問題。在這個(gè)系列文章的第二篇中，我曾經(jīng)簡(jiǎn)短的介紹了如何通過memoization技術(shù)來替代函數(shù)中太多的遞歸調(diào)用。memoization是一種可以緩存之前運(yùn)算結(jié)果的技術(shù)，這樣我們就不需要重新計(jì)算那些已經(jīng)計(jì)算過的結(jié)果。對(duì)于通過遞歸來進(jìn)行計(jì)算的函數(shù)，memoization簡(jiǎn)直是太有用了。我現(xiàn)在使用的memoizer是由 Crockford寫的，主要應(yīng)用在那些返回整數(shù)的遞歸運(yùn)算中。當(dāng)然并不是所有的遞歸函數(shù)都返回整數(shù)，所以我們需要一個(gè)更加通用的memoizer()函數(shù)來處理更多類型的遞歸函數(shù)。
function memoizer(fundamental, cache) {
cache = cache || {};
var shell = function(arg) {
if (! (arg in cache)) {
cache[arg] = fundamental(shell, arg);
}
return cache[arg];
};
return shell;}
這個(gè)版本的函數(shù)和Crockford寫的版本有一點(diǎn)點(diǎn)不同。首先，參數(shù)的順序被顛倒了，原有函數(shù)被設(shè)置為第一個(gè)參數(shù)，第二個(gè)參數(shù)是緩存對(duì)象，為可選參數(shù)，因?yàn)椴⒉皇撬械倪f歸函數(shù)都包含初始信息。在函數(shù)內(nèi)部，我將緩存對(duì)象的類型從數(shù)組轉(zhuǎn)換為對(duì)象，這樣這個(gè)版本就可以適應(yīng)那些不是返回整數(shù)的遞歸函數(shù)。在shell函數(shù)里，我使用了in操作符來判斷參數(shù)是否已經(jīng)包含在緩存里。這種寫法比測(cè)試類型不是undefined更加安全，因?yàn)閡ndefined是一個(gè)有效的返回值。我們還是用之前提到的斐波納契數(shù)列來做說明：
var fibonacci = memoizer(function(recur, n) {
return recur(n - 1) + recur(n - 2);
}, { "0": 0, "1": 1} );
同樣的，執(zhí)行fibonacci(40)這個(gè)函數(shù)，只會(huì)對(duì)原有的函數(shù)調(diào)用40次，而不是夸張的331,160,280次。memoization對(duì)于那些有著嚴(yán)格定義的結(jié)果集的遞歸算法來說，簡(jiǎn)直是棒極了。然而，確實(shí)還有很多遞歸算法不適合使用memoization方法來進(jìn)行優(yōu)化。
我在學(xué)校時(shí)的一位教授一直堅(jiān)持認(rèn)為，任何使用遞歸的情況，如果有需要，都可以使用迭代來代替。實(shí)際上，遞歸和迭代經(jīng)常會(huì)被作為互相彌補(bǔ)的方法，尤其是在另外一種出問題的情況下。將遞歸算法轉(zhuǎn)換為迭代算法的技術(shù)，也是和開發(fā)語言無關(guān)的。這對(duì)JavaScript來說是很重要的，因?yàn)楹芏鄸|西在執(zhí)行環(huán)境中是受到限制的（the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive.）。讓我們回顧一個(gè)典型的遞歸算法，比如說歸并排序，在JavaScript中實(shí)現(xiàn)這個(gè)算法需要下面的代碼：
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);
}
//采用遞歸實(shí)現(xiàn)的歸并排序算法
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));
}
調(diào)用mergeSort()函數(shù)處理一個(gè)數(shù)組，就可以返回經(jīng)過排序的數(shù)組。注意每次調(diào)用mergeSort()函數(shù)，都會(huì)有兩次遞歸調(diào)用。這個(gè)算法不可以使用memoization來進(jìn)行優(yōu)化，因?yàn)槊總�(gè)結(jié)果都只計(jì)算并使用一次，就算緩沖了結(jié)果也沒有什么用。如果你使用mergeSort()函數(shù)來處理一個(gè)包含100個(gè)元素的數(shù)組，總共會(huì)有199次調(diào)用。1000個(gè)元素的數(shù)組將會(huì)執(zhí)行1999次調(diào)用。在這種情況下，我們的解決方案是將遞歸算法轉(zhuǎn)換為迭代算法，也就是說要引入一些循環(huán)（關(guān)于算法，可以參考這篇《List Processing: Sort Again, Naturally》）：
// 采用迭代實(shí)現(xiàn)的歸并排序算法
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 = (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];
}
這個(gè)歸并排序算法實(shí)現(xiàn)使用了一系列循環(huán)來代替遞歸進(jìn)行排序。由于歸并排序首先要將數(shù)組拆分成若干只有一個(gè)元素的數(shù)組，這個(gè)方法更加明確的執(zhí)行了這個(gè)操作，而不是通過遞歸函數(shù)隱晦的完成。work數(shù)組被初始化為包含一堆只有一個(gè)元素?cái)?shù)組的數(shù)組。在循環(huán)中每次會(huì)合并兩個(gè)數(shù)組，并將合并后的結(jié)果放回 work數(shù)組中。當(dāng)函數(shù)執(zhí)行完成后，排序的結(jié)果會(huì)通過work數(shù)組中的第一個(gè)元素返回。在這個(gè)歸并排序的實(shí)現(xiàn)中，沒有使用任何遞歸，同樣也實(shí)現(xiàn)了這個(gè)算法。然而，這樣做卻引入了大量的循環(huán)，循環(huán)的次數(shù)基于要排序的數(shù)組中元素的個(gè)數(shù)，所以我們可能需要使用在 上篇討論過的技術(shù) 來進(jìn)行修訂，處理這些額外開銷。
總結(jié)一下基本原則，不管是什么時(shí)候使用遞歸的時(shí)候都應(yīng)該小心謹(jǐn)慎。memoization和迭代是代替遞歸的兩種解決方案，最直接的結(jié)果當(dāng)然就是避免那個(gè) 提示腳本失控的對(duì)話框。
本文鏈接：http://www.95time.cn/tech/web/2009/6462.asp 
出處：七月佑安
責(zé)任編輯：bluehearts
◎進(jìn)入論壇網(wǎng)頁制作、WEB標(biāo)準(zhǔn)化版塊參加討論，我還想發(fā)表評(píng)論。
|
