DIV CSS 佈局教程網

JavaScript 如何重構巢狀迴圈與遞迴
編輯:關於JavaScript     

這是 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 物件,可以透過計時器連續呼叫一組函式。

不管現有技術能幫我們把複雜流程切得多細,對開發者而言,理解並定位腳本失控的瓶頸仍然很重要。無論是迴圈太多、遞迴太深還是其他原因,你現在應該都知道該怎麼處理了。但也別忘了,這裡提到的技術與函式只是拋磚引玉,實務上你該依情境調整,才能發揮最大效果。

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