Grep ogromną liczbę wzorów z ogromnego pliku

Mam plik, który rośnie około 200 000 wierszy dziennie, i wszystko składa się z bloków po trzy linie jako takie:

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

Teraz mam inny plik, z którego wyodrębniam około 10 000 wzorców kluczy, takich jak 1358726575123. Następnie uruchamiam forpętlę z tymi wzorami i muszę je porównać z pierwszym plikiem. Jeśli plik nie zawiera takiego wzorca, zapisuję go w trzecim pliku do dalszego przetwarzania:

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

Przykładowy kod przechwytuje ogromny plik 10 000 razy, a tę pętlę uruchamiam mniej więcej raz na minutę, przez cały dzień .

Ponieważ ogromny plik wciąż rośnie, co mogę zrobić, aby to wszystko przyspieszyć i zaoszczędzić trochę procesora? Zastanawiam się, czy posortowanie pliku według klucza (jeśli tak, to w jaki sposób?) Czy użycie db zamiast zwykłego tekstu pomogłoby ...

Ta odpowiedź oparta jest na awkodpowiedzi wysłanej przez potong .
Jest dwa razy szybsza niż commmetoda (w moim systemie), dla tych samych 6 milionów linii w głównym pliku i 10 tysięcy kluczy ... (teraz zaktualizowano, by używało FNR, NR)

Chociaż awkjest szybszy niż twój obecny system i da tobie i twojemu komputerowi trochę przestrzeni do oddychania, pamiętaj, że gdy przetwarzanie danych jest tak intensywne, jak opisano, uzyskasz najlepsze ogólne wyniki, przechodząc do dedykowanej bazy danych; na przykład. 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

Problem polega oczywiście na tym, że uruchamiasz grep na dużym pliku 10 000 razy. Oba pliki powinieneś przeczytać tylko raz. Jeśli chcesz pozostać poza językami skryptowymi, możesz to zrobić w ten sposób:

1. Wyodrębnij wszystkie liczby z pliku 1 i posortuj je
2. Wyodrębnij wszystkie liczby z pliku 2 i posortuj je
3. Uruchom commna posortowanych listach, aby uzyskać to, co jest tylko na drugiej liście

Coś takiego:

$ 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

Zobaczyć man comm.

Jeśli możesz obcinać duży plik każdego dnia (np. Plik dziennika), możesz przechowywać pamięć podręczną posortowanych liczb i nie musisz za każdym razem analizować go w całości.

Tak, zdecydowanie skorzystaj z bazy danych. Są wykonane dokładnie do takich zadań.

To może Ci pomóc:

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

EDYTOWAĆ:

Zmieniony skrypt pozwalający na duplikaty i nieznane klucze w obu plikach, nadal wytwarza klucze z pierwszego pliku nieobecnego w drugim:

 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

Przy tak dużej ilości danych naprawdę powinieneś przełączyć się na bazę danych. W międzyczasie jedyną rzeczą, którą musisz zrobić, aby zbliżyć się do przyzwoitej wydajności, jest nie szukać file1osobno dla każdego klucza. Uruchom pojedynczy, grepaby wyodrębnić wszystkie niewykluczone klucze naraz. Ponieważ to greprównież zwraca wiersze, które nie zawierają klucza, odfiltruj je.

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

( -Fxoznacza przeszukiwanie całych linii, dosłownie. -f -oznacza odczytanie listy wzorców ze standardowego wejścia).

Pozwól mi wzmocnić to, co powiedzieli inni: „Zabierz cię do bazy danych!”

Pliki binarne MySQL są swobodnie dostępne dla większości platform.

Dlaczego nie SQLite? Opiera się na pamięci, ładuje płaski plik po uruchomieniu, a następnie zamyka po zakończeniu. Oznacza to, że jeśli komputer ulegnie awarii lub proces SQLite zniknie, wszystkie dane również.

Twój problem wygląda jak tylko kilka wierszy SQL i będzie działał w milisekundach!

