要對一組物件依某個屬性排序,最直覺的作法是傳入比較函式給原生 sort。但當資料量上千、屬性又需要計算時,反覆比對的開銷會相當可觀。本文示範一個換湯不換藥卻快很多的技巧:先把排序依據抽出來包成字串物件,掛上原物件參照,排完再取回。
<script>
/*
* 洗牌:產生一份亂數索引
*/
function getRandomPlayCard(m) {
var array1 = new Array(m);
for (var i = 0; i < m; i++) {
var rnd = Math.floor(Math.random() * (i + 0.99999));
array1[i] = array1[rnd];
array1[rnd] = i;
}
return array1;
}
/*
* 快速排序,按某個屬性,或按「取得排序依據的函式」來排序
* @method sortBy
* @static
* @param {array} arr 待處理陣列
* @param {string|function} prop 排序依據屬性,或取得依據的函式
* @param {boolean} desc 是否降序
* @return {array} 回傳排序後的新陣列
*/
var sortBy = function (arr, prop, desc) {
var props = [], ret = [], i = 0, len = arr.length;
if (typeof prop == 'string') {
for (; i < len; i++) {
var oI = arr[i];
(props[i] = new String(oI && oI[prop] || ''))._obj = oI;
}
} else if (typeof prop == 'function') {
for (; i < len; i++) {
var oI = arr[i];
(props[i] = new String(oI && prop(oI) || ''))._obj = oI;
}
} else {
throw '參數類型錯誤';
}
props.sort();
for (i = 0; i < len; i++) {
ret[i] = props[i]._obj;
}
if (desc) ret.reverse();
return ret;
};
for (var i = 0; i < 1000; i++) {
document.write('<div>a' + i + '</div>');
}
var els = document.getElementsByTagName('div');
var cards = getRandomPlayCard(els.length);
var randomEls = [];
for (var i = 0, len = cards.length; i < len; i++) randomEls[cards[i]] = els[i];
alert(['總數:', randomEls.length, '打亂順序後: ',
randomEls[0].innerHTML, randomEls[randomEls.length - 1].innerHTML]);
var d0 = new Date();
var elsSorted = sortBy(randomEls, function (el) { return el.sourceIndex + 100000000; });
alert(['總數:', elsSorted.length, '排序耗時:', new Date() - d0,
'重新排序後: ', elsSorted[0].innerHTML, elsSorted[elsSorted.length - 1].innerHTML]);
</script>
Array 原生的 sort,一旦傳入比較函式,無論內部採用哪種排序演算法,都必須反覆呼叫該函式進行兩兩比對。比較次數隨資料量呈 n log n 成長,而每次比對若涉及屬性取值或計算,成本就被放大。
這裡的做法把「取值」與「排序」兩個階段分離:
關鍵在於屬性值只被讀取一次,之後所有比較都發生在原生字串上。實測在 IE 環境中處理上千個節點,耗時幾乎可以忽略。
這套技巧有幾個限制值得注意:字串排序是字典序而非數值序,因此純數字屬性可能出現 "10" 排在 "9" 前面的情況,需要自行補零或改用數值包裝物件;另外 sourceIndex 屬於 IE 專屬屬性,跨瀏覽器時需替換為標準方案。理解這個「先映射、再排序、後還原」的骨架,比記住具體程式碼更有價值。