何时使用SortedList <TKey,TValue>而不是SortedDictionary <TKey,TValue>？

Question

这似乎与这个问题重复,后者询问" 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>是更好的选择,除非您需要更快的插入和删除未排序数据的操作.

问题仍然存在,鉴于以上信息,使用a的实际(现实世界,商业案例等)原因是SortedDictionary<TKey, TValue>什么？根据绩效信息,这意味着根本没有必要SortedDictionary<TKey, TValue>.

Answer 1

我不确定MSDN文档的准确性SortedList和准确性SortedDictionary.似乎两者都是使用二叉搜索树实现的.但是,如果SortedList使用二进制搜索树,为什么添加时要慢得多SortedDictionary？

无论如何,这里有一些性能测试结果.

每个测试都在SortedList/ SortedDictionary包含10,000个int32键上运行.每个测试重复1.000次(Release build,Start without Debugging).

第一组测试按顺序添加键,从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倍.

如果两者都在内部使用二进制树,则非常令人惊讶的是,对未排序数据的Add操作要慢得多SortedList.排序列表也可能同时将项添加到排序的线性数据结构中,这会减慢它的速度.

但是,您可能希望a的内存使用量SortedList等于或大于或至少等于a 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. 您的输入数据已经排序(假设您已从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. 

将来,如果您对一个系列的性能特征不满意,则更容易切换.

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

Answer 4

性能差异的视觉表示。

Answer 5

这里的所有都是它的。键的检索是可比的，但字典的添加速度要快得多。

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

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