3. Quicksort - Problem

Quicksort - Problem

  • I

    Bei Boost ist grade eine Bibliothek namens "Sorting" auf dem Review-Scheduler, die einen Sortieralgorithmus bietet, der laut Beschreibung schneller als std::sort sei. Ich glaube das war Radixsort oder eine Variante davon.

    0
  • M

    314159265358979 schrieb:

    Was spricht eigentlich gegen Mergesort?

    Speicher und Zeit?

    0

  • SeppJ schrieb:

    hustbaer schrieb:

    std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet.

    😮 ⚠ Gleich Komplexitätsklasse != Genau gleich schnell ⚠

    Nein. Gleicher Algorithmus == Genau gleich schnell.
    Nicht verstanden haben, aber gleich mal die Warnschilder auspacken.

    Wikipedia schrieb:

    Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

    D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

    Jetzt klar?

    0
  • W

    hustbaer schrieb:

    SeppJ schrieb:

    hustbaer schrieb:

    std::sort ist Introsort, und damit genau gleich schnell wie Quicksort, so lange Quicksort nicht entartet.

    😮 ⚠ Gleich Komplexitätsklasse != Genau gleich schnell ⚠

    Nein. Gleicher Algorithmus == Genau gleich schnell.
    Nicht verstanden haben, aber gleich mal die Warnschilder auspacken.

    Ich glaube aber (hab ich mal ausprobiert), bei kleinen Mengen (und die kommen ja bei Quicksort mit der Aufteilung bei der Rekursion vor) können andere Algorithmen durchaus schneller sein (bei mir hat das mit Heapsort funktioniert, war leicht schneller, aber immer noch langsamer als std::sort()).

    EDIT:

    hustbaer schrieb:

    Wikipedia schrieb:

    Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

    D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

    Jetzt klar?

    Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung 🙂 . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

    0

  • ipsec schrieb:

    Bei Boost ist grade eine Bibliothek namens "Sorting" auf dem Review-Scheduler, die einen Sortieralgorithmus bietet, der laut Beschreibung schneller als std::sort sei. Ich glaube das war Radixsort oder eine Variante davon.

    Naja, es gibt viele Sortieralgorithmen die schneller als Quicksort sind, bloss keine mir bekannten general purpose Sortieralgorithmen.
    Radixsort ist kein general purpose Sortieralgorithmus.

    0

  • wxSkip schrieb:

    EDIT:

    hustbaer schrieb:

    Wikipedia schrieb:

    Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

    D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

    Jetzt klar?

    Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung 🙂 . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

    Bist du sicher?
    Bei den allermeisten Inputs schaltet std::sort nämlich nicht um.

    Könnte auch daran liegen wie du das Pivot Element ermittelt hast (üblich ist "Median of 3 Medians of 3"), bzw. wann du für kleine Mengen auf Insertion-Sort umgeschaltet hast.

    0
  • ?

    mazal schrieb:

    314159265358979 schrieb:

    Was spricht eigentlich gegen Mergesort?

    Speicher und Zeit?

    nee, MergeSort ist im WorstCase so schnell wie QuickSort im BestCase ...
    eigentlich gibt's für MergeSort gar keinen WorstCase ...
    von daher ist MergeSort zumindest theoretisch am schnellsten ...
    allerdings ist es nicht so einfach, MergeSort genauso maschinenfreundlich zu
    implementieren, wie QuickSort, von daher macht QuickSort wieder einiges gut ...
    aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
    der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
    QuickSort
    es gibt ein paar Studien, die wollen bewiesen haben, dass für häufiges
    Sortieren 'mittelgroßer' Datenmengen (~100.000 Zahlen)
    Shell-Sort noch schneller als Quick- oder sogar MergeSort sein soll ...
    in einigen Sonderfällen ist allerdings auch nichts schneller als Radix-Sort,
    aber leider nicht immer anwendbar
    heap sort ist eine langsamere MergeSort Variante, die dafür weniger zusätzlichen
    Speicher benötigt als MergeSort
    Insgesamt stellt sich die Lage also circa so dar (vom schnellsten zum
    langsamsten)

    1. Radix Sort, Bucket Sort & Konsorten
