114

我发现SortedList<TKey, TValue> SortedDictionary<TKey, TValue>并Dictionary<TKey, TValue>实现了相同的接口。

  1. 我们什么时候应该选择SortedList和SortedDictionary结束Dictionary？
  2. SortedList在应用方面和SortedDictionary方面有什么区别？
4

6 回答 6

107

  1. 当迭代两者中的任何一个元素时，将对元素进行排序。不是这样Dictionary<T,V>。

  2. MSDNSortedList<T,V>解决了​​ 和之间的区别SortedDictionary<T,V>：

SortedDictionary(TKey, TValue) 泛型类是具有 O(log n) 检索的二叉搜索树，其中 n 是字典中元素的数量。在这方面，它类似于 SortedList(TKey, TValue) 泛型类。这两个类具有相似的对象模型，并且都具有 O(log n) 检索。这两个类的不同之处在于内存使用和插入和删除速度：

SortedList(TKey, TValue) 使用的内存比 SortedDictionary(TKey, TValue) 少。

SortedDictionary(TKey, TValue) 对未排序的数据具有更快的插入和删除操作：O(log n) 相对于 SortedList(TKey, TValue) 的 O(n)。

如果列表是从排序数据中一次性填充的，SortedList(TKey, TValue) 比 SortedDictionary(TKey, TValue) 快。

于 2009-09-15T13:23:44.877 回答
72

在此处输入图像描述

我会提到字典之间的区别。

上图显示，Dictionary<K,V>在每种情况下，它都等于或快于Sorted模拟，但如果需要元素的顺序，例如打印它们，Sorted则选择一个。

来源：http : //people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

于 2013-10-31T09:29:46.843 回答
27

总结性能测试的结果 - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable，不同场景的结果从最好到最差：

内存使用情况：

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

插入：

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

搜索操作：

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

foreach 循环操作

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
于 2015-11-12T13:29:30.003 回答
17

我可以看到建议的答案侧重于性能。下面提供的文章没有提供有关性能的任何新内容，但它解释了底层机制。另请注意，它并不关注Collection问题中提到的三种类型，而是解决了System.Collections.Generic命名空间的所有类型。

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

提取物：

字典<>

Dictionary 可能是最常用的关联容器类。Dictionary 是关联查找/插入/删除最快的类，因为它在幕后使用哈希表。因为键是散列的，所以键类型应该正确地实现 GetHashCode() 和 Equals()或者你应该在构造时为字典提供一个外部 IEqualityComparer。字典中项目的插入/删除/查找时间是摊销的常数时间 - O(1) - 这意味着无论字典有多大，查找某些内容所需的时间都保持相对恒定。这对于高速查找是非常可取的。唯一的缺点是字典，本质上使用哈希表，是无序的，所以您不能轻松地按顺序遍历 Dictionary 中的项目。

排序字典<>

SortedDictionary 在使用上与 Dictionary 类似，但在实现上却大不相同。SortedDictionary在后台使用二叉树来按 key 保持项目的顺序。作为排序的结果，用于键的类型必须正确实现 IComparable以便键可以正确排序。排序字典用一点查找时间换取了按顺序维护项目的能力，因此排序字典中的插入/删除/查找时间是对数的 - O(log n)。一般来说，使用对数时间，您可以将集合的大小加倍，并且只需执行一次额外的比较即可找到该项目。当您想要快速查找但又希望能够通过键按顺序维护集合时，请使用 SortedDictionary。

排序列表<>

SortedList 是通用容器中的另一个排序关联容器类。再一次，SortedList 和 SortedDictionary 一样，使用一个键来对键值对进行排序。然而，与 SortedDictionary 不同的是， SortedList 中的项目存储为已排序的项目数组. 这意味着插入和删除是线性的 - O(n) - 因为删除或添加项目可能涉及在列表中向上或向下移动所有项目。但是，查找时间为 O(log n)，因为 SortedList 可以使用二分搜索通过其键查找列表中的任何项目。那么你为什么要这样做呢？嗯，答案是，如果你要预先加载 SortedList，插入会更慢，但是因为数组索引比对象链接快，查找比 SortedDictionary 快一点。再一次，我会在您想要快速查找并希望通过键按顺序维护集合以及插入和删除很少的情况下使用它。

