Grep ogromną liczbę wzorów z ogromnego pliku


18

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 ...


Odpowiedzi:


11

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


Jest to szybkie, ale nie rozumiem wiele z awk: jak powinny wyglądać nazwy plików? Próbowałem file1 -> mainfilei file2 -> keysz gawk i mawk i wyprowadza błędnych kluczy.
Teresa e Junior

plik1 ma klucze, nazwy i zadania.
Teresa e Junior

„plik główny” to duży plik (z kluczami, nazwami i zadaniami). Właśnie nazwałem go „plikiem głównym”, ponieważ ciągle się myliłem, który plik był który (plik1 vs. plik2) .. „klucze” zawierają tylko 10 tysięcy kluczy, ale jakkolwiek wiele kluczy. Dla twojej sytuacji NIE przekierowuj niczego. .. po prostu użyj file1 plik EOF2 Są to nazwy twoich plików .. „EOF” to 1-liniowa kreacja pliku skryptu wskazująca koniec pierwszego pliku (główny plik danych) i początek drugiego pliku ( klucze). awkpozwalają na odczytanie szeregu plików .. W tym przypadku ta seria zawiera 3. Pliki wyjściowe trafiają dostdout
Peter.O

Ten skrypt będzie drukować żadnych kluczy, które są obecne w mainfile, I będzie to również wydrukować żadnych kluczy z keyspliku, które są nie w mainfile... To jest chyba to, co się dzieje ... (będę patrzeć nieco dalej do niego ...
Peter.O

Dziękuję, Peter.O! Ponieważ pliki są poufne, próbuję utworzyć przykładowe pliki $RANDOMdo przesłania.
Teresa e Junior

16

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.


1
Schludny! 2 sekundy (na niezbyt szybkich dyskach) z 200 000 losowymi wpisami w pliku głównym (tj. 600 000 wierszy) i 143 000 losowymi kluczami (tak właśnie skończyły moje dane testowe) ... przetestowałem i działa (ale wiesz, że: ) ... Zastanawiam się nad {12}... OP użył 12, ale przykładowe klucze mają 13 długości ...
Peter.O

2
Tylko mała uwaga, możesz to zrobić bez zajmowania się plikami tymczasowymi, używając <(grep...sort)nazw plików.
Kevin

Dziękuję, ale grepowanie i sortowanie plików trwa znacznie dłużej niż moja poprzednia pętla (+ 2 min.).
Teresa e Junior

@Teresa e Junior. Jak duży jest twój główny plik? ... Wspomniałeś, że rośnie on przy 200 000 linii dziennie, ale nie jest tak duży ... Aby zmniejszyć ilość danych, które musisz przetworzyć, możesz odczytać 200 000 linii z obecnych dni, notując ostatni przetworzony numer linii (wczoraj) i używany tail -n +$linenumdo wyświetlania tylko najnowszych danych. W ten sposób będziesz przetwarzał tylko około 200 000 linii każdego dnia. Właśnie przetestowałem go z 6 milionami linii w pliku głównym i 10 tysiącami kluczy ... czas : prawdziwe 0m0.016s, użytkownik 0m0.008s, sys 0m0.008s
Peter.O

Jestem naprawdę bardzo zdziwiony / ciekawy, jak możesz grepować swój główny plik 10 000 razy i znaleźć go szybciej niż ta metoda, która gretuje go tylko raz (i raz dla znacznie mniejszego pliku1 ) ... Nawet jeśli sortowanie trwa dłużej niż mój test, po prostu nie mogę przestać myśleć o tym, że czytanie dużego pliku, który wiele razy nie przeważa nad jednym rodzajem (czasowo)
Peter.O

8

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


Dzięki! Nie mam dużego doświadczenia z bazami danych. Którą bazę danych polecasz? Mam zainstalowany MySQL i polecenie sqlite3.
Teresa e Junior

1
Oba są w porządku, sqlite jest prostszy, ponieważ jest to po prostu plik i interfejs API SQL, aby uzyskać do niego dostęp. W MySQL musisz skonfigurować serwer MySQL, aby z niego korzystać. Chociaż nie jest to również bardzo trudne, najlepiej zacząć od sqlite.
Mika Fischer

3

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

Spowoduje to pominięcie nowych kluczy, które występują więcej niż jeden raz w głównym pliku (i w tym przypadku, które występują więcej niż jeden raz w pliku kluczy). Wydaje się, że wymaga to, aby przyrost liczby tablic w głównym pliku nie przekraczał 1, lub inne równoważne obejście (+1, ponieważ jest bardzo blisko znaku)
Peter.O

1
Próbowałem z gawk i mawk, i to wyprowadza złe klucze ...
Teresa e Junior

@ Peter.OI założył, że główny plik ma unikalne klucze, a ten plik 2 był podzbiorem głównego pliku.
potong

@potong Drugi działa dobrze i bardzo szybko! Dziękuję Ci!
Teresa e Junior

@Teresa e Junior Czy na pewno działa poprawnie? Podane dane testowe , które powinny wygenerować 5000 kluczy, kiedy je uruchamiam, dają 136703 kluczy, tak jak ja, dopóki nie zrozumiałem, jakie były twoje wymagania ... @potong Oczywiście! FNR == NR (nigdy wcześniej go nie używałem :)
Peter.O

2

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).


