DIV CSS 佈局教程網

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

「怎麼去掉陣列裡的重複項」幾乎是前端面試的標準題,百度、騰訊、盛大都出過。題目看起來簡單,但考的其實是你對程式執行方式的理解——同一個功能,用 indexOf、用 hash 表、用排序,效能可能差上好幾倍。

方法一:indexOf 逐一比對

Array.prototype.unique1 = function() {
    var n = [];   //臨時陣列
    for (var i = 0; i < this.length; i++) {
        //若當前項已在臨時陣列中則跳過,否則推入
        if (n.indexOf(this[i]) == -1) n.push(this[i]);
    }
    return n;
}

方法二:以物件當雜湊表

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;
            r.push(this[i]);
        }
    }
    return r;
}

方法三:比對第一次出現的位置

Array.prototype.unique3 = function() {
    var n = [this[0]];
    for (var i = 1; i < this.length; i++) {
        //若第 i 項第一次出現的位置不是 i,表示它是重複的
        if (this.indexOf(this[i]) == i) n.push(this[i]);
    }
    return n;
}

方法一與方法三都用到 indexOf。這個方法在引擎內部必須逐一走訪直到命中,因此會浪費不少時間。方法二改用雜湊表,以屬性名的方式記錄已出現的值,查表遠比線性搜尋快。

我曾經做過一個測試:產生一萬筆隨機數組成的陣列,分別用這幾種方法跑。結果方法二明顯快於另外兩種。代價是它多了一個 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(引擎內部多為快速排序)。實測執行時間約為方法二的三倍,但仍比方法一、三快。要注意 sort() 會直接改動原陣列,若不想影響外部資料,先 slice() 複製一份。

方法五:自行補上 indexOf 相容實作

做搜尋歷史記錄功能時也會用到。原本直接用 indexOf,但這個方法在 ECMAScript 5 才有,IE8 及以下不支援,因此可以自己補一個:

Array.prototype.unique = function(){
    var length = this.length;
    if (length <= 1) { return this; }

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

    var result = [];
    for (var i = 0; i < length; i++) {
        if (result.indexOf(this[i]) === -1) result.push(this[i]);
    }
    return result;
}

方法六:雙層迴圈暴力法

function unique(arr) {
    var result = [], isRepeated;
    for (var i = 0, len = arr.length; i < len; i++) {
        isRepeated = false;
        for (var j = 0, len2 = result.length; j < len2; j++) {
            if (arr[i] == result[j]) { isRepeated = true; break; }
        }
        if (!isRepeated) result.push(arr[i]);
    }
    return result;
}

思路是把元素一個個搬到新陣列,搬運時檢查是否重複。從巢狀迴圈就能看出它效率極低,時間複雜度是 O(n²)。改善方式正是方法二的思路:用雜湊結構記錄已有元素,省掉內層迴圈。

比較與選擇

雜湊法(方法二)在多數情況下最快,缺點是遇到物件時會把 [object Object] 當成同一個鍵,造成誤判;排序法(方法四)不改變元素型別判斷方式但會動到原陣列;暴力法只適合小陣列。

如果是現代環境,其實不必自己寫:[...new Set(arr)] 一行就能完成,而且 Set 使用 SameValueZero 演算法,連 NaN 也能正確視為同一值。若要自訂比較邏輯(例如依 id 去重物件),則用 filter 搭配一個 Map 記錄看過的鍵會最清楚。

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