面試時經常被問到「用 JavaScript 幫陣列去重」,這大概是因為它同時考驗了語法熟悉度與效能概念。以下整理常見的幾種做法,並附上一組實測數據。
最直覺的做法:準備一個空陣列裝結果,外層迴圈遍歷原陣列,每取出一個元素就拿去和結果陣列逐一比對,若沒有重複才放進去。
Array.prototype.unique1 = function () {
// 建立一個新陣列,存放結果
var newArray = [this[0]];
// for 迴圈,每次從原陣列取出一個元素,用來與結果陣列比對
for (var i = 1; i < this.length; i++) {
var repeat = false;
for (var j=0; j < newArray.length; j++) {
// 原陣列取出的元素與結果陣列元素相同
if(this[i] == newArray[j]) {
repeat = true;
break;
}
}
if(!repeat) {
// 如果結果陣列中沒有該元素,則放入結果陣列
newArray.push(this[i]);
}
}
return newArray;
}
測試用的陣列:
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1',`2`]; arr.unique1(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5]
這種寫法據說比較耗時。實際測一下(測試碼寫得比較隨便):
function test () {
var arr = [];
for (var i = 0; i < 1000000; i++) {
arr.push(Math.round(Math.random(i) * 10000));
}
doTest(arr, 1);
}
function doTest(arr, n) {
var tStart = (new Date()).getTime();
var re = arr.unique1();
var tEnd = (new Date()).getTime();
console.log('雙重迴圈去重方法使用時間是:' + (tEnd - tStart) + 'ms');
return re;
}
test();
在 Chrome 上跑出來的時間是 11031ms。
同樣的思路可以用 forEach() 搭配 indexOf() 改寫:
function unique1() {
var newArray = [];
this.forEach(function (index) {
if (newArray.indexOf(index) == -1) {
newArray.push(index);
}
});
return newArray;
}
透過 unique1.apply(arr) 或 unique1.call(arr) 呼叫。效率好得多,同樣的測試資料只要 5423ms,幾乎快了一半。
先用 sort() 排序,讓重複值相鄰,之後只需檢查當前元素是否等於結果陣列的最後一項。
Array.prototype.unique2 = function () {
// 原陣列先排序
this.sort();
// 建立一個新陣列存放結果
var newArray = [];
for (var i = 1; i < this.length; i++) {
// 因為已排序,重複元素會落在相鄰位置
if(this[i] !== newArray[newArray.length - 1]) {
newArray.push(this[i]);
}
}
return newArray;
}
例如:
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique2(); // ["1", 1, 2, "2", 3, 32, 34, 4, 5, 56, "a", "b", "c"]
這個方法有兩個副作用:一是輸出的陣列是排序過的;二是 '1' 和 1 這類值在排序後難以區分。實測 1232ms。
思路是建立一個空物件當查表用:遍歷原陣列時,把每個元素當成物件的鍵,若不存在就推進結果陣列,並把該鍵標記為 1。
Array.prototype.unique3 = function () {
// 建立一個新陣列存放結果
var newArray = [];
// 建立一個空物件
var object = {};
// 每次取出一個元素與物件比對
// 若不重複,就放入結果陣列,同時把該元素作為屬性名並賦值 1
for (var i = 0; i < this.length; i++){
// 檢測 object 中是否已包含該元素
if(!object[typeof(this[i]) + this[i]]) {
newArray.push(this[i]);
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}
跑前面的範例:
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique3(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]
注意這裡用 typeof 加上值本身當鍵,正好規避了 a[1] 與 a["1"] 被視為同一個鍵的問題。實測 621ms,是幾種寫法裡最快的,代價是多佔一些記憶體。
// 方法四
Array.prototype.unique4 = function () {
var newArray = [];
for (var i = 0; i < this.length; i++) {
for (j = i + 1; j < this.length; j++) {
// 若找到相同元素,跳過 i
if(this[i] === this[j]) {
j = ++i;
}
}
newArray.push(this[i]);
}
return newArray;
}
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique4(); // ["a", 1, 3, 4, 56, 32, 34, 2, "b", "c", 5, "1", "2"]
同樣無法區分 1 與 '1'。
// 方法五
Array.prototype.unique5 = function () {
var newArray = [];
for (var i = 0; i < this.length; i++) {
var index = this[i];
// 若不在結果陣列中,才推進去
if (newArray.indexOf(index) === -1) {
newArray.push(index);
}
}
return newArray;
}
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique5(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]
實測 14361ms。
// 方法六
Array.prototype.unique6 = function () {
return this.reduce(function (newArray, index) {
if(newArray.indexOf(index) < 0) {
newArray.push(index);
}
return newArray;
},[]);
}
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique6(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]
實測 16490ms。
// 方法七
Array.prototype.unique7 = function(){
var newArray;
newArray = this.filter(function (ele,i,arr) {
return arr.indexOf(ele) === i;
});
return newArray;
}
var arr = [1,2,3,4,'a','b',1,3,4,56,32,34,2,'b','c',5,'1','2']; arr.unique7(); // [1, 2, 3, 4, "a", "b", 56, 32, 34, "c", 5, "1", "2"]
實測 13201ms。
寫法雖然多,但綜合效能來看,物件鍵值對(unique3)仍是較優秀的方案:
Array.prototype.unique3 = function () {
var newArray = [];
var object = {};
for (var i = 0; i < this.length; i++){
if(!object[typeof(this[i]) + this[i]]) {
newArray.push(this[i]);
object[typeof(this[i]) + this[i]] = 1;
}
}
return newArray;
}
而在 ES6 之後,還有更簡潔的寫法:
// ES6
function unique (arr) {
const seen = new Map()
return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}
// 或者
function unique (arr) {
return Array.from(new Set(arr))
}
以上就是陣列去重的幾種常見做法與實測比較,希望對大家有幫助。