DIV CSS 佈局教程網

JavaScript 組件實作:Smart Queue 的編碼與排序演算法
編輯:JavaScript綜合知識     

前面討論了佇列管理組件的設計,並給它取名為 Smart Queue。這次要把設計化為程式碼,而其中最有趣的部分,是如何用拓撲排序處理任務之間的相依關係。

檔案布局的考量

第一步是決定程式碼怎麼拆分。之所以要拆,一方面是為了區分「外部程式碼」與「組件本體」,另一方面分散到獨立檔案也方便日後維護——當你希望在現有功能之上擴充新能力、同時保持對外介面不變時,把新程式碼寫進獨立檔案是最省事的選擇。

建立命名空間

var SmartQueue = window.SmartQueue || {};
SmartQueue.version = '0.1';

初始化時若遇到命名空間衝突就沿用既有物件。這通常是由於重複引入組件導致的,沿用即可;最壞情況下若頁面上另有同名物件,則會被覆蓋。順帶記上一個版本號。

建立三個優先級佇列

var Q = SmartQueue.Queue = [[], [], []];

三個空陣列分別對應低、中、高三種優先級,並建立一個簡寫 Q,後續以 Q[n] 直接存取。

Task 建構函式

主角登場。這個建構函式支援兩種呼叫方式:傳入多個參數,或傳入一個物件(含部分屬性的「雛形」)。

var _setupTask = function (fn, level, name, dependencies) {
    if (typeof fn !== "function") {
        throw new Error('Invalid argument type: fn.');
    }
    this.fn = fn;
    this.level = _validateLevel(level) ? level : LEVEL_NORMAL;
    this.name = (typeof name === "string" && name) ? name : 't' + _id++;
    // dependencies 可能是 Object,故用 instanceof 判斷
    this.dependencies = dependencies instanceof Array ? dependencies : [];
};

var T = SmartQueue.Task = function (task) {
    if (arguments.length > 1) {
        _setupTask.apply(this, arguments);
    } else {
        _setupTask.call(this, task.fn, task.level, task.name, task.dependencies);
    }
    // 允許自訂執行時的 context 與傳入資料
    this.context = task.context || window;
    this.data = task.data || {};
};

這樣一來,原本的多參數寫法繼續可用,而想偷懶的人可以只傳必要屬性:

var task1 = new SmartQueue.Task({ fn: obj.fn, dependencies: obj.dependencies });

關鍵在 apply/call——這是 JavaScript 在方法之間傳遞「上下文」的利器,值得細細體會。

在原型上定義屬性與方法

JavaScript 物件的三段式是:定義建構函式 → 在原型上定義屬性與方法 → new 出物件來用。屬性已在 _setupTask 中處理,接著補上原型方法:

T.prototype = {
    enabled: true,

    register: function () {
        var queue = Q[this.level];
        if (_findTask(queue, this.name) !== -1) {
            throw new Error('Specified name exists: ' + this.name);
        }
        queue.push(this);
    },

    changeTo: function (level) {
        if (!_validateLevel(level)) throw new Error('Invalid argument: level');
        level = parseInt(level, 10);
        if (this.level === level) return;
        Q[this.level].remove(this);
        this.level = level;
        this.register();
    },

    execute: function () {
        if (this.enabled) {
            this.fn.call(this.context, this.data);   // 傳入 context 與 data
        }
    },

    toString: function () {
        var str = this.name;
        if (this.dependencies.length) {
            str += ' depends on: [' + this.dependencies.join(', ') + ']';
        }
        return str;
    }
};

這裡值得特別一提的是 toString。它看似最不受重視,卻有多重價值:能讓除錯器顯示有意義的資訊、方便把物件摘要寫進日誌,在統一的編碼風格下還能少寫一些程式碼。

SmartQueue 本體的方法

SmartQueue.init = function () {
    Q.forEach(function (queue) {
        queue.length = 0;      // 清空並釋放所有元素
    });
};

這裡用了 JavaScript 1.6 為陣列提供的 forEach。把 length 設為 0 會清空陣列並釋放其中的項。

核心:fire() 與拓撲排序

最後的 fire 是整個組件最主要的函式,負責排序所有佇列並逐個執行。排序的目的是確保被相依的任務一定先於依賴它的任務執行。這是一個典型的深度優先拓撲排序問題。

var _dirty = true,   // 旗標:佇列是否需要重新排序
    _sorted = [], index;

var _visit = function (queue, task) {
    if (task._visited >= 1) {
        task._visited++;
        return;
    }
    task._visited = 1;

    // 找出並訪問所有相依任務
    var dependencies = [], i;
    task.dependencies.forEach(function (dependency) {
        i = _findTask(queue, dependency);
        if (i != -1) dependencies.push(queue[i]);
    });
    dependencies.forEach(function (t) { _visit(queue, t); });

    if (task._visited === 1) {
        _sorted[index].push(task);
    }
};

var _sort = function (suppress) {
    for (index = LEVEL_LOW; index <= LEVEL_HIGH; index++) {
        var queue = Q[index];
        _sorted[index] = [];
        queue.forEach(function (task) { _visit(queue, task); });

        if (!suppress && queue.length > _sorted[index].length) {
            throw new Error('Cycle found in queue: ' + queue);
        }
    }
};

演算法邏輯

圖片來自維基百科

維基百科提供的深度優先排序演算法大致如下:

  1. 訪問每一個待排序節點
  2. 若已訪問過則返回
  3. 否則標記為已訪問
  4. 找出它連結(這裡是相依)的每個節點,遞迴訪問
  5. 訪問完畢後把當前節點加入已排序列表
  6. 繼續下一個節點

如何偵測循環依賴

原始演算法無法偵測循環依賴。若 A 依賴 B、B 依賴 C、C 又依賴 A,這三個節點形成迴圈,遞迴會陷入死循環。

僅靠「是否已訪問」這個布林旗標,並不足以判斷。因為從 C 回到 A 時,A 確實已訪問過——但這可能只是表示 A 是其他已處理完的節點,C 無從得知 A 是否在自己的上游鏈上。

解法是把「是否已訪問」改成訪問計數(task._visited++)。只在節點被訪問過恰好一次時(task._visited === 1)才將它加入已排序列表;全部走訪完後,若待排序的節點數多於已排序的(queue.length > _sorted[index].length),就代表多出的那些節點參與了循環依賴。這正是上面程式碼中那個 throw new Error('Cycle found...') 的由來。

使用方式

var t1 = new SmartQueue.Task(function () {
    alert("Hello, world!");
});

var t2 = new SmartQueue.Task(function () {
    alert("High level task has name");
}, 2, 'myname');

t1.register();
t2.register();

SmartQueue.fire();

任務相依(dependencies)等進階功能就留給讀者自行發掘了。本文貼出的都是局部片段,部分輔助方法未列出。

設計上的觀察

這個組件在當時的背景下是合理的選擇——它用極少的程式碼提供了優先級與相依排序,並把 context、data 的注入設計得很靈活。若今天要重新實作同樣的功能,有幾點會不一樣:優先級佇列可以改用正式的 Queue 結構而非陣列;相依圖的排序可直接用 Kahn 演算法(以入度為基礎的迭代式拓撲排序),它能更自然地偵測迴圈且不必遞迴;錯誤處理則應改用 Error 子類別並附上形成迴圈的具體節點清單,方便就地除錯。

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