Czy szybsze jest dodawanie do kolekcji, a następnie sortowanie, czy dodawanie do posortowanej kolekcji?

Jeśli mam Maptaki:

HashMap<Integer, ComparableObject> map;

i chcę uzyskać zbiór wartości posortowanych przy użyciu naturalnego porządku, która metoda jest najszybsza?

(ZA)

Utwórz instancję sortowanej kolekcji, na przykład ArrayListdodaj wartości, a następnie posortuj ją:

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

(B)

Utwórz wystąpienie uporządkowanej kolekcji, na przykład TreeSet, a następnie dodaj wartości:

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

Zwróć uwagę, że kolekcja wynikowa nigdy nie jest modyfikowana, więc sortowanie musi odbywać się tylko raz.

TreeSet ma gwarancję log(n)złożoności czasowej dla add()/remove()/contains()metod. Sortowanie ArrayListprzyjmuje n*log(n)operacje, ale add()/get()tylko 1operację.

Więc jeśli głównie pobierasz i nie sortujesz często, ArrayListlepszym wyborem jest. Jeśli często sortujesz, ale nie pobierasz tak dużo, TreeSetbyłby to lepszy wybór.

Teoretycznie sortowanie na końcu powinno być szybsze. Utrzymanie posortowanego stanu w trakcie procesu może wymagać dodatkowego czasu procesora.

Z punktu widzenia CS obie operacje to NlogN, ale 1 sort powinien mieć niższą stałą.

Dlaczego nie skorzystać z tego, co najlepsze z obu światów? Jeśli nigdy więcej jej nie użyjesz, posortuj przy użyciu TreeSet i zainicjuj ArrayList z zawartością

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

EDYTOWAĆ:

Stworzyłem benchmark (możesz uzyskać do niego dostęp na pastebin.com/5pyPMJav ), aby przetestować trzy podejścia (ArrayList + Collections.sort, TreeSet i moje najlepsze podejście z obu światów), a moje zawsze wygrywa. Plik testowy tworzy mapę z 10000 elementów, których wartości mają celowo okropny komparator, a następnie każda z trzech strategii ma szansę a) posortować dane ib) powtórzyć je. Oto przykładowe dane wyjściowe (możesz je samodzielnie przetestować):

EDYCJA: Dodałem aspekt, który rejestruje wywołania do Thingy.compareTo (Thingy), a także dodałem nową strategię opartą na PriorityQueues, która jest znacznie szybsza niż którekolwiek z poprzednich rozwiązań (przynajmniej w sortowaniu).

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

O dziwo, moje podejście działa najlepiej w iteracji (pomyślałem, że nie będzie różnic w podejściu ArrayList w iteracji, czy mam błąd w moim benchmarku?)

Zastrzeżenie: Wiem, że to prawdopodobnie okropny punkt odniesienia, ale pomaga ci to zrozumieć i na pewno nie manipulowałem nim, aby moje podejście wygrywało.

(Kod ma zależność do apache commons / lang dla konstruktorów equals / hashcode / compareTo, ale powinno być łatwe do zreformowania)

Koniecznie przeczytaj mój komentarz na temat TreeSet na dole, jeśli zdecydujesz się zaimplementować B)

Jeśli Twoja aplikacja wykonuje tylko sporadyczne sortowanie, ale często ją iteruje, powiedziałbym, że najlepiej jest użyć prostej, niesortowanej listy. Sortuj to raz, a następnie skorzystaj z szybszej iteracji. Iteracja jest szczególnie szybka na liście tablic.

Jeśli jednak chcesz, aby porządek sortowania był gwarantowany przez cały czas lub często dodajesz / usuwasz elementy, użyj posortowanej kolekcji i weź udział w iteracji.

Więc w twoim przypadku powiedziałbym, że A) jest lepszą opcją. Lista jest posortowana raz, nie zmienia się i dlatego zyskuje na byciu tablicą. Iteracja powinna być bardzo szybka, zwłaszcza jeśli znasz jej ArrayList i możesz bezpośrednio użyć ArrayList.get () zamiast Iteratora.

