c# - 何时使用 SortedList 而不是 SortedDictionary？

Question

这似乎是这个 question 的副本，它会问“SortedList 和 SortedDictionary 有什么区别？”不幸的是，答案只是引用了 MSDN 文档(其中明确指出两者之间存在性能和内存使用差异)，但实际上并未回答问题。

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

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:

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

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

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

所以，很明显这表明 SortedList<TKey, TValue>是更好的选择除非您需要更快地插入和删除未排序数据的操作。

问题仍然存在，鉴于以上信息，使用 SortedDictionary<TKey, TValue> 的实际(现实世界、业务案例等)原因是什么？ ？根据性能信息，这意味着确实没有必要 SortedDictionary<TKey, TValue>完全没有。

Answer 1

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

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

每个测试都对包含 10,000 个 int32 键的 SortedList/SortedDictionary 进行操作。每个测试重复 1,000 次(发布构建、不调试启动)。

第一组测试按从 0 到 9,999 的顺序添加键。第二组测试在 0 到 9,999 之间添加随机打乱的 key (每个数字恰好添加一次)。

***** 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 对未排序数据的 Add 操作要慢得多，这是相当令人惊讶的。排序列表也可能同时将项目添加到排序的线性数据结构中，这会减慢速度。

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