69

这似乎是这个问题的重复，它询问“ SortedList和SortedDictionary之间有什么区别？” 不幸的是，答案只不过是引用了 MSDN 文档（其中明确指出两者之间存在性能和内存使用差异），但实际上并没有回答这个问题。

事实上（所以这个问题没有得到相同的答案），根据 MSDN：

SortedList<TKey, TValue>泛型类是具有 O(log n) 检索的二叉搜索树，其中 n 是字典中元素的数量。在这方面，它类似于 SortedDictionary<TKey, TValue>泛型类。这两个类具有相似的对象模型，并且都具有 O(log n) 检索。这两个类的不同之处在于内存使用和插入和删除速度：

  • SortedList<TKey, TValue>使用的内存少于SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue>对未排序的数据具有更快的插入和删除操作，O(log n) 而不是 O(n) for SortedList<TKey, TValue>.

  • 如果列表是从排序的数据中一次性填充的，SortedList<TKey, TValue>则比 SortedDictionary<TKey, TValue>.

因此，显然这表明这SortedList<TKey, TValue>是更好的选择，除非您需要对未排序的数据进行更快的插入和删除操作。

鉴于上述信息，问题仍然存在，使用SortedDictionary<TKey, TValue>? 根据性能信息，这意味着根本没有必要拥有SortedDictionary<TKey, TValue>。

4

6 回答 6

56

我不确定 MSDN 文档在SortedList和SortedDictionary. 似乎是说两者都是使用二叉搜索树实现的。但是如果 SortedList 使用二叉搜索树，为什么它在加法上会比 慢得多SortedDictionary？

无论如何，这里有一些性能测试结果。

每个测试都在包含 10,000 个 int32 键的SortedList/上运行。SortedDictionary每个测试重复 1,000 次（发布构建，开始而不调试）。

第一组测试按从 0 到 9,999 的顺序添加键。第二组测试添加 0 到 9,999 之间的随机混洗键（每个数字仅添加一次）。

***** Tests.PerformanceTests.SortedTest

SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms


SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms

***** Tests.PerformanceTests.UnsortedTest

SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms


SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms

与任何分析一样，重要的是相对性能，而不是实际数字。

如您所见，在排序数据上，排序列表比SortedDictionary. 在未排序的数据SortedList上，检索速度稍快，但添加速度慢约 9 倍。

如果两者都在内部使用二叉树，那么对未排序数据的添加操作对于SortedList. 排序列表也可能同时将项目添加到排序的线性数据结构中，这会减慢速度。

但是，您会期望 a 的内存使用量SortedList等于或大于或至少等于 a SortedDictionary。但这与 MSDN 文档所说的相矛盾。

于 2009-11-18T06:38:44.217 回答
37

我不知道为什么 MSDN 说SortedList<TKey, TValue>使用二叉树来实现它，因为如果你用反编译器查看代码，Reflector你就会意识到它不是真的。

SortedList<TKey, TValue>只是一个随时间增长的数组。

每次插入元素时，它首先检查数组是否有足够的容量，如果没有，则重新创建一个更大的数组并将旧元素复制到其中（如List<T>）

之后，它使用二进制搜索搜索插入元素的位置（这是可能的，因为数组是可索引的并且已经排序）。

为了保持数组排序，它将位于要插入的元素位置之后的所有元素移动（或推送）一个位置（使用Array.Copy()）。

例如：

// we want to insert "3" 

2  
4  <= 3
5
8
9
.      
.      
.  

// we have to move some elements first

2
.  <= 3
4 
5  |
8  v
9
.
.

这就解释了为什么SortedList插入未排序的元素时性能如此糟糕。它几乎每次插入都必须重新复制一些元素。唯一不需要这样做的情况是元素必须插入到数组的末尾。

SortedDictionary<TKey, TValue>不同的是，使用二叉树来插入和检索元素。它在插入时也有一些成本，因为有时需要重新平衡树（但不是每次插入）。

SortedList使用或搜索元素时性能非常相似，SortedDictionary因为它们都使用二进制搜索。

在我看来，你永远不应该只对SortedList数组进行排序。除非您的元素很少，否则将值插入列表（或数组）然后调用Sort()方法总是会更快。

SortedList当您有一个已经排序的值列表时（例如：来自数据库），您希望保持它的排序并执行一些可以利用它排序的操作（例如：执行二进制搜索而不是线性搜索的方法Contains()）SortedList

SortedDictionarySortedList如果要插入的值尚未排序，则提供相同的优点但性能更好。

SortedDictionary<TKey, TValue>编辑：如果您使用的是 .NET Framework 4.5，则可以替代 .NET Framework 4.5 SortedSet<T>。它的工作方式与SortedDictionary使用二叉树的方式相同，但这里的键和值是相同的。

于 2012-03-01T14:19:10.807 回答
11

它们是为了两个不同的目的吗？

.NET 中的这两种集合类型没有太大的语义差异。它们都提供键控查找以及保持条目按键排序。在大多数情况下，您都可以接受其中任何一个。也许唯一的区别是索引检索SortedList许可。

但是性能呢？

但是，性能差异可能是在它们之间进行选择的更重要因素。这是它们渐近复杂度的表格视图。

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

概括

粗略地总结一下，您需要一个SortedList<K, V>何时：

  1. 您需要索引查找。
  2. 希望有更少的内存开销。
  3. 您的输入数据已经排序（假设您已经从 db 订购了它）。

相反，您会更喜欢SortedDictionary<K, V>when：

  1. 相对整体性能很重要（关于缩放）。
  2. 您的输入数据是无序的。

编写代码

两者都SortedList<K, V>实现SortedDictionary<K, V>，IDictionary<K, V>因此在您的代码中，您可以IDictionary<K, V>从方法返回或将变量声明为IDictionary<K, V>. 基本上隐藏实现细节，以及针对接口的代码。

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg.

将来，如果您对某个集合的性能特征不满意，则可以更轻松地从其中一种切换。

有关这两种集合类型的更多信息，请参阅链接的原始问题。

于 2014-05-22T17:21:29.737 回答
4

性能差异的直观表示。

在此处输入图像描述

于 2014-05-30T08:10:48.967 回答
2

这里的所有都是它的。检索键是可比的，但使用字典加法要快得多。

我尝试尽可能多地使用 SortedList，因为它允许我遍历键和值集合。据我所知，这对于 SortedDictionary 是不可能的。

我不确定这一点，但据我所知，字典将数据存储在树结构中，而列表将数据存储在线性数组中。这就解释了为什么字典的插入和删除要快得多，因为需要移动的内存更少。它还解释了为什么可以迭代 SortedLists 而不能迭代 SortedDictionary。

于 2009-09-04T02:38:56.490 回答
0

对我们来说一个重要的考虑因素是我们经常有小的字典（<100 个元素），并且当前的进程在访问顺序内存时要快得多，同时执行一些难以预测的分支。（即迭代线性数组而不是遍历树） 因此，当字典中的元素少于 60 个时，SortedList<> 通常是许多用例中最快且内存效率最高的字典。

于 2018-10-16T19:18:20.603 回答