Cuándo utilizar una SortedList <TKey, TValue> sobre SortedDictionary <TKey, TValue>?

Question

Esto puede parecer un duplicado de este question, que pregunta "¿Cuál es la diferencia entre SortedList y ?" Desafortunadamente, las respuestas no hacen más que citar la documentación de MSDN (que establece claramente que existen diferencias en el rendimiento y la memoria entre los dos), pero en realidad no responden la pregunta.

De hecho (y por lo que esta cuestión no obtiene las mismas respuestas), de acuerdo con MSDN:

La clase genérica SortedList<TKey, TValue> 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 SortedDictionary<TKey, TValue> clase genérica . 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<TKey, TValue> utiliza menos memoria que SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> tiene inserción más rápida y la eliminación 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 de datos ordenados, SortedList<TKey, TValue> es más rápido que SortedDictionary<TKey, TValue>.

Por lo tanto, claramente esto habría indicado que SortedList<TKey, TValue> es la mejor opción a menos necesita más rápido insertar y extraer de las operaciones de datos no ordenados.

La pregunta aún permanece, dada la información anterior, ¿cuáles son las razones prácticas (caso real, business case, etc.) para usar un SortedDictionary<TKey, TValue>? Según la información de rendimiento, implicaría que realmente no es necesario tener SortedDictionary<TKey, TValue> en absoluto.

Answer 1

Eso es todo lo que hay que hacer. La recuperación de claves es comparable, pero la adición es mucho más rápida con los diccionarios.

Intento usar SortedList tanto como sea posible porque me permite iterar sobre las claves y las colecciones de valores. Esto no es posible con SortedDictionary hasta donde yo sé.

No estoy seguro de esto, pero por lo que sé, los diccionarios almacenan datos en estructuras de árbol, mientras que los datos de la tienda de listas en matrices lineales. Eso explica por qué la inserción y eliminación es mucho más rápida con los diccionarios, ya que hay que cambiar menos memoria. También explica por qué puede iterar sobre SortedLists pero no SortedDictionary.

Answer 2

No estoy seguro de qué tan precisa es la documentación de MSDN en SortedList y SortedDictionary. Parece decir que ambos se implementan usando un árbol de búsqueda binario.Pero si SortedList utiliza un árbol de búsqueda binario, ¿por qué sería mucho más lento en adiciones que SortedDictionary?

De todos modos, aquí hay algunos resultados de pruebas de rendimiento.

Cada prueba funciona en un SortedList/SortedDictionary que contiene 10,000 teclas int32. Cada prueba se repite 1.000 veces (versión de lanzamiento, inicio sin depuración).

El primer grupo de pruebas agrega claves en secuencia de 0 a 9.999. El segundo grupo de pruebas agrega claves barajadas al azar entre 0 y 9.999 (cada número se agrega exactamente una vez).

***** Tests.PerformanceTests.SortedTest 

SortedDictionary Add sorted: 4411 ms 
SortedDictionary Get sorted: 2374 ms 


SortedList Add sorted: 1422 ms 
SortedList Get sorted: 1843 ms 

***** Tests.PerformanceTests.UnsortedTest 

SortedDictionary Add unsorted: 4640 ms 
SortedDictionary Get unsorted: 2903 ms 


SortedList Add unsorted: 36559 ms 
SortedList Get unsorted: 2243 ms 

Como con cualquier perfil, lo importante es el rendimiento relativo, no los números reales.

Como puede ver, en los datos ordenados, la lista ordenada es más rápida que SortedDictionary. En los datos sin clasificar, el SortedList es un poco más rápido en la recuperación, pero aproximadamente 9 veces más lento en la adición.

Si ambos están utilizando árboles binarios internamente, es bastante sorprendente que la operación Agregar en datos no ordenados sea mucho más lenta para SortedList. Es posible que la lista ordenada también pueda estar agregando elementos a una estructura de datos lineal ordenada al mismo tiempo, lo que podría ralentizarla.

Sin embargo, es de esperar que el uso de memoria de SortedList sea igual o superior o igual a SortedDictionary. Pero esto contradice lo que dice la documentación de MSDN.

Answer 3

