使用标签数组提高标记算法的性能-Java 学习之路

这是我的 class Sample .

Sample 实例可以：

有许多标签，例如 Tag1 ， Tag2 等 .
使用方法 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 回答

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

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

回复于 2024-04-23T19:27:29+08:00

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

1 回答

相关问题