要比較效能,先得有度量工具。下面的 Watch 物件用 new Date().getTime() 記錄每段的耗時,最後以橫條圖輸出:
var Watch = {
result: [],
guid: -1,
totalTime: 0,
start: function (title) {
this.result[++this.guid] = [title || this.guid, new Date().getTime()];
},
stop: function () {
var r = this.result[this.guid];
var t = new Date().getTime() - r[1];
this.totalTime += t;
r[1] = t;
if (t >= 10000) {
alert("This code takes too long to run, you should optimizate them.");
}
},
report: function (parent) {
var div = document.createElement("div");
var str = [];
str.push("<p><b>The total times:</b><span style='color:#f00'>" +
this.totalTime + "</span> ms.</p>");
for (var i = 0, l = this.result.length; i < l; i++) {
if (this.result[i].length > 1) {
var w = this.totalTime === 0 ? 0 :
parseInt(200 * this.result[i][1] / this.totalTime);
str.push("<p><span style='width:200px;display:inline-block;background-color:#f7f7f7'>" +
"<span style='background-color:#0c0;width:" + w + "px;display:inline-block'>" +
this.result[i][1] + "</span></span> " +
"<span style='width:150px;display:inline-block'>" +
this.result[i][0] + "</span></p>");
} else {
str.push(this.result[i][0]);
}
}
div.innerHTML = str.join("");
(parent || document.body).appendChild(div);
this.totalTime = 0; this.guid = -1; this.result = [];
},
print: function (str) { this.result[++this.guid] = [str]; }
};
Array.prototype.unique1 = function () {
var r = new Array();
label:
for (var i = 0, n = this.length; i < n; i++) {
for (var x = 0, y = r.length; x < y; x++) {
if (r[x] == this[i]) { continue label; }
}
r[r.length] = this[i];
}
return r;
};
用標籤 continue label 一跳出內層。邏輯最直白,時間複雜度 O(n²)。
Array.prototype.unique2 = function () {
return this.sort().join(",,")
.replace(/(,|^)([^,]+)(,,\2)+(,|$)/g, "$1$2$4")
.replace(/,,+/g, ",")
.replace(/,$/, "")
.split(",");
};
先把重複項排在一起,再用正則把連續重複的片段收掉。程式碼短,但會破壞原陣列順序,而且遇到含逗號的內容會出錯。
Array.prototype.unique3 = function () {
var temp = {}, len = this.length;
for (var i = 0; i < len; i++) {
var tmp = this[i];
if (!temp.hasOwnProperty(tmp)) {
temp[this[i]] = "my god";
}
}
len = 0;
var tempArr = [];
for (var i in temp) { tempArr[len++] = i; }
return tempArr;
};
利用屬性名的唯一性去重,接近 O(n)。代價是所有元素都會被轉成字串,且回傳順序不保證。
Array.prototype.unique4 = function () {
var temp = new Array();
this.sort();
for (i = 0; i < this.length; i++) {
if (this[i] == this[i + 1]) { continue; }
temp[temp.length] = this[i];
}
return temp;
};
同樣會改動原陣列順序,但比法二可靠得多。
測試資料用 2000 筆隨機數字,逐一比較四種做法的耗時:
var test = (function () {
var arr2 = [];
for (var i = 0; i < 2000; i++) {
arr2[i] = (parseInt(Math.random() * 2000) + 1).toString();
}
return function () { return arr2; };
})();
window.onload = function () {
var arr;
Watch.start("Cost times1:");
arr = test(); console.log(arr.length);
arr = arr.unique1(); console.log(arr.length);
Watch.stop();
Watch.start("Cost times2:");
arr = test(); arr = arr.unique2(); Watch.stop();
Watch.start("Cost times3:");
arr = test(); arr = arr.unique3(); Watch.stop(); // 陣列很大時最快
Watch.start("Cost times4:");
arr = test(); arr = arr.unique4(); Watch.stop();
Watch.report();
};
選擇建議:資料量小、要保留原順序,用 unique1;資料量很大且不介意型別被字串化,用 unique3;若原陣列本來就無所謂順序,unique4 是簡單又快的折衷。
更現代的寫法可以直接用 [...new Set(arr)],一行解決,且能正確處理物件參照與非字串鍵。