DIV CSS 佈局教程網

JavaScript 陣列去重四種寫法與效能比較
編輯:關於JavaScript     

陣列去重是面試常見題,也是實務上偶爾會遇到的需求。坊間流傳的寫法很多,但它們的時間複雜度差異不小。以下四種由慢到快排列,並說明各自的適用時機。

寫法一:indexOf 檢查(O(n²))

Array.prototype.unique1 = function () {
  const result = [];
  for (let i = 0; i < this.length; i++) {
    if (result.indexOf(this[i]) === -1) result.push(this[i]);
  }
  return result;
};

思路最直覺,但 indexOf 本身是線性搜尋,包在迴圈裡就變成平方級。資料量一大就會明顯變慢。

寫法二:用物件當雜湊表(O(n))

Array.prototype.unique2 = function () {
  const seen = {}, result = [];
  for (let i = 0; i < this.length; i++) {
    if (!seen[this[i]]) {
      seen[this[i]] = true;
      result.push(this[i]);
    }
  }
  return result;
};

把已經出現過的值當成物件的 key 記錄下來。屬性查找是常數時間,因此整體是線性的,這四種裡最快。

但要注意:物件 key 一律是字串,所以數字 1 和字串 '1' 會被視為同一項。另外 seen['toString'] 這類繼承而來的屬性會誤判,穩妥寫法是改用 Set(見下)或 Object.create(null)。

寫法三:indexOf 首次出現位置(O(n²))

Array.prototype.unique3 = function () {
  const result = [this[0]];
  for (let i = 1; i < this.length; i++) {
    if (this.indexOf(this[i]) === i) result.push(this[i]);
  }
  return result;
};

原理是「若某項第一次出現的位置正好是當前索引,它就是首次出現」。看起來比寫法一聰明,但 indexOf 仍舊是線性搜尋,複雜度一樣是平方級。

寫法四:先排序再比鄰(O(n log n))

Array.prototype.unique4 = function () {
  const sorted = this.slice().sort();
  const result = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] !== result[result.length - 1]) result.push(sorted[i]);
  }
  return result;
};

排序後重複項必然相鄰,因此只需比對前一個。排序本身是 n log n,實測通常比寫法一、三快,但仍是寫法二的三倍左右。

注意這裡加了 slice():直接 this.sort() 會改動原陣列,這是原型擴充最容易被詬病的副作用。

現代寫法:Set

ES2015 之後,這個問題已經不需要自己寫了:

const arr = [1, 2, 2, 2, 3, 3, 4, 5];

[...new Set(arr)];            // [1, 2, 3, 4, 5]
Array.from(new Set(arr));     // 同上,另一種轉回陣列的寫法

Set 天生不允許重複,內部用雜湊實作,時間複雜度 O(n),而且用 SameValueZero 演算法比較,所以 NaN 能被正確去重(indexOf 做不到),物件與陣列也能各自獨立保留。

要自訂比較邏輯(例如依 id 去重物件)時,可以搭配 filter 或直接操作 Map:

const byId = arr.filter((item, i, list) =>
  list.findIndex(x => x.id === item.id) === i
);

該不該擴充 Array.prototype

原始寫法把 unique 掛在 Array.prototype 上,看起來呼叫很順,但實務上不建議:一旦與其他函式庫或 polyfill 撞名,就會出現難以追蹤的衝突;而且 for...in 遍歷陣列時會把這個方法也列舉出來。改成獨立函式 unique(arr) 或用 Set,都是更安全的选择。

總結一句:新專案直接用 new Set();面試時能說出「indexOf 是平方級、雜湊是線性、排序是 n log n」這三種複雜度的差別,比背出任何一段程式碼都有說服力。

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