Ich schaue mir jetzt meine alte Schulaufgabe an und möchte die Lösung einer Frage finden.Welche Sortiermethode ist am besten für die Parallelverarbeitung geeignet?
Welche Sortiermethode ist am besten für die Parallelverarbeitung geeignet?
Ich denke, schnell sortieren (oder Art fusionieren?) Ist die Antwort.
Bin ich richtig?
wie Mergesort, quicksort auch aufgrund seiner Teile-und-Herrsche Natur leicht parallelisiert werden kann. Einzelne In-Place-Partitionsoperationen sind schwer zu parallelisieren, aber wenn sie geteilt sind, können verschiedene Abschnitte der Liste parallel sortiert werden.
Ein Vorteil des parallelen Quicksort gegenüber anderen parallelen Sortieralgorithmen ist, dass keine Synchronisation erforderlich ist. Ein neuer Thread wird gestartet, sobald eine Unterliste verfügbar ist, an der er arbeiten kann, und er kommuniziert nicht mit anderen Threads. Wenn alle Threads abgeschlossen sind, ist die Sortierung abgeschlossen.
Ich denke, Mergesort
Sie können den Datensatz teilen und parallele Operationen auf ihnen machen ..
Es hängt ganz von der Methode der Parallelisierung. Für Multithread-allgemeine Berechnungen bietet eine Zusammenführungssortierung ziemlich zuverlässige Lastenausgleichs- und Speicherlokalisierungseigenschaften. Für eine große sorting network in Hardware, ist eine Form der Batcher, Bitonic oder Shell-Sortierung tatsächlich am besten, wenn Sie eine gute O (log² n) Leistung wünschen.
+1 für die einzige richtige Antwort hier. –
Ich denke Merge Sort wäre die beste Antwort hier. Weil die Grundidee hinter merge sort darin besteht, das Problem in einzelne Lösungen zu unterteilen. Löse sie und füge sie zusammen.
Das machen wir auch in der Parallelverarbeitung. Teilen Sie das ganze Problem in kleine Einheitenanweisungen auf, um parallel zu berechnen und dann die Ergebnisse zu verbinden. Danke
Es ist merge sort, da die Sortierung auf zwei Sub-Arrays erfolgt und sie am Ende verglichen und sortiert werden. Diese können parallel
Ich glaube nicht, dass es notwendig ist, die vorhandenen Antworten zu duplizieren. – Mysticial
+1: Quicksort erfordert keine Synchronisierung nach der Teilung. Mergesort erfordert die Synchronisierung zum Zusammenführen. –
"Ein Vorteil des parallelen Quicksort gegenüber anderen parallelen Sortieralgorithmen ist, dass keine Synchronisation erforderlich ist". Äh, nein. Sie müssen natürlich warten, bis die Subtasks abgeschlossen sind, bevor Sie die Antwort, die Synchronisation, zurückgeben. –