什么时候使用SortedList<TKey，TValue>而不是SortedDictionary<TKey，TValue>？

Question

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

事实上(因此这个问题没有得到相同的答案)，根据MSDN：

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

• SortedList<TKey, TValue>使用的内存比SortedDictionary<TKey, TValue>少。
• 对于未排序数据，SortedDictionary<TKey, TValue>具有更快的插入和删除操作，与SortedList<TKey, TValue>的O(n)相比，O(log )的插入和删除操作更快。
• 如果从排序数据一次性填充列表，则SortedList<TKey, TValue>比SortedDictionary<TKey, TValue>更快。

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

这个问题仍然存在，考虑到上面的信息，什么是实际的(现实世界，商业案例等等)。使用SortedDictionary<TKey, TValue>的原因？根据性能信息，这意味着根本不需要使用SortedDictionary<TKey, TValue>。

Answer 1

我不确定SortedList和SortedDictionary上的MSDN文档有多准确。这似乎是说两者都是使用二进制搜索树实现的。但是如果SortedList使用二进制搜索树，为什么它在添加时比SortedDictionary慢得多？

总之，这里有一些性能测试结果。

每个测试都在包含10,000个SortedList密钥的SortedDictionary / int32上运行。每个测试重复1000次(发布构建，开始时不进行调试)。

第一组测试按0到9 999顺序添加键。第二组测试添加0到9999之间的随机混合密钥(每个数字加一次)。

***** 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来说，对未排序数据的添加操作要慢得多，这是非常令人惊讶的。排序列表也可能同时将项添加到排序的线性数据结构中，这会使其慢下来。

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

Answer 2

我不知道为什么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>是不同的，它使用二叉树插入和检索元素。它在insert上也有一些成本，因为有时树需要重新平衡(但不是每一个插入)。

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

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

当您有一个已经排序的值列表(例如:从数据库中)时，SortedList非常有用，您希望对其进行排序，并执行一些利用排序的操作(例如：SortedList的Contains()方法执行二进制搜索而不是线性搜索)。

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

编辑:如果您使用的是.NET Framework4.5，则SortedDictionary<TKey, TValue>的替代方案是SortedSet<T>。它的工作方式与SortedDictionary一样，使用二叉树，但是这里的键和值是相同的。

Answer 3

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

在.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>：

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. 

将来，如果您对一个集合的性能特性不满意，就更容易从这两个集合中切换。

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