Dlaczego Quicksort jest lepszy od innych algorytmów sortowania w praktyce?

31

To jest odpowiedź na pytanie do cs.SE autorstwa Janomy . Pełne kredyty i łupy dla niego lub cs.SE.

W standardowym kursie z algorytmów uczymy się, że quicksort wynosi średnio O (n log n) i O (n²) w najgorszym przypadku. Jednocześnie badane są inne algorytmy sortowania, które w najgorszym przypadku to O (n log n) (np. Scalesort i heapsort ), a nawet czas liniowy w najlepszym przypadku (np. Bąbelkowy ), ale z pewnymi dodatkowymi potrzebami pamięci.

Po szybkim spojrzeniu na kilka dłuższych czasów pracy jest naturalne stwierdzenie, że quicksort nie powinien być tak wydajny jak inne.

Weź również pod uwagę, że uczniowie uczą się podczas podstawowych kursów programowania, że ​​rekursja nie jest ogólnie dobra, ponieważ mogłaby zużyć zbyt dużo pamięci itp. Dlatego (i chociaż nie jest to prawdziwy argument), daje to wyobrażenie, że Quicksort może nie być naprawdę dobrze, ponieważ jest to algorytm rekurencyjny.

Dlaczego zatem Quicksort przewyższa inne algorytmy sortowania w praktyce? Czy ma to związek ze strukturą rzeczywistych danych ? Czy ma to związek ze sposobem działania pamięci w komputerach? Wiem, że niektóre wspomnienia są znacznie szybsze od innych, ale nie wiem, czy to jest prawdziwy powód tego sprzecznego z intuicją działania (w porównaniu z teoretycznymi szacunkami).

Raphael
źródło
3
Reputacja Quicksort pochodzi z czasów, gdy pamięć podręczna nie istniała.
AProgrammer
9
„dlaczego Quicksort przewyższa w praktyce inne algorytmy sortowania?” Jasne, że to prawda? Pokaż nam prawdziwą implementację, do której odwołujesz się w tym oświadczeniu, a społeczność powie ci, dlaczego ta konkretna implementacja zachowuje się tak, jak ona. Wszystko inne doprowadzi do dzikiego zgadywania o nieistniejących programach.
Doc Brown
1
@DocBrown: Wiele implementacji Quicksort (lub jego wariantów) jest wybieranych w wielu bibliotekach, prawdopodobnie dlatego, że działają najlepiej (mam nadzieję, że tak). Może więc być coś w algorytmie, który sprawia, że ​​Quicksort jest szybki, niezależnie od implementacji .
Raphael
1
Ktoś musi to powiedzieć dla kompletności, więc ja: Quicksort nie jest (zwykle) stabilny. Z tego powodu możesz nie chcieć go używać. Z tego powodu domyślnym sortowaniem może nie być Quicksort, nawet jeśli tego właśnie chcesz.
RalphChapin
1
@Raphael: Często tak zwane szybkie sortowanie jest w rzeczywistości pewną odmianą, taką jak sortowanie intro (używane, afaik, w standardowej bibliotece C ++), a nie czystym szybkim sortowaniem.
Giorgio

Odpowiedzi:

21

Nie zgodziłbym się, że quicksort jest lepszy niż inne algorytmy sortowania w praktyce.

Do większości celów Timsort - hybryda między sortowaniem scalania / wstawiania, który wykorzystuje fakt, że sortowane dane często zaczynają się prawie posortowane lub posortowane odwrotnie.

Najprostszy Quicksort (bez losowego obrotu) traktuje ten potencjalnie powszechny przypadek jako O (N ^ 2) (redukując do O (Nlg N) z losowymi obrotami), podczas gdy TimSort może obsłużyć te przypadki w O (N).

