DIV CSS 佈局教程網

JavaScript 陣列去重的四種寫法與效能比較
編輯:關於JavaScript     

四種陣列去重方法

第一種:indexOf 搭配暫存陣列

 Array.prototype.unique1 = function () { var n = []; //新的暫存陣列 for (var i = 0; i < this.length; i++) //遍歷目前陣列 { //若目前項目已存在於暫存陣列,indexOf 會回傳 -1 以外的值,跳過; //否則推入暫存陣列 if (n.indexOf(this[i]) == -1) n.push(this[i]); } return n; }

第二種:以 hash 表記錄

 Array.prototype.unique2 = function() { var n = {},r=[]; //n 為 hash 表,r 為暫存陣列 for(var i = 0; i < this.length; i++) //遍歷目前陣列 { if (!n[this[i]]) //hash 表中沒有目前項目 { n[this[i]] = true; //存入 hash 表 r.push(this[i]); //推入暫存陣列 } } return r; } var arr = [1, 'a', 'a', 'b', 'd', 'e', 'e', 1, 0] alert(arr.unique2());

第三種:利用 indexOf 與索引相等判斷

 Array.prototype.unique3 = function() { var n = [this[0]]; //結果陣列,先放入第一項 for(var i = 1; i < this.length; i++) //從第二項開始遍歷 { //若目前項目「第一次出現的位置」不是 i,代表它是重複的,忽略; 否則推入結果陣列 if (this.indexOf(this[i]) == i) n.push(this[i]); } return n; }

第一種與第三種都用到了陣列的 indexOf。這個方法要找出參數在陣列中第一次出現的位置,而 JS 引擎的實作方式是從頭遍歷直到找到目標,因此會浪費不少時間。

第二種改用 hash 表,把已出現過的項目以屬性的形式存進物件。屬性查找的成本遠低於線性搜尋陣列,這就是它快的原因。

為了驗證差異,可以產生一個一萬筆隨機數的陣列,分別用這幾種方法計時。實測結果第二種明顯快於另外兩種;代價是記憶體占用較高,因為多存了一份 hash 表——典型的空間換時間。

第四種:先排序再比對相鄰項

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

這個方法的思路是排序後重複項必然相鄰,只需比對前一項即可。sort 是 JS 原生方法,內部通常採用快速排序。實測耗時約為第二種的三倍,但仍比第一、三種快上不少。

選擇建議:資料量小、在意可讀性就用第三種;追求效能用第二種;若資料本來就需要排序,第四種可以順手一起做。

最後提醒兩個實務陷阱。第一,直接擴充 Array.prototype 會污染所有陣列,容易與第三方函式庫或其他同事的程式碼相撞(例如 for-in 會把它列舉出來),建議改成獨立函式。第二,第二種與第四種都有各自的副作用:hash 表寫法會把數字 1 與字串 '1' 視為同一個 key;sort 未指定比較函式時會以字串順序排序,數字陣列要用 arr.sort((a,b) => a-b)。若陣列內含物件,則需改用 JSON 序列化或自訂比較邏輯。ES6 之後最簡潔的選擇其實是 [...new Set(arr)],底層同樣是 hash 實作。

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