O ile się nie mylę, nie rozwiązuje to problemu przechowywania kluczy, których nie ma w dużym pliku, ale przechowuje klucze, które się w nim znajdują.
Kevin

@Kevin dokładnie, a to zmusiło mnie do użycia pętli.
Teresa e Junior

@TeresaeJunior: add -v( -Fxv) może się tym zająć.
Wstrzymano do odwołania.

@DennisWilliamson To wybrałoby wszystkie wiersze w dużym pliku, które nie pasują do żadnego z pliku klucza, w tym nazwiska, zadania itp.
Kevin

@Kevin Dzięki, źle odczytałem pytanie. Dodałem filtr do wierszy niekluczowych, chociaż teraz wolę używaćcomm .
Gilles 'SO - przestań być zły'

2

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

Pliki binarne MySQLswobodnie 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ń.


Tak, zacznę migrować moje dane do SQL za kilka dni, dziękuję! Jednak skrypty awk bardzo mi pomagały, dopóki tego nie zrobię!
Teresa e Junior

1

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).


Uważam, że to też znajduje liczby, które są w dużym pliku, a nie te, których nie ma.
Kevin

Zgadza się, nie widziałem „!” w PO. Wystarczy użyć grep -vfzamiast grep -f.
Arcege

2
Bez @arcege, grep -vf nie wyświetli niepasujących kluczy, wyświetli wszystko, łącznie z nazwami i zadaniami.
Teresa e Junior

1

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.


Niestety jest wolny i po 40 sekundach grep: Memory exhausted
pojawia się

@ Peter.O Ale to prawda. W każdym razie dlatego zaproponowałbym bazę danych lub commw tej kolejności.
Kevin

Tak, to działa, ale jest znacznie wolniejsze niż pętla.
Teresa e Junior

1

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.


Byłoby dobrze, ale plik klucza jest zawsze inny.
Teresa e Junior

1

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

Mam dość pamięci, ale znalazłem ją jeszcze wolniej. W każdym razie dzięki!
Teresa e Junior

1

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.


Dziękujemy za skrypt w języku Python! Myślę, że /usr/bin/sqlite3działa w ten sam sposób dla skryptów powłoki ( packages.debian.org/squeeze/sqlite3 ), chociaż nigdy go nie używałem.
Teresa e Junior

Tak, możesz używać /usr/bin/sqlite3ze skryptami powłoki, jednak zalecam unikanie skryptów powłoki z wyjątkiem prostych programów służących do wyrzucania i zamiast tego używaj języka takiego jak python, który ma lepszą obsługę błędów i jest łatwiejszy w utrzymaniu i rozwoju.
aculich
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.