SortedList < > ;, SortedDictionary < > y Diccionario < >

Question

Encuentro que SortedList < TKey, TValue > SortedDictionary < TKey, TValue > y Dictionary < TKey, TValue > implementan las mismas interfaces .

1. ¿Cuándo deberíamos optar por SortedList y SortedDictionary sobre Dictionary ?
2. ¿Cuál es la diferencia entre SortedList y SortedDictionary en términos de aplicación?

Answer 1

1. Al iterar sobre los elementos en cualquiera de los dos, los elementos se ordenarán. No es así con Dictionary<T,V>.

2. MSDN aborda la diferencia entre SortedList y lt ; T, V > y SortedDictionary < T, V > :

  

La clase genérica SortedDictionary (TKey, TValue) es una búsqueda binaria   árbol con recuperación O (log n), donde n es el número de elementos en   el diccionario. A este respecto, es similar a SortedList (TKey,   TValue) clase genérica. Las dos clases tienen modelos de objetos similares, y   ambos tienen O (log n) recuperación. Donde las dos clases difieren es en   uso de memoria y velocidad de inserción y extracción:

     

SortedList (TKey, TValue) usa menos memoria que SortedDictionary (TKey,   TValue).

     

SortedDictionary (TKey, TValue) tiene una inserción y extracción más rápidas   operaciones para datos sin clasificar: O (log n) en oposición a O (n) para   SortedList (TKey, TValue).

     

Si la lista se completa de una vez a partir de datos ordenados,   SortedList (TKey, TValue) es más rápido que SortedDictionary (TKey,   TValue).

Answer 2

Mencionaría la diferencia entre los diccionarios.

La imagen de arriba muestra que Dictionary < K, V > es igual o más rápido en todos los casos que Sorted , pero si se requiere el orden de los elementos, p. ej. para imprimirlos, se elige Sorted one.

Src: http: // people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Answer 3

Para resumir los resultados de una Prueba de rendimiento - SortedList vs. SortedDictionary vs. Diccionario vs.Hashtable , los resultados de mejor a peor para diferentes escenarios:

Uso de memoria:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Inserciones:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operaciones de búsqueda:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

operaciones de bucle foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

Answer 4

1. Cuando desea que la colección se ordene por clave cuando itera sobre ella. Si no necesita ordenar sus datos, es mejor que solo tenga un diccionario, tendrá un mejor rendimiento.

2. SortedList y SortedDictionary hacen más o menos lo mismo, pero se implementan de manera diferente, por lo tanto tienen diferentes fortalezas y debilidades explicado aquí .

Answer 5

Puedo ver que las respuestas propuestas se centran en el rendimiento. El artículo proporcionado a continuación no proporciona nada nuevo con respecto al rendimiento, pero explica los mecanismos subyacentes. También tenga en cuenta que no se centra en los tres tipos de Collection mencionados en la pregunta, sino que aborda todos los Tipos del espacio de nombres System.Collections.Generic .

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Extractos:

Dictionario < >

  

El diccionario es probablemente la clase de contenedor asociativo más utilizada. El Diccionario es la clase más rápida para búsquedas / inserciones / eliminaciones asociativas porque usa una tabla hash debajo de las cubiertas . Debido a que las claves están en hash, el tipo de clave debe implementar correctamente GetHashCode () y Equals () o debe proporcionar un IEqualityComparer externo al diccionario en construcción. El tiempo de inserción / eliminación / búsqueda de elementos en el diccionario se amortiza el tiempo constante - O (1) - lo que significa que no importa qué tan grande sea el diccionario, el tiempo que lleva encontrar algo permanece relativamente constante. Esto es altamente deseable para búsquedas de alta velocidad. El único inconveniente es que el diccionario, por la naturaleza de usar una tabla hash, no está ordenado, por lo que no puede atravesar fácilmente los elementos en un Diccionario en orden .

SortedDictionary < >

  

SortedDictionary es similar al Diccionario en uso pero muy diferente en implementación. SortedDictionary utiliza un árbol binario debajo de las cubiertas para mantener los elementos ordenados por la clave . Como consecuencia de la ordenación, el tipo utilizado para la clave debe implementar correctamente IComparable para que las claves se puedan ordenar correctamente. El diccionario ordenado intercambia un poco de tiempo de búsqueda por la capacidad de mantener los elementos en orden, por lo tanto, los tiempos de inserción / eliminación / búsqueda en un diccionario ordenado son logarítmicos - O (log n). En términos generales, con el tiempo logarítmico, puede duplicar el tamaño de la colección y solo tiene que realizar una comparación adicional para encontrar el artículo. Utilice SortedDictionary cuando desee búsquedas rápidas pero también desee poder mantener la colección ordenada por la tecla.

SortedList < >

  

SortedList es la otra clase de contenedor asociativo ordenado en los contenedores genéricos. Una vez más, SortedList, como SortedDictionary, usa una clave para ordenar pares clave-valor . Sin embargo, a diferencia de SortedDictionary, los elementos en una SortedList se almacenan como una matriz ordenada de elementos . Esto significa que las inserciones y eliminaciones son lineales (O (n)) porque eliminar o agregar un elemento puede implicar desplazar todos los elementos hacia arriba o hacia abajo en la lista. Sin embargo, el tiempo de búsqueda es O (log n) porque SortedList puede usar una búsqueda binaria para encontrar cualquier elemento de la lista por su clave. Entonces, ¿por qué querrías hacer esto? Bueno, la respuesta es que si va a cargar SortedList por adelantado, las inserciones serán más lentas, pero debido a que la indexación de matriz es más rápida que seguir enlaces de objeto, las búsquedas son marginalmente más rápidas que SortedDictionary. Una vez más, usaría esto en situaciones en las que desea búsquedas rápidas y desea mantener la colección en orden por la clave, y donde las inserciones y eliminaciones son raras.

---

Resumen provisional de procedimientos subyacentes

Los comentarios son muy bienvenidos ya que estoy seguro de que no hice todo bien.

• Todas las matrices son de tamaño n .
• Matriz no ordenada = .Añadir / .Remove es O (1), pero .Item (i) es O (n).
• Matriz ordenada = .Agregar / .Remo

Answer 6

Intentando asignar una puntuación de rendimiento a cada caso presentado por @Lev, utilicé los siguientes valores:

• O (1) = 3
• O (log n) = 2
• O (n) = 1
• O (1) u O (n) = 2
• O (log n) u O (n) = 1.5

Los resultados son (más alto = mejor):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Por supuesto, cada caso de uso dará más peso a ciertas operaciones.