.net - SortedList vs. SortedDictionary vs. Sort()

performance sorting

Question

Esta es una continuación de preguntas como esta .

¿Hay alguna guía para ajustar el rendimiento? No me refiero a las ganancias en big-O, solo ahorrando algo de tiempo lineal.

Por ejemplo, ¿cuánto ahorra la clasificación previa en SortedList o SortedDictionary ?

Digamos que tengo una clase de persona con 3 propiedades para clasificar, una de ellas es la edad en años. ¿Debo colocar los objetos en la edad primero?

¿Debería primero ordenar en una propiedad, luego usar la lista / diccionario resultante para ordenar en dos propiedades y así sucesivamente?

¿Alguna otra optimización que viene a la mente?

Answer 1

Bueno, es una victoria fácil en SortedList. Insertar un elemento requiere una búsqueda binaria (O (log (n)) para encontrar el punto de inserción, luego un List.Insert (O (n)) para insertar el elemento. ^ 2). Si los elementos de entrada ya están ordenados, la inserción se colapsa en O (1) pero no afecta la búsqueda. La población ahora es O (nlog (n)). No se preocupa de cuán grande es el Oh, ordenar primero siempre es más eficiente. Suponiendo que puede pagar el doble requisito de almacenamiento.

SortedDictionary es diferente, usa un árbol rojo-negro. Encontrar el punto de inserción requiere O (log (n)). Es posible que luego se requiera volver a equilibrar el árbol, que también toma O (log (n)). Por lo tanto, al poblar el diccionario se toma O (nlog (n)). El uso de la entrada ordenada no cambia el esfuerzo para encontrar el punto de inserción o el rebalanceo, sigue siendo O (nlog (n)). Ahora bien, el Oh importa, la inserción de entradas ordenadas requiere que el árbol se reequilibre constantemente. Funciona mejor si la entrada es aleatoria, no desea una entrada ordenada.

Por lo tanto, rellenar SortedList con entrada ordenada y llenar SortedDictionary con entrada sin clasificar es O (nlog (n)). Ignorando el costo de proporcionar entradas ordenadas, Oh of SortedList es más pequeño que Oh of SortedDictionary. Eso es un detalle de implementación debido a la forma en que List asigna memoria. Solo tiene que hacerlo O (log (n)) veces, un árbol rojo-negro tiene que asignar O (n) veces. Muy pequeño Oh por cierto.

Notable es que ninguno de los dos se compara favorablemente en lugar de simplemente rellenar una Lista, y luego llamar a Ordenar (). Eso también es O (nlog (n)). De hecho, si la entrada ya está ordenada accidentalmente, puede omitir la llamada Sort (), esto colapsa a O (n). El análisis de costos ahora necesita pasar al esfuerzo que se necesita para ordenar las entradas. Es difícil pasar por alto la complejidad fundamental de Sort (), O (nlog (n)). Puede que no sea fácilmente visible, puede obtener la entrada ordenada por, por ejemplo, una consulta SQL. Sólo tomará más tiempo en completarse.

El punto de usar SortedList o SortedDictonary es mantener la colección ordenada después de las inserciones. Si solo te preocupas por poblar pero no por mutar, entonces no deberías usar esas colecciones.