284

SortedList<TKey,TValue>a和 a之间有什么真正的实际区别SortedDictionary<TKey,TValue>吗？在任何情况下您会专门使用一种而不是另一种吗？

4

7 回答 7

321

是的 - 它们的性能特征显着不同。调用它们可能会更好SortedList，SortedTree因为这更能反映实现。

查看每个文件的 MSDN 文档 ( SortedList, SortedDictionary)，了解在不同情况下不同操作的性能细节。这是一个很好的总结（来自SortedDictionary文档）：

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) 而不是 O(n) for SortedList<TKey, TValue>.

  • 如果列表是从排序的数据中一次性填充的，SortedList<TKey, TValue>则比 SortedDictionary<TKey, TValue>.

（SortedList实际上维护一个排序数组，而不是使用树。它仍然使用二进制搜索来查找元素。）

于 2009-06-01T16:38:04.353 回答
121

如果有帮助，这是一个表格视图...

从性能的角度来看：

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | O(n)**  | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

  * Insertion is O(log n) for data that are already in sort order, so that each 
    element is added to the end of the list. If a resize is required, that element
    takes O(n) time, but inserting n elements is still amortized O(n log n).
    list.
** Available through enumeration, e.g. Enumerable.ElementAt.

从实现的角度来看：

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

粗略地说，如果您需要原始性能SortedDictionary可能是更好的选择。如果您需要更少的内存开销并且索引检索SortedList更适合。有关何时使用 which 的更多信息，请参阅此问题。

您可以在此处、此处、此处、此处和此处阅读更多内容。

于 2014-05-20T20:14:29.703 回答
23

我打开了 Reflector 来看看这个，因为似乎有点困惑SortedList。它实际上不是二叉搜索树，它是键值对的排序（按键）数组。还有一个TKey[] keys变量与键值对同步排序并用于二进制搜索。

这是一些来源（针对 .NET 4.5）来支持我的声明。

私人会员

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.ctor(IDictionary, IComparer) 

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

SortedList.Add(TKey, TValue) : 无效

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

SortedList.RemoveAt(int) : 无效

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}
于 2013-02-23T05:53:48.467 回答
13

查看SortedList 的 MSDN 页面：

从备注部分：

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

  • SortedList<(Of <(TKey, TValue>)>)使用的内存少于SortedDictionary<(Of <(TKey, TValue>)>).

  • SortedDictionary<(Of <(TKey, TValue>)>)与forO(log n)相比，对未排序的数据具有更快的插入和删除操作。O(n)SortedList<(Of <(TKey, TValue>)>)

  • 如果列表是从排序的数据中一次性填充的，SortedList<(Of <(TKey, TValue>)>)则比SortedDictionary<(Of <(TKey, TValue>)>).

于 2009-06-01T16:39:21.060 回答
13

这是性能如何相互比较的直观表示。

于 2014-05-30T08:09:17.960 回答
11

关于这个话题已经说得够多了，但是为了简单起见，这是我的看法。

在以下情况下应使用排序字典-

  • 需要更多的插入和删除操作。
  • 未排序的数据。
  • 密钥访问就足够了，不需要索引访问。
  • 内存不是瓶颈。

另一方面，应在以下情况下使用排序列表：

  • 需要更多的查找和更少的插入和删除操作。
  • 数据已经排序（如果不是全部，大多数）。
  • 需要索引访问。
  • 内存是一种开销。

希望这可以帮助！！

于 2016-06-06T15:11:00.943 回答
1

索引访问（这里提到）是实际的区别。如果需要访问后继者或前驱者，则需要 SortedList。SortedDictionary 无法做到这一点，因此您在如何使用排序（first / foreach）方面受到了相当大的限制。

于 2014-11-15T14:36:47.767 回答