快速随机访问集合

本文关键字：集合 访问 随机 | 更新日期: 2023-09-27 18:35:52

我正在使用一股半随机令牌。对于每个令牌，我维护大量数据（包括一些子集合）。

唯一代币的数量是无限的，但实际上往往在 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 个令牌/秒。

性能分析表明，总 CPU 周期的 85% 都花在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
        }

快速随机访问集合

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

如果你用哈希集做同样的事情，那就没有节省。哈希集经过优化，可以快速回答"这个成员在集合中吗？"而不是"是否有一个成员使这个谓词在集合中为真？"这个问题。 后者是线性时间，无论是哈希集还是列表。

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

  • 创建从文本到状态的字典映射，然后在字典中搜索文本键以获取结果状态。这是理论上搜索和插入的 O（1）;实际上，这取决于哈希的质量。

  • 创建从文本到状态的排序字典映射。再次，搜索文本。 排序词典将键排序在平衡树中，因此搜索和插入为 O（log n）。

>30k并不多，所以如果状态是唯一的，你可以做这样的事情。字典访问要快得多。

var statesDic = model.States.ToDictionary(x => x.Condition, x => x);
var match = statesDic.ConstainsKey(stateText) ? statesDic[stateText] : default(State);

引用MSDN：

字典泛型类提供从一组键到一组值的映射。字典中的每个添加项都包含一个值及其关联的键。使用值键检索值非常快，接近 O（1），因为 Dictionary 类是作为哈希表实现的。

您可以在此处找到有关词典的更多信息。还要注意，字典使用内存空间来提高性能，您可以对 300k 个项目进行快速测试，看看我说的是什么样的空间，如下所示：

var memoryBeforeDic = GC.GetTotalMemory(true);
var dic = new Dictionary<string,object>(300000);
var memoryAfterDic = GC.GetTotalMemory(true);
Console.WriteLine("Memory: {0}", memoryAfterDic - memoryBeforeDic);
相关文章：