在实践中,SortedList<TKey,TValue>
和SortedDictionary<TKey,TValue>
之间是否存在任何真正的实际差异?是否有任何情况下你会特别使用其中一个而不是另一个?
在实践中,SortedList<TKey,TValue>
和SortedDictionary<TKey,TValue>
之间是否存在任何真正的实际差异?是否有任何情况下你会特别使用其中一个而不是另一个?
是的 - 两者的性能特征有很大的不同。更好的称呼可能是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),而SortedList<TKey,TValue>
则具有O(n)。如果列表一次性从排序数据中填充,
SortedList<TKey,TValue>
比SortedDictionary<TKey,TValue>
更快。
(SortedList
实际上维护了一个已排序的数组,而不是使用树。它仍然使用二分查找来查找元素。)
如果有助于理解,这里是表格视图...
从性能的角度来看:
+------------------+---------+----------+--------+----------+----------+---------+
| 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 |
+------------+---------------+----------+------------+------------+------------------+
< p >简单概括一下,如果您需要原始性能,SortedDictionary
可能是更好的选择。如果您需要较低的内存开销和索引检索,则SortedList
更适合。请参阅此问题以了解更多有关何时使用哪种的信息。
BDictionary<Key,Value>
而不是 SortedDictionary
。链接 - QwertieBDictionary
通常比SortedDictionary
慢,但如果有超过700个项目,它比SortedList
更快。由于在树的叶子中使用数组,内存使用应该只比SortedList
略高(比SortedDictionary
低得多)。 - Qwertie// 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) : void
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) : void
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++;
}
已经有足够的关于这个主题的讨论了,然而为了简化,以下是我的看法。
当-
另一方面,当-
希望能对您有所帮助!
这是一种将性能相互比较的可视化表示方式。
Dictionary<K, V>
不保留其元素的插入顺序,而 SortedList<K, V>
和 SortedDictionary<K, V>
则按照给定的 IComparer<K>
进行排序。 - Steve Guidi来自备注部分:
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>)>)
对于未排序的数据具有更快的插入和删除操作,是O(log n)
,而不是SortedList<(Of <(TKey, TValue>)>)
的O(n)
。如果列表一次性从已排序的数据中填充,则
SortedList<(Of <(TKey, TValue>)>)
比SortedDictionary<(Of <(TKey, TValue>)>)
更快。
索引访问(在此处提到)是实际上的区别。如果需要访问后继或前驱,您需要使用SortedList。SortedDictionary无法做到这一点,因此您在使用排序(首个/foreach)时受到相当大的限制。
SortedList<TKey, TValue>
而不是一个SortedList<T>
?它为什么没有实现IList<T>
?我感到困惑。 - Colonel Panic