Lista con comparables Vs TreeSet

Question

Opción 1: Haga una lista que implemente Comparable y oriéntela usando collections.sort (Lista l) cada vez que agregue un valor. Opción 2: crear un TreeSet (que se mantiene ordenado todo el tiempo).

¿Cuál será más rápido? Lo estoy preguntando porque List me da la opción de ListIterator que necesito en mi caso, ya que me permite agregar un elemento al iterar.

Answer 1

Las diferencias más importantes:

Criterion  | List with Collections.sort | TreeSet 
----------------+----------------------------+--------- 
cost of adding | O(n log n)     | O(log n) 
equal sort keys | permitted     | eliminated as duplicates 
iteration  | bidirectional, can insert | unidirectional, can not insert 

Para insertar un elemento cuando se repite sin conseguir un ConcurrentModificationException, que puede hacer:

for (E e : new ArrayList<E>(collection)) { 
    // some other code 

    collection.add(anotherE); 
} 

Answer 2

Utilice TreeSet aquí.

Agregar a TreeSet es una operación log(n). Agregar a la lista es tiempo constante, pero ordenarlo es n log(n).

Answer 3

Collections.sort utiliza una combinación en una especie modificada con Nlog (n) ordenar el tiempo. Si llama al método en cada adición, puede terminar con n^2log (n) tiempo. Mientras que la inserción en TreeSet está garantizada log (n). Entonces, si lo llama en cada adición, se convierte en n.log (n). Así que sugeriría usar TreeSet en su lugar. Pero TreeSet no permite duplicados, por lo que podría afectar su decisión.

Si usa List, en lugar de usar Collections.sort, hay una cosa que puede hacer para optimizar; como usted sabe, cada vez que inserta el elemento en la lista, la lista ya está ordenada, por lo que si utiliza la ordenación por inserción aquí obtendrá un mejor rendimiento, ya que la ordenación por inserción es mejor en esos casos.