mische eine große Liste von Elementen, ohne sie in den Speicher zu laden

Wenn Sie 16 GB Speicher für dieses Programm reservieren können, habe ich ein Programm namens sample geschrieben, das die Zeilen von eine Datei, indem sie ihre Byte-Offsets einliest, die Offsets mischt und dann die Ausgabe druckt, indem sie durch die Datei zu den gemischten Offsets sucht. Es verwendet 8 Bytes für jeden 64-Bit-Offset, also 16 GB für eine Zwei-Milliarden-Zeilen-Eingabe.

Es wird nicht schnell gehen, aber auf einem System mit genügend Speicher wird sample Dateien mischen, die groß genug sind, um GNU shuf zum Scheitern zu bringen. Darüber hinaus verwendet es mmap Routinen, um zu versuchen, die I / O-Kosten eines zweiten Durchlaufs durch Ihre Datei zu minimieren. Es hat auch ein paar andere Optionen; Weitere Informationen finden Sie in --help .

Dieses Programm wird standardmäßig ohne Ersetzen und Mischen nach einzelnen Zeilen getestet. Wenn Sie mit dem Ersetzen mischen möchten oder Ihre Eingabe in FASTA, FASTQ oder einem anderen mehrzeiligen Format erfolgt, können Sie einige Optionen hinzufügen, um die Art und Weise der Probennahme anzupassen. (Oder Sie können einen alternativen Ansatz anwenden, auf den ich in einer Perl-Liste unten verlinke, aber sample adressiert diese Fälle.)

Wenn sich Ihre FASTA-Sequenzen alle zwei Zeilen befinden, das heißt, sie wechseln zwischen dem Sequenzkopf in einer Zeile und Sequenzdaten in der nächsten Zeile, können Sie immer noch mit sample und mit der Hälfte des Speichers mischen, da Sie nur sind Mischen die Hälfte der Anzahl der Offsets. Siehe die Option --lines-per-offset ; Sie würden zum Beispiel 2 angeben, um Zeilenpaare zu mischen.

Im Falle von FASTQ-Dateien werden ihre Datensätze alle vier Zeilen aufgeteilt. Sie können --lines-per-offset=4 angeben, um eine FASTQ-Datei mit einem Viertel des Speichers zu mischen, der zum Mischen einer einzeiligen Datei benötigt wird.

Alternativ dazu habe ich ein hier , das in Perl geschrieben ist und Sequenzen ohne Ersetzung aus einer FASTA-Datei ohne Rücksicht auf Beispiele abtastet für die Anzahl der Zeilen in einer Sequenz. Beachten Sie, dass dies nicht genau dasselbe ist wie das Mischen einer ganzen Datei, aber Sie können dies als Ausgangspunkt verwenden, da es die Offsets sammelt. Anstatt einige der Offsets abzutasten, entfernen Sie Zeile 47, die gemischte Indizes sortiert. Verwenden Sie dann Dateisuchvorgänge, um die Datei zu durchsuchen, indem Sie die Liste mit den gemischten Indizes direkt verwenden.

Auch hier wird es nicht schnell gehen, weil Sie durch eine sehr große Datei springen, aber das Speichern von Offsets ist viel billiger als das Speichern ganzer Zeilen und das Hinzufügen von mmap-Routinen könnte ein wenig helfen, was im Wesentlichen ein ist Reihe von Operationen mit wahlfreiem Zugriff. Und wenn Sie mit FASTA arbeiten, müssen Sie immer noch weniger Offsets speichern. Daher sollte Ihre Speicherauslastung (mit Ausnahme eines relativ unbedeutenden Container- und Programm-Overheads) maximal 8 GB betragen - und wahrscheinlich weniger, je nach Struktur.

Wie wäre es mit:

Diese Lösung sollte nur alle Dateioffsets der Zeilen in der Datei speichern, also zwei Wörter pro Zeile plus Container-Overhead.

Sie können mein HugeFileProcessor -Tool überprüfen. Es ist ähnlich wie @ Alex-Reynolds sample , sollte aber deutlich schneller sein, da es keine Suche geben würde.

Hier finden Sie die Details zur Shuffle-Implementierung. Es erfordert die Angabe von batchSize - Anzahl der Zeilen, die beim Schreiben in die Ausgabe im RAM verbleiben sollen. Je mehr, desto besser (es sei denn, Sie haben keinen Arbeitsspeicher mehr), da die gesamte Mischzeit (Anzahl der Zeilen in sourceFile) / batchSize * (Zeit zum vollständigen Lesen von sourceFile) wäre . Bitte beachten Sie, dass das Programm ganze Datei mischt und nicht pro Batch.

Der Algorithmus ist wie folgt.

1. Zählt Zeilen in sourceFile . Dies geschieht einfach, indem die ganze Datei Zeile für Zeile gelesen wird. (Siehe einige Vergleiche hier .) Dies gibt auch ein Maß dafür, wie viel Zeit würde es dauern, ganze Datei einmal zu lesen. So könnten wir abschätzen, wie oft ein vollständiger Shuffle gemacht werden würde, weil es Ceil (linesCount / batchSize) vollständige Dateilesevorgänge erfordern würde.

2. Da wir nun den gesamten ZeilenCount kennen, können wir ein Index-Array mit der Größe linesCount erstellen und es mit Fisher-Yates (im Code orderArray genannt). Dies würde uns eine Reihenfolge geben, in der wir Zeilen in einer gemischten Datei haben möchten. Beachten Sie, dass dies eine globale Reihenfolge über die gesamte Datei ist, nicht pro Batch oder Chunk oder so.

3. Jetzt der eigentliche Code. Wir müssen alle Zeilen von sourceFile in einer Reihenfolge abrufen, die wir gerade berechnet haben, aber wir können nicht ganze Dateien im Speicher lesen. Also haben wir die Aufgabe geteilt.

   • Wir würden durch die sourceFile gehen, die alle Zeilen liest und im Speicher nur die Zeilen speichert, die sich in der ersten batchSize des orderArray befinden. Wenn wir alle diese Zeilen erhalten, können wir sie in der erforderlichen Reihenfolge in outFile schreiben, und es ist ein batchSize / Zeilenanzahl der ausgeführten Arbeit.
   • Als nächstes würden wir den ganzen Prozess immer wieder wiederholen, indem wir die nächsten Teile von orderArray nehmen und sourceFile für jeden Teil von Anfang bis Ende lesen. Schließlich wird das ganze orderArray verarbeitet und wir sind fertig.

Warum funktioniert das?

Weil wir nur die Quelldatei von Anfang bis Ende lesen. Nein sucht vorwärts / rückwärts, und das ist was HDDs mögen. Die Datei wird entsprechend den internen HDD-Puffern, FS-Blöcken, CPU-Cahce usw. in Blöcken gelesen und alles wird sequentiell gelesen.

Einige Zahlen

Auf meinem Rechner (Core i5, 16GB RAM, Win8.1, HDD Toshiba DT01ACA200 2 TB, NTFS) konnte ich mit batchSize von 3 500 000. Mit batchSize von 2 000 000 hat es ungefähr 8 Stunden gedauert. Lesegeschwindigkeit betrug rund 118000 Zeilen pro Sekunde.