在SortedList<TKey,TValue>和SortedDictionary<TKey,TValue>之间有任何真正的实际区别吗?在某些情况下,你会特别使用其中一种而不是另一种吗?
当前回答
关于这个话题已经说得够多了,但是为了简单起见,这里是我的看法。
排序字典应该使用时-
需要更多的插入和删除操作。 无序数据。 键访问就足够了,不需要索引访问。 内存不是瓶颈。
另一方面,当-时应该使用Sorted List
需要更多的查找和更少的插入和删除操作。 数据已经排序(如果不是全部,也是大部分)。 需要索引访问。 内存是一种开销。
希望这能有所帮助!!
其他回答
是的,它们的表现特征有很大不同。将它们命名为SortedList和SortedTree可能更好,因为这样可以更准确地反映实现。
查看它们各自的MSDN文档(SortedList, SortedDictionary),了解不同情况下不同操作的性能细节。下面是一个很好的总结(来自SortedDictionary文档):
The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal: SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>. SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<TKey, TValue>. If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.
(SortedList实际上维护一个排序的数组,而不是使用树。它仍然使用二进制搜索来查找元素。)
查看SortedList的MSDN页面:
备注部分:
The SortedList<(Of <(TKey, TValue>)>) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this, it is similar to the SortedDictionary<(Of <(TKey, TValue>)>) generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal: SortedList<(Of <(TKey, TValue>)>) uses less memory than SortedDictionary<(Of <(TKey, TValue>)>). SortedDictionary<(Of <(TKey, TValue>)>) has faster insertion and removal operations for unsorted data, O(log n) as opposed to O(n) for SortedList<(Of <(TKey, TValue>)>). If the list is populated all at once from sorted data, SortedList<(Of <(TKey, TValue>)>) is faster than SortedDictionary<(Of <(TKey, TValue>)>).
索引访问(这里提到)是实际的区别。 如果需要访问后继对象或前任对象,则需要SortedList。SortedDictionary无法做到这一点,因此您在如何使用排序(first / foreach)方面受到相当的限制。
我打开Reflector来看看这个,因为似乎有一些关于SortedList的困惑。它实际上不是一个二叉搜索树,它是一个由键-值对排序的数组。还有一个TKey[]键变量,它与键值对同步排序,用于二进制搜索。
这里有一些源代码(针对。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): 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++;
}
如果有用的话,这里有一个表格视图。
从性能角度看:
+------------------+---------+----------+--------+----------+----------+---------+
| 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更适合。关于何时使用哪个,请参阅这个问题。
你可以在这里,这里,这里,这里和这里阅读更多。
推荐文章
- Linq-to-Entities Join vs GroupJoin
- 为什么字符串类型的默认值是null而不是空字符串?
- 在list中获取不同值的列表
- 组合框:向项目添加文本和值(无绑定源)
- AutoMapper:“忽略剩下的?”
- 如何为ASP.net/C#应用程序配置文件值中的值添加&号
- 从System.Drawing.Bitmap中加载WPF BitmapImage
- 如何找出一个文件存在于c# / .NET?
- 为什么更快地检查字典是否包含键,而不是捕捉异常,以防它不?
- [DataContract]的命名空间
- string. isnullorempty (string) vs. string. isnullowhitespace (string)
- 完全外部连接
- 如何使用。net 4运行时运行PowerShell ?
- 在foreach循环中编辑字典值
- 如何在xml文档中引用泛型类和方法