DIV CSS 佈局教程網

JavaScript 陣列去重:從慢到快、從繁到簡的六種寫法
編輯:關於JavaScript     

處理陣列時,去除重複項幾乎是必備技能。以下由直觀到進階,整理六種做法與各自的取捨。

寫法一:indexOf 逐項比對

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

問題是 IE6-8 沒有陣列的 indexOf(雖然這話題有點古老了)。若要顧及舊環境,就得自己補一個:

var indexOf = [].indexOf
    ? function (arr, item) { return arr.indexOf(item); }
    : function indexOf(arr, item) {
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] === item) { return i; }
        }
        return -1;
    }

Array.prototype.unique2 = function () {
    var arr = [];
    for (var i = 0; i < this.length; i++) {
        var item = this[i];
        if (indexOf(arr, item) === -1) {
            arr.push(item);
        }
    }
    return arr;
}

還有一種更省記憶體的 indexOf 思路:不另建新陣列,而是判斷「這個元素第一次出現的位置是否就是當前索引」。

Array.prototype.unique3 = function () {
    var arr = [this[0]];
    for (var i = 1; i < this.length; i++) {
        if (this.indexOf(this[i]) == i) {
            arr.push(this[i]);
        }
    }
    return arr;
}

寫法二:用 hash 換速度

上面幾種正確性沒問題,但雙層迴圈在資料量大時會拖慢效能。用物件當雜湊表,就是經典的「以空間換時間」:

Array.prototype.unique4 = function () {
    var arr = [];
    var hash = {};
    for (var i = 0; i < this.length; i++) {
        var item = this[i];
        var key = (typeof item) + item;
        if (hash[key] !== 1) {
            arr.push(item);
            hash[key] = 1;
        }
    }
    return arr;
}
[1, 2, 3, '4', 3, 4, 3, 1, '34', 2].unique4();
// [1, 2, 3, "4", 4, "34"]

這裡有個細節要注意:物件的鍵只能是字串,所以 typeof(item) + item 是必要的,否則數值 1 與字串 '1' 會被當成同一個鍵。ES6 的 Map 沒有這個限制,鍵可以是任意型別,是更完整的雜湊結構。

如果你反而希望 '4' 與 4 被視為相同:

Array.prototype.unique5 = function () {
    var arr = [];
    var hash = {};
    for (var i = 0, len = this.length; i < len; i++) {
        if (!hash[this[i]]) {
            arr.push(this[i]);
            hash[this[i]] = true;
        }
    }
    return arr;
}
[1, 2, 3, '4', 3, 4, 3, 1, '34', 2].unique5();
// [1, 2, 3, "4", "34"]

寫法三:排序後比鄰

Array.prototype.unique6 = function () {
    this.sort();
    var arr = [this[0]];
    for (var i = 1; i < this.length; i++) {
        if (this[i] !== arr[arr.length - 1]) {
            arr.push(this[i]);
        }
    }
    return arr;
}
[1, 2, 3, '4', 3, 4, 3, 1, '34', 2].unique6();
// [1, 2, 3, "34", "4", 4]

先排序再比相鄰兩項,速度很快。唯一缺陷是預設排序依字元編碼順序,所以會出現 10 排在 2 前面的情況——不過對去重本身不影響。若在意排序結果,傳入自訂比較函數即可:

function compare(value1, value2) {
    if (value1 < value2) { return -1; }
    else if (value1 > value2) { return 1; }
    else { return 0; }
}
[1, 2, 5, 2, 10, 3, 20].sort(compare);
// [1, 2, 2, 3, 5, 10, 20]

另外要留意 unique6 會直接改動原陣列,若不想有副作用,記得先 slice() 複製一份。

寫法四:Set 一行解決

ES6 的 Set 天生就不允許重複成員,現在主流瀏覽器與 Node 都已支援:

Array.prototype.unique7 = function () {
    return Array.from(new Set(this));
}
[1, 2, 3, '4', 3, 4, 3, 1, '34', 2].unique7();
// [1, 2, 3, "4", 4, "34"]

日常開發我會直接寫這一句,簡潔又不易出錯。

寫法五:直接用現成方法庫

Underscore.js 在瀏覽器與 Node 都很受歡迎,_.uniq 現成可用:

const _ = require('underscore');
_.uniq([1, 2, 1, 3, 1, 4]); // [1, 2, 3, 4]

怎麼挑?量一下再說

效能這種事,憑感覺不如憑數字。用 console.time 就能快速比較:

console.time("test");
[1, 2, 3, '4', 3, 4, 3, 1, '34', 2].unique7();
console.timeEnd("test");
// test: 0.378ms

把資料量放大到一百萬筆,差距會非常明顯:

var arr = [];
var num = 0;
for (var i = 0; i < 1000000; i++) {
    num = Math.floor(Math.random() * 100);
    arr.push(num);
}

console.time("test");
arr.unique7();
console.timeEnd("test");

實務上的建議:新專案直接用 Set;需要兼容舊環境或想避開 prototype 擴充,就用 hash 版本;資料本來就需要排序時,排序後比鄰是最省的選擇。順帶一提,直接擴充 Array.prototype 容易與第三方庫衝突,正式專案裡建議寫成獨立工具函數。

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