Po zainstalowaniu MySQL (które zalecam w porównaniu z innymi opcjami) wydałbym 40 USD na książkę kucharską SQL O'Reilly autorstwa Anthony'ego Molinaro, która ma wiele wzorców problemów, zaczynając od prostych SELECT * FROM tablezapytań, przechodząc przez agregacje i wiele sprzężeń.

Nie jestem pewien, czy jest to dokładnie to, czego szukasz, ale prawdopodobnie najłatwiejszym sposobem jest:

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

Możesz także użyć:

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

Każdy z nich tworzy tymczasowy plik sygnatur, który służy do zbierania liczb z dużego pliku ( file1).

W pełni zgadzam się z twoją bazą danych (MySQL jest dość łatwy w użyciu). Dopóki tego nie uruchomisz, podoba mi się commrozwiązanie Angusa , ale tak wielu ludzi próbuje grepi robi to źle, że myślałem, że pokażę (lub przynajmniej jeden) właściwy sposób, aby to zrobić grep.

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

Pierwszy grepdostaje klucze. Trzeci grep(w <(...)) pobiera wszystkie klucze użyte w dużym pliku, a <(...)przekazuje go jak plik jako argument -fw drugim grep. To powoduje, że drugi grepużywa go jako listy pasujących linii. Następnie używa go do dopasowania danych wejściowych (listy kluczy) z potoku (najpierw grep) i drukuje wszystkie klucze wyodrębnione z pliku kluczy, a nie ( -v) duży plik.

Oczywiście możesz to zrobić z plikami tymczasowymi, które musisz śledzić i pamiętać o usunięciu:

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

Spowoduje to wydrukowanie wszystkich linii allkeys, które się nie pojawiają usedkeys.

Plik klucza się nie zmienia? Następnie powinieneś unikać ciągłego przeszukiwania starych wpisów.

Dzięki tail -fmożesz uzyskać wynik rosnącego pliku.

tail -f growingfile | grep -f keyfile 

grep -f odczytuje wzorce z pliku, jedna linia jako wzorzec.

Nie zamierzałem publikować mojej odpowiedzi, ponieważ uważałem, że taka ilość danych nie powinna być przetwarzana za pomocą skryptu powłoki, a już podano prawidłową odpowiedź na użycie bazy danych. Ale od teraz istnieje 7 innych podejść ...

Odczytuje pierwszy plik z pamięci, następnie greps drugi plik dla liczb i sprawdza, czy wartości są przechowywane w pamięci. Powinno to być szybsze niż wiele greps, jeśli masz wystarczającą ilość pamięci, aby załadować cały plik, to znaczy.

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

Zgadzam się z @ jan-steinman , że powinieneś używać bazy danych do tego rodzaju zadań. Istnieje wiele sposobów na zhakowanie rozwiązania za pomocą skryptu powłoki, jak pokazują inne odpowiedzi, ale zrobienie tego w ten sposób doprowadzi do wielu nieszczęść, jeśli zamierzasz używać i utrzymywać kod przez dłuższy czas niż tylko jednodniowy projekt jednorazowy.

Zakładając, że korzystasz z Linuksa, najprawdopodobniej masz domyślnie zainstalowanego Pythona, który zawiera bibliotekę sqlite3 od Python v2.5. Możesz sprawdzić swoją wersję Pythona za pomocą:

% python -V
Python 2.7.2+

Polecam korzystanie z biblioteki sqlite3, ponieważ jest to proste rozwiązanie oparte na plikach, które istnieje na wszystkich platformach (w tym w przeglądarce internetowej!) I nie wymaga instalacji serwera. Zasadniczo zerowa konfiguracja i zerowa konserwacja.

Poniżej znajduje się prosty skrypt Pythona, który przeanalizuje format pliku podany jako przykład, a następnie wykona proste zapytanie „zaznacz wszystko” i wyświetli wszystko, co jest zapisane w bazie danych.

#!/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

Tak, oznacza to, że musisz nauczyć się trochę SQL , ale na dłuższą metę będzie to warte zachodu. Ponadto zamiast parsowania plików dziennika może być możliwe zapisanie danych bezpośrednio w bazie danych sqlite.