java - usando - ¿Es más rápido agregarlo a una colección, luego ordenarlo o agregarlo a una colección ordenada?

titledborder java

Question

Si tengo un Map como este:

HashMap<Integer, ComparableObject> map;

y quiero obtener una colección de valores ordenados usando ordenamiento natural, ¿qué método es el más rápido?

(UN)

Cree una instancia de una colección clasificable como ArrayList , agregue los valores y ordénelo:

List<ComparableObject> sortedCollection = new ArrayList<ComparableObject>(map.values());
Collections.sort(sortedCollection);

(SEGUNDO)

Cree una instancia de una colección ordenada como TreeSet , luego agregue los valores:

Set<ComparableObject> sortedCollection = new TreeSet<ComparableObject>(map.values());

Tenga en cuenta que la colección resultante nunca se modifica, por lo que la clasificación solo debe tener lugar una vez.

Answer 1

¿Por qué no usar lo mejor de ambos mundos? Si nunca vuelve a utilizarlo, ordene usando un TreeSet e inicialice una ArrayList con los contenidos

List<ComparableObject> sortedCollection = 
    new ArrayList<ComparableObject>( 
          new TreeSet<ComparableObject>(map.values()));

EDITAR:

He creado un punto de referencia (puede acceder a él en pastebin.com/5pyPMJav ) para probar los tres enfoques (ArrayList + Collections.sort, TreeSet y mi mejor enfoque de ambos mundos) y el mío siempre gana. El archivo de prueba crea un mapa con 10000 elementos, cuyos valores tienen un intencionalmente horrible comparador, y luego cada una de las tres estrategias tiene la oportunidad de a) ordenar los datos y b) iterar sobre ellos. Aquí hay algunos resultados de muestra (puede probarlo):

EDITAR: He agregado un aspecto que registra llamadas a Thingy.compareTo (Thingy) y también he agregado una nueva Estrategia basada en PriorityQueues que es mucho más rápida que cualquiera de las soluciones anteriores (al menos en la clasificación).

compareTo() calls:123490
Transformer ArrayListTransformer
    Creation: 255885873 ns (0.255885873 seconds) 
    Iteration: 2582591 ns (0.002582591 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer TreeSetTransformer
    Creation: 199893004 ns (0.199893004 seconds) 
    Iteration: 4848242 ns (0.004848242 seconds) 
    Item count: 10000

compareTo() calls:121665
Transformer BestOfBothWorldsTransformer
    Creation: 216952504 ns (0.216952504 seconds) 
    Iteration: 1604604 ns (0.001604604 seconds) 
    Item count: 10000

compareTo() calls:18819
Transformer PriorityQueueTransformer
    Creation: 35119198 ns (0.035119198 seconds) 
    Iteration: 2803639 ns (0.002803639 seconds) 
    Item count: 10000

Extrañamente, mi enfoque funciona mejor en iteración (Hubiera pensado que no habría diferencias con el método ArrayList en la iteración, ¿tengo algún error en mi punto de referencia?)

Descargo de responsabilidad: Sé que este es probablemente un punto de referencia horrible, pero ayuda a transmitirle el punto y ciertamente no lo manipulé para hacer que mi enfoque gane.

(El código tiene una dependencia de apache commons / lang para los constructores equals / hashcode / compareTo, pero debería ser fácil refactorizarlo)

Answer 2

Asegúrese de leer mi comentario sobre TreeSet en la parte inferior si elige implementar B)

Si su aplicación solo hace géneros ocasionales, pero repite mucho, diría que es mejor que use una lista sencilla sin clasificar. Ordénelo una vez y luego benefíciese de una iteración más rápida. La iteración es especialmente rápida en una lista de matriz.

Sin embargo, si desea que el orden de clasificación esté garantizado todo el tiempo o posiblemente agregue / elimine elementos con frecuencia, utilice una colección ordenada y realice el impacto en la iteración.

Entonces, en tu caso, diría que A) es la mejor opción. La lista se ordena una vez, no cambia y, por lo tanto, se beneficia al ser una matriz. La iteración debe ser muy rápida, especialmente si usted sabe que es una ArrayList y puede usar directamente ArrayList.get () en lugar de un iterador.

También agregaría que TreeSet por definición es un conjunto que significa que los objetos son únicos. Un TreeSet determina la igualdad mediante el uso de compareTo en su Comparador / Comparable. Puede encontrar datos perdidos fácilmente si intenta agregar dos objetos cuyo compareTo devuelve un valor de 0. Por ejemplo, agregar "C", "A", "B", "A" a un TreeSet devolverá "A", "B" "," C "

Answer 3

Insertar en un SortedSet es O (log (n)) (PERO! El n actual y no el n final). Insertar en una lista es 1.

Ordenar en un SortedSet ya está incluido en la inserción, por lo que es 0. Ordenar en una lista es O (n * log (n)).

La complejidad total de SortedSet es O (n * k), k <log (n) para todos los casos, pero el último. En cambio, la complejidad total de la lista es O (n * log (n) + n), por lo que O (n * log (n)).

Por lo tanto, SortedSet matemáticamente tiene el mejor rendimiento. Pero al final, tiene un conjunto en lugar de una lista (porque SortedList no existe) y Set le ofrece menos funciones que la lista. Entonces, en mi opinión, la mejor solución para las características disponibles y el rendimiento es la propuesta por Sean Patrick Floyd:

• use un SortedSet para insertar,
• coloque el SortedSet como un parámetro para crear una lista para devolver.

Answer 4

Teóricamente, ordenar al final debería ser más rápido. Mantener el estado ordenado durante el proceso podría implicar un tiempo de CPU adicional.

Desde el punto de vista de CS, ambas operaciones son NlogN, pero 1 clasificación debe tener una constante menor.

Answer 5

TreeSet tiene una garantía de complejidad de tiempo de log(n) para los métodos add()/remove()/contains() . Ordenar una ArrayList toma n*log(n) operaciones, pero add()/get() toma solo 1 operación.

Entonces, si está recuperando principalmente, y no ordena con frecuencia, ArrayList es la mejor opción. Si ordena con frecuencia pero no recupera tanto, TreeSet sería una mejor opción.

Answer 6

Collections.sort usa mergeSort que tiene O (nlog n).

TreeSet tiene un árbol Rojo-Negro subyacente, las operaciones básicas tienen O (logn). Por lo tanto, n elementos también tiene O (nlog n).

Entonces ambos son el mismo algoritmo O grande.