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

.net generics

Question

¿Hay alguna diferencia práctica real entre una lista SortedList<TKey,TValue> y un SortedDictionary<TKey,TValue> ? ¿Hay alguna circunstancia en la que utilizarías específicamente una y no la otra?

Answer 1

Abrí el Reflector para ver esto, ya que parece haber un poco de confusión acerca de la 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 variable de TKey[] keys que se ordena en sincronización con los pares clave-valor y se usa para la búsqueda binaria.

Aquí hay algunas fuentes (con .NET 4.5) para hacer una copia de seguridad de 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++;
}

Answer 2

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

Parafraseando en términos generales , si necesita un rendimiento en bruto, SortedDictionary podría ser una mejor opción. Si necesita una menor sobrecarga de memoria y la recuperación indexada, la SortedList ajusta mejor. Vea esta pregunta para más información sobre cuándo usar cuál.

Puedes leer más here , here , here , here y here .

Answer 3

Echa un vistazo a la SortedList :

De la sección de observaciones:

La SortedList<(Of <(TKey, TValue>)>) es un árbol binario de búsqueda 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 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<(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 lugar de O(n) para SortedList<(Of <(TKey, TValue>)>) .

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

Answer 4

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 (first / foreach).

Answer 5

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

Answer 6

Sí, sus características de rendimiento difieren significativamente. Probablemente sería mejor llamarlos SortedList y SortedTree ya que eso 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 para diferentes operaciones en diferentes situaciones. Aquí hay un buen resumen (de la documentación de SortedDictionary ):

La clase genérica SortedDictionary<TKey, TValue> es un árbol binario de búsqueda 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<TKey, TValue> . 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 rellena a la vez a partir de los datos ordenados, SortedList<TKey, TValue> es más rápido que SortedDictionary<TKey, TValue> .

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

Answer 7

Ya se ha dicho suficiente sobre el tema, pero para hacerlo simple, aquí está mi opinión.

Diccionario ordenado debe ser utilizado cuando

• Se requieren más inserciones y operaciones de eliminación.
• Datos no ordenados.
• El acceso clave es suficiente y el acceso al índice no es necesario.
• 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).
• Se requiere acceso al índice.
• La memoria es una sobrecarga.

¡¡Espero que esto ayude!!