¿Cuál es la diferencia entre SortedList y SortedDictionary?

¿Existe alguna diferencia práctica real entre SortedList y SortedDictionary ? ¿Hay alguna circunstancia en la que usarías específicamente una y no la otra?

Sí, sus características de rendimiento difieren significativamente. Probablemente sea mejor llamarlos SortedList y SortedTree ya que esto refleja la implementación más de cerca.

Mire los documentos de MSDN para cada uno de ellos ( SortedList , SortedDictionary ) para obtener detalles sobre el rendimiento de diferentes operaciones en diferentes situaciones. Aquí hay un buen resumen (de los documentos SortedDictionary ):

La clase genérica SortedDictionary es un árbol de búsqueda binario con recuperación O (log n), donde n es el número de elementos en el diccionario. En esto, es similar a la clase genérica SortedList . Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O (log n). Donde las dos clases difieren es en el uso de la memoria y la velocidad de inserción y eliminación:

  • SortedList usa menos memoria que SortedDictionary .

  • SortedDictionary tiene operaciones de inserción y eliminación más rápidas para datos sin clasificar, O (log n) en oposición a O (n) para SortedList .

  • Si la lista se completa de una sola vez a partir de datos ordenados, SortedList es más rápido que SortedDictionary .

( SortedList realidad mantiene una matriz ordenada, en lugar de utilizar un árbol. Todavía utiliza la búsqueda binaria para encontrar elementos).

Aquí hay una vista tabular si ayuda …

Desde una perspectiva de rendimiento :

 +------------------+---------+----------+--------+----------+----------+---------+ | 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). 

Desde una perspectiva de implementación :

 +------------+---------------+----------+------------+------------+------------------+ | 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 | +------------+---------------+----------+------------+------------+------------------+ 

Para SortedDictionary aproximada , si requiere un rendimiento sin procesar, SortedDictionary podría ser una mejor opción. Si necesita una sobrecarga de memoria menor y una recuperación indexada SortedList encaja mejor. Consulte esta pregunta para obtener más información sobre cuándo usarla.

Puedes leer más aquí , aquí , aquí , aquí y aquí .

Abrí un Reflector abierto para echar un vistazo a esto, ya que parece haber un poco de confusión sobre SortedList . De hecho, no es un árbol de búsqueda binario, es una matriz clasificada (por clave) de pares clave-valor . También hay una variable de TKey[] keys que se ordena en sincronización con los pares clave-valor y se utiliza para la búsqueda binaria.

Aquí hay alguna fuente (orientación .NET 4.5) para respaldar mis reclamos.

Miembros privados

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

SortedList.ctor (IDictionary, IComparer)

 public SortedList(IDictionary dictionary, IComparer 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(this.keys, this.values, comparer); this._size = dictionary.Count; } 

SortedList.Add (TKey, TValue): vacío

 public void Add(TKey key, TValue value) { if (key == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } int num = Array.BinarySearch(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++; } 

Consulte la página de MSDN para SortedList :

De la sección de Comentarios:

La SortedList<(Of <(TKey, TValue>)>) es un árbol de búsqueda binaria con recuperación O(log n) , donde n es el número de elementos en el diccionario. En esto, es similar a la SortedDictionary<(Of <(TKey, TValue>)>) . Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O(log n) . Donde las dos clases difieren es en el uso de la memoria y la velocidad de inserción y eliminación:

  • SortedList<(Of <(TKey, TValue>)>) utiliza menos memoria que SortedDictionary<(Of <(TKey, TValue>)>) .
  • SortedDictionary<(Of <(TKey, TValue>)>) tiene operaciones de inserción y eliminación más rápidas para datos sin clasificar, O(log n) en oposición a O(n) para SortedList<(Of <(TKey, TValue>)>) .

  • Si la lista se rellena todo a la vez a partir de datos ordenados, SortedList<(Of <(TKey, TValue>)>) es más rápido que SortedDictionary<(Of <(TKey, TValue>)>) .

Esta es una representación visual de cómo las actuaciones se comparan entre sí.

Ya se ha dicho suficiente sobre el tema, sin embargo, para mantenerlo simple, esta es mi opinión.

El diccionario ordenado se debe usar cuando-

  • Se requieren más inserciones y operaciones de eliminación.
  • Datos en orden.
  • El acceso a la clave es suficiente y no se requiere acceso al índice.
  • La memoria no es un cuello de botella.

Por otro lado, la lista ordenada debe usarse cuando:

  • Se requieren más búsquedas y menos inserciones y operaciones de eliminación.
  • Los datos ya están ordenados (si no todos, la mayoría).
  • El acceso al índice es obligatorio.
  • La memoria es una sobrecarga.

¡¡Espero que esto ayude!!

Acceso a índice (mencionado aquí) es la diferencia práctica. Si necesita acceder al sucesor o predecesor, necesita SortedList. SortedDictionary no puede hacer eso, por lo que está bastante limitado con respecto a cómo puede usar la clasificación (first / foreach).