c# - 快速随机访问集合

Question

我正在消费一连串的半随机 token 。对于每个 token ，我都在维护大量数据(包括一些子集合)。

唯一 token 的数量没有限制，但实际上往往在 100,000-300,000 个数量级。

我从一个列表开始，并使用 Linq 查询确定要更新的适当 token 对象。

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

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

在前 ~30k 个独特的 token 中，我能够找到并更新~1,100 个 token /秒。

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

因此，我将列表切换到 HashSet 并再次分析，确信 HashSet 能够更快地随机查找。这一次，我只处理了大约 900 个 token /秒。在 Linq 上花费的时间几乎相同 (89%)。

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

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

要回答评论中的一些问题...条件是唯一的(如果我两次获得相同的 token ，我想更新相同的条目)，HashSet 是股票 .Net 实现(System.Collections.Generic.HashSet<T>)。

更广泛的代码 View 是...

        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)。