DIV CSS 佈局教程網

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

把陣列裡重複的元素清掉是很常見的需求。以下用四種思路各寫一版,並實測在 2000 筆資料下的耗時差異。

<script language="JavaScript">
var arrData = new Array();
for (var i = 0; i < 1000; i++) {
  arrData[arrData.length] = String.fromCharCode(Math.floor(Math.random() * 26) + 97);
}

// 方法一:兩層迴圈,逐一比對後移除
function myArray_Unique(myArray) {
  var haha = myArray;
  for (var i = 0; i < myArray.length; i++) {
    for (var j = 0; j < myArray.length; j++) {
      temp = myArray[i];
      if ((i + j + 1) < myArray.length && temp == myArray[i + j + 1]) {
        haha.splice(i + j + 1, 1);
      }
    }
  }
  return haha;
}

// 方法二:複製一份,固定待比較項,後面相同的就刪掉
function getUnique(someArray) {
  var tempArray = someArray.slice(0);
  for (var i = 0; i < tempArray.length; i++) {
    for (var j = i + 1; j < tempArray.length; ) {
      if (tempArray[j] == tempArray[i]) {
        tempArray.splice(j, 1); // 刪除後元素自動前移,j 不動
      } else {
        j++;
      }
    }
  }
  return tempArray;
}

// 方法三:正則表達式(僅適用字串陣列)
function getUnique2(A) {
  var str = "\x0f" + A.join("\x0f");
  while (/(\w+)[^\1]*\1/.test(str)) {
    str = str.replace("\x0f" + RegExp.$1, "");
  }
  return str.substr(1).split("\x0f");
}

// 方法四:用關聯物件當雜湊表
Array.prototype.unique = function() {
  var o = new Object();
  for (var i = 0, j = 0; i < this.length; i++) {
    if (typeof o[this[i]] == 'undefined') { o[this[i]] = j++; }
  }
  this.length = 0;
  for (var key in o) { this[o[key]] = key; }
  return this;
};

var d = new Date().getTime();
document.write(myArray_Unique(arrData));
d = new Date().getTime() - d;
document.write("<br/>方法一耗時 " + d + " 毫秒<br/>");   // 約 370~390ms

d = new Date().getTime();
document.write(getUnique(arrData));
d = new Date().getTime() - d;
document.write("<br/>方法二耗時 " + d + " 毫秒<br/>");   // 約 360~380ms

d = new Date().getTime();
document.write(getUnique2(arrData));
d = new Date().getTime() - d;
document.write("<br/>方法三(正則)耗時 " + d + " 毫秒<br/>"); // 約 80ms

d = new Date().getTime();
document.write(arrData.unique());
d = new Date().getTime() - d;
document.write("<br/>方法四(關聯結構)耗時 " + d + " 毫秒");  // 約 0~10ms
</script>

效能差異的原因

前兩種都是 O(n²) 的巢狀迴圈,還搭配 splice(每次刪除都要搬移元素),資料量一大就明顯變慢。方法三用正則一次比對,快了幾倍。方法四之所以快到幾乎即時,是因為它以雜湊表做查找,把時間複雜度降到接近 O(n)。

方法四的兩個陷阱

第一,用物件當雜湊表時,鍵會被轉成字串,因此數字 1 與字串 "1" 會被視為同一項;__proto__、constructor 這類名稱也會與原型屬性衝突。第二,直接擴充 Array.prototype 會汙染全域,若其他程式有用 for...in 遍歷陣列就會出問題,這是套件開發的大忌。

現在只需要一行

ES6 的 Set 天生就不允許重複值,這個問題已經被語言本身解決了:

const arr = ['a', 'b', 'a', 'c', 'b'];

// 寫法一:Set + 展開
const unique1 = [...new Set(arr)];

// 寫法二:Array.from
const unique2 = Array.from(new Set(arr));

console.log(unique1); // ["a", "b", "c"]

它使用真正的 SameValueZero 演算法比對,NaN 也能正確去重(indexOf 找不到 NaN),物件則以參考位址判斷。若要去重物件陣列,用 Map 或以某個欄位當鍵值分組即可:

const users = [{id:1}, {id:2}, {id:1}];
const byId = [...new Map(users.map(u => [u.id, u])).values()];
console.log(byId); // [{id:1}, {id:2}]

除非要支援非常舊的環境,否則不必再手寫去重邏輯了。上面四種寫法的價值,在於理解「為什麼雜湊法比巢狀迴圈快」這件事。

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