DIV CSS 佈局教程網

陣列去重的三種思路:從 shift 到雜湊表
編輯:關於JavaScript     

陣列去重看起來簡單,但寫法差很多。這篇收錄兩種以 Array.prototype.del 為名的實作,剛好對應兩種不同的思路。

寫法一:統計出現次數

先把整個陣列倒進一個物件裡計數,凡是出現超過一次的,再把它的索引收集起來一次刪掉:

Array.prototype.del = function(){
    var b = {}, c, i = 0, l = this.length, j;
    for(; i < l; i++){
        c = this.shift();
        c in b ? b[c]++ : b[c] = 0;
    }
    for(j in b){
        if(b[j] > 0) this.push(+j || j);
    }
    return this;
};

var a = [1, 2, 2, 3, 3, 3, 'a', 'b', 'b'];
alert(a.del());

這裡有兩個值得多看兩眼的細節:

  • 用 shift 清空原陣列:反覆 shift() 直到取完,等於順便清空了 this,之後再 push 回來,就不需要另外處理「要不要保留原陣列」的問題。
  • +j || j 的雙重轉型:物件的鍵一律是字串,所以 b 的屬性名都是 "1"、"2" 這種。前面加 + 可以轉回數字,但遇到 'a' 會得到 NaN(falsy),此時 || j 就退回原本的字串。一個運算式同時處理了數字與字串兩種情況,寫得相當聰明。

寫法二:一次遍歷,直接以雜湊表去重

另一種思路更精簡:邊走訪邊把值當鍵塞進空物件,沒見過就留下、見過就跳過,最後用陣列長度一次截斷:

Array.prototype.del = function(){
    return (function (i, n, j, u, o){
        for (; i < j; i++) {
            o = this[i];
            o in u ? 0 : (u[this[n++] = o] = 1)
        }
        this.length = n;
        return this
    }).call(this, 0, 0, this.length, {})
}

var a = [1, 2, 2, 3, 3, 3, 'a', 'b', 'b'];
alert(a.del());

這段程式碼密度很高,值得逐字拆解:

  • 用 IIFE + call 借 this:把主體包成立即執行函式,透過 call(this, ...) 把原本的陣列傳進來當 this,同時用參數預告了 i、n、j、u、o 五個區域變數——這是為了不污染外部作用域。
  • n 是寫入游標:它與 i 不同,只有「第一次見到」時才遞增。因為 n 恆小於等於 i,寫入永遠落後於讀取,不會覆蓋到還沒讀的資料。
  • u[this[n++] = o] = 1:這一句子做了兩件事——把值寫回陣列的 n 位置並讓 n 前進,同時在雜湊表 u 裡標記「看過了」。運算式回傳的值剛好是索引,可以當運算結果繼續用。
  • this.length = n:既然去重後只寫了 n 個元素,直接把長度截到 n 就完成了,不必刪除任何節點。

兩者比較

第一種直觀好讀,適合維護中的專案;第二種只遍歷一次、沒有 shift 的搬移成本,效率更好,但可讀性代價明顯。若真要追求速度,用 indexOf 搭配 filter 也是常見選擇:

arr.filter(function(item, pos){
    return arr.indexOf(item) === pos;
});

而 ES6 之後最乾脆的答案是 [...new Set(arr)]——一行搞定,語意清楚,效能也不差。上面這些手工實作的價值,在於它們示範了「用雜湊表把時間複雜度從 O(n²) 降到 O(n)」這個經典手法,而這正是 JavaScript 裡最常用的效能技巧之一。

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