Pytanie Dlaczego Collections.sort używa sortowania scalonego zamiast quicksort? [Zamknięte]


Wiemy, że szybkie sortowanie jest najszybszym algorytmem sortowania.

W collections.sort wykorzystano algorytm sortowania scalającego zamiast szybkiego sortowania. Ale Arrays.sort używa szybkiego sortowania.

Z jakiego powodu CollectionsSort używa sortowania scalonego zamiast szybkiego sortowania?


76
2018-03-01 09:12


pochodzenie


Jeśli nie możesz poprosić autora JDK o odpowiedź, wszystko, co dostaniesz, to zgadywanie. To nie jest prawdziwe pytanie. - user207421
@ EJP Dobra rada, ale z pewnością "Brak konstruktywności" jest właściwym powodem zamknięcia. Dla mnie jest jasne, o co tu chodzi. - Duncan Jones
Ponieważ członkowie Java postanowili zrobić to w ten sposób. Poprosić ich. Nie sądzę, że nie można uzyskać uzasadnionej odpowiedzi. I szybkie sortowanie nie najlepszy. To jest tylko najlepsze dla ogólne użycie. - Adam Arold
Jedno przypuszczenie: Quicksort nie jest stabilny, Mergesort jest. Dla prymitywów stabilny / niestabilny sort jest nieistotny, ponieważ może to być obiekt (a przynajmniej można uzyskać błędy wniesione przeciwko sortowaniu niestabilnemu). - parsifal
@EJP, Nic nie stoi na przeszkodzie, aby intencje autorów JDK stały się publiczne. Gdy jest to publiczne, nie potrzebujemy odpowiedzi od samego autora. W rzeczywistości można uzyskać odpowiedź, która jest więcej niż zgadywaniem, nawet bez odpowiedzi autora JDK. - Pacerier


Odpowiedzi:


Bardzo prawdopodobne od Josha Blocha §:

Napisałem te metody, więc przypuszczam, że mam kwalifikacje do odpowiedzi. To jest   prawda, że ​​nie ma jednego najlepszego algorytmu sortowania. QuickSort ma   dwa główne braki w porównaniu do mergesort:

  1. Nie jest stabilny (jak zauważył parsifal).

  2. Tak nie jest gwarancja n log n wydajność; może obniżyć się do kwadratowej wydajności na wejściach patologicznych.

Stabilność nie jest problemem dla typów pierwotnych, ponieważ nie ma pojęcia   tożsamość w odróżnieniu od (wartości) równości. I możliwość   zachowanie kwadratowe uznano za nie problem w praktyce   Implementacja Bentely i McIlroy (lub później dla Podwójny Pivot   Szybkie sortowanie), dlatego te warianty QuickSort zostały użyte   prymitywne rodzaje.

Stabilność to wielka sprawa przy sortowaniu dowolnych obiektów. Na przykład,   załóżmy, że masz obiekty reprezentujące wiadomości e-mail i sortujesz   najpierw według daty, a następnie przez nadawcę. Oczekujesz, że zostaną posortowane według   w każdym nadawcy, ale będzie to prawdą tylko w przypadku sortowania   stabilny. Właśnie dlatego zdecydowaliśmy się na dostarczenie stabilnego sortowania (Merge Sort)   do sortowania odniesień do obiektów. (Technikally speaking, wielokrotny sekwencyjny   stabilne sortowanie skutkuje uporządkowaniem leksykograficznym na klawiszach w   kolejność odwrotna sortów: ostateczny sort decyduje o tym najbardziej   znaczący podklucz.)

To dobra strona korzyści, które Merge Sortuj gwarancje n log n (godzina)   wydajność bez względu na dane wejściowe. Oczywiście jest jeszcze jedna strona:   sortowanie szybkie to sortowanie "na miejscu": wymaga tylko log n przestrzeni zewnętrznej   (aby zachować stos wywołań). Połącz, sortuj, z drugiej strony,   wymaga O (n) przestrzeni zewnętrznej. Wariant TimSort (wprowadzony w Javie   SE 6) wymaga znacznie mniej miejsca (O (k)), jeśli macierz wejściowa jest   prawie posortowane.

Ponadto następujący Jest istotna:

Algorytm używany przez java.util.Arrays.sort i (pośrednio) przez   java.util.Collections.sort do sortowania referencji obiektów jest "zmodyfikowany   mergesort (w którym pominięto scalenie, jeśli najwyższy element w   mała podlista jest mniejsza niż najniższy element na wysokiej podlistie)   jest względnie szybkim, stabilnym rodzajem, który gwarantuje O (n log n)   wydajność i wymaga O (n) dodatkowej przestrzeni. W swoim czasie (zostało napisane   w 1997 roku Joshua Bloch), był to dobry wybór, ale dzisiaj, ale możemy   znacznie lepiej.

Od 2003 roku sortowanie list w Pythonie wykorzystuje algorytm znany jako timsort   (za Tima Petersa, który to napisał). Jest stabilny, adaptacyjny, iteracyjny   mergesort, który wymaga znacznie mniej niż n log (n) porównań, kiedy   działa na częściowo posortowanych tablicach, oferując jednocześnie wydajność   porównywalne do tradycyjnego mergesort, gdy są uruchamiane na losowych tablicach. Lubić   wszystkie właściwe mergesorts timsort jest stabilne i działa w czasie O (n log n)   (najgorszy przypadek). W najgorszym przypadku timsort wymaga tymczasowego przechowywania   spacja dla odwołań do obiektu n / 2; w najlepszym razie wymaga tylko   mała stała ilość miejsca. Porównaj to z prądem   implementacja, która zawsze wymaga dodatkowej przestrzeni dla obiektu n   referencje i bije n log n tylko na prawie posortowanych listach.

Timsort jest opisany szczegółowo tutaj:    http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Pierwotna implementacja Tima Petersa została napisana w C. Joshua Bloch   przeniesiono go z C na Javę i przetestowano, przetestowano i dostrojono   wynikowy kod ekstensywnie. Powstały kod to drop-in   zamiennik dla java.util.Arrays.sort. Na wysoce uporządkowanych danych, to   kod może działać do 25 razy szybciej niż bieżąca implementacja (włączona   maszyna wirtualna HotSpot). Na losowych danych, prędkości starych i nowych   wdrożenia są porównywalne. W przypadku bardzo krótkich list, nowe   wdrożenie jest znacznie szybsze niż stare, nawet losowe   danych (ponieważ pozwala uniknąć niepotrzebnego kopiowania danych).

Zobacz także Czy Java 7 używa Tim Sort dla Method Arrays.Sort?.

Nie ma jednego "najlepszego" wyboru. Podobnie jak wiele innych rzeczy, chodzi o kompromisy.


156
2018-03-01 09:20