Beste Sortierung für Multi-Thread-Anwendungen

Sie verwenden merge sort für Multithread-Anwendungen.

Der Grund:

Durch die Sortierung wird das Problem in einzelne kleinere Probleme (kleinere Arrays) unterteilt und anschließend zusammengeführt. Dies kann in separaten Threads erfolgen.

Bei der schnellen Sortierung wird eine Pivot-Sortierung für ein einzelnes Array durchgeführt. Daher ist es schwieriger, das Problem effizient zwischen Threads aufzuteilen.

Jeder Divide and Conquer-Algorithmus kann relativ einfach parallelisiert werden. Merge sort und quicksort folgen demselben grundlegenden Schema, das parallel ausgeführt werden kann:

Wo sie sich unterscheiden, ist die Aufteilung in Quicksort schwierig und das Zusammenführen ist trivial (keine Operation). In merge sort ist es umgekehrt: Dividieren ist trivial und das Zusammenführen ist schwierig.

Wenn Sie das obige Schema implementieren, ist Quicksort eigentlich einfacher , um parallelisiert zu werden, weil Sie den Zusammenführungsschritt einfach vergessen können. Für die Zusammenführungs-Sortierung müssen Sie abgeschlossene parallele Aufgaben verfolgen. Dies verschraubt den Lastenausgleich.

Wenn Sie andererseits dem obigen Schema folgen, haben Sie ein Problem: Die allererste Division und die allerletzte Zusammenführung werden nur einen einzigen Prozessor verwenden und alle anderen Prozessoren sind inaktiv. Daher ist es sinnvoll, diese Operationen parallel zu betreiben. Und hier sehen wir, dass die Parallelisierung des Partitionierungsschritts in Quicksort viel schwieriger ist als die Parallelisierung des Merge-Schritts in Merge-Sort.

Eine Merge-Sortierung scheint einfacher zu sein, parallelisieren und verteilen zu können ... denk darüber nach, du brichst es in saubere Sub-Probleme auf, die leicht geteilt und verteilt werden können. Das gilt aber auch für Quicksort. Allerdings würde ich es wahrscheinlich mit merge sort tun, da es wahrscheinlich einfacher wäre.

Unter der Annahme einer anständigen Pivot-Auswahl ist das nicht ganz anders.

Teilprobleme sind trivial zu parallelisieren; Sie verwenden (meist) disjunkten Speicher und benötigen keine Synchronisation, so dass der eigentliche Unterschied in den Engpässen liegt: die anfängliche Partition von Quick-Sort vs. die finale Zusammenführung in Merge-Sort. Vernachlässigt man diese Parallelisierung, führt dies zu schlechten Beschleunigungen für viele Kerne oder wenige Elemente (Dies macht sich viel schneller bemerkbar, als man denkt!).

Beide Algorithmen können effizient parallelisiert werden. Siehe dieses MCSTL-Dokument für einige experimentelle Ergebnisse und Details zur Implementierung. Der MCSTL war die Basis für den GNU C ++ std-lib Parallelmodus.

Es ist nicht klar, welcher Algorithmus unter allen Umständen besser funktioniert, da er von der Datenverteilung abhängt und ob Swaps oder Vergleiche langsamer sind.

Ich denke, sie suchen nach merge-sort als Antwort, da es einfach ist zu sehen, wie man das zwischen Threads aufteilt. Obwohl ein anderer Kommentar anzeigt, dass qsort auch in kleinere Probleme aufgeteilt werden kann. Wahrscheinlich können viele in kleinere Probleme aufgeteilt werden.

Es gibt einen kritischen Aspekt, der nicht ignoriert werden kann. Die Kommunikation mit den anderen Threads benötigt viel Zeit. Der Datensatz, den Sie sortieren, muss riesig oder sehr teuer sein, bevor Sie die Threads erstellen und die Kommunikation zwischen ihnen durchführen, ist besser als nur einen einzelnen Thread zu verwenden.

Darüber hinaus haben Sie ein ernstes Problem mit falschem Teilen. Wenn mehrere Threads mit denselben Daten arbeiten, können sie (ungeachtet der Kommunikationszeit) langsamer sein, da die CPU gezwungen ist, Daten zwischen mehreren Kernen zu teilen und zu aktualisieren. Wenn Ihr Algorithmus die Daten nicht richtig ausrichten kann, wird sie durch Verteilen an verschiedene Threads verlangsamt.