去除陣列中重複的項目是常見需求,實作起來不難,但不同寫法的效能差距可以高達數十倍。以下從最直覺的雙重迴圈出發,逐步優化。
最直覺的做法是兩層迴圈,逐一比對後續元素是否相同。對於小陣列,這樣做完全沒問題,程式碼也一目了然。
但當陣列有上萬個元素時,雙重迴圈的時間複雜度是 O(n²),效率極為低下。
JavaScript 物件本質上是雜湊表,查找與寫入接近 O(1)。利用這個特性,可以把整個去重降到 O(n):
<script>
function unique(data) {
data = data || [];
var a = {};
for (var i = 0; i < data.length; i++) {
var v = data[i];
if (typeof (a[v]) == 'undefined') {
a[v] = 1;
}
}
data.length = 0;
for (var i in a) {
data[data.length] = i;
}
return data;
}
function test() {
var arr = [9, 1, 3, 8, 7, 7, 6, 6, 5, 7, 8, 8, 7, 4, 3, 1];
var arr1 = unique(arr);
alert(arr1.join(","));
}
test();
</script>
輸出結果為 9,1,3,8,7,6,5,4。
手法是把每個值當成物件的鍵,利用「鍵唯一」的特性去重,最後再用 for-in 把鍵值取回陣列。
Array.prototype.delRepeat = function () {
var newArray = new Array();
var len = this.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (this[i] === this[j]) {
j = ++i;
}
}
newArray.push(this[i]);
}
return newArray;
};
很明顯,這裡又是一個 for 迴圈內嵌另一個 for 迴圈,大資料量下必然耗時。
Array.prototype.delRepeat = function () {
var newArray = [];
var provisionalTable = {};
for (var i = 0, item; (item = this[i]) != null; i++) {
if (!provisionalTable[item]) {
newArray.push(item);
provisionalTable[item] = true;
}
}
return newArray;
};
使用一個臨時的 provisionalTable 物件,把陣列的值作為鍵值。若對應的值不存在,就把這個項目 push 進新陣列並標記為已存在。效率大幅提升。
誠實說,上面幾個版本都有問題,值得逐一指出。
第一,型別混淆。假設陣列是 [6, "6"],這兩個值在作為物件鍵時都會被轉成 "6",因此會被誤判為重複而刪掉一個。物件的鍵只能是字串,這是雜湊去重法的根本限制。
第二,null 提前終止。迴圈條件 (item = this[i]) != null 會在遇到 null 或 undefined 時直接結束,後面的元素全部被忽略。稀疏陣列或含 null 的陣列會得到錯誤結果。
第三,原型污染風險。若物件原型上被擴充了屬性,for-in 會把它們一起枚舉出來。用 Object.create(null) 建立無原型的物件,或改用 Map,可以避開這個問題。
第四,擴充 Array.prototype 的危險。為原型加上可枚舉屬性,會讓所有使用 for-in 遍歷陣列的程式碼都受到影響。若真要擴充,應以 Object.defineProperty 設為不可枚舉。
ES6 提供了 Set,語意明確且正確處理各種型別:
// 最簡潔 var arr1 = [...new Set([9, 1, 3, 8, 7, 7, 6])]; // [9,1,3,8,7,6] // 用 Array.from 亦可 var arr2 = Array.from(new Set([9, 1, 3, 8, 7, 7, 6]));
Set 使用 SameValueZero 演算法比較,因此 6 與 "6" 是兩個不同項目,NaN 也能正確被視為同一個值。這正好解決了前述所有 bug。
需要自訂比較規則(例如依 id 去重物件陣列)時,用 Map 或 reduce:
// 依物件某屬性去重 var uniqueBy = (arr, key) => [ ...new Map(arr.map(item => [item[key], item])).values() ]; // 保留首次出現的物件 var result = arr.filter((item, i, self) => self.findIndex(x => x.id === item.id) === i );
第一個寫法利用 Map 的鍵唯一性,一行完成,時間複雜度 O(n)。第二個用 findIndex 是 O(n²),資料量大時應改用第一種。
從 O(n²) 的雙重迴圈,到 O(n) 的雜湊查表,差距在萬筆資料以上是數十倍等級。但真正重要的收穫不是「哪個寫法快」,而是理解了為什麼快:把「兩兩比對」換成「查表標記」,本質上是用額外的空間換取時間。而 Set/Map 的出現,讓我們不必再手動處理型別、null、原型污染這些細節——語言標準已經幫我們做對了。
最後提醒:不要修改 Array.prototype。這是 JavaScript 社群的共識,原因如上所述。要擴充就寫成獨立函式或靜態方法。