DIV CSS 佈局教程網

JavaScript DOM 節點排序:從 sourceIndex 到最近共同祖先的兩版演進
編輯:關於JavaScript     

把一批 DOM 節點依文件中的實際出現順序重新排列,聽起來簡單,做起來卻牽涉瀏覽器差異與演算法選擇。本文記錄兩個版本的實作思路與效能對比。

第一版:借力 sourceIndex

靈感來自網路上「陣列快速依屬性排序」的討論。IE 的每個元素都有 sourceIndex,代表它在文件中的序號,於是排序就變成單純的數字排序:

var hasDuplicate = false;
var sortBy = function (nodes) {
  var result = [], array = [], n = nodes.length, i = n, node;
  while (node = nodes[--n]) {
    (array[n] = new Number(~~node.sourceIndex))._ = node;
  }
  array.sort(function (a, b) {
    if (a === b) hasDuplicate = true;
    return a - b;
  });
  while (i) result[--i] = array[i]._;
  return result;
}

問題是標準瀏覽器並不支援 sourceIndex,IE 中處理 XML 文件時也拿不到這個屬性。於是我們必須改為比較節點的 parentNode 與 nextSibling。但若只做兩兩比較,速度反而下降,因此要把比較的對象提升到「最近共同祖先(LCA)的孩子們」。

過渡版:先求最近共同祖先

這一版依據社群提供的 LCA 思路實作,整體架構參考自前輩的分享:

var tick = 0, hasDuplicate = false;
var Rage = {
  getLCA: function (nodes) {
    var hash = {}, i = 0,
        attr = "data-find" + (++tick),
        length = nodes.length, node, parent, counter = 0, uuid;
    while (node = nodes[i++]) {
      parent = node;
      while (parent) {
        if (parent.nodeType === 1) break;
        uuid = parent.getAttribute(attr);
        if (!uuid) {
          uuid = "_" + (++counter);
          parent.setAttribute(attr, uuid);
          hash[uuid] = { node: parent, count: 1 };
        } else {
          hash[uuid].count++;
        }
        parent = parent.parentNode;
      }
    }
    for (var i in hash) {
      if (hash[i].count === length) return hash[i].node;
    }
  },
  getList: function (nodes, parent) { /* 取得元素到共同祖先之間的祖先鏈 */ },
  getLists: function () { /* 對每個節點呼叫 getList */ },
  sortList: function (a, b) {
    var n = Math.min(a.length, b.length), ap, bp;
    for (var i = 0; i < n; i++) {
      ap = a[i]; bp = b[i];
      if (ap !== bp) {
        while (ap = ap.nextSibling) {
          if (ap === bp) return -1;
        }
        return 1;
      }
    }
    return a.length - b.length;
  },
  uniqueSort: function (nodes) { /* 主流程 */ }
}

實際效果不如預期,比 jQuery 的 sortOrder 還慢,推測瓶頸在反覆求 LCA 與動態寫入屬性的成本。

第二版:砍掉 LCA 計算,終於快上三倍

改進方向很明確:不再為每個節點標記屬性去統計共同祖先,而是直接為每個節點建立「到文件根節點的完整祖先鏈」,再從鏈的尾端對齊比較,找出第一個分歧點。測試對象為擁有機百餘個節點的文件,結果比 jQuery 快約三倍。

var hasDuplicate = false;
var Rage = {
  getList: function (node) {
    var list = [];
    while (node) {
      if (node.nodeType === 9) break;   // 抵達 document 節點即停止
      list.unshift(node);
      node = node.parentNode;
    }
    return list;
  },
  getLists: function (nodes) {
    var lists = [], getList = Rage.getList, i = 0, node;
    while (node = nodes[i++]) lists[lists.length] = getList(node);
    return lists;
  },
  sliceList: function (lists, num) {
    var result = [], i = 0, list;
    while (list = lists[i++]) {
      list = list.slice(num);
      if (list.length) result[result.length] = list;
    }
    return result;
  },
  sortList: function (a, b) {
    var n = Math.min(a.length, b.length), ap, bp;
    for (var i = 0; i < n; i++) {
      ap = a[i]; bp = b[i];
      if (ap !== bp) {
        while (ap = ap.nextSibling) {
          if (ap === bp) return -1;
        }
        return 1;
      }
    }
    return a.length - b.length;
  },
  uniqueSort: function (nodes) {
    var length = nodes.length;
    var lists = Rage.getLists(nodes);
    lists.sort(function (a, b) { return a.length - b.length; });

    var depth = lists[0].length, parent, cut, ii = 0;
    for (var i = 0; i < depth; i++) {
      parent = lists[0][i];
      cut = true;
      for (var j = 1; j < length; j++) {
        if (parent !== lists[j][i]) { cut = false; break; }
      }
      if (cut) ii++; else break;
    }

    var LCA = lists[0][ii - 1];
    lists = Rage.sliceList(lists, ii);
    lists.sort(Rage.sortList);

    var list, i = 0, result = [];
    while (list = lists[i++]) result[result.length] = list.pop();

    if (result.length !== length) {
      result.unshift(LCA);
      if (result.length != length) hasDuplicate = true;
    }
    return result;
  }
}

演進帶來的啟示

第一版依賴瀏覽器私有的 sourceIndex,遷移性最差;過渡版試圖用 LCA 抽象化,卻因為反覆操作屬性與節點指針而變慢;第二版放棄「求 LCA」這個中間步驟,改成一次性建立完整祖先鏈再對齊裁剪,反而更快。

這個過程說明了效能優化的常見套路:真正昂貴的往往不是演算法的漸進複雜度,而是隱藏的常數成本——屬性讀寫、DOM 查詢、反覆的指標跳動。少做一次 DOM 屬性寫入,往往比改善一層迴圈結構更有效。若今天要重寫這段功能,標準瀏覽器可直接使用 compareDocumentPosition,一行就能完成,但理解這段演進過程,對建立效能分析能力仍很有幫助。

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