DIV CSS 佈局教程網

JavaScript 陣列去重的三種實作與效能實測比較
編輯:JavaScript綜合知識     

在資料處理、標籤篩選、清單渲染這類場景裡,「把重複項目清掉」幾乎是每個前端工程師都會遇到的需求。問題在於,網路上流傳的寫法少說有五六種,各自的取捨卻很少被講清楚。本文整理三種常見的陣列去重思維,並用十萬筆資料實測它們的耗時差異,最後補充現代 JavaScript 更簡潔的替代方案。

方法一:以物件當雜湊表

核心想法是拿一個空物件當索引表,走訪陣列時把每個值當成鍵去查表,查不到就視為首次出現。由於物件屬性讀寫接近常數時間,整體只需一次迴圈。

Array.prototype.unique = function () {
  var newArr = [], obj = {};
  for (var i = 0, len = this.length; i < len; i++) {
    if (!obj[this[i]]) {
      newArr.push(this[i]);
      obj[this[i]] = true;
    }
  }
  return newArr;
}; // 約 10ms

但這個版本有兩個盲點:數字 1 與字串 '1' 會被當成同一個鍵;而 {x:1} 這類物件會被統一轉成 "[object Object]",因此不同物件也會互相吃掉。

改良方式是把型別一起拼進鍵名,讓型別不同的值互不干擾:

Array.prototype.unique = function () {
  var newArr = [], obj = {};
  for (var i = 0, len = this.length; i < len; i++) {
    var key = typeof (this[i]) + this[i];
    if (!obj[key]) {
      newArr.push(this[i]);
      obj[key] = this[i];
    }
  }
  return newArr;
}; // 約 30ms

代價是多了字串拼接與型別判斷,速度略慢,但語意正確得多。注意物件型別仍然無法真正區分,這是所有雜湊法的共同極限。

方法二:雙層迴圈逐一比對

最直覺的做法:外層固定一個位置,內層往後掃,遇到相同就 splice 移除並把索引回退一格。

Array.prototype.unique = function () {
  var newArr = this.concat();
  for (var i = 0, len = newArr.length; i < len; i++) {
    for (var j = i + 1; j < newArr.length; j++) {
      if (newArr[i] === newArr[j]) {
        newArr.splice(j, 1);
        j--;
      }
    }
  }
  return newArr;
}; // 約 250ms

它用 === 嚴格比較,因此結果最貼近「真正相等」的定義,連物件參考也分得清。缺點是時間複雜度退化成 O(n²),加上 splice 本身要搬移元素,資料量一大就非常吃力。

方法三:借助 indexOf

把結果收進暫存陣列,用 indexOf 判斷是否已存在,不存在才推入。程式碼短、可讀性高。

Array.prototype.unique = function () {
  var newArr = [];
  for (var i = 0, len = this.length; i < len; i++) {
    if (newArr.indexOf(this[i]) === -1) {
      newArr.push(this[i]);
    }
  }
  return newArr;
}; // 約 25ms

它同樣是嚴格相等比較,效能比雙層迴圈好一截,但仍然是 O(n²) 量級,而且無法處理物件內容相同的情況。

實測環境與結果

測試用的原始資料是一份混合了數字、字串與物件的樣本陣列,再用亂數反覆取樣湊成十萬筆:

var arr = [], num;
for (var i = 0; i < 100000; i++) {
  num = Math.floor(Math.random() * 50);
  arr.push(arr0[num]);
}

var t1 = new Date().getTime();
arr.unique();
var t2 = new Date().getTime();
console.log(t2 - t1);

同一份資料下,雜湊法約 10~30ms,indexOf 約 25ms,雙層迴圈則要 250ms 上下。差距接近十倍,資料量越大越明顯。

那麼今天該怎麼寫?

上述三種寫法都出自 Array.prototype 擴充的年代,如今有更好的選擇。ES6 的 Set 天生不含重複值,一行就能完成去重:

var unique = [...new Set(arr)];

如果需要依特定欄位判斷重複(例如以 id 為鍵),可以用 filter 搭配 Map 或索引物件:

var byId = arr.filter(function (item, i, list) {
  return list.findIndex(function (o) { return o.id === item.id; }) === i;
});

結論很簡單:追求簡潔與效能就用 Set;需要自訂比較邏輯時,用索引物件搭配一次走訪;只有在必須嚴格區分物件參考、且資料量不大的舊專案裡,雙層迴圈才還有一席之地。另外,直接改寫原生 prototype 容易與第三方套件互撞,實務上建議改成獨立工具函式。

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