Ich suche nach einem Algorithmus, um mehrere sortierte Sequenzen, sagen wir X-sortierte Sequenzen mit n Elementen, in eine sortierte Sequenz in c ++ zusammenzufassen, können Sie einige Beispiele liefern?
Hinweis: Ich möchte keine Bibliothek verwenden
Es gibt drei Methoden zum Zusammenführen: -
Angenommen, Sie führen m lists mit n elements each
Algorithmus 1: -
Zusammenführen listet zwei gleichzeitig auf. Verwenden Sie merge sort wie merge routine zum Zusammenführen, wenn die Listen sortiert sind. Dies ist sehr einfach ohne Bibliotheken zu implementieren. Aber braucht Zeit O(m^2*n) , was klein genug ist, wenn m nicht groß ist.
Algorithmus 2: -
Dies ist eine Verbesserung gegenüber 1. wo wir immer Liste zusammenführen, die die kleinsten zwei in der verbleibenden Liste sind. Verwenden Sie dazu priority queue , wählen Sie die Liste mit den kleinsten zwei Werten aus, fügen Sie sie zusammen und fügen Sie der Warteschlange eine neue Liste hinzu. Tun Sie dies, bis nur noch eine Liste übrig ist, die Ihre Antwort wäre. Diese Technik wird in huffman coding verwendet und ergibt optimal merge pattern . Dies dauert O(m*n*logm) . Darüber hinaus kann für Listen ähnlicher Größe parallel verwendet werden, da wir ein Listenpaar auswählen und parallel zusammenführen können. Angenommen, Sie haben m processors , dann kann der Algorithmus idealerweise in O(n*logm) statt in O(m*n*logm)
Algorithmus 3: -
Dies ist der effizienteste Algorithmus, bei dem Sie ein priority queue für die ersten Elemente aller Listen beibehalten und min extrahieren, um ein neues Element zu erhalten, sowie den Index der Liste, zu der min Element gehört, damit Sie das nächste Element aus dieser Liste hinzufügen können. Dies nimmt O(s*logm) , wobei s die Summe der Elemente in allen Listen ist.
Die folgende Methode funktioniert mit jedem Container wie Array, Vektor, Liste usw. Ich gehe davon aus, dass wir mit Listen arbeiten.
Nehmen wir an, wir haben m sortierte Listen, die wir zusammenführen wollen.
Lassen Sie n die Gesamtzahl der Elemente in allen Listen angeben.
Das erste Element in der resultierenden Liste muss das kleinste Element in der Menge aller Listenköpfe sein.
Die Idee ist ziemlich einfach. Wählen Sie einfach den kleinsten Kopf und verschieben Sie ihn von der ursprünglichen Liste zum Ergebnis. Sie möchten diese Routine wiederholen, solange mindestens eine nicht leere Liste vorhanden ist. Entscheidend ist hier, den kleinsten Kopf schnell auszuwählen.
Ein linearer Scan durch die Köpfe ist O(m) , was zu O(m * n) Gesamtzeit führt, was in Ordnung ist, wenn m eine kleine Konstante ist.
Dann können wir es besser machen, indem wir eine Prioritätswarteschlange verwenden, zum Beispiel einen Heap . Die Invariante hier ist, dass das kleinste Element im Heap immer das kleinste Element aktueller Köpfe ist.
Das minimale Element ist ein Heap ist O(1) , das Minimum ist O(log m) wenn es m Elemente im Heap gibt, und das Einfügen eines Elements in den Heap ist auch O(log m) .
Zusammenfassend fügen wir für jedes n -Element es einmal in den Heap ein und löschen es von dort auch einmal. Die Gesamtkomplexität mit einem Heap ist O(n log m) , was wesentlich schneller ist als O(n * m) , wenn m keine kleine Konstante ist.
Welche Methode schneller ist, hängt davon ab, wie viele Listen wir zusammenführen möchten. Wenn m klein ist, wählen Sie den linearen Scan , im anderen Fall implementieren Sie ihn mit einer Prioritätswarteschlange . Manchmal ist es schwierig zu beurteilen, ob m klein ist oder nicht und in diesem Fall sind einige Experimente hilfreich.
Ich nehme an, dass ohne Bibliotheken die Fusion . Andernfalls müssen Sie eine eigene verknüpfte Liste erstellen (dies kann vorwärts sein oder normale Liste ). Ruhe gleich. Einfaches Beispiel (für zwei Listen):
%Vor%Ergebnis:
1 2 3 4 5 6 7 8 9 9 10
Achtung! Sie müssen mit dem Flag -std = C ++ 11 (oder anders zu C ++ 11) kompilieren. Zum Beispiel:
g ++ -std = c ++ 11 -Wand -pedantisch -Wextra -O2 d.cpp -o programm.out
Die Komplexität: Θ (n)
Speicher: Θ (n)
Es ist nicht schwer zu sehen, dass jedes Element genau einmal in O (1) ausgewertet wird, wir haben n Elemente, also Θ (n) . p>
Speicherkomplexität ist offensichtlich. Es ist erwähnenswert, dass, wenn die zwei Listen nicht mehr benötigt werden, kann es ohne zusätzliche Zuweisungen (const Speicher) gemacht werden.
Der Algorithmus selbst wurde so oft beschrieben , dass es nicht mehr sinnvoll ist, noch einmal zu schreiben.
Im Hauptproblem haben wir viele Sequenzen, aber die Idee ist die gleiche. Hier haben Sie beispielsweise angereichert:
%Vor%Die Komplexität: Θ (n log k)
Speicher: Θ (n)
Pop- und Insert-Operationen sind in O (log k) , wir führen sie n mal durch, also ist es O (n log k) .
Speicher ist immer noch offensichtlich, wir haben immer k Elemente in priority_queue und O (n) in out-Sequenz.
Der Code dafür könnte einem Zeiger- und zählungsbasierten Mischsortieren ähneln, indem ein "Quell" -Array aus Zeigern und Zählern für jede Sequenz erstellt wird und ein zweites "Ziel" -Array zugewiesen wird, um das "Quell" -Array zusammenzuführen von Zeigern und zählt in. Jeder Durchlauf dieses Algorithmus führt Paare von Zeigern und Zählern basierend auf den Sequenzen von dem "Quellen" -Array in das "Ziel" -Array zusammen, wodurch die Anzahl von Einträgen in dem Array um ungefähr 1/2 reduziert wird. Dann werden Zeiger auf die "Quell" - und "Ziel" -Arrays vertauscht, und der Zusammenführungsprozess wird wiederholt, bis ein Array von Zeigern und Zählern nur einen einzelnen Eintrag aufweist.