c# - 为什么排序字典和列表的添加、删除和获取值比未排序慢？

Question

我做了一些测试:SortedDictionary、SortedList 和 Dictionary(只是为了比较)。结果是，Dictionary 在基于键添加、删除和返回值方面比其他两个要快得多(每个字典中有 100,000 对键+值)。

有人可以告诉我为什么 SortedList 和 SortedDictionary 比 Dictionary 慢吗？

Answer 1

举一个基于未排序列表的排序列表的简单示例。

假设在未排序列表中任意索引处的插入时间为 O(n/2)，其中 n 是列表的大小。这反射(reflect)出，平均而言，一半的列表元素必须被替换，以便为要插入的元素腾出空间。

类似地，在此列表中，从任意位置删除元素也是 O(n/2)，因为平均而言，必须移动一半的元素才能缩小间隙。

。 。 。

现在，想象一下相同的实现，但进行了排序。

排序必须在插入时完成——它必​​须找到新元素的位置。由于所有先前的元素都已排序(我们在插入时进行排序，所以这是正确的)，因此我们可以从头开始扫描。

在我们开始插入之前，这是一个 O(n/2) 操作。那只是找到插入点。

更好的方法是使用二分搜索，这样我们就能以 O(log n) 的时间复杂度找到插入位置，但仍然需要支付 O(n/2) 的插入本身成本。

如果扫描操作的成本为 s，插入操作的成本为 m(用于移动)，则排序插入的成本为:

s x O(log n) + m x (n/2)

但是，在未排序列表的任意位置进行插入操作只能是:

 m x (n /2)

这是排序操作花费更长时间的真正原因的具体示例。

此类理论还有更多内容，但这应该是一个开始。