Gegeben 100 GB Integer-Daten auf der Festplatte mit einem RAM von 2 GB, wie man die Integer mit minimaler Festplattenoperation sortiert. Hier wird das Abrufen einer Nummer von der Festplatte als eine Diskoperation betrachtet (obwohl in Wirklichkeit ein Datenblock abgerufen werden kann).
Wir können zusätzlichen Speicherplatz auf der Festplatte für temporäre Speicherung verwenden und müssen die Vorgänge zum Bereinigen temporärer Speicher nicht berücksichtigen.
Wie andere Leute bemerkt haben, können Sie eine O (n) Zählsortierung verwenden. Es gibt jedoch einige zusätzliche Probleme, die Sie berücksichtigen müssen. Wir nehmen an, dass Sie 32-Bit-Ganzzahlen speichern, also 100 GB ~ 279 Zoll.
Wenn alle Ganzzahlen gleich sind, dann wird es ~ 27e9 mal vorkommen, was größer ist als ein 32 Bit int. Daher müssen Ihre Zähler 64-Bit-Ganzzahlen sein.
Mit 2 GB RAM können Sie nur ~ 125e6-Zähler im RAM gleichzeitig speichern. Wenn wir keine Annahmen über die Verteilung von ganzen Zahlen machen können, müssten wir entweder:
Ich denke, die letztere Option ist besser. Da wir ~ 4e9 64-Bit-Zähler benötigen und nur 2GB speichern können, müssten wir ~ 16 mal durch das gesamte Array laufen. Die erste Option ist eindeutig nicht gut, wenn wir eine Folge von ganzen Zahlen wie 0,1 & lt; & lt; 31,0 betrachten. Diese Zähler werden nicht gleichzeitig im RAM gespeichert, und daher sind mindestens 2 HD-Schreibvorgänge erforderlich.
Aus diesem Grund denke ich für die spezifische Größe Ihres Problems (100 GB), eine N-Wege-Zusammenführung zu sortieren wäre besser, da dies nur das Lesen des gesamten Arrays log_2 (100) ~ 8 mal erfordern würde.
Wenn jedoch der Interviewer die Frage sofort in "10 TB Array, noch 2 GB RAM" änderte, würde die zählende Sortierung leicht gewinnen.
Da die zu sortierenden Daten vom Integer-Typ sind (4 Byte) und die Datenmenge 100 GB beträgt (wobei GB 2 ^ 30 ist), müssten Sie 26.843.545.600 Ganzzahlen sortieren. Da Sie 4.294.967.296 mögliche Integer-Werte haben, können Sie diese Daten als ein Array von Longs darstellen, die als Zähler dienen und etwa 34 GB Speicherplatz belegen. Lesen Sie die 100-GB-Daten einmal durch, erhöhen Sie die einzelnen Zähler für jeden möglichen ganzzahligen Wert (300 GB Gesamt-Festplattenzugriff, um den Wert zu lesen, lesen Sie den Zähler, schreiben Sie den inkrementierten Zähler), lesen Sie die Zähler der Reihe nach und schreiben Sie die Nummer der Werte, die Sie von jedem Wert lesen (134 GB Festplattenzugriff).
Dies würde die Daten mit insgesamt 434 GB Festplattenzugriff sortieren. Wenn Sie RAM verwenden, um einen Teil des Bereichs der Zähler für ganzzahlige Werte zu speichern, können Sie den Umfang des Festplattenzugriffs sogar noch weiter verringern.
Für mich hängt die Antwort auf diese Frage entscheidend von der erwarteten Verteilung der Zahlen in der Datei ab.
Es gibt 12,5 Milliarden Ints in 100 Gigs int-Daten. Es gibt auch nur ~ 4,3 Milliarden verschiedene Ints.
Bei einer vollkommen gleichmäßigen Verteilung über alle möglichen Ints würden Sie erwarten, dass jeder Int etwa 3 Mal nachgibt oder nimmt. Diese geringe Anzahl von Duplizierungen ist kein Garant für die Änderung einer Standardsortierroutine (eine, die Blöcke gleichzeitig sortiert und dann die Blöcke zusammenfügt).
Wenn wir jedoch die "file ints" auf alle nichtnegativ beschränken, erwarten wir sofort, dass jedes gültige int etwa sechsmal erscheint. Dies nähert sich einem Grad an Duplizierung, der eine Änderung der Sortierroutine rechtfertigen könnte. Also, ich denke, Sie sollten den Interviewer fragen, ob noch mehr über die Verbreitung von Ints auf der Festplatte zu erwarten ist. Schließlich wäre es komisch, 100 GB Daten zu haben und keine Ahnung zu haben, ob es vorhersagbare Muster aufweist.
Ich denke, dass für einen schnellen Algorithmus weitere 100 GB freier Festplattenspeicher Voraussetzung sind.
Benutze einfach jede Art von 2GB Chunks und lege sie zurück. Jetzt haben Sie 50 sortierte Stücke in der Akte, und Sie können die Zusammenführungssortierung benutzen, wie von Mihir auf ihnen vorgeschlagen. Schreiben Sie den Ausgabepuffer, während er die Ausgabedatei ausfüllt. Sie müssen nur die Eingabe- und Ausgabepuffergrößen feineinstellen.
Es gibt einige Lösungen mit dem Zählen. Es kann nicht auf so große Reichweite und maximal mögliche Anzahl verwendet werden. Sie können QWORD-Zähler nur auf der Festplatte speichern, aber das bedeutet viele zufällige Zugriffe, die sicherlich langsamer sind als die Arbeit mit größeren Puffern.
100 GB Ganzzahldaten bedeuten, dass Sie eine große Anzahl von doppelten Daten haben. Ich würde persönlich einen (Bucketsort / Auswahl) / Mergesort-Ansatz als meinen ersten Instinkt wählen, wenn ich versuche, Festplatten-I / O zu minimieren.
Lesen Sie zuerst ein Bit unter 1 Gig von Daten in Speicher, mergesort diese Daten im Speicher. Auf Festplatte spülen. Wiederholen Sie dies für jeden Speicherbereich. Dann können Sie jeden Datenblock laufen lassen und alle Nullen aufnehmen, für jede ganze Zahl wiederholen. Es wird eine lange Zeit dauern, aber das ist nur 203GB Read und 200GB write worst case (theoretisch).
Merge Sort ist ein beliebter Ansatz, wenn es um begrenzten Speicher geht
Tags und Links algorithm