DIV CSS 佈局教程網

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

面試跑一圈下來,最大的收穫是認清自己的差距在哪、知識面有多窄——適度被打擊一下自信心其實有必要的。回頭把「陣列去重」這個看似簡單的題目做一次完整整理。

由簡到繁比较容易理解。先假設要處理的是簡單型別的陣列:

var arr = [1, 2, 2, 3, '5', 6, 5, '', ' ']

裡面只包含數字與字串兩種型別。

方法一:雙重迴圈暴力比對

最直覺的想法:把陣列複製一份,用兩層迴圈逐一比對目前值與後面所有的值,若與後面所有值都不相等,就把該值放進新陣列。

// 第一種方法
Array.prototype.distinct = function () {
    var clone, newArr = [], n = 0;
    if (this.length < 2) return;
    clone = this;
    for (var i = 0, len = this.length; i < len; i++) {
        for (var j = i + 1, len2 = clone.length; j < len2; j++) {
            if (this[i] !== clone[j]) {
                n++;
            }
        }
        if (n == (len - i - 1)) {
            newArr.push(this[i])
        }
        n = 0;
    }
    return newArr;
}
console.log([1, 2, 2, 3, '5', 6, 5, '', ' '].distinct());

基本能滿足需求,對簡單型別來說不用動太多腦筋。但問題在效能:陣列長度為 n 時,時間複雜度是 O(n²)。陣列一長就很難看。

方法二:利用排序去重

// 第二種方法
Array.prototype.distinct = function () {
    var newArr = this.concat().sort(), self = this;
    newArr.sort(function (a, b) {
        var n;
        if (a === b) {
            n = self.indexOf(a);
            self.splice(n, 1);
        }
    });
    return self;
}
console.log([1, 2, 2, 3, '5', 6, 5, 6, 6, 15, 5, '5', 5, '', ' '].distinct());

程式碼看起來短了很多,連一個 for 迴圈都沒有。但別被表象騙了——sort 本身的複雜度就不低,而迴圈內又呼叫了 indexOf(O(n))與 splice(O(n)),整體反而可能更慢。而且這個實作會直接修改原陣列,是個副作用陷阱。

方法三:利用物件屬性不會重名的特性

// 第三種方法
Array.prototype.distinct = function () {
    var newArr = [], obj = {};
    for (var i = 0, len = this.length; i < len; i++) {
        if (!obj[this[i]]) {
            newArr.push(this[i]);
            obj[this[i]] = 'new';
        }
    }
    return newArr;
}
console.log([1, 2, 2, 3, '5', 6, 5, 6, 6, 15, 5, '5', 5, '', ' '].distinct());

這個版本的時間複雜度降為 O(n),速度快得多。但執行結果與前面的方法不一致——仔細看會發現它把數字 5 和字串 '5' 當成重複值去掉了。原因是物件屬性名會被強制轉型為字串,兩者在鍵值空間裡撞在一起。

解法是把型別資訊一起編進鍵值:

// 第三種方法補充版
Array.prototype.distinct = function () {
    var newArr = [], obj = {};
    for (var i = 0, len = this.length; i < len; i++) {
        if (!obj[typeof (this[i]) + this[i]]) {
            newArr.push(this[i]);
            obj[typeof (this[i]) + this[i]] = 'new';
        }
    }
    return newArr;
}

遇到物件型別就複雜了

拿更複雜的資料來測試:

console.log([1, null, 2, {a:'vc'}, {}, '5', 6, 5, 6, {a:'vv'}, 15, 5, '5', 5, '', ' ', [1], [1], [1,2], ,].distinct());

問題來了:{a:'vc'}、{}、{a:'vv'} 這三個明顯不同的物件,全被當成同一個值剔除掉了。因為它們轉成鍵值後都是 [object Object]。要正確處理,就得進一步遞迴比對物件的屬性與值:

// 第三種方法加強版
Array.prototype.distinct = function () {
    var sameObj = function (a, b) {
        var tag = true;
        if (!a || !b) return false;
        for (var x in a) {
            if (!b[x]) return false;
            if (typeof (a[x]) === 'object') {
                tag = sameObj(a[x], b[x]);
            } else {
                if (a[x] !== b[x]) return false;
            }
        }
        return tag;
    }
    var newArr = [], obj = {};
    for (var i = 0, len = this.length; i < len; i++) {
        if (!sameObj(obj[typeof (this[i]) + this[i]], this[i])) {
            newArr.push(this[i]);
            obj[typeof (this[i]) + this[i]] = this[i];
        }
    }
    return newArr;
}

用前面的例子測試,基本沒有問題了。這個 sameObj 的實作還有改進空間——例如用 if (!b[x]) 判斷會把值為 0、''、false 的屬性誤判為不存在,嚴謹的寫法應該是 if (!(x in b));另外它也沒有處理陣列與物件的型別區分。

現代寫法

今天的JavaScript有更好的答案。Set 天生就是不重複的集合,一行就能完成基本型別的去重:

var arr = [1, 2, 2, 3, '5', 6, 5, '', ' '];
var unique = [...new Set(arr)];        // Set 使用 SameValueZero 比較,能正確區分 5 與 '5'
var unique2 = Array.from(new Set(arr)); // 效果相同

若需要處理物件並保留首次出現的順序,可以用 filter 搭配 indexOf,或用 Map 以物件本身作為鍵(Map 的鍵不轉型,物件之間以參照比較):

var seen = new Set();
var result = arr.filter(function (item) {
    var key = JSON.stringify(item);   // 依需求決定要用參照還是結構做鍵
    if (seen.has(key)) return false;
    seen.add(key);
    return true;
});

關鍵是:去重前先想清楚「怎樣算重複」。是型別也要比?物件要比結構還是比參照?NaN 要不要視為等於自己?把這個定義想清楚,再選對應的資料結構,就不會像上面那樣一路補丁補到底了。

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