把一批 DOM 節點依文件中的實際出現順序重新排列,聽起來簡單,做起來卻牽涉瀏覽器差異與演算法選擇。本文記錄兩個版本的實作思路與效能對比。
靈感來自網路上「陣列快速依屬性排序」的討論。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 與動態寫入屬性的成本。
改進方向很明確:不再為每個節點標記屬性去統計共同祖先,而是直接為每個節點建立「到文件根節點的完整祖先鏈」,再從鏈的尾端對齊比較,找出第一個分歧點。測試對象為擁有機百餘個節點的文件,結果比 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,一行就能完成,但理解這段演進過程,對建立效能分析能力仍很有幫助。