Bueno, es una ganancia fácil en SortedList. La inserción de un elemento requiere una búsqueda binaria (O (log (n)) para encontrar el punto de inserción, luego una Lista.Insertar (O (n)) para insertar el elemento. El Insertar() domina, poblar la lista requiere O (n^2). Si los elementos de entrada ya están ordenados, la inserción se contrae a O (1) pero no afecta a la búsqueda. Poblando ahora es O (nlog (n)). No te preocupes qué tan grande es Oh, la ordenación primero siempre es más eficiente. Suponiendo que puede pagar el requisito de almacenamiento duplicado
SortedDictionary es diferente, utiliza un árbol rojo-negro. Encontrar el punto de inserción requiere O (log (n)). Reequilibrar el árbol podría ser requerido después, que también toma O (log (n)). Poblar el diccionario toma O (nlog (n)). Usar la entrada ordenada no cambia el esfuerzo para encontrar el punto de inserción o reequilibrio, todavía es O (nlog (n)). Ahora bien, el Oh importa, insertar una entrada ordenada requiere que el árbol sea constante No se reequilibre. Funciona mejor si la entrada es aleatoria, no quiere entrada ordenada.
Completando así SortedList con entrada ordenada y rellenando SortedDictionary con entrada no ordenada es O (nlog (n)). Ignorando el costo de proporcionar entradas clasificadas, Oh de SortedList es más pequeño que Oh de SortedDictionary. Es un detalle de implementación debido a la forma en que la Lista 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.
Es notable que ninguno de los dos se compara favorablemente con simplemente llenar una Lista, y luego llamar a Sort(). Eso también es O (nlog (n)). De hecho, si la entrada ya está clasificada por accidente, puede omitir la llamada de Sort(), esto colapsará en O (n). El análisis de costos ahora necesita pasar al esfuerzo que se requiere para ordenar la entrada. Es difícil pasar por alto la complejidad fundamental de Sort(), O (nlog (n)). Puede no ser fácilmente visible, puede obtener la entrada ordenada por, por ejemplo, una consulta SQL. Solo llevará más tiempo completarlo.
El punto de utilizar SortedList u SortedDictonary es mantener la colección ordenada después de las inserciones. Si solo te preocupa poblar pero no mutar, entonces no deberías usar esas colecciones.
¿Ha intentado crear un perfil de su código para asegurarse de que la inicialización de las estructuras de datos ordenadas es, de hecho, el cuello de botella en su código? –
Hasta ahora es una pregunta hipotética, pero sí, este será el cuello de botella, por el momento. – Martin
No puedo recordar, pero supongo que estaba asumiendo que todos los métodos eran asintóticamente iguales en rendimiento y que tal vez difirieran en el rendimiento promedio (O (1)) según el caso de uso. – Martin