Zgodnie z tymi testami porównawczymi w języku C # porównującymi wbudowany quicksort z TimSort, Timsort jest znacznie szybszy w najczęściej posortowanych przypadkach i nieco szybszy w przypadkowym przypadku danych, a TimSort staje się lepszy, jeśli funkcja porównywania jest szczególnie wolna. Nie powtórzyłem tych testów i nie zdziwiłbym się, gdyby Quicksort lekko pobił TimSort za jakąś kombinację losowych danych lub jeśli jest coś dziwnego we wbudowanym sortowaniu C # (opartym na Quicksort), który to spowalnia. Jednak TimSort ma wyraźne zalety, gdy dane mogą być częściowo posortowane, i jest mniej więcej równy szybkiemu sortowaniu pod względem prędkości, gdy dane nie są częściowo posortowane.

TimSort ma również dodatkową zaletę bycia stabilnym gatunkiem, w przeciwieństwie do Quicksort. Jedyną wadą TimSort jest użycie pamięci O (N) w porównaniu z pamięcią O (lg N) w zwykłej (szybkiej) implementacji.

dr jimbob
źródło
18

Szybkie sortowanie uważa się za szybsze, ponieważ współczynnik jest mniejszy niż jakikolwiek inny znany algorytm. Nie ma na to żadnego powodu ani dowodu, po prostu nie znaleziono algorytmu o mniejszym współczynniku. To prawda, że ​​inne algorytmy również mają czas O ( n log n ), ale w świecie rzeczywistym współczynnik jest również ważny.

Zauważ, że w przypadku małych wstawiania danych sortowanie (takie, które jest uważane za O ( n 2 )) jest szybsze ze względu na naturę funkcji matematycznych. Zależy to od konkretnych współczynników, które różnią się w zależności od maszyny. (Na końcu tak naprawdę działa tylko asembler.) Tak więc czasami hybryda szybkiego sortowania i sortowania wstawiania jest najszybsza w praktyce.

Ramzi Kahil
źródło
7
+ Prawo. Nauczyciele muszą być bardziej świadomi (a ja byłem nauczycielem) faktu, że stałe czynniki mogą się różnić w zależności od rzędów wielkości. Zatem umiejętność dostrajania wydajności naprawdę ma znaczenie, bez względu na duże O. Problem polega na tym, że wciąż uczą gprof , tylko dlatego, że muszą przekroczyć ten punkt kulminacyjny w programie nauczania, czyli 180 stopni niewłaściwe podejście.
Mike Dunlavey
2
„Nie ma na to żadnego powodu ani uzasadnienia”: na pewno jest. Jeśli kopiesz wystarczająco głęboko, znajdziesz powód.
Gilles „SO- przestań być zły”
2
@B Seven: aby znacznie uprościć… dla algorytmu sortowania O (n log n) istnieją (n log n) iteracje pętli sortowania w celu posortowania n elementów. Współczynnik określa czas trwania każdego cyklu pętli. Gdy n jest naprawdę duże (co najmniej tysiące), współczynnik nie ma tak dużego znaczenia jak O (), nawet jeśli współczynnik jest ogromny. Ale gdy n jest małe, współczynnik ma znaczenie - i może być najważniejszą rzeczą, jeśli sortujesz tylko 10 przedmiotów.
Matt Gallagher
4
@MikeDunlavey - dobrym przykładem jest to, że budowanie piramid to O (n), a sortowanie ich zdjęć to O (n ln n), ale jest szybsze!
Martin Beckett
2
Istnieją gwarantowane algorytmy O (n log n), takie jak heapsort i scalesort, więc w asymptotycznych najgorszych przypadkach Quicksort nie jest tak samo szybki jak najlepszy. Ale w rzeczywistych warunkach niektóre warianty Quicksort radzą sobie wyjątkowo dobrze. Jednak powiedzenie „współczynnik jest mniejszy” jest jak powiedzenie „jest szybszy, ponieważ jest szybszy”. Dlaczego stałe czynniki są tak małe? Głównym powodem jest to, że Quicksort jest bardzo dobry pod względem lokalizacji - bardzo dobrze wykorzystuje pamięci podręczne. Mergesort ma również dobrą lokalizację, ale bardzo trudno jest zrobić to w miejscu.
Steve314
16

