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

79

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.

java  sorting  collections 
— gutch
źródło
Zależy to od kolejności danych wejściowych - np. jeśli pobierasz wiele wierszy i używasz ORDER BY, to jest jeden przypadek - jeśli masz losowy zestaw wskazówek - inny.
— Boris Treukhov
Dlaczego zamiast tego nie użyć TreeMap?
— Thorbjørn Ravn Andersen
TreeMap nie pomogłoby tutaj, ponieważ sortowanie musi odbywać się na wartościach ( ComparableObject), a nie na kluczu ( Integer).
— gutch
3
Należy również pamiętać, że zestaw obsługuje tylko unikatowe wpisy. Z drugiej strony kolekcja „wartości” HashMap może zawierać duplikaty. Z tego punktu widzenia TreeSet nie jest dobrym rozwiązaniem.
— rompetroll
@gutch, może się przydać moja odpowiedź na stronie „ stackoverflow.com/questions/3759112/… ”.
— Richard

Odpowiedzi:

87

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.

— fasseg
źródło
W moim przypadku musimy tylko iterować przez wynikową kolekcję, nigdy nie jest ona modyfikowana. Więc w oparciu o twoją odpowiedź ArrayListjest lepszym wyborem tutaj.
— gutch
Ponadto sortowanie tablic może odbywać się równolegle i zapewnia znacznie lepszą wydajność pamięci podręcznej.
— kaiser
21

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łą.

— BarsMonster
źródło
4
+1 Jeden z tych przypadków, w których teoria i rzeczywistość zostają rozdzielone. :) Z mojego doświadczenia
— wynika
Chyba że są O (N), co miałoby miejsce w przypadku danych całkowitych. Kolejki priorytetowe obejmują również operacje O (log N) do wstawiania, usuwania i zarządzania.
— Richard
10

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)

— Sean Patrick Floyd
źródło
3
Czy to nie byłoby najgorsze z obu światów? Wszystko, czego potrzebuję, to kolekcja w naturalnym porządku, która new TreeSet<ComparableObject>(map.values())wraca. Opakowanie tego w an ArrayListdoda tylko niepotrzebne operacje.
— gutch
1
Ostatecznym celem był posortowany Collection... co TreeSetjest. Nie widzę tutaj żadnej wartości, która konwertuje zestaw na listę.
— Gunslinger47
to nie jest zawijanie, to inicjalizacja. a arraylist jest lepszy w wyszukiwaniu, podczas gdy zestaw drzew jest lepszy w sortowaniu
— Sean Patrick Floyd
4
Doceniam wysiłek, jaki włożyłeś w napisanie benchmarku! Myślę jednak, że jest w tym błąd. Wygląda na to, że JVM uruchamia Transformerinstancje, które są później na liście, szybciej niż wcześniejsze: umieść je jako BestOfBothWorldsTransformerpierwsze i nagle zacznie działać znacznie wolniej. Więc przepisałem twój test porównawczy, aby losowo wybrać transformator i uśrednić wyniki. W moim teście TreeSetTransformerbije konsekwentnie BestOfBothWorldsTransformer, co konsekwentnie bije ArrayListTransformer- wcale nie tego się spodziewałem! Różnica jest jednak niewielka. Zobacz pastebin.com/L0t5QDV9
— gutch
1
Wiem, jakie jest twoje następne pytanie: co z PriorityQueueTransformer? Czy nie jest to znacznie szybsze niż inne? Cóż, tak jest, szkoda jednak, że nie ma poprawnej kolejności! Spójrz na listy generowane przez każdy transformator w moim kodzie powyżej, a zobaczysz, że PriorityQueueTransformer nie jest w porządku! Może używam PriorityQueuenieprawidłowo? Czy masz przykład prawidłowego sortowania?
— gutch
6

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 ”

— locka
źródło
1
Dobra uwaga na temat TreeSetpotencjalnie brakujących danych, jeśli compareTo zwraca 0. Ustaliłem, że w tym konkretnym przypadku implementacja compareTo nigdy nie zwróci 0, więc oba TreeSeti ArrayListbędą zachowywać się tak samo. Jednak już wcześniej złapał mnie ten problem, więc dziękuję za przypomnienie!
— gutch
PriorityQueue jest prawdopodobnie lepsze do sortowania listy niż TreeSet.
— locka
tak, w moim teście porównawczym (zobacz moją odpowiedź) PriorityQueue przewyższa TreeSet o 600 do 700%.
— Sean Patrick Floyd
PriorityQueuerzeczywiście działa szybciej, ale kiedy go wypróbowałem, wartości nie były w rzeczywistości posortowane - oczywiście, dlaczego było tak szybko! Może źle zinterpretowałem, jak używać PriorityQueue ... Przydałby się przykład tego, jak działa.
— gutch
PriorityQueue to po prostu kolejka z porównawczym / porównywalnym testem. Kiedy dodajesz () elementy do kolejki, insert porównuje nowy element z już istniejącymi, aby określić miejsce wstawienia. Podczas sondowania () kolejki lub iteracji jej zawartość jest już posortowana. Spodziewam się, że wstawianie odbywa się za pomocą jakiegoś algorytmu rekurencyjnego, tj. Podziel listę na dwie części i określ, w której połowie ją wstawić, ponownie podziel na dwie itd., Więc wydajność będzie wynosić O (log N), co teoretycznie jest takie samo jak TreeSet / TreeMap, ale implementacja może przyspieszyć.
— locka
1

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.

— 卢 声 远 Shengyuan Lu
źródło
6
Chociaż wydaje się to prawdą, pokrywa to niektóre ważne koszty. MergeSort działa w czasie O (n log n), ale czerwono-czarny będzie wymagał O (n log n) do wstawienia i ponownie do usunięcia. Notacja duże-O ukrywa istotne różnice w algorytmach.
— Richard
0

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.
— George Lords of Castle
źródło
0

Ś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.

  1. 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).

— FraK
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.