DIV CSS 佈局教程網

Array.indexOf 的效能瓶頸與 Hash 解法
編輯:關於JavaScript     

先看 Ext 為 Array.prototype 擴充的 indexOf 實作:

Ext.applyIf(Array.prototype, {
    /**
     * 檢查指定物件是否存在於陣列中
     * @param {Object} o 要檢查的物件
     * @param {Number} from (Optional) 開始搜尋的索引
     * @return {Number} o 在陣列中的索引(找不到回傳 -1)
     */
    indexOf: function(o, from) {
        var len = this.length;
        from = from || 0;
        from += (from < 0) ? len : 0;
        for (; from < len; ++from) {
            if (this[from] === o) {
                return from;
            }
        }
        return -1;
    }
});

源碼說明得很直白:這就是一次線性搜尋,時間複雜度 O(n)。也就是說,把它放進迴圈裡反覆呼叫,整體複雜度會退化為 O(n²)。資料量一大,卡頓幾乎是必然的。《JavaScript 權威指南》對此給出的建議是:用模擬 Hash 表的方式取代陣列。

有問題的寫法

var hostsIP = [];
Ext.each(_this.hosts, function(item) {
    hostsIP.push(item.ip);
});

Ext.each(txtHostsIP, function(ip) {
    if (hostsIP.indexOf(ip) === -1) { // 問題所在
        var host = {
            isAppend: true,   // 新增的主機
            isAgentOk: false,
            ip: ip
        };
        _this.hosts.push(
            Ext.apply(host, _this.MAPPING_FIELDS)
        );
        isAppend = true;
    } else {
        errors.push('IP[' + ip + ']已存在');
    }
});

外層要跑 txtHostsIP 這麼多輪,每一輪內部又做一次線性查找。實測中,當 hostsIP 的長度超過 2000 項時,IE8 就會跳出腳本執行超時的提示:

改用物件模擬 Hash

按照《權威指南》的思路,把陣列換成物件,用屬性名當 key,查詢就從 O(n) 降到接近 O(1):

var hostsIP = {};
Ext.each(_this.hosts, function(item) {
    hostsIP[item.ip] = item.ip;
});

Ext.each(txtHostsIP, function(ip) {
    if (!hostsIP.hasOwnProperty(ip)) {
        var host = {
            isAppend: true,   // 新增的主機
            isAgentOk: false,
            ip: ip
        };
        _this.hosts.push(
            Ext.apply(host, _this.MAPPING_FIELDS)
        );
        isAppend = true;
    } else {
        errors.push('IP[' + ip + ']已存在');
    }
});

改動只有兩行,但效果立竿見影。這裡有兩個細節值得留意:一是必須用 hasOwnProperty 判斷,避免 toString、constructor 這類原型鏈上的屬性造成誤判;二是若 key 可能與內建屬性重名,更穩妥的做法是建立一個沒有原型的物件(Object.create(null))。

結論很樸素:需要頻繁「判斷是否存在」時,首選 Map/Set 或物件索引,而不是 indexOf。

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