Dies ist eine weitere Frage aus dem Coding-Interview, ich habe immer noch Zweifel, nachdem ich es gelesen habe.
%Vor%LÖSUNG
Wenn ein Interviewer eine Größenbeschränkung von 2 GB angibt, sollte er Ihnen etwas sagen - in diesem Fall schlägt er vor, dass Sie nicht möchten, dass Sie alle Daten in den Speicher bringen. Also, was machen wir? Wir bringen nur einen Teil der Daten in den Speicher. Algorithmus:
Wie viel Speicher haben wir zur Verfügung? Nehmen wir an, wir haben X MB Speicher zur Verfügung.
Teilen Sie die Datei in K-Blöcke, wobei X * K = 2 GB ist. Bringen Sie jeden Block in den Speicher und sortieren Sie die Zeilen wie gewohnt mit einem beliebigen O (n log n) -Algorithmus. Speichern Sie die Zeilen in der Datei.
Bringe nun den nächsten Chunk in den Speicher und sortiere ihn.
Wenn wir fertig sind, füge sie einzeln zusammen.
Der obige Algorithmus wird auch als externe Sortierung bezeichnet. Schritt 3 ist als N-Wege-Merge bekannt Der Grund für die Verwendung externer Sortierung ist die Größe der Daten. Da die Daten zu groß sind und wir nicht alles in den Speicher bringen können, müssen wir uns für einen diskettenbasierten Sortieralgorithmus entscheiden.
Zweifel:
Wenn wir in Schritt 3 die Merge-Sortierung durchführen und dabei zwei Arrays vergleichen, brauchen wir bei jedem Vergleich 2 * X-Platz. Und das Limit war X MB. Sollen wir die Brocken in (X / 2) * 2K = 2 GB machen? Damit wird jeder Chunk X / 2 MB und es werden 2K Chunks sein. Oder ich verstehe nur, dass die Zusammenführung falsch ist? Danke!
Zunächst ist Schritt 3 selbst keine Merge-Sortierung, das ganze Ding ist eine Merge-Sortierung. Schritt 3 ist nur eine Zusammenführung, überhaupt keine Sortierung.
Und was die Speicherung betrifft, gibt es zwei Möglichkeiten.
Die erste besteht darin, die sortierten Daten in Zweiergruppen zusammenzuführen. Angenommen, Sie haben drei Gruppen:
%Vor% Bei dieser Methode würden Sie A und B in eine einzelne Gruppe Y zusammenführen und anschließend Y und C in das endgültige Ergebnis Z :
Dies hat den Vorteil einer sehr kleinen konstanten Speicheranforderung, da Sie immer nur das "nächste" Element aus jeder der beiden Listen speichern müssen, aber natürlich müssen Sie mehrere Zusammenführungsoperationen durchführen.
Der zweite Weg ist eine "richtige" N-Wege-Zusammenführung, bei der Sie das nächste Element aus any der Gruppen auswählen. Damit würden Sie den niedrigsten Wert in jeder Liste überprüfen, um zu sehen, welcher als nächstes kommt:
%Vor%Dies beinhaltet nur eine Zusammenführungsoperation, aber es erfordert mehr Speicher, im Grunde ein Element pro Liste.
Welche davon Sie auswählen, hängt vom verfügbaren Speicher und der Elementgröße ab.
Wenn Ihnen beispielsweise 100M Speicher zur Verfügung steht und die Elementgröße 100K beträgt, können Sie letztere verwenden. Das liegt daran, dass Sie für eine 2G-Datei 20 Gruppen (jeweils 100M) für die Sortierphase benötigen, was bedeutet, dass eine ordnungsgemäße N-Wege-Zusammenführung 100K mal 20 oder etwa 2M benötigt, also weit unter Ihrer Speicherverfügbarkeit.
Alternativ können Sie sagen, dass Sie nur 1M zur Verfügung haben. Das wird ungefähr 2000 (2G / 1M) Gruppen sein und das multiplizieren mit 100K ergibt 200M, weit über Ihre Kapazität.
Sie müssten also in mehreren Durchgängen zusammenführen. Beachten Sie jedoch, dass es nicht mehrere Pässe sein müssen, die zwei Listen zusammenführen.
Sie könnten einen Mittelweg finden, wo zum Beispiel jeder Durchgang zehn Listen zusammenführt. Zehn Gruppen von 100 K sind nur ein Megaparameter, passen also in Ihre Speicherbeschränkung und das führt zu weniger Zusammenführungsdurchläufen.
Ein kurzer Blick auf Wikipedia sagt mir, dass Sie während des Merging-Prozesses niemals einen ganzen Block im Gedächtnis behalten. Also, wenn Sie K Chunks haben, haben Sie K open Dateizeiger, aber Sie werden nur eine Zeile aus jeder Datei im Speicher zu einem bestimmten Zeitpunkt halten. Sie werden die Zeilen, die Sie im Speicher haben, vergleichen und dann die kleinste (z. B. aus Chunk 5) an Ihre sortierte Datei (auch einen offenen Dateizeiger, nicht im Speicher) ausgeben und dann diese Zeile mit der nächsten Zeile aus dieser Datei überschreiben ( In unserem Beispiel, Datei 5) in den Speicher und wiederholen, bis Sie das Ende aller Chunks erreichen.
Der Zusammenführungsprozess ist viel einfacher als das. Sie geben sie in einer neuen Datei aus, aber im Grunde brauchen Sie nur Konstanten Speicher: Sie müssen nur jeweils ein Element aus jeder der beiden Eingabedateien lesen.