DIV CSS 佈局教程網

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

準備:一個簡易計時器

要比較效能,先得有度量工具。下面的 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)],一行解決,且能正確處理物件參照與非字串鍵。

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