DIV CSS 佈局教程網

JS 物件陣列依屬性排序的高效能寫法
編輯:關於JavaScript     

要對一組物件依某個屬性排序,最直覺的作法是傳入比較函式給原生 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 成長,而每次比對若涉及屬性取值或計算,成本就被放大。

這裡的做法把「取值」與「排序」兩個階段分離:

  1. 先取出每個元素的屬性值,用它產生一個 String 物件。
  2. 把原元素掛在該 String 物件的 _obj 屬性上。
  3. 用這些 String 物件組成新陣列。
  4. 直接呼叫原生 sort 排序這個純字串陣列——此時不需要比較函式,走的是引擎最佳化的預設路徑。
  5. 在排好序的結果中依序取出 _obj,即得到排序後的元素陣列。

關鍵在於屬性值只被讀取一次,之後所有比較都發生在原生字串上。實測在 IE 環境中處理上千個節點,耗時幾乎可以忽略。

使用提醒

這套技巧有幾個限制值得注意:字串排序是字典序而非數值序,因此純數字屬性可能出現 "10" 排在 "9" 前面的情況,需要自行補零或改用數值包裝物件;另外 sourceIndex 屬於 IE 專屬屬性,跨瀏覽器時需替換為標準方案。理解這個「先映射、再排序、後還原」的骨架,比記住具體程式碼更有價值。

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