使用标签数组提高标记算法的性能

这是我的 class Sample .

Sample 实例可以:

  • 有许多标签,例如 Tag1Tag2 等 .
    使用方法 isTagged 查询
  • 以查明它是否已标记或未标记(即 !Tag1
function Sample(){
        // [..]
        this.tags = [];
        // [..]
    }

    Sample.prototype.tag = function(tags){
        // [..]
        this.tags[tags] = true;
        // [..]
    };

    // if an array is passed, isTagged will return true at the first match ie. not all need to match, just one
    Sample.prototype.isTagged = function(tag){

        if(tag){
            if(Array.isArray(tag)){

                let tLength = tag.length;

                while(tLength--){
                    if(isTaggedSingleNoChecks(this, tag[tLength])){
                        return true;
                    }
                }

                return false;
            }
            else{
                return isTaggedSingleNoChecks(this, tag);
            }
        }

        return false;
    };

    function isTaggedSingleNoChecks(sample, tag){
        const isNegated = tag.charAt(0) == "!";
                
        if(isNegated){
            tag = tag.replace(/^[!]/, "");

            return sample.tags[tag]!==true;    
        }
        else{
            return sample.tags[tag]===true; 
        }
    }
    
    // showing usage
    var sample = new Sample();
    sample.tag('Tag1'); 
    sample.tag('Tag2');
    
    console.log(sample.isTagged('Tag1'));
    console.log(sample.isTagged('Tag3'));
    console.log(sample.isTagged('!Tag2'));

这一切都很好,但是我的应用程序递归地在数千个 Sample 实例上查询了数百万次,而我的分析显示这是一个性能瓶颈 .

有关如何提高性能的任何建议?

回答(1)

2 years ago

在开始优化之前,如何首先简化代码并摆脱最明显的怪异(对象而不是集合,无用的正则表达式等)

class Sample {
    constructor() {
        this.tags = new Set();
    }

    tag(...tags) {
        for (let t of tags)
            this.tags.add(t);
    }

    isTagged(...tags) {
        return tags.some(t =>
            (t[0] === '!')
                ? !this.tags.has(t.slice(1))
                : this.tags.has(t)
        )
    }
}

如果这仍然太慢,那么你必须求助于全局对象标记倒排索引,例如:

class SetMap extends Map {
    get(key) {
        if (!this.has(key))
            this.set(key, new Set)
        return super.get(key)
    }
}

let tagIndex = new SetMap()


class Sample {
    tag(...tags) {
        for (let t of tags) {
            tagIndex.get(t).add(this)
        }
    }

    isTagged(...tags) {
        return tags.some(t => tagIndex.get(t).has(this))
    }
}

当然,更多的工作将涉及取消标记(标记删除),尤其是正确的序列化 .

索引本身不会立即加速 isTagged ,但会极大地优化查询"find objects that are tagged by X and/or Y" .