¿Cuándo utilizar SortedList sobre SortedDictionary ?

Esto puede parecer un duplicado de esta pregunta , que pregunta “¿Cuál es la diferencia entre SortedList y SortedDictionary ?” 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 esta pregunta no obtiene las mismas respuestas), de acuerdo con MSDN:

La clase genérica SortedList es un árbol de búsqueda binaria 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 SortedDictionary . Las dos clases tienen modelos de objetos similares, y ambos 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 eliminación:

  • SortedList usa menos memoria que SortedDictionary .

  • SortedDictionary tiene operaciones de inserción y eliminación más rápidas para datos sin clasificar, O (log n) en oposición a O (n) para SortedList .

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

Por lo tanto, claramente esto indicaría que SortedList es la mejor opción a menos que necesite una inserción más rápida y operaciones de eliminación de datos sin clasificar .

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

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 opera en SortedList / SortedDictionary 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, 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 una SortedList sea ​​igual o superior o igual a SortedDictionary . Pero esto contradice lo que dice la documentación de MSDN.

No sé por qué MSDN dice que SortedList usa un árbol binario para su implementación porque si miras el código con un descomstackdor como Reflector te das cuenta de que no es cierto.

SortedList es simplemente una matriz que crece con el tiempo.

Cada vez que inserta un elemento, primero comprueba si la matriz tiene suficiente capacidad; si no, se recrea una matriz más grande y se copian elementos antiguos (como List ).

Después de eso, busca dónde 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, mueve (o empuja) todos los elementos situados después de la posición del elemento que se va a insertar en una posición (usando Array.Copy() ).

P.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 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 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 cuando se busca un elemento con SortedList u SortedDictionary porque ambos usan una búsqueda binaria.


En mi opinión, nunca debes usar SortedList para 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 útil principalmente cuando tiene una lista de valores ya ordenados (por ej .: desde la base de datos), desea mantenerlo ordenado y realizar algunas operaciones que lo aprovecharían, es ordenado (por ejemplo, el método Contains() 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.


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

¿Están destinados a 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 sería la recuperación indexada que SortedList permite.

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 aproximadamente, quiere una SortedList cuando:

  1. necesita una búsqueda indexada.
  2. es deseable tener una menor carga de memoria.
  3. sus datos de entrada ya están ordenados (digamos que ya lo ha obtenido de db).

En su lugar, preferiría preferir SortedDictionary cuando:

  1. el rendimiento general relativo importa (con respecto a la escala).
  2. sus datos de entrada están desordenados.

Escribir código

Tanto SortedList y SortedDictionary implementan IDictionary , por lo que en su código puede devolver IDictionary desde el método o declarar la variable como IDictionary . Básicamente, oculte los detalles de implementación y codifique contra la interfaz.

 IDictionary x = new SortedDictionary(); //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 colecciones, vea la pregunta original vinculada.

Representación visual de las diferencias de rendimiento.

enter image description here

Eso es todo al respecto. 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.