Wie greife ich direkt und effizient auf sehr große Textdateien zu?

Lesezeit: 5 Minuten

Ich habe sehr große Textdateien (+10 GB), die ich für einige Data-Mining-Techniken lesen möchte. Dazu verwende ich parallele Techniken mit MPI, so dass viele Prozesse gemeinsam auf dieselbe Datei zugreifen können.
Tatsächlich möchte ich, dass jeder Prozess N Zeilen liest. Da die Datei nicht strukturiert ist (gleiche Anzahl von Feldern, aber jedes Feld kann eine unterschiedliche Anzahl von Zeichen enthalten), bin ich verpflichtet, die Datei zu parsen, und das ist nicht parallel und es kostet viel Zeit. Gibt es eine Möglichkeit, direkt auf eine bestimmte Anzahl von Zeilen zuzugreifen, ohne die Zeilen zu analysieren und zu zählen? Danke für deine Hilfe.

Wenn Ihre Datei nicht anderweitig indiziert ist, gibt es keinen direkten Weg.

Es könnte sich lohnen, es zu indizieren (scannen Sie es einmal, um alle Zeilenenden zu finden, und speichern Sie die Offsets jeder Zeile oder jedes Zeilenblocks). Wenn Sie die Datei mehrmals verarbeiten müssen und sie sich nicht ändert, können die Kosten für die Indizierung durch die einfache Verwendung des Indexes für weitere Läufe ausgeglichen werden.

Ansonsten, wenn man nicht alle Jobs haben muss exakt die gleiche Anzahl von Zeilen / Elementen, Sie könnten es einfach verfälschen.
Suchen Sie nach einem bestimmten Offset (z. B. 1 G) und suchen Sie nach dem nächstgelegenen Zeilentrenner. Wiederholen Sie bei Offset 2G usw., bis Sie genügend Unterbrechungspunkte gefunden haben.

Sie können dann Ihre parallelen Aufgaben auf jedem der von Ihnen identifizierten Chunks abfeuern.

  • Danke für Ihre Antwort. Ich denke, dass die zweite Idee besser ist, da ich die Datei normalerweise pünktlich parse. In Anbetracht dieser Lösung werde ich also jeden Prozesszugriff von einem bestimmten Offset aus vornehmen, sagen wir (File_size/process_number *process_rank), dann suche ich nach dem Anfang einer neuen Zeile. Also würde ich bei schlechteren number_of_process Zeilen verlieren?

    – ezakrem

    30. April 2012 um 9:01 Uhr

  • +1 Das einmalige Scannen, um Zeilenumbrüche zu finden, und das Übergeben der Indizes an andere Prozesse ist allem anderen absolut vorzuziehen, da jede zufällige Suche um mehrere Größenordnungen teurer ist als alles, was Sie durch die Parallelisierung der Analyse einiger Felder pro Zeile in a kaufen können Textdatei. Sequentielles Lesen und Pullen aus dem Buffer-Cache geht schnell, alles andere macht jede Optimierung zunichte.

    – Dämon

    30. April 2012 um 9:01 Uhr

  • fseek sucht völlig blind. Es bewegt den Dateizeiger um die angegebene Anzahl von Bytes, das ist alles. Ob dies genau eine konstante Zeit ist oder nicht, könnte von den Implementierungsdetails des Dateisystems abhängen, aber angesichts Ihres Szenarios spielt das keine Rolle – die Suche erfolgt “sofort”. (Es sei denn, Ihre Datei befindet sich auf einem mechanischen Bandlaufwerk …)

    – Matte

    30. April 2012 um 9:15 Uhr

  • Beachten Sie, dass Sie, wenn die Lösung zufällige Suchen beinhaltet, die Datei im Binärmodus öffnen müssen (und eine plattformabhängige Definition des Zeilenabschlusszeichens verwenden müssen). Wenn die Datei im Textmodus geöffnet wird, sind die einzigen zulässigen Suchvorgänge vorne, hinten oder an einer Position, die von zurückgegeben wird tell.

    – James Kanze

    30. April 2012 um 9:52 Uhr

  • Sie könnten die Datei speicherzuordnen und das Betriebssystem/FS den besten Caching- und Suchansatz für die Verwendung ermitteln lassen (vorausgesetzt, dass dies im Betriebssystem/FS optimiert ist).

    – edA-qa mort-ora-y

    30. April 2012 um 12:09 Uhr

