从字典中获取任何元素的最快方法

我在C＃中实现A *（不用于寻路），我需要Dictionary来保存开放节点，因为我需要快速插入和快速查找。我想从字典中获得第一个开放节点（它可以是任何随机节点）。使用Dictionary.First（）非常缓慢。如果我使用迭代器，MoveNext（）仍然占用我程序整个CPU时间的15％。什么是从字典中获取任何随机元素的最快方法？从字典中获取任何元素的最快方法

来源

2014-06-21 Yekoor

你真的需要一本字典或一套吗？ –

一套也可以工作。 – Yekoor

+1分析！ – Gabe

尝试

Enumerable.ToList(dictionary.Values)[new Random().next(dictionary.Count)].

应该有相当不错的表现，但注意内存的使用情况，如果你的字典是巨大的。显然，请不要每次创建随机对象，并且如果其成员不会频繁更改，则可能会缓存返回值Enumerable.ToList。

来源

2014-06-21 13:46:26

我将它重写为Enumerable.ToList（dictionary.Values）[0]，因为我只需要任何元素。但ToList（）现在占用CPU时间的38％。所以看起来像枚举器更快。 – Yekoor

正如你所指出的，为了使这个表现更好，返回的列表肯定需要被缓存，因为创建一个完整的列表副本而不是使用枚举器肯定是更加努力的。如果我没有弄错，A *算法总是改变所述列表的内容，所以不能直接进行缓存。应该可以手动更新列表，但这似乎没有比更专门的方法带来多少好处。 – mafu

查找字典中的第一个（或索引）元素实际上是O（n），因为它必须迭代每个存储桶直到找到一个非空的元素，因此MoveNext实际上是最快的方法。

如果这是一个问题，我会考虑使用类似堆栈的东西，其中pop是O（1）操作。

来源

2014-06-21 14:00:26 Gabe

我认为“DictionaryStack”对于这种情况来说是完美的。 – mafu

为了达到这个目的，我建议你使用专门的数据结构，因为没有为此设置常规字典。

在Java中，我可能会推荐LinkedHashMap，它有自定义的C＃等价物（不是内置的悲哀）（see）。

然而，以合理的方式自己实现这一点相当容易。例如，你可以使用带有元组的指向下一个元素的常规字典以及实际数据。或者您可以保留一个辅助堆栈，只需按照添加顺序存储所有密钥。只是一些想法。我从来没有实现过，也没有亲自分析过，但我相信你会找到一个好方法。

哦，如果你还没有，你可能还想检查哈希码分布，以确保没有问题。

来源

2014-06-21 14:03:35 mafu

从字典中获取任何元素的最快方法

回答

相关问题