DIV CSS 佈局教程網

JS 陣列去重的四種實作與效能比較
編輯:關於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;
};

解法二:用雜湊表記錄已出現的項

Array.prototype.unique2 = function () {
  var n = {}, r = []; // 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++) {
    // 若第 i 項第一次出現的位置不是 i,即為重複項
    if (this.indexOf(this[i]) == i) n.push(this[i]);
  }
  return n;
};

效能分析

第一、三種都用到 indexOf,而 JS 引擎實作這個方法時必須從頭遍歷直到找到目標,資料量大時耗時可觀。第二種改用雜湊表,以鍵值查詢取代線性搜尋,速度明顯快得多,整體時間複雜度從 O(n²) 降到接近 O(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;
};

思路是先排序,再逐一比對相鄰兩值。sort 內部通常使用快速排序,整體複雜度約為 O(n log n)。實測執行時間約為第二種的三倍,但仍比第一、三種快上許多。

補充:現代寫法

今天不必再手寫這些。ES6 提供了兩行就能搞定的方案:

// 利用 Set 自動去重
var unique = [...new Set(arr)];

// 或用 filter
var unique2 = arr.filter(function (item, index) {
  return arr.indexOf(item) === index;
});

Set 底層基於雜湊實作,效率與解法二相當,且不會污染 Array.prototype。另外提醒:直接在原型上擴充內建物件,容易造成與第三方庫的命名衝突,即使要寫也建議改用獨立工具函數。

最後要注意的是,上述所有方法都使用嚴格相等比較,因此 NaN 與物件參照的去重行為需另行留意;Set 對 NaN 的處理較為直覺,這也是它值得優先採用的一點。

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