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

Question

¿Hay alguna diferencia real entre una práctica SortedList<TKey,TValue> y una SortedDictionary<TKey,TValue> ? ¿Hay algunas circunstancias en las que usaría en concreto uno y no el otro?

Answer 1

Sí - sus características de rendimiento difieren significativamente. Probablemente sería mejor llamarlos SortedList y SortedTree como que refleja la puesta en práctica más de cerca.

Mire la documentación de MSDN para cada uno de ellos ( SortedList , SortedDictionary ) para más detalles sobre el funcionamiento de las diferentes operaciones en diferentes situtations. He aquí un buen resumen (de los documentos SortedDictionary):

  

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

     

  

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

  

• SortedDictionary<TKey, TValue> tiene   la inserción y remoción más rápida   operaciones de datos no ordenados, O (log n)   en contraposición a O (n) para   SortedList<TKey, TValue>.

  

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

  

(SortedList realidad mantiene una matriz ordenada, en lugar de utilizar un árbol. Se sigue utilizando la búsqueda binaria para encontrar elementos.)

Answer 2

Esta es una vista tabular si ayuda ...

A partir de una rendimiento 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).

Desde un aplicación 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 más o menos paráfrasis, si necesita SortedDictionary rendimiento bruto podría ser una mejor opción. Si requiere menor sobrecarga de memoria e indexado SortedList recuperación encaja mejor. Ver esta cuestión para más información sobre cuándo usar cuál.

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

Answer 3

Me agrietada Reflector abierto a echar un vistazo a esto ya que parece que hay un poco de confusión sobre SortedList. Es, de hecho, no es un árbol binario de búsqueda, es una matriz ordenada (con llave) de pares de valores clave . También hay una variable TKey[] keys que se clasifica en sincronía con los pares de valores clave y se utiliza para la búsqueda binaria.

Aquí hay alguna fuente (con orientación a .NET 4.5) para copia de seguridad de mis reclamos.

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.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++;
}

Answer 4

Consulte el página de MSDN para SortedList :

Desde la sección Observaciones:

  

La clase genérica SortedList<(Of <(TKey, TValue>)>) es un árbol binario de búsqueda con la 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 SortedDictionary<(Of <(TKey, TValue>)>). Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O(log n). Cuando las dos clases difieren es en el uso de memoria y la velocidad de inserción y extracción:

     

  
• SortedList<(Of <(TKey, TValue>)>) utiliza menos memoria que SortedDictionary<(Of <(TKey, TValue>)>).
  

• SortedDictionary<(Of <(TKey, TValue>)>) tiene operaciones de inserción y extracción rápidas para datos no ordenados, O(log n) en oposición a O(n) para SortedList<(Of <(TKey, TValue>)>).

  

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

  

Answer 5

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

Answer 6

Suficiente se dice que ya están en el tema, sin embargo, que sea sencillo, aquí está mi opinión.

diccionario Ordenado se debe utilizar cuando -

Se requieren
• Más insertos y operaciones de borrado.
• Los datos de ONU-ordenada.
• Clave de acceso es suficiente y no se requiere acceso índice.
• La memoria no es un cuello de botella.

Por otro lado, lista ordenada se debe utilizar cuando -

• Más operaciones de búsqueda y menos insertos y borrar se requieren operaciones.
• Los datos ya está ordenada (si no todos, la mayoría).
• Se requiere acceso Índice.
• La memoria es una sobrecarga.

Espero que esto ayude !!

Answer 7

Índice de acceso (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 cómo se puede utilizar la clasificación (primera / foreach).