当使用排序列表＆LT; TKEY的，TValue＆GT;在一个SortedDictionary＆LT; TKEY的，TValue＆GT;？ [英] When to use a SortedList<TKey, TValue> over a SortedDictionary<TKey, TValue>?

问题描述

这可能表现为这种重复<一个href="http://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary">question,它问：什么是间排序列表和的SortedDictionary~~MD~~aux 的？遗憾的是，答案做无非引用MSDN文档（其中明确规定，有两者之间的性能和内存使用的差异），但实际上并没有回答这个问题。

This may appear to be a duplicate of this question, which asks "What’s the difference between SortedList and SortedDictionary?" Unfortunately, the answers do nothing more than quote the MSDN documentation (which clearly states that there are performance and memory use differences between the two) but don't actually answer the question.

在事实上（所以这个问题不得到同样的答案），根据MSDN：

In fact (and so this question doesn't get the same answers), according to MSDN:

在排序列表＆LT; TKEY的，TValue＆GT; 通用   类是用二进制搜索树   O（log n）的检索，其中n是   在字典中的元素数目。   在此，它是类似于    SortedDictionary＆LT; TKEY的，TValue＆GT; 通用   类。这两个类具有相似的   对象模型，并且都为O（log n）的   检索。其中，这两个类   不同之处在于内存使用和速度   插入和删除：

The SortedList<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

  

• 排序列表＆LT; TKEY的，TValue＆GT; 使用较少   内存比 SortedDictionary＆LT; TKEY的，   TValue＆GT;

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.

SortedDictionary＆LT; TKEY的，TValue＆GT; 有   更快的插入和移除   对于未排序的数据操作，O（log n）的   而不是为O（n），用于   排序列表＆LT; TKEY的，TValue＆GT;

SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

如果该列表中填充一次全部   从排序的数据，排序列表＆LT; TKEY的，   TValue＆GT; 比快    SortedDictionary＆LT; TKEY的，TValue＆GT;

If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

因此​​，很明显，这将表明，排序列表＆LT; TKEY的，TValue＆GT; 是更好的选择除非您需要更快的插入和删除操作的< STRONG>未分类数据。

So, clearly this would indicated that SortedList<TKey, TValue> is the better choice unless you need faster insert and remove operations for unsorted data.

现在的问题仍然存在，鉴于上面有什么实际的（真实世界，商业案例等）的理由使用的信息 SortedDictionary＆LT; TKEY的，TValue＆GT; ？基于性能的信息，这将意味着，真的有没有必要有 SortedDictionary＆LT; TKEY的，TValue＆GT; 所有

The question still remains, given the information above what are the practical (real-world, business case, etc.) reasons for using a SortedDictionary<TKey, TValue>? Based on the performance information, it would imply that there really is no need to have SortedDictionary<TKey, TValue> at all.

推荐答案

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

I'm not sure how accurate the MSDN documentation is on SortedList and SortedDictionary. It seems to be saying both are implemented using a binary search tree. But if the SortedList uses a binary search tree, why would it be much slower on additions than SortedDictionary?

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

Anyway, here are some performance test results.

每个测试运行在一个排序列表 / SortedDictionary 包含10,000个INT32键。每次测试重复1.000倍（发布版本，不开始调试）。

Each test operates on a SortedList / SortedDictionary containing 10,000 int32 keys. Each test is repeated 1.000 times (Release build, Start without Debugging).

测试第一组的顺序添加键从0到9,999。测试第二组在0到9,999添加随机洗牌键（每个号码添加只有一次）。

The first group of tests add keys in sequence from 0 to 9,999. The second group of tests add random shuffled keys between 0 to 9,999 (every number is added exactly once).

***** 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

对于任何分析，最重要的是相对业绩，而不是实际的数字。

As with any profiling, the important thing is the relative performance, not the actual numbers.

正如你所看到的，在排序的数据排序列表比 SortedDictionary 更快。在未排序的数据的排序列表是稍快的检索，但增加速度较慢约9倍。

As you can see, on sorted data the sorted list is faster than the SortedDictionary. On unsorted data the SortedList is slightly quicker on retrieval, but about 9 times slower on adding.

如果两者都是内部使用二叉树，这是相当令人惊讶的是对未排序的数据的添加操作是排序列表这么慢得多。这是可能的排序的列表也可以将项目添加到排序的线性数据结构的同时，这会慢下来。

If both are using binary trees internally, it is quite surprising that the Add operation on unsorted data is so much slower for SortedList. It is possible that sorted list may also be adding items to a sorted linear data structure at the same time, which would slow it down.

不过，你所期望的内存使用排序列表等于或大于或至少等于 SortedDictionary 。但是，这有什么矛盾MSDN文档说。

However, you would expect the memory usage of a SortedList to be equal or greater than or at least equal to a SortedDictionary. But this contradicts what the MSDN documentation says.

这篇关于当使用排序列表＆LT; TKEY的，TValue＆GT;在一个SortedDictionary＆LT; TKEY的，TValue＆GT;？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！