No sé por qué MSDN dice que SortedList<TKey, TValue> usa un árbol binario para su implementación porque si observa el código con un descompilador como Reflector, se da cuenta de que no es cierto.

SortedList<TKey, TValue> es simplemente una matriz que crece con el tiempo.

Cada vez que se inserta un elemento, en primer lugar comprobar si la matriz tiene suficiente capacidad, si no, un arreglo más grande se vuelve a crear y viejos elementos se copian en ella (como List<T>)

Después de eso, se busca en donde para insertar el elemento, utilizando una búsqueda binaria (esto es posible ya que la matriz es indexable y ya está ordenada).

Para mantener la matriz ordenada, se mueve (o empuja) todos los elementos situados después de la posición de elemento que se inserta por una posición (usando Array.Copy()).

Ej:

// we want to insert "3" 

2 
4 <= 3 
5 
8 
9 
.  
.  
. 

// we have to move some elements first 

2 
. <= 3 
4 
5 | 
8 v 
9 
. 
. 

Eso explica por qué el rendimiento de SortedList es tan malo cuando se inserta elementos sin clasificar. Tiene que volver a copiar algunos elementos en casi todas las inserciones. El único caso que no debe hacerse es cuando el elemento debe insertarse al final de la matriz.

SortedDictionary<TKey, TValue> es diferente y utiliza un árbol binario para insertar y recuperar elementos. También tiene algún costo en la inserción porque a veces el árbol necesita ser reequilibrado (pero no en todas las inserciones).

El rendimiento es bastante similar al buscar un elemento con SortedList o SortedDictionary porque ambos utilizan una búsqueda binaria.

---

En mi opinión, nunca se debe uso SortedList simplemente ordenar una matriz. A menos que tenga muy pocos elementos, siempre será más rápido insertar valores en una lista (o matriz) y luego llamar al método Sort().

SortedList es sobre todo útil cuando se tiene una lista de valores ya ordenados (por ejemplo: de la base de datos), que desea mantener lo resuelto y realizar algunas operaciones que se aprovecharían se clasifica (por ejemplo: Contains() método de SortedList realiza una búsqueda binaria en lugar de búsqueda lineal)

SortedDictionary ofrece las mismas ventajas que SortedList pero funciona mejor si los valores para insertar no están ya ordenados.

---

EDIT: Si está utilizando .NET Framework 4.5, una alternativa a SortedDictionary<TKey, TValue> es SortedSet<T>. Funciona de la misma manera que SortedDictionary, utilizando un árbol binario, pero las claves y los valores son los mismos aquí.

Answer 4

¿Están hechas para dos propósitos diferentes?

No hay mucha diferencia semántica entre estos dos tipos de colección en .NET. Ambos ofrecen búsquedas con clave, así como mantener las entradas en orden de las claves. En la mayoría de los casos, estarás bien con cualquiera de ellos. Quizás el único diferenciador sea la recuperación indexada SortedList permisos.

¿Pero el rendimiento?

Sin embargo, hay una diferencia de rendimiento que podría ser un factor más fuerte para elegir entre ellos. Aquí hay una vista tabular de su complejidad asintótica.

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

Resumen

Para resumir más o menos, que desea una SortedList<K, V> cuando:

1. se requieren en un índice de búsqueda.
2. es deseable tener menos sobrecarga de memoria.
3. sus datos de entrada ya están ordenados (digamos que ya lo ha obtenido de db).

Usted tendría lugar que desee preferir un SortedDictionary<K, V> cuando:

1. relativos asuntos rendimiento global (con respecto a la ampliación).
2. sus datos de entrada no están ordenados.

Escribir código

Tanto SortedList<K, V> y SortedDictionary<K, V> aplicar IDictionary<K, V>, por lo que en su código puede volver IDictionary<K, V> del método o declarar la variable como IDictionary<K, V>. Básicamente, oculte los detalles de implementación y codifique contra la interfaz.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

En el futuro, es más fácil cambiar de cualquiera en caso de que no esté satisfecho con el rendimiento característico de una colección.

---

Para obtener más información sobre los dos tipos de colección ver el original question vinculado.

Answer 5

Representación visual de las diferencias de rendimiento.