把陣列裡重複的元素清掉是很常見的需求。以下用四種思路各寫一版,並實測在 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}]
除非要支援非常舊的環境,否則不必再手寫去重邏輯了。上面四種寫法的價值,在於理解「為什麼雜湊法比巢狀迴圈快」這件事。