基本程序的初步总结

非常欢迎提供反馈，因为我确信我没有做对所有事情。

  • 所有数组的大小为n。
  • 未排序的数组 = .Add/.Remove 是 O(1)，但 .Item(i) 是 O(n)。
  • 排序数组 = .Add/.Remove 是 O(n)，但 .Item(i) 是 O(log n)。

字典

记忆

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

添加

  1. 添加HashArray(n) = Key.GetHash# O(1)
  2. 添加KeyArray(n) = PointerToKey# O(1)
  3. 添加ItemArray(n) = PointerToItem# O(1)

消除

  1. For i = 0 to ni,找到HashArray(i) = Key.GetHash # O(log n) (排序数组)
  2. 删除HashArray(i)#O(n)（排序数组）
  3. 删除KeyArray(i)# O(1)
  4. 删除ItemArray(i)# O(1)

获取物品

  1. For i = 0 to ni,找到HashArray(i) = Key.GetHash# O(log n) (排序数组)
  2. 返回ItemArray(i)

依次通过

  1. For i = 0 to n， 返回ItemArray(i)

排序字典

记忆

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

添加

  1. 添加KeyArray(n) = PointerToKey# O(1)
  2. 添加ItemArray(n) = PointerToItem# O(1)
  3. For i = 0 to n, 找到i哪里KeyArray(i-1) < Key < KeyArray(i)(使用ICompare) # O(n)
  4. 添加OrderArray(i) = n# O(n)（排序数组）

消除

  1. For i = 0 to ni,找到KeyArray(i).GetHash = Key.GetHash# O(n)
  2. 删除KeyArray(SortArray(i))# O(n)
  3. 删除ItemArray(SortArray(i))# O(n)
  4. 删除OrderArray(i)#O(n)（排序数组）

获取物品

  1. For i = 0 to ni,找到KeyArray(i).GetHash = Key.GetHash# O(n)
  2. 返回ItemArray(i)

依次通过

  1. For i = 0 to n， 返回ItemArray(OrderArray(i))

排序列表

记忆

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

添加

  1. For i = 0 to n, 找到i哪里KeyArray(i-1) < Key < KeyArray(i)（使用ICompare）# O(log n)
  2. 添加KeyArray(i) = PointerToKey# O(n)
  3. 添加ItemArray(i) = PointerToItem# O(n)

消除

  1. For i = 0 to ni,找到KeyArray(i).GetHash = Key.GetHash# O(log n)
  2. 删除KeyArray(i)# O(n)
  3. 删除ItemArray(i)# O(n)

获取物品

  1. For i = 0 to ni,找到KeyArray(i).GetHash = Key.GetHash# O(log n)
  2. 返回ItemArray(i)

依次通过

  1. For i = 0 to n， 返回ItemArray(i)
于 2019-02-20T16:02:08.553 回答
9

  1. 当您希望在迭代集合时按键对集合进行排序。如果您不需要对数据进行排序，最好只使用一个字典，它会有更好的性能。

  2. SortedList 和 SortedDictionary 几乎做同样的事情，但实现方式不同，因此这里解释了不同的优点和缺点。

于 2009-09-15T13:25:40.720 回答
0

尝试为@Lev 提出的每个案例分配性能分数，我使用了以下值：

  • O(1) = 3
  • O(log n) = 2
  • O(n) = 1
  • O(1) 或 O(n) = 2
  • O(log n) 或 O(n) = 1.5

结果是（更高=更好）：

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

当然，每个用例都会赋予某些​​操作更多的权重。

于 2018-08-02T20:05:25.663 回答