2. MergeSort / ShellSort
3. HeapSort
4. QuickSort
4. Insertion / Selection Sort
5. Bubble Sort

    Einzig MergeSort ist für jeden Fall anwendbar und kann zudem stabil
    und sogar in-place (extrem komplex) implementiert werden, und wäre somit
    von den vergleichsbasierten Algos der geeignetste Multi-Purpose-Algo.

    Viel schneller als eine riesige Datenmenge mit z.B. 100.000.000 Einträgen
    'auf einmal' zu sortieren wäre eine Umverteilung auf einzelne, kleinere
    Buckets, die man dann jeweils separat mit MergeSort (falls stabil gewünscht
    ist) oder ShellSort (wenn's instabil sein darf) vorsortiert, und die dann
    letzten Endes wieder mit Merge() zusammenführt.

    HeapSort ist nicht stabil und etwas weniger maschinenfreundlich als MergeSort,
    dafür kann kein pathologischer WorstCase eintreten wie bei QuickSort.

    Gegen Quicksort spricht hauptsächlich dessen Unzuverlässigkeit plus ein
    Worst Case, der das Potential hat, im RL gewaltige Schäden anzurichten.
    Ansonsten natürlich im Durchschnittsfall zirka ebenso schnell wie
    MergeSort, aber leider auch nicht stabil.

    Selection Sort, Insertion Sort oder Bubble Sort könnte man auch schon sehr
    früh im Schulunterricht durchnehmen, sind hauptsächlich von pädagogischem
    Nutzen, überraschen aber in einigen Spezialfällen mit dem Bestcase bei
    Feldern, die schon größtenteils vorsortiert vorliegen. In solchen Fällen
    sogar schneller als MergeSort und en-par mit Radix-/Bucket Sort.

    So, also das alles noch mal zur Auffrischung des Uni-Lehrstoffs, den einige
    schon vergessen haben. In der Praxis interessiert es nicht weiter, da nimmt
    man ohnehin den Sortierer aus der Bibliothek (je nach Compiler-System ist
    der Algorithmus hinter der Schnittstelle von Anbieter zu Anbieter verschieden,
    auch wenn sie jedes Mal qsort oder std::sort() heißt, handelt es sich dabei
    eher selten um QuickSort (wohl eher eine getunete MergeSort Variante - idR))

    ...

    0
  • 3

    Einen großen Vorteil von Mergesort hast du allerdings vergessen, er lässt sich auch mit ForwardAccess implementieren und ist somit auch für Listen geeignet und gerade dort besonders effizient, weil kein zusätzlicher Speicher benötigt wird, ein splicen reicht 😉

    0

  • SortierFachmann schrieb:

    (komisches Getrolle)

    Dass Merge-Sort im average case schneller (oder auch nur gleich schnell) sein soll als Quicksort ist purer Unfug.
    Dass Quicksort dafür worst case schlecht aussieht ist unbestritten.
    Deswegen verwendet man ihn ja auch nicht alleine.

    0
  • B

    SortierFachmann schrieb:

    aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
    der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
    QuickSort

    Das "etwas zu oft" sollte man quantifizieren. Meiner Erinnerung nach ist es kein Problem, wenn Quicksort mit einer Wahrscheinlichkeit von 0,9 das ungünstigste Pivotelement erwischt. Das Problem ist einfach, dass die meisten Sortieranwendungen auf fast vorsortierten Daten stattfinden.

    heap sort ist eine [...] MergeSort Variante

    Wow, so hab ich das noch gar nicht gesehen. Made my day. 👍

    0

  • Bashar schrieb:

    SortierFachmann schrieb:

    aber wehe, QuickSort erwischt als Pivot-Element mal etwas zu oft einen Wert,
    der weit weg vom Durchschnittswert liegt! dann ist sogar bubble sort besser als
    QuickSort

    Das "etwas zu oft" sollte man quantifizieren. Meiner Erinnerung nach ist es kein Problem, wenn Quicksort mit einer Wahrscheinlichkeit von 0,9 das ungünstigste Pivotelement erwischt. Das Problem ist einfach, dass die meisten Sortieranwendungen auf fast vorsortierten Daten stattfinden.

    Vorsortierte Daten sind super für Quicksort, wenn man den Pivot mit z.B. Median of 3 auswählt.
    Es zwingt einen ja keiner die problematische Variante mit Pivot = erstes Element zu implementieren.

    0
  • ?

    hustbaer schrieb:

    SortierFachmann schrieb:

    (komisches Getrolle)

    Dass Merge-Sort im average case schneller (oder auch nur gleich schnell) sein soll als Quicksort ist purer Unfug.
    Dass Quicksort dafür worst case schlecht aussieht ist unbestritten.
    Deswegen verwendet man ihn ja auch nicht alleine.

    Heutzutage arbeitet man aber auch kaum noch mit Single-Core Prozessoren, sondern
    verteilt größere Jobs auch gerne mal auf mehrere physische CPUs. Jetzt erklär
    mir mal bitte, wie QuickSort seine beiden Listen gleichzeitig sortieren
    und dabei die zur Verfügung stehende Zeit auch optimal ausnutzen soll, wenn
    Liste 1 10 Einträge und Liste 2 100000 Einträge enthält. CPU1 ist mit seiner
    Teilliste fertig und darf dann mal ein paar Stunden darauf warten, bis
    CPU2 mit der 10000x größeren Liste fertig ist. Tja, so sehen wohl die
    Laufzeit-Effizienz Vorstellungen von Prof. hustbaer und Dr. Bashar aus.
    Zum Glück gibt's noch andere kompetente Programmierer da draußen, die
    zunehmend QuickSort in die Tonne kippen, weil's einfach nicht mehr zeitgemäß
    ist auf nem Multicore (wegen der inferioren Laufzeiteffizienz). Ganz zu
    schweigen vom Super-GAU-Potential, wenn QuickSort mal eine Pechsträhne
    beim Pivot-Pokern haben sollte.

    MergeSort hat gar keinen worst case oder best case, sondern einfach nur einen
    average case, der sogar theoretisch immer schneller sein muss als
    jeder noch so günstige best case-Verlauf von QuickSort. Hat der Professor
    damals Länge mal Breite bewiesen, also muss es wohl so sein.
    Sogar auf dem SingleCore.
    Nur wegen der schnellen inneren Schleife kann QuickSort diesen
    theoretischen Nachteil in der physischen Realität kompensieren, verliert
    aber gegenüber MergeSort spätestens dann massiv an Boden, wenn man die
    stets gleich großen Listen von MergeSort auf mehrere CPUs verteilen kann
    (während die 5%-links, 95%-rechts Listen von QSort nicht gerade optimal
    dazu geeignet sind!)

    So, jetzt haste mal wieder was gelernt, Prof. hustbaer
    C & D

    0
  • B

    Warum so gehässig? Warst du schon so, bevor du Sortierfachmann wurdest?

    0
  • ?

    Er hat wahrscheinlich einen kleinen Penis.

    0

  • Lieber Herr Prof. Dr. Dr. SortierFachmann,

    Parallelisierbarkeit ist nun wieder ein ganz eigenes Thema.

    Wenn man auf geringe Latenz optimieren will, und dafür schlechteren Throughput in kauf nimmt, dann wird es Sinn machen einen parallelen Merge-Sort zu verwenden. Vorausgesetzt man hat mehr als 2 CPUs, denn mit nur 2 CPUs wird Introsort vermutlich auch noch besser abschneiden.

    Wenn man dagegen auf Throughput optimieren will, was jetzt nicht gerade ein seltener Fall ist, dann wird es wohl mehr Sinn machen einen (parallelen oder auch nicht) Introsort zu verwenden.

    @Bashar:

    Bashar schrieb:

    Warum so gehässig?

    Weil er Student ist, und meint die Weisheit mit dem Löffel gefressen zu haben.

    0
  • S

    Irgendwer schrieb:

    Er hat wahrscheinlich einen kleinen Penis.

    👍 👍 👍 hihi^^

    er hat penis gesagt hihi^^

    0
  • K

    314159265358979 schrieb:

    [...]Mergesort[...]weil kein zusätzlicher Speicher benötigt wird, ein splicen reicht 😉

    Ganz ohne zusätzlichen Speicher kommt man da nicht aus. Du brauchst O(log n) zusätzlichen Speicher für Mergesort. Rekursiv implementiert, wird O(log n) Speicher vom "Stapel" verwendet. Iterativ gibt's den Algorithmus auch. Dann brauchst Du aber immer noch O(log n) temporäre Listen, zwischen denen Du hin und her "splicen" musst. libstd++ hat zB std::list<>::sort iterativ implementiert und legt zwischenzeitlich ein lokales Array von 64 Listen an. Das reicht zum Sortieren für ca pow(2,64) Elemente. 😉

    Aber wenn man nicht gerade auf Listen arbeitet, sondern auf "Arrays", sehe ich nicht, wie man Mergesort ohne mindestens 50% Overhead (Speicherverbrauch bezogen auf das ursprüngliche Array) erledigen kann.

    0
  • W

    hustbaer schrieb:

    wxSkip schrieb:

    EDIT:

    hustbaer schrieb:

    Wikipedia schrieb:

    Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted.

    D.h. so lange Introsort nicht umschaltet *ist* es ein Quicksort. Der minimale Overhead die Rekursionstiefe mitzuzählen fällt dabei wirklich nicht ins Gewicht.

    Jetzt klar?

    Hey, genau so habe ich das auch "erfunden", inklusive logarithmischer Berechnung 🙂 . Und dort liegt eben auch der Unterschied in der Geschwindigkeit von Introsort.

    Bist du sicher?
    Bei den allermeisten Inputs schaltet std::sort nämlich nicht um.

    Könnte auch daran liegen wie du das Pivot Element ermittelt hast (üblich ist "Median of 3 Medians of 3"), bzw. wann du für kleine Mengen auf Insertion-Sort umgeschaltet hast.

    Aha, doch falsch verstanden 😉

    Am Pivotelement liegt es nicht, beim Durchschnitt aus 2 oder 3 Elementen ist es bei mir ziemlich genau gleich schnell.

    @SortierFachmann: Dann erklär mir doch mal, was dich daran hindert, nachdem Thread 1 mit der 10-Elemente-Liste fertig ist, die zwei Teile aus der 100000-Elemente-Liste wieder auf 2 Threads aufzuteilen? Ich glaube nicht, dass der Zeitraum, der benötigt wird, um einen Thread zu erstellen, so groß ist, dass Mergesort da schneller wird.

    0
Anmelden zum Antworten