Grep eine große Anzahl von Mustern aus einer großen Datei

18

Ich habe eine Datei, die ungefähr 200.000 Zeilen pro Tag umfasst und die aus Blöcken mit drei Zeilen besteht:

1358726575123       # key
    Joseph Muller   # name
    carpenter       # job
9973834728345
    Andres Smith
    student
7836472098652
    Mariah Anthony
    dentist

Jetzt habe ich eine andere Datei, aus der ich ungefähr 10.000 Schlüsselmuster extrahiere, wie z 1358726575123. Dann führe ich eine forSchleife mit diesen Mustern durch und muss sie mit der ersten Datei vergleichen. Wenn die Datei kein solches Muster enthält, speichere ich das Muster zur weiteren Verarbeitung in einer dritten Datei:

for number in $(grep -o '[0-9]\{12\}' file2); do  # finds about 10.000 keys
     if ! grep -q ^$number$ file1; then           # file1 is a huge file
         printf "$number\n" >>file3               # we'll process file3 later
     fi
done

Der Beispielcode greift 10.000 Mal nach einer riesigen Datei, und ich führe diese Schleife den ganzen Tag über etwa einmal pro Minute aus .

Was kann ich tun, um all das zu beschleunigen und CPU zu sparen, da die riesige Datei immer größer wird? Ich frage mich, ob es hilfreich ist, die Datei irgendwie nach ihrem Schlüssel zu sortieren (wenn ja, wie?) Oder eine Datenbank anstelle von einfachem Text zu verwenden ...

Teresa und Junior
quelle

Antworten:

11

Diese Antwort basiert auf der awkAntwort von potong .
Sie ist doppelt so schnell wie die commMethode (auf meinem System), für die gleichen 6 Millionen Zeilen in der Hauptdatei und 10 Tausend Schlüssel ... (jetzt aktualisiert, um FNR zu verwenden, NR)

Obwohl awkes schneller ist als Ihr aktuelles System und Ihnen und Ihren Computern eine gewisse Atempause einräumt, sollten Sie sich bewusst sein, dass Sie bei einer so intensiven Datenverarbeitung wie beschrieben die besten Gesamtergebnisse erzielen, wenn Sie zu einer dedizierten Datenbank wechseln. z.B. SQlite, MySQL ...


awk '{ if (/^[^0-9]/) { next }              # Skip lines which do not hold key values
       if (FNR==NR) { main[$0]=1 }          # Process keys from file "mainfile"
       else if (main[$0]==0) { keys[$0]=1 } # Process keys from file "keys"
     } END { for(key in keys) print key }' \
       "mainfile" "keys" >"keys.not-in-main"

# For 6 million lines in "mainfile" and 10 thousand keys in "keys"

# The awk  method
# time:
#   real    0m14.495s
#   user    0m14.457s
#   sys     0m0.044s

# The comm  method
# time:
#   real    0m27.976s
#   user    0m28.046s
#   sys     0m0.104s

