DIV CSS 佈局教程網

JavaScript 陣列去重的四種做法與效能比較
編輯:JavaScript綜合知識     

陣列去重是面試與實務中都常出現的需求。本文先限定在「同型別資料」的單純情境,整理四種常見寫法,再從效能角度做個比較——畢竟思路清楚之外,能不能跑得夠快才是工程上的重點。

四種實作

// 做法一:借助 indexOf 檢查是否已存在
Array.prototype.unique1 = function () {
  var n = [];
  for (var i = 0; i < this.length; i++) {
    if (n.indexOf(this[i]) == -1) n.push(this[i]);
  }
  return n;
};

// 做法二:用 object 當雜湊表
Array.prototype.unique2 = function () {
  var n = {}, r = [];
  for (var i = 0; i < this.length; i++) {
    if (!n[this[i]]) {
      n[this[i]] = true;
      r.push(this[i]);
    }
  }
  return r;
};

// 做法三:比較第一次出現的位置
Array.prototype.unique3 = function () {
  var n = [this[0]];
  for (var i = 1; i < this.length; i++) {
    if (this.indexOf(this[i]) == i) n.push(this[i]);
  }
  return n;
};

// 做法四:先排序,再比對相鄰元素
Array.prototype.unique4 = function () {
  this.sort();
  var re = [this[0]];
  for (var i = 1; i < this.length; i++) {
    if (this[i] !== re[re.length - 1]) re.push(this[i]);
  }
  return re;
};

var arr = [1, 2, 2, 2, 3, 3, 4, 5];
console.log(arr.unique1());  // [1, 2, 3, 4, 5]
console.log(arr.unique2());  // [1, 2, 3, 4, 5]
console.log(arr.unique3());  // [1, 2, 3, 4, 5]
console.log(arr.unique4());  // [1, 2, 3, 4, 5]

效能分析

做法一與做法三都依賴陣列的 indexOf。這個方法的實作方式是從頭開始逐一比對直到找到目標,因此每插入一個元素,整體就多一次線性掃描,資料量大時會明顯變慢。

做法二改用雜湊表:把出現過的值以下標形式存進 object,後續只需一次屬性查找即可判定。屬性存取的時間複雜度遠優於線性搜尋,因此在這四種寫法裡效能最好。

做法四的思路是先排序,再比較相鄰兩項是否相同。排序用的是 JS 原生的 sort(引擎內部一般為快速排序)。實測顯示,它的平均執行時間約為做法二的三倍,但仍明顯快過做法一與做法三。

幾個實務提醒

  • 直接改 prototype 不是好習慣。擴充內建物件容易造成命名衝突,也可能被第三方套件覆蓋。改成 function unique(arr){...} 這類獨立函式更安全。
  • 做法四會破壞原陣列順序。若後續邏輯依賴原始排序,記得先複製一份再排序。
  • 現代寫法可以更簡潔。ES6 之後,同型別去重一行就夠:[...new Set(arr)];物件陣列則可用 filter 搭配 findIndex 或 Map 來處理。

理解這四種做法的取捨,重點不在背起來,而在建立「資料結構選擇會直接影響效能」這條直覺。

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