Quicksort nie przewyższa wszystkich innych algorytmów sortowania. Na przykład sortowanie od dołu do góry ( Wegener 2002 ) przewyższa szybkie sortowanie dla rozsądnych ilości danych i jest również algorytmem na miejscu. Jest również łatwy do wdrożenia (przynajmniej nie trudniejszy niż jakiś zoptymalizowany wariant Quicksort).

Po prostu nie jest tak dobrze znany i nie ma go w wielu podręcznikach, co może wyjaśniać, dlaczego nie jest tak popularny jak Quicksort.

Doktor Brown
źródło
+1: Przeprowadziłem kilka testów i rzeczywiście scalanie sortowania było zdecydowanie lepsze niż szybkie sortowanie dla dużych tablic (> 100000 elementów). Sortowanie sterty było nieco gorsze niż sortowanie po scaleniu (ale sortowanie po scaleniu wymaga więcej pamięci). Myślę, że to, co ludzie nazywają szybkim sortowaniem, jest często odmianą zwaną sortowaniem wstępnym: szybkie sortowanie, które wraca do sortowania hałdy, gdy głębokość rekurencji przekroczy określony limit.
Giorgio
@Giorgio: quicksort można zmodyfikować na kilka sposobów, aby go poprawić, patrz na przykład tutaj: algs4.cs.princeton.edu/23quicksort Czy próbowałeś tych ulepszeń?
Doc Brown
Ciekawe, czy możesz podać odniesienie do książki / strony, aby przeczytać o niej więcej? (najlepiej książka)
Ramzi Kahil
@Martin: masz na myśli stertę dołu do góry? Cóż, podałem powyżej odniesienie. Jeśli chcesz darmowego zasobu, niemiecka wikipedia ma artykuł na ten temat ( de.wikipedia.org/wiki/BottomUp-Heapsort ). Nawet jeśli nie mówisz po niemiecku, myślę, że nadal możesz przeczytać przykład C99.
Doc Brown
7

Nie powinieneś koncentrować się tylko na najgorszym przypadku i tylko na złożoności czasu. Chodzi bardziej o średnią niż najgorsze, a także o czas i przestrzeń.

Szybkie sortowanie:

  • ma średni czas złożoności Θ ( n log n );
  • może być zaimplementowany ze złożonością przestrzeni of (log n );

Weź również pod uwagę, że duża notacja O nie uwzględnia żadnych stałych, ale w praktyce robi różnicę, jeśli algorytm jest kilka razy szybszy. Θ ( n log n ) oznacza, że ​​algorytm wykonuje się w K  n  log ( n ), gdzie K jest stałe. Quicksort jest algorytm sortowania porównanie z najniższym K .

vartec
źródło
1
@Gilles: ma niski K, ponieważ jest to prosty algorytm.
vartec
5
WTF? To nie ma sensu. Prostota algorytmu nie ma związku z jego prędkością działania. Sortowanie wyboru jest prostsze niż szybkie sortowanie, co nie przyspiesza.
Gilles „SO- przestań być zły”
1
@Gilles: sortowanie wyboru to O (n ^ 2) dla każdego przypadku (najgorsze, średnie i najlepsze). Więc nie ma znaczenia, jakie to proste. Quicksort to O (n log n) dla średniego przypadku, a wśród wszystkich alg z O (n log n) avg jest najprostszy.
vartec
1
@Gilles: inne rzeczy są równe, prostota poprawia wydajność. Powiedzmy, że porównujesz dwa algorytmy, z których każdy pobiera (K n log n) iteracje swoich wewnętrznych pętli: algorytm, który musi robić mniej rzeczy na pętlę, ma przewagę wydajności.
nadchodząca burza
1
@comingstorm: sformułowane w ten sposób twoje zdanie jest tautologią, ale nie odnosi się do „prostoty”. Istnieją na przykład bardziej skomplikowane warianty Quicksort (rozróżnianie wielkości liter!), Które skutkują mniejszym czasem działania (zarówno w teorii, jak i praktyce).
Raphael
5