Benutzer-Avatar
Kein_ein_Golfer

Einige andere Optionen, die über das hinausgehen, was hier erwähnt wurde, bei denen nicht die gesamte Datei gescannt werden muss:

  1. Erstellen Sie einen Master-Prozess, der Leitungen über Pipes/Fifos an untergeordnete Prozesse weiterleitet, die die eigentliche Verarbeitung durchführen. Dies könnte etwas langsamer sein, aber wenn beispielsweise 90% der Zeit, die in den Unterprozessen verbracht wird, auf das eigentliche Knirschen von Texten entfällt, sollte es in Ordnung sein.

  2. Ein dummer, aber effektiver Trick: Angenommen, Sie haben N Prozesse, und Sie können jedem Prozess durch argv oder etwas sagen, dass es sich um eine “Seriennummer” handelt, z processor -serial_number [1|2|3...N] -num_procs Nsie können alle dieselben Daten lesen, aber nur Zeilen verarbeiten, die dies haben lineno % num_procs == serial_number. es ist ein bisschen weniger effizient, weil sie alle die gesamten Daten lesen, aber wenn sie nur in jeder N-ten Zeile arbeiten, und das ist es, was die meiste Zeit verbraucht, sollte es Ihnen gut gehen.

  • +1 für alternatives Denken. Manchmal ist der beste Weg, um zu gewinnen, die Regeln zu ändern.

    – Matthias M.

    30. April 2012 um 9:35 Uhr

Nein, gibt es nicht: Bis Sie Ihre unbekannten Daten nicht durchgelesen haben, wird niemand wissen, wie viele neue Zeilenzeichen es gibt. Diese Problemkomplexität ist O (n), was bedeutet, dass zumindest einmal Sie müssen die gesamte Datei lesen. Dann möchten Sie vielleicht eine Indextabelle erstellen, in der Sie aufzeichnen, wo in Ihrer Datei neue Zeilenzeichen sind: Dies kann von allen Prozessen verwendet werden, und mit fseek können Sie den weiteren Zugriff erheblich beschleunigen.

  • danke für die Antwort, scheint eine gute Lösung zu sein. Ich werde das tun und sehen, ob es sich lohnt, da ich im seriellen Modus eine der Dateien lese und dann für jede Zeile viele CPU-Berechnungen durchführe. Bisher habe ich zwei Lösungen: Ich parse die Datei, um eine Indexdatei zu erstellen, dann können alle Prozesse sie verwenden. Oder ich lasse einen Prozess aus der Datei lesen und andere Prozesse berechnen.

    – ezakrem

    30. April 2012 um 8:55 Uhr

  • Mit O(n) bezog ich mich auf diese Notation: en.wikipedia.org/wiki/Time_complexity#Linear_time Übrigens kann die Indexierung sehr einfach parallel ausgeführt werden. Wenn Sie mehrere Prozesse haben, können Sie die Datei aufteilen auch zum Indexieren, sagen wir also, der 1. Prozess liest das 1. GB, der 2. das 2. usw. und alle speichern die Positionen der Zeilenumbruchzeichen in derselben gemeinsam genutzten Ressource. Dies kann auch die Indizierung beschleunigen. Vergessen Sie jedoch nicht, dass das sequentielle Lesen je nach verwendeter Speicherhardware VIEL schneller sein kann.

    – Herr TJ

    30. April 2012 um 9:03 Uhr

  • Es geht also darum, zwei Schritte zu mischen. 1- Machen Sie N Prozesse, um Indizes zu erhalten, wie Sie sagten. 2- Für CPU-Computing greift jeder Prozess direkt mit fseek() auf den spezifischen Offset zu. Das sieht zum Ausprobieren gut aus. Vielen Dank

    – ezakrem

    30. April 2012 um 9:28 Uhr

1246010cookie-checkWie greife ich direkt und effizient auf sehr große Textdateien zu?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy