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

261

¿Hay alguna diferencia práctica real entre ay SortedList<TKey,TValue>a SortedDictionary<TKey,TValue>? ¿Hay alguna circunstancia en la que usarías específicamente uno y no el otro?

Shaul Behr
fuente
13
Estoy confundido. ¿Por qué SortedList tiene dos parámetros de tipo en SortedList<TKey,TValue>lugar de uno SortedList<T>? ¿Por qué no se implementa IList<T>?
Coronel Panic
3
@ColonelPanic porque funcionalmente SortedList es un mapa, no una colección lineal. No dejes que el nombre te engañe. Al igual que un diccionario, se pasa una clave y se devuelve un valor. Mientras el diccionario no está ordenado, SortedList se ordena en su orden natural ordenado.
nawfal

Respuestas:

294

Sí, sus características de rendimiento difieren significativamente. Probablemente sería mejor llamarlos SortedListy SortedTreeeso refleja la implementación más de cerca.

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

La SortedDictionary<TKey, TValue>clase genérica 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 SortedList<TKey, TValue>clase genérica. Las dos clases tienen modelos de objetos similares, y ambas 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 extracción:

  • SortedList<TKey, TValue>usa menos memoria que SortedDictionary<TKey, TValue>.

  • SortedDictionary<TKey, TValue>tiene operaciones de inserción y eliminación más rápidas para datos sin clasificar, O (log n) en lugar de O (n) para SortedList<TKey, TValue>.

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

(en SortedListrealidad mantiene una matriz ordenada, en lugar de usar un árbol. Todavía usa la búsqueda binaria para encontrar elementos).

Jon Skeet
fuente
Muchas gracias a todos por los consejos. Supongo que soy demasiado vago para RTFM ... mucho más fácil preguntarle a la gente amable sobre SO ...;) Les voté a ambos por las respuestas; Jon obtiene crédito de respuesta por ser el primero en disparar. :)
Shaul Behr
2
Creo que la definición de SortedList debería corregirse ya que no creo que sea un árbol de búsqueda binario ...?
nchaud
1
Miré usando el reflector y descubrí que no usaba un árbol de búsqueda binario.
Daniel Imms
Creo que el Sorteddictionary es un árbol AVL o Red-Blacktree (toda la operación cuesta O (log). Y el SortedList es una búsqueda binaria (en el peor de los casos cuesta o (n) tiempo) l
Ghoster
105

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 más o menos paráfrasis, si necesita rendimiento bruto SortedDictionarypodría ser una mejor opción. Si necesita menos sobrecarga de memoria y la recuperación indexada se SortedListajusta mejor. Consulte esta pregunta para obtener más información sobre cuándo usar cuáles.

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

nawfal
fuente
Tenga en cuenta que si desea un buen rendimiento y un uso de memoria relativamente bajo y recuperación indexada, considere BDictionary<Key,Value>en LoycCore en lugar de hacerlo SortedDictionary.
Qwertie
1
Sí, mira la parte inferior de este artículo . Resulta que BDictionarygeneralmente es más lento que a SortedDictionaryexcepción de los tamaños muy grandes, pero es más rápido que SortedListsi hay más de 700 artículos más o menos. El uso de la memoria debe ser solo ligeramente mayor que SortedList(mucho menor que SortedDictionary), debido al uso de matrices en las hojas del árbol.
Qwertie
22

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

Aquí hay alguna fuente (dirigida a .NET 4.5) para respaldar mis reclamos.

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.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++;
}
Daniel Imms
fuente
13

Consulte la página de MSDN para SortedList :

De la sección de Observaciones:

La SortedList<(Of <(TKey, TValue>)>)clase genérica es un árbol de búsqueda binario con O(log n)recuperación, donde nes el número de elementos en el diccionario. En esto, es similar a la SortedDictionary<(Of <(TKey, TValue>)>)clase genérica. Las dos clases tienen modelos de objetos similares, 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 extracción:

  • SortedList<(Of <(TKey, TValue>)>)usa 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 lugar de O(n)para SortedList<(Of <(TKey, TValue>)>).

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

Stephan
fuente
9
El texto citado es incorrecto (y se actualizó en MSDN): SortedList no es un "árbol de búsqueda binario", es una "matriz de pares clave / valor".
Eldritch Conundrum
12

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

Lev
fuente
¿De dónde sacaste esa información? De este esquema podemos ver que Dictinary es mejor de cualquier manera, por lo que no hay razón para que existan otros.
alex kostin
9

Ya se ha dicho lo suficiente sobre el tema, sin embargo, para simplificar, aquí está mi opinión.

El diccionario ordenado debe usarse cuando:

  • Se requieren más operaciones de inserción y eliminación.
  • Datos en desordenados.
  • El acceso 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 operaciones de inserción y eliminación.
  • Los datos ya están ordenados (si no todos, la mayoría).
  • Se requiere acceso al índice.
  • La memoria es una sobrecarga.

¡¡Espero que esto ayude!!

Prakash Tripathi
fuente
1

El acceso al í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 la forma en que puede usar la clasificación (primero / foreach).

Chico
fuente