Dodałbym również, że TreeSet z definicji jest zestawem, co oznacza, że ​​obiekty są unikalne. TreeSet określa równość, używając funkcji compareTo w komparatorze / porównawczym. Możesz łatwo znaleźć brakujące dane, jeśli spróbujesz dodać dwa obiekty, których funkcja compareTo zwraca wartość 0. np. Dodanie „C”, „A”, „B”, „A” do TreeSet zwróci „A”, „B” „,„ C ”

Collections.sort używa mergeSort, który ma O (nlog n).

TreeSetma drzewo czerwono-czarne, podstawowe operacje mają O (logn). Stąd n elementów ma również O (nlog n).

Więc oba są tym samym dużym algorytmem O.

Wstawienie do SortedSet to O (log (n)) (ALE! Bieżące n, a nie ostatnie n). Wstawienie na listę to 1.

Sortowanie w SortedSet jest już uwzględnione przy wstawianiu, więc wynosi 0. Sortowanie na liście to O (n * log (n)).

Zatem całkowita złożoność SortedSet wynosi O (n * k), k <log (n) dla wszystkich przypadków oprócz ostatniego. Zamiast tego całkowita złożoność listy wynosi O (n * log (n) + n), więc O (n * log (n)).

Tak więc SortedSet matematycznie ma najlepszą wydajność. Ale ostatecznie masz zestaw zamiast listy (ponieważ SortedList nie istnieje), a Set zapewnia mniej funkcji niż List. Dlatego moim zdaniem najlepszym rozwiązaniem dla dostępnych funkcji i wydajności jest to, które zaproponował Sean Patrick Floyd:

• użyj SortedSet do wstawiania,
• umieścić SortedSet jako parametr do tworzenia listy do zwrócenia.

Świetne pytanie i świetne odpowiedzi. Pomyślałem, że dodam kilka punktów do wzięcia pod uwagę:

1. Jeśli Twoja kolekcja do posortowania jest krótkotrwała, na przykład używana jako argument metody i potrzebujesz posortowanej listy w ramach metody, użyj opcji Collections.sort (kolekcja). Lub jeśli jest to obiekt długowieczny, ale bardzo rzadko trzeba go sortować.

Uzasadnienie: posortowana kolekcja jest wymagana do czegoś konkretnego i prawdopodobnie nie będziesz jej często dodawać ani usuwać. Więc tak naprawdę nie obchodzą Cię elementy w kolekcji po jej posortowaniu. Zasadniczo:

sortuj -> użyj -> zapomnij

Jeśli dodasz nowy element do posortowanej kolekcji, będziesz musiał ponownie posortować kolekcję, ponieważ kolejność nie jest gwarantowana podczas wstawiania nowego elementu.

2. Jeśli Twoja kolekcja, która ma być posortowana, jest długowieczna i / lub jeśli jest to pole w klasie i chcesz, aby była sortowana przez cały czas , powinieneś użyć posortowanej struktury danych, takiej jak TreeSet.

Uzasadnienie: Zawsze dbasz o kolejność odbioru. Chcesz, aby był on zawsze sortowany. Więc jeśli ciągle dodajesz lub usuwasz elementy, masz gwarancję, że kolekcja jest posortowana. Więc w zasadzie:

wstaw / usuń -> używaj (cały czas masz gwarancję, że kolekcja jest posortowana)

Nie ma konkretnego momentu, w którym chcesz posortować kolekcję, zamiast tego chcesz, aby kolekcja była sortowana przez cały czas.

Wadą korzystania z TreeSet są zasoby wymagane do przechowywania posortowanej kolekcji. Używa czerwono-czarnego drzewa i wymaga O (log n) kosztu czasu na operacje get, put.

Natomiast jeśli używasz prostej kolekcji, takiej jak ArrayList, operacje get, add mają stały czas O (1).