快速随机访问集合

Question

我正在消耗一串半随机令牌.对于每个令牌,我正在维护大量数据(包括一些子集合).

唯一令牌的数量是无限的,但实际上往往大约为100,000-300,000.

我从一个列表开始,并使用Linq查询确定要更新的相应令牌对象.

public class Model {
    public List<State> States { get; set; }
    ...
}

var match = model.States.Where(x => x.Condition == stateText).SingleOrDefault();

在第一个~30k的独特令牌中,我能够找到并更新〜1,100个令牌/秒.

性能分析表明,85%的总Cpu周期都花在了Where(...).SingleOrDefault()(这是有道理的,列表是低效的搜索方式).

所以,我将列表切换到HashSet并再次进行分析,确信HashSet能够随机搜索更快.这一次,我只处理~900令牌/秒.Linq(89%)的时间几乎相同.

所以...首先,我是否滥用了HashSet？(使用Linq是强制转换为IEnumerable然后是枚举/类似的东西？)

如果没有,那么实施自己的最佳模式是什么？我的印象是HashSet已经进行了二元搜索,所以我假设我需要构建某种树结构并且有更小的子集？

回答一些问题形式的评论...条件是唯一的(如果我得到相同的标记两次,我想更新相同的条目),HashSet是股票.Net实现(System.Collections.Generic.HashSet<T>).

更广泛的代码视图是......

        var state = new RollingList(model.StateDepth); // Tracks last n items and drops older ones. (Basically an array and an index that wraps around
        var tokens = tokeniser.Tokenise(contents); // Iterator
        foreach (var token in tokens) {
            var stateText = StateToString(ref state);
            var match = model.States.Where(x => x.Condition == stateText).FirstOrDefault();
            // ... update the match as appropriate for the token
        }

Answer 1

var match = model.States.Where(x => x.Condition == stateText).SingleOrDefault();

如果你使用哈希集做同样的事情,那就没有节省.散列集经过优化,可以快速回答"这个集合中的成员是谁？" 不是"是否有成员在集合中使这个谓词成立？" 后者是线性时间,无论是哈希集还是列表.

可能满足您需求的数据结构:

• 创建一个从文本到状态的字典映射,然后在文本键的字典中搜索以获得结果状态.这是理论上搜索和插入的O(1); 在实践中,它取决于哈希的质量.

• 制作从文本到状态的排序字典映射.再次,搜索文本.排序的字典使密钥按平衡树排序,因此用于搜索和插入的是O(log n).