Tal vez una pregunta tonta, pero hay una real diferencia práctica entre un SortedList
y SortedDictionary
? Hay circunstancias en las que específicamente se utilice uno y el otro no?
Respuestas
¿Demasiados anuncios?Sí - sus características difieren significativamente. Probablemente sería mejor llamarlas SortedList
y SortedTree
como la que se refleja la aplicación más de cerca.
Buscar en el MSDN docs para cada uno de ellos (SortedList
, SortedDictionary
) para los detalles de la ejecución de diferentes operaciones en diferentes situtations. He aquí un buen resumen (de la SortedDictionary
docs):
La
SortedDictionary<TKey, TValue>
genérico la clase es un árbol de búsqueda binario con O(log n) de recuperación, donde n es el número de elementos en el diccionario. En esto, es similar a laSortedList<TKey, TValue>
genérico clase. Las dos clases similares modelos de objetos, y ambos tienen O(log n) recuperación. Donde las dos clases difieren es en el uso de la memoria y la velocidad de inserción y eliminación:
SortedList<TKey, TValue>
utiliza menos memoria deSortedDictionary<TKey, TValue>
.
SortedDictionary<TKey, TValue>
ha más rápido de inserción y de eliminación de las operaciones para los datos sin ordenar, O(log n) como contraposición a O(n) paraSortedList<TKey, TValue>
.Si la lista se rellena de una vez de datos ordenados,
SortedList<TKey, TValue>
es más rápido queSortedDictionary<TKey, TValue>
.
(SortedList
realmente mantiene un conjunto ordenado, en lugar de utilizar un árbol. Todavía se utiliza binario de búsqueda para encontrar los elementos.)
Aquí está una vista tabular si ayuda...
A partir de un rendimiento de perspectiva:
+------------------+---------+----------+--------+----------+----------+---------+
| Collection | Indexed | Keyed | Value | Addition | Removal | Memory |
| | lookup | lookup | lookup | | | |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser |
| SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+
* Insertion is O(1) for data that are already in sort order, so that each
element is added to the end of the list (assuming no resize is required).
A partir de la aplicación de la perspectiva:
+------------+---------------+----------+------------+------------+------------------+
| 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 |
+------------+---------------+----------+------------+------------+------------------+
A aproximadamente paráfrasis, si usted requiere de rendimiento bruto SortedDictionary
podría ser una mejor opción. Si usted requiere menor sobrecarga de la memoria y la recuperación indizada SortedList
encaja mejor. Ver esta cuestión para obtener más información sobre cuándo utilizar.
Usted puede leer más aquí, aquí, aquí, aquí y aquí.
Me partió el Reflector a echar un vistazo a este como parece haber un poco de confusión acerca de SortedList
. En realidad no se trata de un árbol de búsqueda binario, es una ordenados (clave) de la matriz de pares clave-valor. También hay un TKey[] keys
variable que se ordena en la sincronización con los pares clave-valor y se utiliza para búsqueda binaria.
Aquí hay algunas de origen (de la orientación .NET 4.5) para copia de seguridad de mis reclamaciones.
Los miembros privados
// 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.cto r(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.Agregar(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++;
}
Echa un vistazo a la página de MSDN para SortedList:
Desde la sección de Observaciones:
La
SortedList<(Of <(TKey, TValue>)>)
clase genérica es un árbol de búsqueda binario conO(log n)
de recuperación, donden
es el número de elementos en el diccionario. En esto, es similar a laSortedDictionary<(Of <(TKey, TValue>)>)
clase genérica. Las dos clases similares modelos de objetos, y ambos tienenO(log n)
de recuperación. Donde las dos clases que se diferencian es en el uso de la memoria y la velocidad de inserción y eliminación:
SortedList<(Of <(TKey, TValue>)>)
utiliza menos memoria queSortedDictionary<(Of <(TKey, TValue>)>)
.
SortedDictionary<(Of <(TKey, TValue>)>)
tiene más rápido de inserción y las operaciones de extracción de datos sin ordenar,O(log n)
frente aO(n)
paraSortedList<(Of <(TKey, TValue>)>)
.Si la lista se rellena de una vez por todas de datos ordenados,
SortedList<(Of <(TKey, TValue>)>)
es más rápido queSortedDictionary<(Of <(TKey, TValue>)>)
.