cuando debería usar un ordenado en lugar de un diccionario

Question

Como escribí en algunos de mis últimos mensajes, todavía soy bastante nuevo en el mundo C# por lo que resulta que escribí un pequeño punto de referencia para comparar Dictionary, Hashtable, SortedList y SortedDictionary en cada otro. La prueba se ejecuta con 8000 iteraciones y de 50 a 100000 elementos. Probé la adición de nuevos elementos, la búsqueda de elementos y el bucle de algunos elementos al azar. Los resultados fueron como esperaba, excepto por el SortedDictionary, que me resultó muy confuso ... Fue lento en todos los resultados. Entonces me faltaba algo sobre el concepto de un diccionario ordenado. Ya le pregunté a google, pero todo lo que descubrí fue que otros habían llegado al mismo resultado de la prueba. Ligeramente diferente en función de su implementación de la prueba. De nuevo mi pregunta: ¿por qué el Sorticionado es mucho más lento que todos los demás?

Answer 1

Un SortedDictionary se implementa como un árbol de búsqueda binaria. Por lo tanto, acceder a un elemento es O (lg (n)). Un diccionario es una tabla hash, y tiene una complejidad de O (1) para el acceso.

Un SortedDictionary es bastante útil cuando necesita que los datos sean ordenados (un diccionario no tiene un orden definido). El diccionario es apropiado para la mayoría de los casos.

Answer 2

La respuesta es simplemente que usaría el SortedDictionary si necesita un diccionario ordenado.

Recuerde que aunque terminó siendo el más lento en sus pruebas, aún no es lento. Si necesita exactamente lo que hace el SortedDictionary, es la mejor solución. Hacer lo mismo usando Dictionary o SortedList sería mucho más lento.

Answer 3

Nuevamente mi pregunta: ¿por qué el Sorticodionario es mucho más lento que todos los demás?

Etienne ya dio la respuesta técnica antes, pero para añadir una observación más 'normal': supongo que la parte "Ordenado" poco de un SortedDictionary pone algo de sobrecarga en insertos e incluso recuperar artículos como parece de la respuesta de Etienne.

Sin embargo, en una aplicación real, SortedDictionary probablemente puede proporcionar un rendimiento considerable o un aumento del "rendimiento percibido" si necesita un "diccionario ya ordenado" en algún momento de su aplicación.

Espero que ayude.