何时通过SortedDictionary <TKey,TValue>使用SortedList <TKey,TValue>?

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

事实上(所以这个问题没有得到相同的答案),根据MSDN:

SortedList<TKey, TValue>generics类是一个O(log n)检索的二叉search树,其中n是字典中元素的数量。 在这里,它类似于SortedDictionary<TKey, TValue>generics类。 这两个类有相似的对象模型,都有O(log n)检索。 这两个类别在内存使用和插入和删除速度方面存在差异:

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

  • SortedDictionary<TKey, TValue>对未sorting的数据有更快的插入和删除操作,O(log n)与SortedList<TKey, TValue> O(n)相对。

  • 如果列表从已sorting的数据一次全部填充,则SortedList<TKey, TValue>SortedDictionary<TKey, TValue>快。

所以,显然这表明SortedList<TKey, TValue>是更好的select, 除非您需要更快地插入和删除未sorting数据的操作。

问题仍然存在,鉴于上面的信息是什么使用SortedDictionary<TKey, TValue>的实际(真实世界,商业案例等)原因? 根据性能信息,这意味着根本不需要有SortedDictionary<TKey, TValue>

我不确定MSDN文档在SortedListSortedDictionary上有多准确。 这似乎是说这两个都是使用二叉search树实现的。 但是,如果SortedList使用二叉search树,那么为什么添加比SortedDictionary慢?

无论如何,这里有一些性能testing结果。

每个testing对包含10,000个int32键的SortedList / SortedDictionary进行操作。 每个testing重复1.000次(发布版本,开始不debugging)。

第一组testing按顺序从0增加到9,999。 第二组testing添加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 

至于任何分析,重要的是相对的performance,而不是实际的数字。

正如你所看到的,在sorting数据上,sorting列表比SortedDictionary快。 在未sorting的数据上, SortedList检索速度稍微快一些,但是添加速度要慢9倍左右。

如果两者都在内部使用二叉树,那么令人惊讶的是对未sorting数据的Add操作对于SortedList来说太慢了。 sorting列表也可能是同时向sorting后的线性数据结构添加项目,这会降低速度。

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

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

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

每次插入元素时,首先检查数组是否具有足够的容量,如果不是,则重新创build一个更大的数组,并将旧元素复制到其中(如List<T>

之后,它使用二进制search来search插入元素的位置(这是可能的,因为该数组是可索引的并且已经sorting)。

为了保持数组的sorting,它将移动(或推)位于要插入元素位置之后的所有元素 (使用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 . . 

这就解释了为什么当插入未sorting的元素时, SortedList性能如此糟糕。 它必须重新复制一些元素几乎每一个插入。 唯一的情况是不得不在数组的末尾插入元素。

SortedDictionary<TKey, TValue>是不同的,并使用二叉​​树来插入和检索元素。 它也有插入的成本,因为有时树需要重新平衡(但不是每插入)。

使用SortedListSortedDictionarysearch元素时,性能非常相似,因为它们都使用二分search。


在我看来,你不应该使用SortedList来sorting数组。 除非有很less的元素,否则将值插入到列表(或数组)中然后调用Sort()方法将会更快。

当你有一个已经sortingSortedList值的列表(例如:从数据库)时, SortedList是非常有用的,你想保持它的sorting并执行一些操作,以便利用sorting(例如: SortedList Contains()方法执行二分查找而不是线性search)

SortedDictionary提供了与SortedList相同的优点,但如果要插入的值尚未sorting,则执行效果会更好。


编辑:如果您使用的是.NET Framework 4.5, SortedDictionary<TKey, TValue>的替代项是SortedSet<T> 。 它和SortedDictionary ,使用二叉树,但是键和值在这里是一样的。

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

这两个集合types在.NET中没有太多的语义差异。 它们都提供了键控查找,并按照键的顺序保存条目。 在大多数情况下,你会对其中的任何一个都行。 也许唯一的区别是SortedList允许的索引检索。

但是performance呢?

但是,性能差异可能是select它们之间更强的因素。 以下是它们渐近复杂性的表格视图。

 +------------------+---------+----------+--------+----------+----------+---------+ | 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. 减less内存开销是可取的。
  3. 你的input数据已经sorting(比如你已经从数据库中订购了)。

在下列情况下,您应该更喜欢SortedDictionary<K, V>

  1. 相对的整体performance很重要(关于缩放)。
  2. 你的input数据是无序的。

编写代码

SortedList<K, V>SortedDictionary<K, V>实现了IDictionary<K, V> ,所以在你的代码中你可以从方法返回IDictionary<K, V>或者声明IDictionary<K, V>variables。 基本上隐藏实现细节,并针对接口进行编码。

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

将来,如果您对某个系列的性能特点不满意,可以更容易地进行切换。


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

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

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

我不知道这一点,但据我所知字典商店数据在树结构,而列表存储数据线性arrays。 这就解释了为什么插入和删除字典更快,因为更less的内存需要转移。 这也解释了为什么你可以遍历SortedLists而不是SortedDictionary。

性能差异的可视化表示。

在这里输入图像说明