146 votos

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

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?

161voto

Jon Skeet Puntos 692016

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 la SortedList<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 de SortedDictionary<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) para SortedList<TKey, TValue>.

  • Si la lista se rellena de una vez de datos ordenados, SortedList<TKey, TValue> es más rápido que SortedDictionary<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.)

46voto

nawfal Puntos 13500

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í.

19voto

Daniel Imms Puntos 16273

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

12voto

Stephan Puntos 4119

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 con O(log n) de recuperación, donde n es el número de elementos en el diccionario. En esto, es similar a la SortedDictionary<(Of <(TKey, TValue>)>) clase genérica. Las dos clases similares modelos de objetos, y ambos tienen O(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 que SortedDictionary<(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 a O(n) para SortedList<(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 que SortedDictionary<(Of <(TKey, TValue>)>).

8voto

Nightwish91 Puntos 633

Esta es la representación visual de cómo las actuaciones comparar el uno al otro.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X