¿Es más rápido agregar a una colección y luego ordenarla o agregarla a una colección ordenada?

Si tengo una Mapcomo esta:

HashMap<Integer, ComparableObject> map;

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

(UN)

Cree una instancia de una colección ordenable como ArrayList, agregue los valores y luego ordénela:

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 realizarse una vez.

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

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

En teoría, la clasificación al final debería ser más rápida. Mantener el estado ordenado a través del proceso podría implicar tiempo adicional de CPU.

Desde el punto de vista de CS, ambas operaciones son NlogN, pero 1 tipo debería tener una constante más baja.

¿Por qué no utilizar lo mejor de ambos mundos? Si nunca lo volverá a usar, ordene usando un TreeSet e inicialice un ArrayList con el contenido

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 comparador intencionalmente terrible, y luego cada una de las tres estrategias tiene la oportunidad de a) ordenar los datos yb) iterar sobre ellos. Aquí hay una salida de muestra (puede probarla usted mismo):

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

Curiosamente, mi enfoque funciona mejor en iteración (habría pensado que no habría diferencias con el enfoque ArrayList en iteración, ¿tengo un error en mi punto de referencia?)

Descargo de responsabilidad: Sé que este es probablemente un punto de referencia terrible, pero te ayuda a hacerte entender y ciertamente no lo manipulé para que mi enfoque ganara.

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

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

Si su aplicación solo hace clasificaciones ocasionales pero la recorre mucho, diría que es mejor que use una lista sencilla y 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 matrices.

Sin embargo, si desea que el orden de clasificación esté garantizado todo el tiempo o posiblemente esté agregando / eliminando elementos con frecuencia, use una colección ordenada y aproveche la iteración.

Entonces, en su caso, diría que A) es la mejor opción. La lista se ordena una vez, no cambia y, por lo tanto, se beneficia de ser una matriz. La iteración debería ser muy rápida, especialmente si 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, lo que significa que los objetos son únicos. Un TreeSet determina la igualdad usando compareTo en su Comparator / Comparable. Es posible que te falten datos fácilmente si intentas agregar dos objetos cuyo compareTo devuelve un valor de 0. Por ejemplo, si agregas "C", "A", "B", "A" a un TreeSet, obtendrás "A", "B ", "C"

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

TreeSettiene un árbol rojo-negro subyacente, las operaciones básicas tienen O (logn). Por tanto, n elementos también tiene O (nlog n).

Entonces ambos son el mismo algoritmo de Big O.

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

La ordenación en un SortedSet ya está incluida en la inserción, por lo que es 0. La ordenación en una Lista es O (n * log (n)).

Entonces, la complejidad total de SortedSet es O (n * k), k <log (n) para todos los casos excepto el último. En cambio, la complejidad total de la lista es O (n * log (n) + n), entonces O (n * log (n)).

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

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

Gran pregunta y grandes respuestas. Solo pensé en agregar algunos puntos a tener en cuenta:

1. Si su colección a ordenar es de corta duración, por ejemplo, se usa como argumento para un método, y necesita la lista ordenada dentro del método, entonces use Collections.sort (colección). O si es un objeto de larga duración, pero es necesario clasificarlo muy raramente.

Justificación: la colección ordenada es necesaria para algo específico, y probablemente no agregará ni eliminará con mucha frecuencia. Por lo tanto, no le importan los elementos de la colección una vez que está ordenada. Básicamente:

ordenar -> usarlo -> olvidar

Si agrega un nuevo elemento a la colección ordenada, tendrá que ordenar la colección nuevamente, ya que el orden no está garantizado al insertar un nuevo elemento.

2. Si la colección que se va a ordenar es de larga duración y / o si es un campo dentro de una clase y necesita que se ordene en todo momento, entonces debe usar una estructura de datos ordenada como TreeSet.

Justificación: Te preocupas por el orden de recogida en todo momento. Quieres que esté ordenado en todo momento. Entonces, si agrega o elimina elementos constantemente, tiene la garantía de que la colección está ordenada. Así que básicamente:

insertar / quitar -> usarlo (todo el tiempo tiene la garantía de que la colección está ordenada)

No hay un momento específico en el que necesite que se ordene la colección, sino que desea que la colección se ordene todo el tiempo.

La desventaja de usar TreeSet son los recursos que requiere para mantener la colección ordenada. Utiliza un árbol rojo-negro y requiere un costo de tiempo O (log n) para las operaciones get, put.

Mientras que si usa una colección simple, como ArrayList, las operaciones get, add son de tiempo constante O (1).