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

Question

我需要存储一组元素.我需要的是功能

1. 删除(单个)元素和
2. 添加(组)元素和
3. 每个对象应该只在集合中一次
4. 从集合中获取随机元素

我选择了HashSet(C#),因为它运行快速删除元素的方法(hashSet.remove(element)),添加集合(hashSet.UnionWith(anotherHashSet))和HashSet的性质保证没有重复,所以要求1到3是照顾的.

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

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

但这非常慢,因为我为地图的每个像素调用一次(从多个起点创建随机洪水填充;此刻mapize 500x500但我想要更大)并且hashset包含相当多的项目.(一项快速测试显示,在再次收缩之前,它会爆发5752个条目.)

分析(CPU采样)告诉我,我的ElementAt调用占用了50%以上.

我意识到在一个大的hashset上运行500x500并不是一件容易的事,但是其他操作(Remove和UnionWith)和ElementAt一样被调用,所以主要问题似乎是操作而不是调用次数.

我模糊地理解为什么从HashSet中获取某个元素是非常昂贵的(与从列表或其他有序数据结构中获取它相比,但我只想要一个随机选择.它真的很难以且没有办法解决它？我的目的是否有更好的数据结构？

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

将HashSet转换为数组并从那里选择我的随机元素预计无济于事,因为从数组中选择一个随机元素很快,首先将hashset转换为数组需要比运行hashSet.ElementAt更长的时间.

如果你想更好地理解我想要做的事情:我的问题和答案的链接.

Answer 1

基本问题是索引.

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

解决这个问题的最好方法是根据实际的密钥选择随机数HashSet.当然,这只有在选择随机密钥时才有效.

如果您无法以令人满意的方式随机选择密钥,您可能希望保留两个单独的列表 - 每当您向a添加新项目时HashSet,将其密钥添加到a List<TKey>; 然后,您可以轻松地从中选择一个随机密钥List,并按照它进行操作.根据您的要求,重复可能不是什么大问题.

当然,ElementAt如果你只进行一次枚举,你可以节省枚举 - 例如,在搜索之前HashSet,你可以将其转换为List.这只有在你一次选择多个随机索引时才有意义(例如,如果你一次随机选择5个指数,你平均可以节省大约 1/5的时间) - 如果你总是在挑选一,然后修改HashSet和挑选另一个,它不会有所帮助.

根据您的具体用例,可能值得一看SortedSet.它以类似的方式工作HashSet,但它维护键中的顺序.有用的部分是你可以使用这个GetViewBetween方法获得一系列的键 - 如果键很稀疏,但在任意范围之间很好地平衡,你可以非常有效地使用它.你只需要随机选择一个范围,然后获取范围内的项目,并从中GetViewBetween选择一个随机的项目.实际上,这将允许您对搜索结果进行分区,并且应该节省相当多的时间.

Answer 2

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