当使用排序列表 在SortedDictionary ？(When to use a Sor

这似乎是这个的重复问题 ，其中问“有什么之间的区别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），用于更快的插入和移除操作SortedList<TKey, TValue> 。

• 如果该列表是从排序的数据填充全部一次， SortedList<TKey, TValue>快于SortedDictionary<TKey, TValue> 。

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

现在的问题仍然存在，鉴于上述哪些实用的信息（真实世界，商业案例等）原因使用SortedDictionary<TKey, TValue> ？ 基于性能的信息，这将意味着，真的有没有必要有SortedDictionary<TKey, TValue>的。

Answer 1:

我不知道MSDN文档如何准确的对SortedList和SortedDictionary 。 这似乎是说两者都使用二叉搜索树实现。 但是，如果SortedList的使用二叉搜索树，为什么会是在增加远远慢SortedDictionary ？

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

每个测试上的操作SortedList / SortedDictionary包含10,000 INT32密钥。 每次测试重复1.000倍（发布版本，不开始调试）。

测试的第一组中的序列添加密钥从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>是不同的，并且使用的二进制树来插入和检索的元素。 它也有插入一些成本，因为有时候树需要重新平衡（但不是每个插入）。

性能颇为相似，而搜索与元素SortedList或SortedDictionary因为它们都使用二进制搜索。

---

在我看来，你不应该使用SortedList ，只是数组排序。 除非你有非常少的元素，它总是会更快的值插入列表（或阵列），然后调用Sort()方法。

SortedList ，当你已经整理值的列表是最有用（例如：从数据库），你要保持它排序，并执行一些操作，将利用它进行排序（如： Contains()的方法SortedList执行二进制搜索代替线性搜索）

SortedDictionary提供相同的优点比SortedList ，但如果插入值尚未排序执行得更好。

---

编辑：如果正在使用的.NET Framework 4.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. 您输入的数据已经排序（说你得到它已经从数据库排序）。

你反而会希望喜欢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. 

在未来，它更容易切换从任的情况下，你不快乐的一个集合的性能特性。

---

有关两种集合类型的详细信息见原来的问题联系在一起。

Answer 4:

的性能差异可视化表示。

Answer 5:

这里的所有都是它的。 键检索相媲美，但除了是字典快得多。

我尝试使用排序列表尽可能的，因为它可以让我遍历键和收藏价值。 这是不可能的SortedDictionary据我所知。

我不知道这一点，但据我所知在树形结构字典存储数据，而线性阵列列表存储数据。 这就解释了为什么插入和删除是字典快得多，因为更少的内存，必须围绕转变。 这也解释了为什么你可以遍历SortedLists但不是SortedDictionary。

Answer 6:

对我们来说是重要的考虑因素是，我们经常有小词典（<100元），以及当前processessors在访问顺序内存，同时执行几个很难预测的分支要快得多。 （即在迭代的线性阵列，而不是遍历树），所以当你在你的字典低于约60元，排序列表<>往往是许多用例最快和最有效的记忆字典。

文章来源: When to use a SortedList over a SortedDictionary?