DIV CSS 佈局教程網

JavaScript 陣列去重的五種實作與效能比較
編輯:關於JavaScript     

直接進主題。題目是:寫一個方法實作陣列去重,傳入一個陣列、回傳去重後的新陣列,且原始陣列不可被更動。

先解釋一下名詞:陣列去重就是把重複的元素拿掉,例如 var arr = [3,2,4,2,1,2] 去重後得到 [3,2,4,1]。這個題目很多人寫過,這篇主要是筆記加上給初學者理解原理用。

方法一:比對新陣列

 var arr = [1,'b','b',4,3,3,4,5,1]; Array.prototype.unique1 = function(){ var arr1 = []; for(var i=0;i<this.length;i++){ if(arr1.indexOf(this[i]) == -1){ arr1.push(this[i]); } } return arr1; } console.log(arr); //[1,'b','b',4,3,3,4,5,1] console.log(arr.unique1()); //[1, "b", 4, 3, 5]

思路是:開一个新陣列,逐一檢查原陣列的元素在新陣列裡有沒有出現過,沒有就放進去。缺點很明顯——每次比較都要掃過整個新陣列,資料量大時效能不佳。

不習慣擴充 prototype 的話,改成一般函式效果一樣:

 var arr = [1,'b','b',4,3,3,4,5,1]; function unique1(arr){ var arr1 = []; for(var i=0;i<arr.length;i++){ if(arr1.indexOf(arr[i]) == -1){ arr1.push(arr[i]); } } return arr1; } console.log(unique1(arr)); //[1, "b", 4, 3, 5]

方法二:用 hash 表

 var arr = [1,'b','b',4,3,3,4,5,1]; Array.prototype.unique2 = function(){ var hash = {}; var arr1 = []; for(var i=0;i<this.length;i++){ if(! hash[this[i]]){ hash[this[i]] = true; arr1.push(this[i]); } } return arr1; } console.log(arr.unique2());

把出現過的值當成物件 key 記下來,查詢是 O(1),所以整體速度最快。代價是要為每個不重複元素配置一份記憶體,屬於「用空間換時間」。資料量不大的情況很推薦這個寫法。

要注意一個坑:物件的 key 會被轉成字串,因此 1 與 '1' 會被視為同一個。若要嚴格區分型別,改用 Set 會更乾脆。

方法三:比對自身位置

 var arr = [1,'b','b',4,3,3,4,5,1]; Array.prototype.unique3 = function(){ var arr1 = []; for(var i=0;i<this.length;i++){ if(this.indexOf(this[i])==i){ arr1.push(this[i]); } } return arr1; } console.log(arr.unique3());

原理是:如果某元素第一次出現的位置剛好等於目前索引,說明它是第一次被看到;若不等,前面已經出現過了。程式碼最短,但 indexOf 的內部迴圈仍會带来額外成本。

方法四:排序後逐一比對

 Array.prototype.unique4 = function(){ this.sort(); var arr1 = [this[0]]; for(var i=1;i<this.length;i++){ if(this[i] !== arr1[arr1.length-1]){ arr1.push(this[i]); } } return arr1; } console.log(arr.unique4());

先排序,重複的值就一定相鄰,於是只要跟「結果陣列的最後一個」比較即可。缺點有兩個:會改動原陣列(可用 slice().sort() 避開),而且回傳的是排序後的結果,順序與原本不同。

方法五:雙層迴圈

 Array.prototype.unique5 = function(){ for(var i=0;i<this.length;i++){ for(j= i+1;j<this.length;j++){ if(this[i] === this[j]){ this.splice(j,1); } } } return this; } console.log(arr.unique5());

直接兩層迴圈兩兩比對、遇到相同的就 splice 刪掉。這個寫法迴圈次數最多,不推薦;而且 splice 會改動原陣列,也可能在刪除後跳過元素,實作時要特別小心索引。

有人會問:方法一和方法三不也是每次都掃一遍嗎?感覺跟第五種差不多?差別在於 indexOf 找到第一個符合就停止,而雙層迴圈無論有沒有找到都會把整段掃完,資料量大時差距就很明顯了。

一個關鍵提醒

比較兩值是否相等時,請一律使用全等 === 與不全等 !==,因為這牽涉到型別——1 與 '1' 是不全等的。

最後補一個現代寫法:ES2015 之後有 Set,一行就能完成且保持原順序:var unique = [...new Set(arr)]; 或 Array.from(new Set(arr))。它使用 SameValueZero 演算法比對,NaN 也能正確去重,這是以物件當 hash 表時做不到的。

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