在一次前端面試中,出現了「陣列去重」這道經典題目。我最初想到的是利用物件儲存鍵值的方法,但在實際測試與比較之後,發現不同方法在效能上差異相當明顯。以下整理三種常見思路及其實測結果。
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 的版本,因速度慢且相容性差而未採用。)