从c# HashSet中快速获取随机元素

本文关键字：获取 随机 元素 HashSet | 更新日期: 2023-09-27 17:50:51

我需要存储一组元素。我需要的是

的功能
  1. 删除(单个)元素和
  2. add (sets of) elements and
  3. 每个对象只能在集合中出现一次，
  4. 从集合
    5. 中获取一个随机元素

我选择了HashSet (c#)，因为它支持快速方法来删除元素( HashSet .remove(element))，添加集合( HashSet . unionwith (anotherHashSet))，并且HashSet的性质保证没有重复，因此满足了需求1到3。

我发现获得随机元素的唯一方法是

Object object = hashSet.ElementAt(rnd.Next(hashSet.Count));

但这是非常慢的，因为我对我的地图的每个像素调用一次(创建一个随机的洪水填充从多个起点;mapsize目前为500x500，但我想更大)，哈希集包含相当多的项。(快速测试显示，在再次收缩之前，它会膨胀到5752个条目。)

分析(CPU采样)告诉我我的ElementAt调用占用超过50%。

我意识到在一个大的哈希集上进行500x500次操作不是一件容易的事，但是其他操作(Remove和UnionWith)被调用的频率和ElementAt一样高，所以主要问题似乎是操作而不是调用的数量。

我模糊地理解为什么从HashSet中获取某个元素非常昂贵(与从列表或其他有序数据结构中获取元素相比)，但我只是想要随机选择。真的这么难吗?真的没有别的办法吗?是否有更好的数据结构为我的目的?

将所有内容更改为列表并没有帮助，因为现在其他方法成为瓶颈，并且需要更长的时间。

将HashSet转换为数组并从中选择随机元素并没有什么帮助，因为虽然从数组中选择随机元素很快，但首先将HashSet转换为数组需要比运行HashSet更长的时间。

如果你想更好地理解我在做什么:链接到我的问题和答案。

从c# HashSet中快速获取随机元素

我认为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键和值-没有通用版本。

[EDIT]多年后，我们现在有了强类型泛型SortedDictionary<TKey, TValue>，这可能会更好。

最基本的问题是索引。

在数组或列表中，数据通过其coördinate索引-通常只是一个简单的int索引。在HashSet中，您自己选择索引—键。副作用是，没有"coördinate"——"索引3处的元素"这个问题真的没有意义。它实际实现的方式是枚举整个HashSet，一项接一项，并返回第n项。这意味着要获得第1000个项目，您必须枚举在此之前的所有999个项目。这伤害。

解决这个问题的最佳方法是根据HashSet的实际密钥选择随机密钥。当然，这只有在合理的情况下才能工作，就像那样随机选择密钥。

如果你不能以一种令人满意的方式随机选择键，你可能想要保持两个单独的列表——每当你向HashSet添加一个新项目时，将其键添加到List<TKey>;然后，您可以轻松地从List中选择一个随机密钥，并遵循它。根据您的需求，副本可能不是什么大问题。

当然，如果您只进行一次枚举，您可以节省ElementAt枚举—例如，在搜索HashSet之前，您可以将其转换为List。当然，这只有在你一次随机选择多个索引时才有意义(例如，如果你一次随机选择5个索引，你将平均节省大约 1/5的时间)——如果你总是选择一个，然后修改HashSet并选择另一个，这是没有帮助的。

根据您确切的用例，SortedSet可能也值得一看。它的工作方式与HashSet类似，但它保持键的顺序。有用的部分是，您可以使用GetViewBetween方法获得整个范围的键—如果您的键是稀疏的，但在任意范围之间很好地平衡，则可以非常有效地使用此方法。你只需要首先随机选择一个范围，然后获得GetViewBetween范围内的项目，并从中随机选择一个。实际上，这将允许您划分搜索结果，并且应该节省相当多的时间。

相关文章：