Zusammenführungsalgorithmus - Merge algorithm

Zusammenführungsalgorithmen sind eine Familie von Algorithmen , die mehrere sortierte Listen als Eingabe verwenden und eine einzelne Liste als Ausgabe erzeugen, die alle Elemente der Eingabelisten in sortierter Reihenfolge enthält. Diese Algorithmen werden als Unterroutinen in verschiedenen Sortieralgorithmen verwendet , am bekanntesten ist Mergesort .

Anwendung

Ein Beispiel für Zusammenführungssortierung

Der Zusammenführungsalgorithmus spielt eine entscheidende Rolle im Zusammenführungssortierungsalgorithmus , einem vergleichsbasierten Sortieralgorithmus . Konzeptionell besteht der Merge-Sort-Algorithmus aus zwei Schritten:

  1. Unterteilen Sie die Liste rekursiv in Unterlisten von (ungefähr) gleicher Länge, bis jede Unterliste nur noch ein Element enthält, oder betrachten Sie bei iterativer (bottom-up) Merge-Sortierung eine Liste von n Elementen als n Unterlisten der Größe 1. A Liste, die ein einzelnes Element enthält, ist per Definition sortiert.
  2. Unterlisten wiederholt zusammenführen, um eine neue sortierte Unterliste zu erstellen, bis die einzelne Liste alle Elemente enthält. Die Einzelliste ist die sortierte Liste.

Der Zusammenführungsalgorithmus wird wiederholt im Zusammenführungssortierungsalgorithmus verwendet.

Ein Beispiel für eine Zusammenführungssortierung ist in der Abbildung dargestellt. Es beginnt mit einem unsortierten Array von 7 ganzen Zahlen. Das Array ist in 7 Partitionen unterteilt; jede Partition enthält 1 Element und wird sortiert. Die sortierten Partitionen werden dann zusammengeführt, um größere sortierte Partitionen zu erzeugen, bis 1 Partition, das sortierte Array, übrig bleibt.

Zusammenführen von zwei Listen

Das Zusammenführen zweier sortierter Listen zu einer kann in linearer Zeit und linearem oder konstantem Raum (je nach Datenzugriffsmodell) erfolgen. Der folgende Pseudocode demonstriert einen Algorithmus, der Eingabelisten (entweder verknüpfte Listen oder Arrays ) A und B zu einer neuen Liste C zusammenführt . Der Funktionskopf ergibt das erste Element einer Liste; "Löschen" eines Elements bedeutet, es aus seiner Liste zu entfernen, normalerweise durch Inkrementieren eines Zeigers oder Index.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

Wenn die Eingaben verknüpfte Listen sind, kann dieser Algorithmus implementiert werden, um nur eine konstante Menge an Arbeitsraum zu verwenden; die Zeiger in den Knoten der Listen können zur Buchführung und zum Aufbau der endgültigen zusammengeführten Liste wiederverwendet werden.

Beim Zusammenführungssortieralgorithmus wird diese Unterroutine typischerweise verwendet, um zwei Unterarrays A[lo..mid] , A[mid+1..hi] eines einzelnen Arrays A zusammenzuführen . Dies kann durch Kopieren der Unterarrays in ein temporäres Array und anschließendes Anwenden des obigen Zusammenführungsalgorithmus erfolgen. Die Zuweisung eines temporären Arrays kann vermieden werden, jedoch auf Kosten der Geschwindigkeit und des Programmierkomforts. Verschiedene in-Place - merge - Algorithmen entwickelt worden, die manchmal die lineare Zeit opfern gebunden eine herzustellen O ( n log n ) Algorithmus; siehe Merge sort § Varianten zur Diskussion.

K-Wege-Zusammenführung

k- way Merging verallgemeinert binäres Zusammenführen auf eine beliebige Anzahl k sortierter Eingabelisten. Anwendungen des k- Wege-Mergings treten in verschiedenen Sortieralgorithmen auf, einschließlich Geduldssortierung und einem externen Sortieralgorithmus , der seine Eingabe in k = 1/M− 1 Blöcke, die in den Speicher passen, sortiert diese nacheinander und fügt diese Blöcke dann zusammen.

Es gibt mehrere Lösungen für dieses Problem. Eine naive Lösung besteht darin, eine Schleife über die k- Listen zu machen, um jedes Mal das minimale Element auszuwählen, und diese Schleife zu wiederholen, bis alle Listen leer sind:

  • Eingabe: eine Liste von k Listen.
  • Während eine der Listen nicht leer ist:
    • Durchlaufen Sie die Listen, um die Liste mit dem kleinsten ersten Element zu finden.
    • Geben Sie das minimale Element aus und entfernen Sie es aus seiner Liste.

Im schlimmsten Fall führt dieser Algorithmus ( k −1)( nk/2) Elementvergleiche, um seine Arbeit zu erledigen, wenn die Listen insgesamt n Elemente enthalten. Es kann verbessert werden, indem die Listen in einer Prioritätswarteschlange ( min-heap ) gespeichert werden, die durch ihr erstes Element gekennzeichnet ist:

  • Erstellen Sie einen Min-Heap h der k- Listen, indem Sie das erste Element als Schlüssel verwenden.
  • Während eine der Listen nicht leer ist:
    • Sei i = find-min( h ) .
    • Geben Sie das erste Element der Liste i aus und entfernen Sie es aus seiner Liste.
    • Erneut aufhäufen h .

Das Suchen nach dem nächstkleinsten auszugebenden Element (find-min) und das Wiederherstellen der Heap-Reihenfolge kann jetzt in O (log k ) Zeit erfolgen (genauer gesagt 2⌊log k Vergleiche), und das vollständige Problem kann in O . gelöst werden ( n log k ) Zeit (ungefähr 2 n log k Vergleiche).

