DIV CSS 佈局教程網

JavaScript 陣列去重三種方法的效能測試與比較
編輯:關於JavaScript     

在一次前端面試中,出現了「陣列去重」這道經典題目。我最初想到的是利用物件儲存鍵值的方法,但在實際測試與比較之後,發現不同方法在效能上差異相當明顯。以下整理三種常見思路及其實測結果。

方法一:以物件儲存鍵值

Array.prototype.distinct1 = function() {
    var i=0, tmp={}, that=this.slice(0)
    this.length=0;
    for(;i<that.length;i++){
        if(!(that[i] in tmp)){
            this[this.length]=that[i];
            tmp[that[i]]=true;
        }
    }
    return this;
};

這個方法思路簡單、實作不複雜,但存在一個致命問題:遇到不同型別卻能轉換成相同字串的情況就會出錯,例如數字 1 和字串 "1" 會被誤判為重複。

方法二:雙重迴圈

Array.prototype.distinct2 = function() {
    var i=0, flag, that=this.slice(0);
    this.length=0;
    for(;i<that.length;i++){
        var tmp=that[i];
        flag=true;
        for(var j=0;j<this.length;j++){
            if(this[j]===tmp){flag=false;break}
        }
        if(flag)this[this.length]=tmp;
    }
    return this;
};

這種方法能正確得到想要的結果,但兩層迴圈的效率相對較低。

方法三:同時儲存鍵值與型別

Array.prototype.distinct4 = function() {
    var i=0, tmp={}, t2, that=this.slice(0), one;
    this.length=0;
    for(;i<that.length;i++){
        one=that[i];
        t2=typeof one;
        if(!(one in tmp)){
            this[this.length]=one;
            tmp[one]=t2;
        }else if(tmp[one].indexOf(t2)==-1){
            this[this.length]=one;
            tmp[one]+=t2;
        }
    }
    return this;
};

這個方法在第一種思路的基礎上,額外用字串保存每個陣列項的型別,遇到新型別就串接上去,從根本上解決了型別混淆的問題。

效能實測比較

為了直觀比較不同資料情境下各算法的效能差距,我設計了幾組極端案例進行驗證。

情境一:1 到 80 全部不重複,循環 1000 次

IE9: Chrome: Firefox: IE6:

情境二:80 項全部重複,循環 1000 次

IE9: Chrome: Firefox: IE6:

綜合兩組數據可以發現:除了 IE6-8 之外,其他瀏覽器的雙重迴圈表現都不錯,而 IE6-8 的雙重迴圈要慢上 10 到 20 倍。如果你的網站只需支援 IE9 以上版本,就可以放心使用雙重迴圈;否則建議採用儲存鍵值的方法,並依實際資料情況,選擇方法一或方法三。(圖中的方法四其實就是本文的方法三,原本還有個使用 Array.indexOf 的版本,因速度慢且相容性差而未採用。)

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