DIV CSS 佈局教程網

JavaScript 學習筆記:陣列去重的多種寫法與效能實測比較
編輯:關於JavaScript     

面試時經常被問到「用 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))
 }

以上就是陣列去重的幾種常見做法與實測比較,希望對大家有幫助。

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