Quicksort jest często dobrym wyborem, ponieważ jest dość szybki, względnie szybki i łatwy do wdrożenia.

Jeśli poważnie myślisz o bardzo szybkim sortowaniu dużych ilości danych, prawdopodobnie lepiej jest z pewną odmianą MergeSort. Można to zrobić, aby skorzystać z pamięci zewnętrznej, może korzystać z wielu wątków, a nawet procesów, ale nie są one trywialne w kodzie.

James Anderson
źródło
1

Rzeczywista wydajność algorytmów zależy od platformy, a także języka, kompilatora, uwagi programisty na szczegółach implementacji, konkretnego wysiłku optymalizacyjnego itp. Tak więc „stała przewaga czynnikowa” szybkiego sortowania nie jest zbyt dobrze zdefiniowana - jest to subiektywna ocena oparta na obecnie dostępnych narzędziach i przybliżona ocena „równoważnego wysiłku wdrożeniowego” przez każdego, kto faktycznie wykonuje porównawcze badanie wydajności. .

To powiedziawszy, uważam, że Quicksort działa dobrze (w przypadku losowego wprowadzania danych), ponieważ jest prosty i ponieważ jego struktura rekurencyjna jest stosunkowo przyjazna dla pamięci podręcznej. Z drugiej strony, ponieważ jego najgorszy przypadek jest łatwy do uruchomienia, wszelkie praktyczne zastosowanie szybkiego sortowania będzie musiało być bardziej złożone, niż wskazywałby jego opis w podręczniku: w ten sposób zmodyfikowane wersje, takie jak introsort.

Z biegiem czasu, wraz ze zmianą dominującej platformy, różne algorytmy mogą zyskać lub utracić (źle zdefiniowaną) względną przewagę. Konwencjonalna wiedza na temat względnej wydajności może pozostawać w tyle za tą zmianą, więc jeśli naprawdę nie masz pewności, który algorytm jest najlepszy dla twojej aplikacji, powinieneś wdrożyć oba i przetestować je.

nadchodząca burza
źródło
Sądzę, że „mniejsza stała”, do której odnoszą się inni, dotyczy analizy formalnej, czyli liczby porównań lub zamian. Jest to bardzo dobrze zdefiniowane, ale nie jest jasne, w jaki sposób przekłada się to na środowisko wykonawcze. Właściwie kolega obecnie prowadzi badania w tej sprawie.
Raphael
Odniosłem wrażenie, że chodziło o ogólną wydajność, ale nie liczyłem na żadną z nich. Masz jednak rację: jeśli twoje porównanie jest szczególnie drogie, możesz sprawdzić liczbę oczekiwanych porównań ...
nadchodzi burza
1
Z tego powodu mówienie o ogólnej wydajności (w czasie) nie ma znaczenia w ogólnym przypadku, ponieważ bierze się pod uwagę zbyt wiele szczegółów. Przyczyną liczenia tylko wybranych operacji nie jest to, że są one drogie, ale że występują one „najczęściej "w sensie Landau-notation (Big-Oh), więc ich liczenie daje ci szorstką asymptotę. Gdy tylko weźmiesz pod uwagę stałe i / lub środowisko wykonawcze, ta strategia jest znacznie mniej interesująca.
Raphael
Dobra implementacja QuickSort skompiluje się tak, że wartości przestawne pozostaną w rejestrze procesora tak długo, jak będą potrzebne. Często wystarcza to do pokonania teoretycznie szybszego sortowania przy porównywalnych czasach Big-O.
Dan Lyons
Różne algorytmy sortowania mają różne cechy w odniesieniu do liczby porównań i liczby dokonywanych przez nie wymian. @DanLyons zauważa, że ​​typowe sortowanie w bibliotece dokonuje porównań za pomocą funkcji dostarczonych przez użytkownika, a przechowywanie wartości w rejestrach w wielu wywołaniach funkcji jest dość trudne.
Pointy