Lista z porównywalnym zestawem drzewiastym Vs

Question

Opcja 1: Utwórz listę, która implementuje wartość Porównywalne i posortuj ją przy użyciu metody collections.sort (Lista l) za każdym razem, gdy dodasz wartość. Opcja 2: Utwórz TreeSet (który jest cały czas sortowany).

Który z nich będzie szybszy? Pytam o to, ponieważ List daje mi opcję ListIterator, której potrzebuję w moim przypadku, ponieważ pozwala mi dodać element podczas iteracji.

Answer 1

Najistotniejsze różnice:

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 

Aby wstawić element podczas iteracji bez uzyskania ConcurrentModificationException, można zrobić:

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

    collection.add(anotherE); 
} 

Answer 2

Użyj ustawienia drzewa tutaj.

Dodawanie do TreeSet to operacja log(n). Dodawanie do listy to czas stały, ale sortowanie to jest n log(n).

Answer 3

Collections.sort wykorzystuje zmodyfikowaną scalania-sort z NLog (n) czas sortowania. Jeśli wywołasz metodę przy każdym dodaniu, możesz uzyskać czas n^2log (n). Podczas wstawiania w TreeSet jest gwarantowany log (n). Więc jeśli wywołasz to przy każdym dodaniu, staje się n.log (n). Sugerowałbym użycie zamiast tego zestawu TreeSet. Ale TreeSet nie zezwala na duplikaty, co może wpłynąć na twoją decyzję.

Jeśli używasz List, to zamiast używać Collections.sort, możesz zrobić jedną rzecz, aby zoptymalizować; jak wiesz, że za każdym razem, gdy wstawiasz element na listę, lista jest już posortowana, więc użycie sortowania wstawiania da ci lepszą wydajność, ponieważ sortowanie wstawiania działa lepiej w takich przypadkach.