Verbessern der Leistung beim Durchsuchen einer großen Datei

10

Ich habe FILE_A mit über 300.000 Zeilen und FILE_B mit über 30 Millionen Zeilen. Ich habe ein Bash- Skript erstellt, das jede Zeile in FILE_A in FILE_B erfasst und das Ergebnis des grep in eine neue Datei schreibt.

Dieser gesamte Vorgang dauert über 5 Stunden.

Wie kann ich die Leistung meines Skripts verbessern?

Ich benutze grep -F -m 1als grep Befehl. FILE_A sieht folgendermaßen aus:

123456789 
123455321

und FILE_B ist wie folgt:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

Mit Bash habe ich also eine whileSchleife, die die nächste Zeile in FILE_A auswählt und in FILE_B übergreift. Wenn das Muster in FILE_B gefunden wird, schreibe ich es in die Datei result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile
rogerio_marcio
quelle

Antworten:

17

Versuchen Sie es mit grep --file==FILE_A. Es lädt die Muster mit ziemlicher Sicherheit in den Speicher, was bedeutet, dass FILE_B nur einmal gescannt wird.

grep -F -m1 --file==300KFile 30MFile
Gort den Roboter
quelle
Dies würde nur funktionieren, wenn ich genug Speicher habe, oder?
Rogerio_marcio
Ehrlich gesagt habe ich es nicht selbst an Dateien dieser Größe ausprobiert, aber ich glaube, es sollte Ihre Geschwindigkeit dramatisch verbessern. Wenn Sie sich auf einem modernen Computer befinden, sollten Sie keine Probleme haben, eine 300-KB-Datei im Speicher zu halten. (Oder eine 30M für diese Angelegenheit.)
Gort the Robot
Wenn ich die Option -f (--file) verwendet habe, wurde die 30MFile im Grunde neu erstellt. Mache ich etwas falsch?
Rogerio_marcio
Hmmm ... vielleicht hatte die 300K-Datei eine leere Zeile?
Gort den Roboter
direkt vor Ort! Das war's! das hat perfekt funktioniert, es war in 30 Sekunden fertig! Danke!!
Rogerio_marcio
2

Hier ist eine Perl- Antwort für die Nachwelt. Ich mache dies routinemäßig, um 1M-Leitungen mit 30-35M-Leitungen abzugleichen. Der Vorgang dauert ca. 10 Sekunden.

Hash zuerst FILE_A:

my %simple_hash;
open my $first_file, '<', 'FILE_A' or die "What have you done?! $!";
while (<$first_file>) {
  chomp;                 ## Watch out for Windows newlines
  $simple_hash{$_} = 1;  ## There may be an even faster way to define this
}
close $first_file;

Dann , wenn Ihre große Datei begrenzt ist , und weiß , was Spalte nach gehen, überprüfen Sie nur die Existenz der Raute - Taste , wie Sie unten FILE_B laufen, die viel, viel schneller als die Überprüfung auf Gleichheit oder reguläre Ausdrücke:

open my $second_file, '<', 'FILE_B' or die "Oh no, not again.. $!";
while (<$second_file>) {
  my ($col1, undef) = split ',';
  if (exists($simple_hash{$col1}) {
    print $_;
  }
}
close $second_file;

Wenn Ihre größere Zieldatei nicht gut analysiert werden kann, verliert dieses Skript seinen Wert, da ein Großteil seiner Geschwindigkeit darauf zurückzuführen ist, dass die Engine für reguläre Ausdrücke nicht gestartet werden muss.

Mintx
quelle
1

Wenn Ihnen die Programmierung nichts ausmacht, sollten Sie Suffixbäume (oder eine Variante) verwenden.

Sie können FILE_Bmit dem Ukkonen-Algorithmus in linearer Zeit vorverarbeiten . Anschließend fragen Sie jede Zeile FILE_Azeitlich linear in der Zeilenlänge ab und erhalten alle übereinstimmenden Zeilennummern (möglicherweise muss der Baum ein wenig angepasst werden), die Sie in eine Ergebnisdatei schreiben können.

Die gesamte Prozedur läuft in der Zeit O (n + Nm) ab, wenn n die Länge von FILE_B, Ndie Anzahl der Zeilen in FILE_Aund m die Länge der längsten Zeile in ist FILE_A- dies ist im Wesentlichen eine lineare Laufzeit. Schlägt die quadratische Zeit, die Ihr ursprünglicher Ansatz benötigt, um Größenordnungen.

Raphael
quelle
1

Ich habe die --mmapFlagge kürzlich gefunden, hatte keine Gelegenheit, sie zu testen, aber ich freue mich über Ihre Ergebnisse. Hier ist die Beschreibung von der Manpage:

--mmap If  possible, use the mmap(2) system call to read input, instead
      of the default read(2) system call.  In some situations,  --mmap
      yields  better performance.  However, --mmap can cause undefined
      behavior (including core dumps) if an input file  shrinks  while
      grep is operating, or if an I/O error occurs.

Siehe dies oder das für weitere Informationen über mmap.

Ramzi Kahil
quelle
Ich werde es auf jeden Fall versuchen und ich werde Sie wissen lassen, wie es geht. Wie wahrscheinlich ist es, dass ich auf einen Core Dump stoße?
Rogerio_marcio
@rogerio_marcio Nun, so wie ich den Mann verstehe, "wenn die Datei schrumpft, während grep ausgeführt wird, oder wenn ein E / A-Fehler auftritt." Nicht wirklich wahrscheinlich, aber Sie sollten das besser wissen. (Wenn, wie ich annehme, die Datei während grep unberührt bleibt - dies sollte nicht passieren)
Ramzi Kahil
Um zu testen, ob diese --mmapDosis nichts entleert, würde ich einen Lauf mit --mmapund einen ohne empfehlen . Und dann verwenden Sie, um wczu sehen, dass Sie die gleiche Menge an Ausgabe haben - dies sollte ein robuster Test sein, wenn man bedenkt, dass wir zweimal grep ausgeführt haben und nur ein Flag unterschiedlich war.
Ramzi Kahil
@rogerio_marcio Hast du das versucht? Irgendwelche Einsichten?
Ramzi Kahil
-1

Warum fügst du diese Datei nicht in eine Datenbank ein? Datenbanken sind wirklich gut darin, einen effizienten Merge-, Hash- oder Nested-Loop-Join wie diesen durchzuführen. Und sie sind wirklich gut darin, virtuellen Speicher zu nutzen

Andyz Smith
quelle
Alles, was Sie mit all den anderen Antworten tun, ist das Datenbankrad neu zu erfinden
Andyz Smith