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

loading...


0

这是我的 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 实例上查询了数百万次,而我的分析显示这是一个性能瓶颈 .

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

loading...

1回答

  • 1

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

    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" .

评论

暂时没有评论!