0

当我使用SortedDictionary<>而不是Dictionary<>考虑到我需要一个排序的字典时是否会影响性能，所以如果我使用字典，我将不得不手动对其进行排序。哪个会更快？ SortedDictionary<>或 ( Dictionary<>+ 手动排序)。

4

4 回答 4

3

插入 aSortedDictionary是 O(log(n))，所以插入 n 项是 O(n log(n))。相反，插入 aDictionary是 O(1)，因此插入 n 个项目是 O(n)，但您需要在使用前对项目进行排序，即 O(n log(n))。基于此，没有太大区别，但Dictionary有散列的开销，而 SortedDictionary 可能具有更差的内存局部性，因为它可能是作为链接结构实现的。

SortedDictionary 还限制了您可以使用的键类型，因为它需要按键排序，而 Dictionary 则没有，因为它使用散列。

确实，哪个更好取决于您的访问模式，因此最好的办法是针对您的用例衡量两者的性能。

于 2013-02-28T21:14:11.443 回答
1

性能受到影响。阅读http://msdn.microsoft.com/en-us/library/f7fta44c.aspx上的备注

基本上，SortedDictionary<T>是二叉搜索树，Dictionary<T>而是哈希表。

对于插入、删除和随机查找，Dictionary<T>会更快。SortedDictionary如果您按顺序进行不频繁的修改和频繁的列表，将会更快。Dictionary如果您进行频繁的修改和随机查找，则速度会更快，并且很少需要排序然后输出。

于 2013-02-28T21:11:12.130 回答
1

这真的取决于你如何使用字典。

  • 您使用的是很多物品还是不是很多物品。
  • 与需要排序的时间相比，您添加新项目的频率。
  • 你做更多的查找或插入

最好的办法是使用这两种方法对真实数据进行一些性能测试，看看哪种方法更适合您的情况。

于 2013-02-28T21:13:33.393 回答
1

这取决于您是将数据添加到字典中而不是获取排序结果，还是一次性完成。

如果您在较长时间内添加数据，每次使用 a 的添加都会对性能造成小幅影响SortedDictionary<>，但是当您最终想要排序结果时，您会立即得到它。例如，如果您等待用户输入添加项目，这是理想的，因为小的性能影响并不明显。

If you create a dictionary, add data to it, and get the sorted result right away, a Dictionary<T> would be faster because it uses a faster sorting algorithm (as it can sort it all at once instead of maintaining a sorted result while items are added).

于 2013-02-28T21:20:34.063 回答