Peter.O
quelle
Das geht schnell, aber ich verstehe nicht viel von awk: Wie sollten die Dateinamen aussehen? Ich habe versucht file1 -> mainfileund file2 -> keysmit gawk und mawk, und es gibt falsche Schlüssel aus.
Teresa e Junior
file1 hat Schlüssel, Namen und Jobs.
Teresa e Junior
'mainfile' ist die große Datei (mit Schlüsseln, Namen und Jobs). Ich habe es gerade "mainfile" genannt, weil ich immer wieder verwechselt habe, welche Datei welche war (file1 vs file2). "Keys" enthält nur die zehntausend oder wie viele Schlüssel. Für Ihre Situation leiten Sie nichts weiter. .. benutze einfach file1 EOF file2 Das sind die Namen deiner Dateien .. "EOF" ist eine 1-zeilige Datei, die vom Skript erstellt wird, um das Ende der ersten Datei (Hauptdatendatei) und den Anfang der zweiten Datei ( können awkSie eine Reihe von Dateien einlesen. In diesem Fall enthält diese Reihe 3 Dateien. Die Ausgabe erfolgt anstdout
Peter.O
Dieses Skript wird alle Tasten drucken , die in sind mainfile, und es wird auch keine Schlüssel aus der keysDruckdatei , die ist nicht in mainfile... Das ist wahrscheinlich das, was passiert ist ... (Ich werde ein bisschen weiter schauen hinein ...
Peter.O
Vielen Dank, @ Peter.O! Da die Dateien vertraulich sind, versuche ich, Beispieldateien $RANDOMzum Hochladen zu erstellen .
Teresa e Junior
16

Das Problem ist natürlich, dass Sie grep 10.000 Mal auf der großen Datei ausführen. Sie sollten beide Dateien nur einmal lesen. Wenn Sie außerhalb der Skriptsprachen bleiben möchten, können Sie dies folgendermaßen tun:

  1. Extrahieren Sie alle Zahlen aus Datei 1 und sortieren Sie sie
  2. Extrahieren Sie alle Zahlen aus Datei 2 und sortieren Sie sie
  3. Führen Sie commdie sortierten Listen aus, um zu ermitteln, was nur auf der zweiten Liste steht

Etwas wie das:

$ grep -o '^[0-9]\{12\}$' file1 | sort -u -o file1.sorted
$ grep -o  '[0-9]\{12\}'  file2 | sort -u -o file2.sorted
$ comm -13 file1.sorted file2.sorted > file3

Sehen man comm.

Wenn Sie die große Datei jeden Tag kürzen könnten (wie eine Protokolldatei), könnten Sie einen Cache mit sortierten Zahlen führen und müssten sie nicht jedes Mal vollständig analysieren.

angus
quelle
1
Ordentlich! 2 Sekunden (auf nicht besonders schnellen Laufwerken) mit 200.000 zufälligen Zeileneinträgen in der Hauptdatei (dh 600.000 Zeilen) und 143.000 zufälligen Schlüsseln (so endeten meine Testdaten) ... getestet, und es funktioniert (aber Sie wussten, dass: ) ... Ich frage mich über die {12}.. OP hat 12 verwendet, aber die Beispielschlüssel sind 13 lang ...
Peter.O
2
Nur eine kleine Anmerkung, Sie können dies tun, ohne sich mit temporären Dateien zu befassen, indem Sie <(grep...sort)die Dateinamen angeben.
Kevin
Vielen Dank, aber das Greifen und Sortieren der Dateien dauert viel länger als in meiner vorherigen Schleife (+2 Min.).
Teresa e Junior
@ Teresa e Junior. Wie groß ist deine Hauptdatei? ... Sie haben erwähnt, dass es mit 200.000 Zeilen pro Tag wächst, aber nicht wie groß es ist ... Um die zu verarbeitende Datenmenge zu verringern, können Sie nur die 200.000 Zeilen des aktuellen Tages lesen, indem Sie sich eine Notiz machen Die letzte verarbeitete Zeilennummer (gestern), mit tail -n +$linenumder nur die neuesten Daten ausgegeben werden. Auf diese Weise werden Sie nur ungefähr 200.000 Zeilen pro Tag verarbeiten. Ich habe es gerade mit 6 Millionen Zeilen in der Hauptdatei und 10.000 Schlüsseln getestet. Zeit : real 0m0.016s, user 0m0.008s, sys 0m0.008s
Peter.O
Ich bin wirklich ziemlich verwirrt / neugierig, wie Sie Ihre Hauptdatei 10.000 Mal durchsuchen und schneller finden können als diese Methode, die sie nur einmal (und einmal für die viel kleinere Datei1 ) durchsucht ... Auch wenn Ihre Sortierung länger dauert als meine Test, ich kann einfach nicht
verstehen,
8

Ja, auf jeden Fall eine Datenbank verwenden. Sie sind genau für solche Aufgaben gemacht.

Mika Fischer
quelle
Vielen Dank! Ich habe nicht viel Erfahrung mit Datenbanken. Welche Datenbank empfehlen Sie? Ich habe MySQL und den Befehl sqlite3 installiert.
Teresa e Junior
1
Sie sind beide in Ordnung, SQLite ist einfacher, weil es im Grunde nur eine Datei und eine SQL-API ist, um darauf zuzugreifen. Bei MySQL müssen Sie einen MySQL-Server einrichten, um ihn verwenden zu können. Auch wenn das nicht sehr schwierig ist, ist SQLite vielleicht der beste Einstieg.
Mika Fischer
3

Das könnte für Sie funktionieren:

 awk '/^[0-9]/{a[$0]++}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

BEARBEITEN:

Geändertes Skript, um Duplikate und unbekannte Schlüssel in beiden Dateien zuzulassen, erzeugt weiterhin Schlüssel aus der ersten Datei, die in der zweiten nicht vorhanden sind:

 awk '/^[0-9]/{if(FNR==NR){a[$0]=1;next};if($0 in a){a[$0]=2}}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3
Potong
quelle
Dadurch werden neue Schlüssel übersehen, die in der Hauptdatei mehrmals vorkommen (und in der Schlüsseldatei auch mehrmals). Es scheint erforderlich zu sein, dass die Erhöhung der Arrayanzahl in der Hauptdatei 1 nicht überschreitet. oder eine gleichwertige Problemumgehung (+1, weil es ziemlich nah an der Marke ist)
Peter.O
1
Ich habe es mit gawk und mawk versucht, und es gibt falsche Schlüssel aus ...
Teresa e Junior
@ Peter.OI nahm an, dass die Hauptdatei eindeutige Schlüssel hatte und dass Datei 2 eine Teilmenge der Hauptdatei war.
Potong
@potong Der zweite funktioniert gut und sehr schnell! Vielen Dank!
Teresa e Junior
@ Teresa e Junior Sind Sie sicher, dass es noch richtig funktioniert? .. Unter Verwendung der von Ihnen angegebenen Testdaten , die 5000 Schlüssel ausgeben sollten , werden beim Ausführen 136703 Schlüssel erzeugt , so wie ich sie erhalten habe, bis ich endlich verstanden habe, was Ihre Anforderungen waren ... @potong Natürlich! FNR == NR (Ich habe es noch nie benutzt :)
Peter.O
2

Mit so vielen Daten sollten Sie wirklich zu einer Datenbank wechseln. In der Zwischenzeit müssen Sie nicht file1für jeden Schlüssel einzeln suchen, um eine annähernd anständige Leistung zu erzielen . Führen Sie einen einzelnen aus grep, um alle nicht ausgeschlossenen Schlüssel auf einmal zu extrahieren. Da dies grepauch Zeilen zurückgibt, die keinen Schlüssel enthalten, filtern Sie diese weg.

grep -o '[0-9]\{12\}' file2 |
grep -Fxv -f - file1 |
grep -vx '[0-9]\{12\}' >file3

( -Fxbedeutet wörtlich, ganze Zeilen zu durchsuchen. -f -bedeutet, eine Liste von Mustern aus der Standardeingabe zu lesen.)

Gilles 'SO - hör auf böse zu sein'
quelle
Wenn ich mich nicht irre, wird das Problem des Speicherns von Schlüsseln, die nicht in der großen Datei enthalten sind, nicht behoben, sondern die darin enthaltenen Schlüssel werden gespeichert.
Kevin
@ Kevin genau, und das hat mich gezwungen, die Schleife zu verwenden.
Teresa e Junior
@TeresaeJunior: das Hinzufügen von -v( -Fxv) kann sich darum kümmern.
Bis auf weiteres angehalten.
@DennisWilliamson Das würde alle Zeilen in der großen Datei auswählen, die nicht in der Schlüsseldatei übereinstimmen, einschließlich Namen, Jobs usw.
Kevin
@ Kevin Danke, ich würde die Frage falsch verstehen. Ich habe einen Filter für Nicht-Tasten-Zeilen hinzugefügt, obwohl ich jetzt die Verwendungcomm bevorzuge .
Gilles 'SO- hör auf böse zu sein'
2

Gestatten Sie mir, das zu bekräftigen, was andere gesagt haben: "Bring dich in eine Datenbank!"

Es gibt MySQL-Binärdateien, die für die meisten Plattformen frei verfügbar sind.

Warum nicht SQLite? Es ist speicherbasiert und lädt eine Flat-Datei, wenn Sie sie starten, und schließt sie, wenn Sie fertig sind. Dies bedeutet, dass wenn Ihr Computer abstürzt oder der SQLite-Prozess nicht mehr ausgeführt wird, auch alle Daten.

Ihr Problem sieht aus wie ein paar Zeilen SQL und wird in Millisekunden ausgeführt!

Nach der Installation von MySQL (was ich vor anderen Optionen empfehle) würde ich 40 US-Dollar für O'Reillys SQL-Kochbuch von Anthony Molinaro ausgeben, das viele Problemmuster aufweist, angefangen bei einfachen SELECT * FROM tableAbfragen bis hin zu Aggregaten und mehreren Verknüpfungen.

Jan Steinman
quelle
Ja, ich fange in ein paar Tagen an, meine Daten auf SQL zu migrieren. Danke! Die awk-Skripte haben mir sehr geholfen, bis ich alles erledigt habe!
Teresa e Junior
1

Ich bin mir nicht sicher, ob dies die genaue Ausgabe ist, nach der Sie suchen, aber der wahrscheinlich einfachste Weg ist:

grep -o '[0-9]\{12\}' file2 | sed 's/.*/^&$/' > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Sie könnten auch verwenden:

sed -ne '/.*\([0-9]\{12\}.*/^\1$/p' file2 > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Jede dieser Dateien erstellt eine temporäre Musterdatei, mit der die Zahlen aus der großen Datei ( file1) abgerufen werden .

Arcege
quelle
Ich glaube, das findet auch Zahlen, die in der großen Datei sind, nicht diejenigen, die nicht sind.
Kevin
Richtig, ich habe das '!' Nicht gesehen im OP. Müssen nur grep -vfanstelle von verwenden grep -f.
Arcege
2
Nein @arcege, grep -vf zeigt keine nicht übereinstimmenden Schlüssel an, sondern zeigt alles an, einschließlich Namen und Jobs.
Teresa e Junior
1

Ich bin völlig damit einverstanden, dass Sie eine Datenbank erhalten (MySQL ist ziemlich einfach zu bedienen). Bis Sie das zum Laufen bringen, mag ich Angus ' commLösung, aber so viele Leute versuchen es grepund verstehen es falsch, dass ich dachte, ich zeige den (oder zumindest einen) richtigen Weg, um es zu tun grep.

grep -o '[0-9]\{12\}' keyfile | grep -v -f <(grep -o '^[0-9]\{12\}' bigfile) 

Der erste grepbekommt die Schlüssel. Der dritte grep(in <(...)) nimmt alle in der großen Datei verwendeten Schlüssel und <(...)übergibt sie wie eine Datei als Argument an -fden zweiten grep. Das führt dazu, dass die zweite grepZeile sie als Liste der übereinstimmenden Zeilen verwendet. Anschließend wird dies verwendet, um die Eingabe (die Liste der Schlüssel) aus der Pipe abzugleichen (zuerst grep) und alle Schlüssel zu drucken, die aus der Schlüsseldatei und nicht aus -vder großen Datei extrahiert wurden .

Natürlich können Sie dies mit temporären Dateien tun, die Sie im Auge behalten und nicht vergessen müssen, zu löschen:

grep -o '[0-9]\{12\}'  keyfile >allkeys
grep -o '^[0-9]\{12\}' bigfile >usedkeys
grep -v -f usedkeys allkeys

Hiermit werden alle Zeilen gedruckt, in allkeysdenen nicht angezeigt wird usedkeys.

Kevin
quelle
Leider ist es langsam und ich erhalte nach 40 Sekunden einen Speicherfehler:grep: Memory exhausted
Peter.O
@ Peter.O Aber es ist richtig. Aus diesem Grund würde ich eine Datenbank vorschlagen oder comm, in dieser Reihenfolge.
Kevin
Ja das funktioniert, ist aber viel langsamer als die Schleife.
Teresa e Junior
1

Die Schlüsseldatei ändert sich nicht? Dann sollten Sie es vermeiden, die alten Einträge immer wieder zu durchsuchen.

Mit tail -fkönnen Sie die Ausgabe einer wachsenden Datei erhalten.

tail -f growingfile | grep -f keyfile 

grep -f liest die Muster aus einer Datei, eine Zeile als Muster.

Benutzer unbekannt
quelle
Das wäre gut, aber die Schlüsseldatei ist immer anders.
Teresa e Junior
1

Ich wollte meine Antwort nicht veröffentlichen, da ich der Meinung war, dass eine solche Datenmenge nicht mit einem Shell-Skript verarbeitet werden sollte und die richtige Antwort für die Verwendung einer Datenbank bereits gegeben wurde. Aber seitdem gibt es 7 andere Ansätze ...

Liest die erste Datei im Speicher, durchsucht dann die zweite Datei nach Zahlen und prüft, ob Werte im Speicher gespeichert sind. Es sollte schneller als ein Vielfaches von greps sein, wenn Sie genug Speicher haben, um die gesamte Datei zu laden.

declare -a record
while read key
do
    read name
    read job
    record[$key]="$name:$job"
done < file1

for number in $(grep -o '[0-9]\{12\}' file2)
do
    [[ -n ${mylist[$number]} ]] || echo $number >> file3
done
forcefsck
quelle
Ich habe genug Gedächtnis, aber ich fand dieses noch langsamer. Trotzdem danke!
Teresa e Junior
1

Ich stimme @ jan-steinman zu, dass Sie für diese Art von Aufgabe eine Datenbank verwenden sollten. Wie die anderen Antworten zeigen, gibt es viele Möglichkeiten, eine Lösung mit einem Shell-Skript zu hacken. Wenn Sie den Code jedoch länger als 15 Minuten verwenden und warten, kann dies zu erheblichen Problemen führen nur ein eintägiges wegwerfprojekt.

Angenommen, Sie arbeiten auf einer Linux-Box, dann ist höchstwahrscheinlich standardmäßig Python installiert, das die sqlite3-Bibliothek ab Python v2.5 enthält. Sie können Ihre Python-Version überprüfen mit:

% python -V
Python 2.7.2+

Ich empfehle die Verwendung von SQLite3-Bibliothek da es sich um eine einfache dateibasierte Lösung handelt, die für alle Plattformen (einschließlich Ihres Webbrowsers) verfügbar ist und keine Installation eines Servers erfordert. Im Wesentlichen konfigurations- und wartungsfrei.

Im Folgenden finden Sie ein einfaches Python-Skript, das das von Ihnen als Beispiel angegebene Dateiformat analysiert und anschließend eine einfache Abfrage "Alles auswählen" durchführt und alles ausgibt, was in der Datenbank gespeichert ist.

#!/usr/bin/env python

import sqlite3
import sys

dbname = '/tmp/simple.db'
filename = '/tmp/input.txt'
with sqlite3.connect(dbname) as conn:
    conn.execute('''create table if not exists people (key integer primary key, name text, job text)''')
    with open(filename) as f:
        for key in f:
            key = key.strip()
            name = f.next().strip()
            job = f.next().strip()
            try:
                conn.execute('''insert into people values (?,?,?)''', (key, name, job))
            except sqlite3.IntegrityError:
                sys.stderr.write('record already exists: %s, %s, %s\n' % (key, name, job))
    cur = conn.cursor()

    # get all people
    cur.execute('''select * from people''')
    for row in cur:
        print row

    # get just two specific people
    person_list = [1358726575123, 9973834728345]
    cur.execute('''select * from people where key in (?,?)''', person_list)
    for row in cur:
        print row

    # a more general way to get however many people are in the list
    person_list = [1358726575123, 9973834728345]
    template = ','.join(['?'] * len(person_list))
    cur.execute('''select * from people where key in (%s)''' % (template), person_list)
    for row in cur:
        print row

Ja, dies bedeutet, dass Sie etwas SQL lernen müssen , aber es wird sich auf lange Sicht lohnen. Anstatt Ihre Protokolldateien zu analysieren, können Sie auch Daten direkt in Ihre SQLite-Datenbank schreiben.

aculich
quelle
Vielen Dank für das Python-Skript! Ich denke, /usr/bin/sqlite3funktioniert genauso für Shell-Skripte ( packages.debian.org/squeeze/sqlite3 ), obwohl ich es nie benutzt habe.
Teresa e Junior
Ja, Sie können /usr/bin/sqlite3Shell-Skripte verwenden. Ich empfehle jedoch, Shell-Skripte zu vermeiden, außer für einfache Wegwerfprogramme. Verwenden Sie stattdessen eine Sprache wie Python, die eine bessere Fehlerbehandlung aufweist und einfacher zu warten und zu erweitern ist.
ACULICH