C# HashSet 快速获取随机元素
Get random element from C# HashSet quickly
我需要存储一组元素。我需要的是
的功能
- 删除（单个）元素并
- 添加（组）元素和
- 每个对象只能出现在集合中一次并且
- 从集合中随机获取一个元素
我选择了 HashSet (C#)，因为它支持 快速 删除元素的方法 (hashSet.remove(element)) , 添加集 (hashSet.UnionWith(anotherHashSet)) 和 HashSet 的性质保证没有重复项，因此满足要求 1 到 3。
我发现获得随机元素的唯一方法是
Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));
但这非常慢，因为我为地图的每个像素调用一次（从多个起点创建随机洪水填充；目前地图大小为 500x500，但我想更大）和哈希集持有相当多的项目。 （一个快速测试显示它在再次收缩之前最多爆炸了 5752 个条目。）
分析（CPU 抽样）告诉我我的 ElementAt 调用占了 50%。
我意识到在一个大哈希集上进行 500x500 次操作并非易事，但其他操作（Remove 和 UnionWith）的调用频率与 ElementAt 一样，因此主要问题似乎是操作而不是调用次数。
我模糊地理解为什么从 HashSet 中获取某个元素非常昂贵（与从列表或其他有序数据结构中获取它相比，但我只是想要随机选择。它真的可以吗这么难，有没有办法解决？有没有更好的数据结构适合我的目的？
将所有内容更改为列表并没有帮助，因为现在其他方法成为瓶颈并且需要更长的时间。
将 HashSet 转换为数组并从中选择我的随机元素预计不会有帮助，因为虽然从数组中选择随机元素很快，但首先将 hashset 转换为数组花费的时间比 运行 hashSet.ElementAt 本身。
如果你想更好地理解我正在尝试做的事情：A link to my question and the answer.
基本问题是索引。
在数组或列表中，数据由其坐标索引 - 通常只是一个简单的 int 索引。在 HashSet 中，您自己选择索引 - 键。但是，副作用是没有 "coördinate" - "element at index 3" 这个问题真的没有意义。它实际实现的方式是枚举整个 HashSet，逐项枚举，然后返回第 n 项。这意味着要获得第 1000 个项目，您还必须枚举之前的所有 999 个项目。好疼啊
解决此问题的最佳方法是根据 HashSet 的实际密钥选择随机数。当然，这只有在合理地选择随机密钥的情况下才有效。
如果您不能以令人满意的方式随机选择密钥，您可能希望保留两个单独的列表 - 每当您将新项目添加到 HashSet 时，将其密钥添加到List<TKey>;然后，您可以轻松地从 List 中选择一个随机键，然后跟随它。根据您的要求，重复可能不是什么大问题。
当然，如果您只进行一次枚举，则可以节省 ElementAt 枚举 - 例如，在搜索 HashSet 之前，您可以将其转换为 List .当然，这只有在您一次选择多个随机索引时才有意义（例如，如果您一次随机选择 5 个索引，您将节省 about 1/5 的时间平均）- 如果您总是选择一个，然后修改 HashSet 并选择另一个，那将无济于事。
根据您的具体用例，可能还值得一看 SortedSet。它的工作方式与 HashSet 类似，但它保持键的顺序。有用的部分是您可以使用 GetViewBetween 方法来获取整个范围的键 - 如果您的键稀疏但在任意范围之间平衡良好，则可以非常有效地使用它。您只需先随机选择一个范围，然后获取 GetViewBetween 范围内的项目，然后再从中随机选择一个。实际上，这将允许您对搜索结果进行分区，并且应该会节省相当多的时间。
我认为 OrderedDictionary 可能适合您的目的：
var dict = new OrderedDictionary();
dict.Add("My String Key", "My String");
dict.Add(12345, 54321);
Console.WriteLine(dict[0]); // Prints "My String"
Console.WriteLine(dict[1]); // Prints 54321
Console.WriteLine(dict["My String Key"]); // Prints "My String"
Console.WriteLine(dict[(object)12345]); // Prints 54321 (note the need to cast!)
这具有快速添加和删除以及 O(1) 索引。它只适用于 object 键和值 - 没有通用版本。
[编辑] 多年后：我们现在有了强类型泛型 SortedDictionary<TKey, TValue>，这可能会更好。
我需要存储一组元素。我需要的是
的功能- 删除（单个）元素并
- 添加（组）元素和
- 每个对象只能出现在集合中一次并且
- 从集合中随机获取一个元素
我选择了 HashSet (C#)，因为它支持 快速 删除元素的方法 (hashSet.remove(element)) , 添加集 (hashSet.UnionWith(anotherHashSet)) 和 HashSet 的性质保证没有重复项，因此满足要求 1 到 3。
我发现获得随机元素的唯一方法是
Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));
但这非常慢，因为我为地图的每个像素调用一次（从多个起点创建随机洪水填充；目前地图大小为 500x500，但我想更大）和哈希集持有相当多的项目。 （一个快速测试显示它在再次收缩之前最多爆炸了 5752 个条目。）
分析（CPU 抽样）告诉我我的 ElementAt 调用占了 50%。
我意识到在一个大哈希集上进行 500x500 次操作并非易事，但其他操作（Remove 和 UnionWith）的调用频率与 ElementAt 一样，因此主要问题似乎是操作而不是调用次数。
我模糊地理解为什么从 HashSet 中获取某个元素非常昂贵（与从列表或其他有序数据结构中获取它相比，但我只是想要随机选择。它真的可以吗这么难，有没有办法解决？有没有更好的数据结构适合我的目的？
将所有内容更改为列表并没有帮助，因为现在其他方法成为瓶颈并且需要更长的时间。
将 HashSet 转换为数组并从中选择我的随机元素预计不会有帮助，因为虽然从数组中选择随机元素很快，但首先将 hashset 转换为数组花费的时间比 运行 hashSet.ElementAt 本身。
如果你想更好地理解我正在尝试做的事情：A link to my question and the answer.
基本问题是索引。
在数组或列表中，数据由其坐标索引 - 通常只是一个简单的 int 索引。在 HashSet 中，您自己选择索引 - 键。但是，副作用是没有 "coördinate" - "element at index 3" 这个问题真的没有意义。它实际实现的方式是枚举整个 HashSet，逐项枚举，然后返回第 n 项。这意味着要获得第 1000 个项目，您还必须枚举之前的所有 999 个项目。好疼啊
解决此问题的最佳方法是根据 HashSet 的实际密钥选择随机数。当然，这只有在合理地选择随机密钥的情况下才有效。
如果您不能以令人满意的方式随机选择密钥，您可能希望保留两个单独的列表 - 每当您将新项目添加到 HashSet 时，将其密钥添加到List<TKey>;然后，您可以轻松地从 List 中选择一个随机键，然后跟随它。根据您的要求，重复可能不是什么大问题。
当然，如果您只进行一次枚举，则可以节省 ElementAt 枚举 - 例如，在搜索 HashSet 之前，您可以将其转换为 List .当然，这只有在您一次选择多个随机索引时才有意义（例如，如果您一次随机选择 5 个索引，您将节省 about 1/5 的时间平均）- 如果您总是选择一个，然后修改 HashSet 并选择另一个，那将无济于事。
根据您的具体用例，可能还值得一看 SortedSet。它的工作方式与 HashSet 类似，但它保持键的顺序。有用的部分是您可以使用 GetViewBetween 方法来获取整个范围的键 - 如果您的键稀疏但在任意范围之间平衡良好，则可以非常有效地使用它。您只需先随机选择一个范围，然后获取 GetViewBetween 范围内的项目，然后再从中随机选择一个。实际上，这将允许您对搜索结果进行分区，并且应该会节省相当多的时间。
我认为 OrderedDictionary 可能适合您的目的：
var dict = new OrderedDictionary();
dict.Add("My String Key", "My String");
dict.Add(12345, 54321);
Console.WriteLine(dict[0]); // Prints "My String"
Console.WriteLine(dict[1]); // Prints 54321
Console.WriteLine(dict["My String Key"]); // Prints "My String"
Console.WriteLine(dict[(object)12345]); // Prints 54321 (note the need to cast!)
这具有快速添加和删除以及 O(1) 索引。它只适用于 object 键和值 - 没有通用版本。
[编辑] 多年后：我们现在有了强类型泛型 SortedDictionary<TKey, TValue>，这可能会更好。