java - ordenamiento - quicksort como funciona
Optimizar la velocidad de inserción en java.util.Map/Set (5)
¿Hay alguna forma de optimizar la velocidad de las inserciones en java.util.Collection al especificar el orden de los elementos?
Por ejemplo
java.util.Set<String> set = java.util.TreeSet<String>();
¿Esta solución?
set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("E");
ser más rápido que este (orden aleatorio)?
set.add("E");
set.add("D");
set.add("C");
set.add("A");
set.add("B");
(y la misma pregunta para las otras colecciones: HashMap, hastable ...)
Gracias
El tiempo de inserción para un árbol rojo-negro (que se usa para implementar TreeSet / TreeMap de Java ) se garantiza que el peor de los casos sea O (log n). Podría ser más rápido si los artículos están en un orden particular, pero no estoy seguro de lo que sería (probablemente pre-clasificado sería el más rápido?).
La inserción en una tabla hash es una operación O (1) (tiempo constante). Lo principal para la inserción es el cálculo del hashcode .
Editar: Starblue sugiere que las preasignaciones pueden producir el peor de los casos, por lo que podría intentar el orden aleatorio.
La respuesta fácil es "medir el tiempo y ver".
La otra respuesta es "no importará". Esto parece ser una micro-optimización que apenas vale la pena el esfuerzo. Creo que pertenece a la categoría de "The Sad Tragedy of Micro-Optimization Theatre" .
Naturalmente, existe una gran diferencia entre las colecciones basadas en hash y las basadas en árboles.
Los basados en árboles se benefician del ordenamiento de elementos para la inserción (por ejemplo, comparaciones entre cadenas), de modo que cuando tiene objetos comparables (como una cadena) es mejor usarlos. TreeSet / TreeMap / etc. en la colección estándar se supone que está equilibrado (árbol rojo-negro), por lo que el orden de inserción no importa demasiado. Si no estaba equilibrado, el orden de inserción sería importante ya que podría terminar con una cadena en lugar de un árbol.
En las tablas hash, el factor de carga y la función hashing lo deciden todo, pero si se trata de cadenas, es mejor que ni siquiera te molestes en el hash.
Si necesita un conjunto de cadenas para muchas cadenas con superposiciones, una Trie puede ser más eficiente con la memoria, pero no creo que haya ninguna en la biblioteca.
Tenga cuidado de considerar las características de su estructura de datos al tomar medidas de optimización. Para un ejemplo extremo, insertar elementos en un árbol binario en orden ordenado resultaría en una lista enlazada.
No para java.util.Map y java.util.Set, porque estas son interfaces, y hay diferentes implementaciones.
Para implementaciones concretas, no es una optimización que valga la pena. Si tiene problemas con el rendimiento, elija una implementación más adecuada, o vuelva a pensar qué y cómo debe almacenar.
Insertar 5000 números aleatorios en un HashSet toma alrededor de un milisegundo en una computadora portátil ordinaria, así que ¿cuántos millones de elementos desea insertar para que este tipo de optimización valga la pena?