Ein dritter Algorithmus für das Problem ist eine Divide-and-Conquer- Lösung, die auf dem binären Merge-Algorithmus aufbaut:

  • Wenn k = 1 ist , geben Sie die Einzeleingabeliste aus.
  • Wenn k = 2 , führe eine binäre Zusammenführung durch.
  • Else, fusioniert rekursiv die ersten k / 2⌋ Listen und die letzten k / 2⌉ Listen, dann binären merge diese.

Wenn die Eingangsliste an diesen Algorithmus durch Länge geordnet sind, kürzeste Erstens erfordert es weniger als n ⌈log k Vergleiche, dh weniger als die Anzahl die Hälfte von dem verwendeten heapbasierten Algorithmus; in der Praxis kann er ungefähr so ​​schnell oder langsam sein wie der heap-basierte Algorithmus.

Paralleles Zusammenführen

Eine parallele Version des binären Zusammenführungsalgorithmus kann als Baustein einer parallelen Zusammenführungssortierung dienen . Der folgende Pseudocode demonstriert diesen Algorithmus in einem parallelen Divide-and-Conquer- Stil (adaptiert von Cormen et al. ). Es arbeitet mit zwei sortierten Arrays A und B und schreibt die sortierte Ausgabe in das Array C . Die Notation A[i...j] bezeichnet den Teil von A vom Index i bis j , exklusiv.

algorithm merge(A[i...j], B[k...ℓ], C[p...q]) is
    inputs A, B, C : array
           i, j, k, ℓ, p, q : indices

    let m = j - i,
        n = ℓ - k

    if m < n then
        swap A and B  // ensure that A is the larger array: i, j still belong to A; k, ℓ to B
        swap m and n

    if m ≤ 0 then
        return  // base case, nothing to merge

    let r = ⌊(i + j)/2⌋
    let s = binary-search(A[r], B[k...ℓ])
    let t = p + (r - i) + (s - k)
    C[t] = A[r]

    in parallel do
        merge(A[i...r], B[k...s], C[p...t])
        merge(A[r+1...j], B[s...ℓ], C[t+1...q])

Der Algorithmus funktioniert, indem er entweder A oder B , je nachdem, welcher Wert größer ist, in (fast) gleiche Hälften teilt. Es teilt dann das andere Array in einen Teil mit Werten, die kleiner als der Mittelpunkt des ersten sind, und einen Teil mit größeren oder gleichen Werten. (Das Unterprogramm für die binäre Suche gibt den Index in B zurück, wobei A [ r ] wäre, wenn es in B wäre ; dass dies immer eine Zahl zwischen k und ℓ wäre .) Schließlich wird jedes Paar von Hälften rekursiv zusammengeführt , und da die rekursiven Aufrufe unabhängig voneinander sind, können sie parallel durchgeführt werden. Der hybride Ansatz, bei dem ein serieller Algorithmus für den Basisfall der Rekursion verwendet wird, hat sich in der Praxis als gut bewährt

Die Arbeit, die der Algorithmus für zwei Arrays mit insgesamt n Elementen leistet, dh die Laufzeit einer seriellen Version davon, ist O ( n ) . Dies ist optimal, da n Elemente in C kopiert werden müssen . Um die Spanne des Algorithmus zu berechnen , ist es notwendig, eine Recurrence-Relation abzuleiten . Da die beiden rekursiven Aufrufe von merge parallel sind, muss nur der teurere der beiden Aufrufe berücksichtigt werden. Im schlimmsten Fall beträgt die maximale Anzahl von Elementen in einem der rekursiven Aufrufe höchstens, da das Array mit mehr Elementen perfekt in zwei Hälften geteilt wird. Addieren wir die Kosten der binären Suche, erhalten wir diese Wiederholung als obere Schranke:

Die Lösung ist , was bedeutet, dass es auf einer idealen Maschine mit einer unbegrenzten Anzahl von Prozessoren so viel Zeit in Anspruch nimmt.

Hinweis: Die Routine ist nicht stabil : Wenn gleiche Elemente durch Aufteilen von A und B getrennt werden , werden sie in C verschachtelt ; auch das Vertauschen von A und B zerstört die Reihenfolge, wenn gleiche Elemente auf beide Eingabe-Arrays verteilt werden. Als Ergebnis erzeugt dieser Algorithmus, wenn er zum Sortieren verwendet wird, eine Sortierung, die nicht stabil ist.

Sprachunterstützung

Einige Computersprachen bieten integrierte oder Bibliotheksunterstützung für das Zusammenführen sortierter Sammlungen .

C++

Die C ++ ‚s Standard Template Library hat die Funktion std :: merge , die zwei Bereiche von sortiert verschmilzt Iteratoren und std :: inplace_merge , die zwei aufeinanderfolgende sortierten Bereiche fusioniert an Ort und Stelle . Darüber hinaus verfügt die Klasse std::list (verknüpfte Liste) über eine eigene Merge- Methode, die eine andere Liste in sich selbst einfügt. Der Typ der zusammengeführten Elemente muss den Kleiner-als- Operator ( < ) unterstützen oder mit einem benutzerdefinierten Komparator versehen sein.

C++17 ermöglicht unterschiedliche Ausführungsrichtlinien, nämlich sequenziell, parallel und parallel-nicht sequenziell.

Python

Die Standardbibliothek von Python (seit 2.6) hat auch eine Merge- Funktion im heapq- Modul, die mehrere sortierte Iterables nimmt und sie zu einem einzigen Iterator zusammenführt.

Siehe auch

Verweise

Weiterlesen

Externe Links