grep alternativa -f per enormi file

Question

grep -F -f file1 file2 

file1 è di 90 Mb (2,5 milioni di linee, una parola per riga)

file2 è di 45 Gb

che il comando non effettivamente produrre qualsiasi cosa, senza importa per quanto tempo lo lascio correre. Chiaramente, questo è oltre l'ambito di grep.

Sembra che grep non possa gestire molte query dall'opzione -f. Tuttavia, il seguente comando fa produrre il risultato desiderato:

head file1 > file3 
grep -F -f file3 file2 

ho dubbi sul fatto che sed o awk sarebbe alternative appropriate sia, date le dimensioni dei file.

Sono in perdita per le alternative ... per favore aiuto. Vale la pena imparare alcuni comandi sql? È facile? Qualcuno può indicarmi la giusta direzione?

Answer 1

Non penso che ci sia una soluzione facile.

Immagina di scrivere il tuo programma che fa quello che vuoi e finirai con un ciclo annidato, in cui il ciclo esterno scorre le righe in file2 e il ciclo interno scorre su file1 (o viceversa). Il numero di iterazioni cresce con size(file1) * size(file2). Questo sarà un numero molto grande quando entrambi i file sono grandi. Rendere più piccolo un file usando head risolve questo problema, al costo di non dare più il risultato corretto.

Una possibile via d'uscita è l'indicizzazione (o l'ordinamento) di uno dei file. Se si esegue l'iterazione su file2 e per ogni parola, è possibile determinare se è presente nel file di pattern senza che deve attraversare completamente il file di pattern, quindi si sta molto meglio. Questo presuppone che tu faccia un confronto parola per parola. Se il file di pattern contiene non solo parole complete, ma anche sottostringhe, questo non funzionerà, perché per una determinata parola in file2 non si saprebbe cosa cercare in file1.

L'apprendimento di SQL è certamente una buona idea, perché imparare qualcosa è sempre buono. Tuttavia, non risolverà il tuo problema, perché SQL soffrirà dello stesso effetto quadratico descritto sopra. Può semplificare l'indicizzazione, dovrebbe essere l'indicizzazione applicabile al tuo problema.

La tua migliore scommessa è probabilmente fare un passo indietro e ripensare al tuo problema.

Answer 2

Si può provare ack. Dicono che è più veloce di grep.

Si può provare parallel:

parallel --progress -a file1 'grep -F {} file2' 

parallelo ha molte altre opzioni utili per rendere i calcoli più velocemente.

Answer 3

Provare a utilizzare LC_ALL = C. Gira il pattern di ricerca da UTF-8 a ASCII che accelera di 140 volte la velocità originale. Ho un file 26G che mi richiederebbe circa 12 ore per arrivare a un paio di minuti. Fonte: Grepping a huge file (80GB) any way to speed it up?

Quindi quello che faccio è:

LC_ALL=C fgrep "pattern" <input >output 

Answer 4

Grep non può gestire che molte domande, e in quel volume, non sarà aiutato dal fissa il grep -f bug che lo rende così insopportabilmente lento.

Sia file1 sia file2 sono composti da una parola per riga? Ciò significa che siete alla ricerca di corrispondenze esatte, che possiamo facciamo molto velocemente con awk:

awk 'NR == FNR { query[$0] = 1; next } query[$0]' file1 file2 

NR (numero di record, il numero di riga) è pari solo al FNR (numero specifico di file record) per il primo file, dove compiliamo l'hash e quindi passiamo alla riga successiva. La seconda clausola controlla l'altro file (s) per se la riga corrisponde a uno salvato nel nostro hash e quindi stampa le linee corrispondenti.

In caso contrario, sarà necessario iterare:

awk 'NR == FNR { query[$0]=1; next } 
    { for (q in query) if (index($0, q)) { print; next } }' file1 file2 

Invece di limitarsi a controllare l'hash, dobbiamo ciclo attraverso ogni query e vedere se corrisponde la riga corrente ($0). Questo è molto più lento di, ma sfortunatamente necessario (anche se stiamo almeno corrispondendo alle semplici stringhe senza usare espressioni regolari, quindi potrebbe essere più lento). Il ciclo si interrompe quando abbiamo una corrispondenza.

Se si desidera effettivamente valutare le righe del file di query come espressioni regolari, è possibile utilizzare $0 ~ q anziché il più veloce index($0, q). Si noti che questo utilizza POSIX extended regular expressions, più o meno lo stesso di grep -E o egrep ma senza bounded quantifiers ({1,7}) o GNU extensions per word boundaries (\b) e shorthand character classes (\s, \w, ecc).

Questi dovrebbero funzionare finché l'hash non supera quello che può essere memorizzato awk. Questo potrebbe essere basso come 2.1B voci (un'ipotesi basata sul più alto firmato a 32 bit int) o alto come la memoria libera.