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

Question

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

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

Answer 1

以基于未排序列表的排序列表为例。

让我们假设在任意索引处的未排序列表上的插入时间为 O(n/2)，其中 n 是列表的大小。这反映了平均而言，一半的列表元素必须被移动，以便为插入的元素腾出空间。

类似地，在这个列表中，从任意位置移除一个元素也是 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)

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

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

Answer 2

Because these data structures do a sort again each time you add or remove values from them. So you get a performance hit when using them.

Answer 3

Dictionary 只是在列表末尾抛出新条目。它所要做的就是跟踪列表末尾的位置。但是，SortedDictionary 必须在列表中找到正确的位置来放置新条目。显然，这需要一些计算工作，并且比简单地将其添加到末尾要慢。

对于删除，这两种类型的对象都必须找出要删除的记录，但排序类型需要评估删除该记录对其内部结构的影响。例如，一个 b-tree 可能需要在删除后重新平衡它的分支。同样需要一些计算来评估这一点。因此性能上的差异。