Il modo più veloce per trovare linee di un file da un altro file più grande in Bash

Ho due file, file1.txt e file2.txt . file1.txt ha circa 14K linee e file2.txt ha circa 2 miliardi. file1.txt ha un singolo campo f1 per riga mentre file2.txt ha 3 campi, da f1 a f3 , delimitato da | .

Voglio trovare tutte le linee da file2.txt dove f1 di file1.txt corrisponde a f2 di file2.txt (o in qualsiasi punto della linea se non vogliamo dedicare più tempo a suddividere i valori di file2.txt ).

file1.txt (circa 14K linee, non ordinate ):

 foo1 foo2 ... bar1 bar2 ... 

file2.txt (circa 2 miliardi di righe, non ordinato ):

 date1|foo1|number1 date2|foo2|number2 ... date1|bar1|number1 date2|bar2|number2 ... 

Uscita prevista:

 date1|foo1|number1 date2|foo2|number2 ... date1|bar1|number1 date2|bar2|number2 ... 

Ecco cosa ho provato e sembra che occorrano diverse ore per eseguire:

 fgrep -F -f file1.txt file2.txt > file.matched 

Mi chiedo se c’è un modo migliore e più veloce per fare questa operazione con i comuni comandi Unix o con un piccolo script.

Una soluzione Perl. [Vedi nota sotto.]

Usa un hash per il primo file. Mentre leggi il file grande riga per riga, estrai il campo per regex (cattura il primo pattern tra || ) o split (ottiene la seconda parola) e stampa se exists . Probabilmente differiscono in velocità un po ‘(tempo li). Il controllo defined non è necessario nella regex mentre per l’uso split // (definito-o) che cortocircuiti.

 use warnings; use strict; # If 'prog smallfile bigfile' is the preferred use die "Usage: $0 smallfile bigfile\n" if @ARGV != 2; my ($smallfile, $bigfile) = @ARGV; open my $fh, '<', $smallfile or die "Can't open $smallfile: $!"; my %word = map { chomp; $_ => 1 } <$fh>; open $fh, '<', $bigfile or die "Can't open $bigfile: $!"; while (<$fh>) { exists $word{ (/\|([^|]+)/)[0] } && print; # Or #exists $word{ (split /\|/)[1] // '' } && print; } close $fh; 

Evitare il ramo if e usare il cortocircuito è più veloce, ma solo molto poco. Su miliardi di righe queste modifiche si sumno, ma di nuovo non troppo. Potrebbe essere (o meno) un po ‘più veloce leggere il piccolo file riga per riga, invece che nel contesto lista come sopra, ma questo non dovrebbe essere evidente.

Aggiornare la scrittura su STDOUT consente di risparmiare due operazioni e più volte lo ritengo un po ‘più veloce rispetto alla scrittura su un file. Tale utilizzo è anche coerente con la maggior parte degli strumenti UNIX, quindi ho deciso di scrivere su STDOUT . Successivamente, il test exists non è necessario e l’operazione di sostituzione risparmia un’operazione. Tuttavia, ottengo costantemente un touch migliore con esso , mentre trasmette anche lo scopo meglio. Nel complesso lo lascio dentro. Grazie a ikegami per i commenti.

Nota La versione commentata è circa il 50% più veloce dell’altra, dal mio benchmark in basso. Questi sono entrambi dati perché sono diversi , uno trova la prima partita e l’altro il secondo campo. Lo terrò in questo modo come una scelta più generica, poiché la domanda è ambigua su questo.


Alcuni confronti (benchmark) [Aggiornato per scrivere su STDOUT , vedi “Aggiornamento” sopra]

Esiste un’analisi approfondita nella risposta di HåkonHægland , che prevede una serie di soluzioni. Ecco un altro fgrep , confrontando le due soluzioni precedenti, la risposta stessa dell’OP e quella fgrep pubblicata, che dovrebbe essere veloce e utilizzata nella domanda e in molte risposte.

Costruisco i dati del test nel modo seguente. Una manciata di righe della lunghezza approssimativamente come mostrato sono fatte con parole casuali, per entrambi i file, in modo da corrispondere nel secondo campo. Quindi copro questo “seme” per i campioni di dati con linee che non corrispondono, in modo da imitare i rapporti tra le dimensioni e le corrispondenze citate da OP: per le linee 14K in file di piccole dimensioni ci sono linee di 1.3M nel file grande, ottenendo 126.000 corrispondenze. Quindi questi esempi vengono scritti ripetutamente per creare file di dati completi come OP, shuffle ogni volta usando List :: Util .

Tutte le 106_120 comparate di seguito producono 106_120 corrispondenze per le dimensioni di file sopra indicate ( diff -ed per un controllo), quindi la frequenza di corrispondenza è abbastanza vicina. Sono benchmark chiamando programmi completi usando my $res = timethese(60 ...) . Il risultato di cmpthese($res) su v5.16 sono

         Valuta regex cfor split fgrep
 regex 1.05 / s - -23% -35% -44%
 cfor 1,36 / s 30% - -16% -28%
 diviso 1,62 / s 54% 19% - -14%
 fgrep 1,89 / s 80% 39% 17% -

Il fatto che il programma fgrep ottimizzato per il programma C non sia sorprendente. Il ritardo di ” regex ” dietro ” split ” può essere dovuto al sovraccarico di avvio del motore per le partite piccole, molte volte. Questo può variare rispetto alle versioni Perl, date le ottimizzazioni del motore regex in evoluzione. Includo la risposta @codeforester (” cfor “) poiché è stata dichiarata più veloce e il suo ritardo del 20% rispetto alla ” divisione ” molto simile è probabilmente dovuta a piccole inefficienze sparse (vedere un commento sotto questa risposta).

Ciò non è radicalmente diverso, mentre ci sono sicuramente variazioni tra hardware e software e dettagli sui dati. L’ho eseguito su diversi Perls e macchine, e la differenza degna di nota è che in alcuni casi fgrep era effettivamente un ordine di grandezza più veloce .

L’esperienza dell’OP di fgrep molto lento è sorprendente. Considerati i tempi di esecuzione quotati, l’ordine di grandezza più lento di quanto sopra, direi che c’è un vecchio sistema da “incolpare”.

Anche se questo è basato interamente sull’I / O, ci sono vantaggi concomitanti dal metterlo su più core e mi aspetto una buona accelerazione, fino ad un certo numero di pochi.

Ho provato a fare un confronto tra alcuni dei metodi presentati qui.

Per prima cosa ho creato uno script Perl per generare i file di input file1.txt e file2.txt . Al fine di confrontare alcune delle soluzioni, ho fatto in modo che le parole da file1.txt solo potessero apparire nel secondo campo in file2.txt . Anche per poter utilizzare la soluzione di join presentata da @GeorgeVasiliou, ho ordinato file1.txt e file2.txt . Attualmente ho generato i file di input sulla base di sole 75 parole casuali (prese da https://www.randomlists.com/random-words ). Solo 5 di queste 75 parole sono state utilizzate in file1.txt le rimanenti 70 parole sono state utilizzate per riempire i campi in file2.txt . Potrebbe essere necessario aumentare sostanzialmente il numero di parole per ottenere risultati realistici (in base all’OP, il file1.txt originale conteneva 14000 parole). Nei test seguenti ho usato un file2.txt con 1000000 (1 milione) linee. Lo script genera anche il file regexp1.txt richiesto dalla soluzione grep di @BOC.

gen_input_files.pl :

 #! /usr/bin/env perl use feature qw(say); use strict; use warnings; use Data::Printer; use Getopt::Long; GetOptions ("num_lines=i" => \my $nlines ) or die("Error in command line arguments\n"); # Generated random words from site: https://www.randomlists.com/random-words my $word_filename = 'words.txt'; # 75 random words my $num_match_words = 5; my $num_file2_lines = $nlines || 1_000_000; my $file2_words_per_line = 3; my $file2_match_field_no = 2; my $file1_filename = 'file1.txt'; my $file2_filename = 'file2.txt'; my $file1_regex_fn = 'regexp1.txt'; say "generating $num_file2_lines lines.."; my ( $words1, $words2 ) = get_words( $word_filename, $num_match_words ); write_file1( $file1_filename, $words2 ); write_file2( $file2_filename, $words1, $words2, $num_file2_lines, $file2_words_per_line, $file2_match_field_no ); write_BOC_regexp_file( $file1_regex_fn, $words2 ); sub write_BOC_regexp_file { my ( $fn, $words ) = @_; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh '\\|' . (join "|", @$words) . '\\|'; close $fh; } sub write_file2 { my ( $fn, $words1, $words2, $nlines, $words_per_line, $field_no ) = @_; my $nwords1 = scalar @$words1; my $nwords2 = scalar @$words2; my @lines; for (1..$nlines) { my @words_line; my $key; for (1..$words_per_line) { my $word; if ( $_ != $field_no ) { my $index = int (rand $nwords1); $word = @{ $words1 }[$index]; } else { my $index = int (rand($nwords1 + $nwords2) ); if ( $index < $nwords2 ) { $word = @{ $words2 }[$index]; } else { $word = @{ $words1 }[$index - $nwords2]; } $key = $word; } push @words_line, $word; } push @lines, [$key, (join "|", @words_line)]; } @lines = map { $_->[1] } sort { $a->[0] cmp $b->[0] } @lines; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh (join "\n", @lines); close $fh; } sub write_file1 { my ( $fn, $words ) = @_; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh (join "\n", sort @$words); close $fh; } sub get_words { my ( $fn, $N ) = @_; open( my $fh, '<', $fn ) or die "Could not open file '$fn': $!"; my @words = map {chomp $_; $_} <$fh>; close $fh; my @words1 = @words[$N..$#words]; my @words2 = @words[0..($N - 1)]; return ( \@words1, \@words2 ); } 

Successivamente, ho creato una solutions sottocartelle con tutti i casi di test:

 $ tree solutions/ solutions/ ├── BOC1 │  ├── out.txt │  └── run.sh ├── BOC2 │  ├── out.txt │  └── run.sh ├── codeforester │  ├── out.txt │  ├── run.pl │  └── run.sh [...] 

Qui i file out.txt è l’output di greps per ogni soluzione. Gli script run.sh esegue la soluzione per il caso di test specificato.

Note sulle diverse soluzioni

  • BOC1 : prima soluzione presentata da @BOC

     grep -E -f regexp1.txt file2.txt 
  • BOC2 : seconda soluzione suggerita da @BOC:

     LC_ALL=C grep -E -f regexp1.txt file2.txt 
  • codeforester : soluzione Perl accettata da @codeforester (vedi sorgente )

  • codeforester_orig : soluzione originale presentata da @codeforested:

     fgrep -f file1.txt file2.txt 
  • dawg : soluzione Python utilizzando dizionario e linea di divisione proposta da @dawg (vedi sorgente )

  • gregory1 : soluzione che utilizza Gnu Parallel suggerito da @gregory

     parallel -k --pipepart -a file2.txt --block "$block_size" fgrep -F -f file1.txt 

    Vedi la nota sotto per sapere come scegliere $block_size .

  • hakon1 : soluzione Perl fornita da @ HåkonHægland (vedi fonte ). Questa soluzione richiede la compilazione dell’estensione c la prima volta che viene eseguito il codice. Non richiede la ricompilazione quando file1.txt o file2.txt cambia. Nota: il tempo utilizzato per compilare l’estensione c nella corsa iniziale non è incluso nei tempi di esecuzione presentati di seguito.

  • ikegami : soluzione che utilizza regexp assemblata e utilizza grep -P come indicato da @ikegami. Nota: la regexp assemblata è stata scritta in un file separato regexp_ikegami.txt , quindi il runtime di generazione della regexp non è incluso nel confronto sottostante. Questo è il codice utilizzato:

     regexp=$(< "regexp_ikegami.txt") grep -P "$regexp" file2.txt 
  • inian1 : prima soluzione di @Inian usando match()

     awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (match($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian2 : seconda soluzione di @Inian usando index()

     awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (index($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian3 : terza soluzione di @Inian che controlla solo il campo $2 :

     awk 'FNR==NR{ hash[$1]; next } $2 in hash' file1.txt FS='|' file2.txt 
  • inian4 : 4th soultion di @Inian (sostanzialmente uguale a codeforester_orig con LC_ALL ):

     LC_ALL=C fgrep -f file1.txt file2.txt 
  • inian5 : 5th solution di @Inian (uguale a inian1 ma con LC_ALL ):

     LC_ALL=C awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (match($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian6 : come inian3 ma con LC_ALL=C Grazie a @GeorgeVasiliou per il suggerimento.

  • jjoao : codice C generato da flex compilato come proposto da @JJoao (vedi fonte ). Nota: la ricompilazione dell'esectuable deve essere eseguita ogni volta che cambia file1.txt . Il tempo utilizzato per compilare l'eseguibile non è incluso nei tempi di esecuzione presentati di seguito.

  • oliv : script Python fornito da @oliv (vedi sorgente )

  • Vasiliou : utilizzo di join come suggerito da @GeorgeVasiliou:

     join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 file1.txt file2.txt 
  • Vasiliou2 : come Vasiliou ma con LC_ALL=C

  • zdim : uso dello script Perl fornito da @zdim (vedi sorgente ). Nota: utilizza la versione di ricerca regexp (anziché la soluzione split line).

  • zdim2 : come zdim tranne per il fatto che utilizza la funzione split anziché la ricerca regexp per il campo in file2.txt .

Gli appunti

  1. Ho sperimentato un po 'con Gnu parallelamente (vedi la soluzione gregory1 sopra) per determinare la dimensione ottimale del blocco per la mia CPU. Ho 4 core, e attualmente sembra che la scelta ottimale sia quella di dividere il file ( file2.txt ) in 4 parti uguali, ed eseguire un singolo lavoro su ciascuno dei 4 processori. Potrebbero essere necessari ulteriori test qui. Quindi per il primo caso di test in cui file2.txt è 20M, ho impostato $block_size su 5M (vedere la soluzione gregory1 sopra), mentre per il caso più realistico presentato di seguito dove file2.txt è 268M, è stato utilizzato un $block_size di 67M.

  2. Le soluzioni BOC1 , BOC2 , codeforester_orig , inian1 , inian4 , inian5 e gregory1 tutte utilizzato la corrispondenza allentata. Significa che le parole da file1.txt non dovevano corrispondere esattamente nel campo # 2 di file2.txt . È stata accettata una corrispondenza ovunque sulla linea. Poiché questo comportamento rendeva più difficile il loro confronto con gli altri metodi, furono introdotti anche alcuni metodi modificati. I primi due metodi chiamati BOC1B e BOC2B utilizzavano un file regexp1.txt modificato. Le righe nel file regexp1.txt originale sul modulo \|foo1|foo2|...|fooN\| che corrisponderebbe alle parole in qualsiasi confine di campo. Il file modificato, regexp1b.txt , ha ancorato la corrispondenza al campo # 2 utilizzando esclusivamente la forma ^[^|]*\|foo1|foo2|...|fooN\| anziché.

    Quindi il resto dei metodi modificati: codeforester_origB , inian1B , inian4B , inian5B e gregory1B utilizzato un file1.txt modificato. Invece di una parola letterale per riga, il file modificato file1b.txt utilizzava file1b.txt per riga nel modulo:

      ^[^|]*\|word1\| ^[^|]*\|word2\| ^[^|]*\|word3\| [...] 

    e inoltre, fgrep -f stato sostituito da grep -E -f per questi metodi.

Esecuzione dei test

Ecco lo script utilizzato per eseguire tutti i test. Usa il comando Bash time per registrare il tempo trascorso per ogni script. Si noti che il comando time restituisce tre diverse volte chiamate real , user e sys . Per prima cosa ho usato user + sys , ma mi sono reso conto che ciò non era corretto quando si utilizzava il comando parallelo di Gnu, quindi l'ora riportata di seguito è ora la parte real restituita dal time . Vedi questa domanda per ulteriori informazioni sui diversi tempi restituiti dal time .

Il primo test viene eseguito con file1.txt contenente 5 righe e file2.txt contenente 1000000 righe. Ecco le prime 52 righe dello script run_all.pl , il resto dello script è disponibile qui .

run_all.pl

 #! /usr/bin/env perl use feature qw(say); use strict; use warnings; use Cwd; use Getopt::Long; use Data::Printer; use FGB::Common; use List::Util qw(max shuffle); use Number::Bytes::Human qw(format_bytes); use Sys::Info; GetOptions ( "verbose" => \my $verbose, "check" => \my $check, "single-case=s" => \my $case, "expected=i" => \my $expected_no_lines, ) or die("Error in command line arguments\n"); my $test_dir = 'solutions'; my $output_file = 'out.txt'; my $wc_expected = $expected_no_lines; # expected number of output lines my $tests = get_test_names( $test_dir, $case ); my $file2_size = get_file2_size(); my $num_cpus = Sys::Info->new()->device( CPU => () )->count; chdir $test_dir; my $cmd = 'run.sh'; my @times; for my $case (@$tests) { my $savedir = getcwd(); chdir $case; say "Running '$case'.."; my $arg = get_cmd_args( $case, $file2_size, $num_cpus ); my $output = `bash -c "{ time -p $cmd $arg; } 2>&1"`; my ($user, $sys, $real ) = get_run_times( $output ); print_timings( $user, $sys, $real ) if $verbose; check_output_is_ok( $output_file, $wc_expected, $verbose, $check ); print "\n" if $verbose; push @times, $real; #push @times, $user + $sys; # this is wrong when using Gnu parallel chdir $savedir; } say "Done.\n"; print_summary( $tests, \@times ); 

risultati

Ecco l'output dall'esecuzione dei test:

 $ run_all.pl --verbose Running 'inian3'.. ..finished in 0.45 seconds ( user: 0.44, sys: 0.00 ) ..no of output lines: 66711 Running 'inian2'.. ..finished in 0.73 seconds ( user: 0.73, sys: 0.00 ) ..no of output lines: 66711 Running 'Vasiliou'.. ..finished in 0.09 seconds ( user: 0.08, sys: 0.00 ) ..no of output lines: 66711 Running 'codeforester_orig'.. ..finished in 0.05 seconds ( user: 0.05, sys: 0.00 ) ..no of output lines: 66711 Running 'codeforester'.. ..finished in 0.45 seconds ( user: 0.44, sys: 0.01 ) ..no of output lines: 66711 [...] 

Sommario

[I risultati ottenuti da @Vasiliou sono mostrati nella colonna centrale.]

  |Vasiliou My Benchmark |Results | Details -------------------------------|---------|---------------------- inian4 : 0.04s |0.22s | LC_ALL fgrep -f [loose] codeforester_orig : 0.05s | | fgrep -f [loose] Vasiliou2 : 0.06s |0.16s | [LC_ALL join [requires sorted files]] BOC1 : 0.06s | | grep -E [loose] BOC2 : 0.07s |15s | LC_ALL grep -E [loose] BOC2B : 0.07s | | LC_ALL grep -E [strict] inian4B : 0.08s | | LC_ALL grep -E -f [strict] Vasiliou : 0.08s |0.23s | [join [requires sorted files]] gregory1B : 0.08s | | [parallel + grep -E -f [strict]] ikegami : 0.1s | | grep -P gregory1 : 0.11s |0.5s | [parallel + fgrep -f [loose]] hakon1 : 0.14s | | [perl + c] BOC1B : 0.14s | | grep -E [strict] jjoao : 0.21s | | [compiled flex generated c code] inian6 : 0.26s |0.7s | [LC_ALL awk + split+dict] codeforester_origB : 0.28s | | grep -E -f [strict] dawg : 0.35s | | [python + split+dict] inian3 : 0.44s |1.1s | [awk + split+dict] zdim2 : 0.4s | | [perl + split+dict] codeforester : 0.45s | | [perl + split+dict] oliv : 0.5s | | [python + compiled regex + re.search()] zdim : 0.61s | | [perl + regexp+dict] inian2 : 0.73s |1.7s | [awk + index($0,i)] inian5 : 18.12s | | [LC_ALL awk + match($0,i) [loose]] inian1 : 19.46s | | [awk + match($0,i) [loose]] inian5B : 42.27s | | [LC_ALL awk + match($0,i) [strict]] inian1B : 85.67s | | [awk + match($0,i) [strict]] Vasiliou Results : 2 X CPU Intel 2 Duo T6570 @ 2.10GHz - 2Gb RAM-Debian Testing 64bit- kernel 4.9.0.1 - no cpu freq scaling. 

Un caso di test più realistico

Ho quindi creato un caso più realistico con file1.txt con 100 parole e file2.txt con 10 milioni di righe (dimensione del file 268Mb). Ho estratto 1000 parole casuali dal dizionario in /usr/share/dict/american-english usando shuf -n1000 /usr/share/dict/american-english > words.txt quindi shuf -n1000 /usr/share/dict/american-english > words.txt estratto 100 di queste parole in file1.txt e poi shuf -n1000 /usr/share/dict/american-english > words.txt costruito file2.txt nello stesso modo descritto sopra per il primo caso di test. Si noti che il file del dizionario era codificato in UTF-8 e ho rimosso tutti i caratteri non ASCII da words.txt .

Quindi eseguo il test senza i tre metodi più lenti del caso precedente. inian1 , inian2 e inian5 sono stati lasciati fuori. Ecco i nuovi risultati:

 gregory1 : 0.86s | [parallel + fgrep -f [loose]] Vasiliou2 : 0.94s | [LC_ALL join [requires sorted files]] inian4B : 1.12s | LC_ALL grep -E -f [strict] BOC2B : 1.13s | LC_ALL grep -E [strict] BOC2 : 1.15s | LC_ALL grep -E [loose] BOC1 : 1.18s | grep -E [loose] ikegami : 1.33s | grep -P Vasiliou : 1.37s | [join [requires sorted files]] hakon1 : 1.44s | [perl + c] inian4 : 2.18s | LC_ALL fgrep -f [loose] codeforester_orig : 2.2s | fgrep -f [loose] inian6 : 2.82s | [LC_ALL awk + split+dict] jjoao : 3.09s | [compiled flex generated c code] dawg : 3.54s | [python + split+dict] zdim2 : 4.21s | [perl + split+dict] codeforester : 4.67s | [perl + split+dict] inian3 : 5.52s | [awk + split+dict] zdim : 6.55s | [perl + regexp+dict] gregory1B : 45.36s | [parallel + grep -E -f [strict]] oliv : 60.35s | [python + compiled regex + re.search()] BOC1B : 74.71s | grep -E [strict] codeforester_origB : 75.52s | grep -E -f [strict] 

Nota

Le soluzioni basate su grep cercavano una corrispondenza sull'intera linea, quindi in questo caso contenevano alcune false corrispondenze: i metodi codeforester_orig , BOC1 , BOC2 , gregory1 , inian4 e oliv estraevano 1.087.609 linee su 10.000.000 linee, mentre gli altri metodi estratto le 997.993 linee corrette da file2.txt .

Gli appunti

  • Ho provato questo sul mio computer portatile Ubuntu 16.10 (CPU Intel Core i7-7500U @ 2.70 GHz)

  • L'intero studio di riferimento è disponibile qui .

Hai provato Awk che potrebbe velocizzare un po ‘le cose:

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

(o) usando la funzione index() in Awk come suggerito dai commenti di Benjamin W. , sotto

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (index($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

(o) una corrispondenza regex più diretta come suggerito da Ed Morton nei commenti,

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if ($0~i) {print; break}}' file1.txt FS='|' file2.txt 

é tutto quello di cui hai bisogno. Immagino che questo sarà più veloce ma non esattamente sicuro sui file con milioni di voci. Qui il problema è con la possibilità di corrispondenza in qualsiasi punto della linea. Se lo stesso fosse stato in una particolare colonna (ad esempio, solo $2 ), un approccio più veloce potrebbe essere

 awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt 

Inoltre puoi accelerare le cose giocando con le impostazioni locale nel tuo sistema. Parafrasando questa meravigliosa risposta di Stéphane Chazelas sull’argomento, potresti velocizzare le cose abbastanza rapidamente impostando il passaggio locale LC_ALL=C al comando localmente eseguito.

Su qualsiasi sistema basato su GNU , i valori predefiniti per la locale

 $ locale LANG=en_US.UTF-8 LC_CTYPE="en_US.UTF-8" LC_NUMERIC="en_US.UTF-8" LC_TIME="en_US.UTF-8" LC_COLLATE="en_US.UTF-8" LC_MONETARY="en_US.UTF-8" LC_MESSAGES="en_US.UTF-8" LC_PAPER="en_US.UTF-8" LC_NAME="en_US.UTF-8" LC_ADDRESS="en_US.UTF-8" LC_TELEPHONE="en_US.UTF-8" LC_MEASUREMENT="en_US.UTF-8" LC_IDENTIFICATION="en_US.UTF-8" LC_ALL= 

Con una variabile LC_ALL , è ansible impostare tutte le variabili di tipo LC_ in una sola volta in una locale specificata

 $ LC_ALL=C locale LANG=en_US.UTF-8 LC_CTYPE="C" LC_NUMERIC="C" LC_TIME="C" LC_COLLATE="C" LC_MONETARY="C" LC_MESSAGES="C" LC_PAPER="C" LC_NAME="C" LC_ADDRESS="C" LC_TELEPHONE="C" LC_MEASUREMENT="C" LC_IDENTIFICATION="C" LC_ALL=C 

Quindi, cosa ha questo impatto?

In parole povere, quando si utilizza il locale C , verrà automaticamente utilizzato il linguaggio Unix / Linux del server ASCII . Fondamentalmente quando grep qualcosa, per impostazione predefinita la tua localizzazione sarà internazionalizzata e impostata su UTF-8 , che può rappresentare ogni carattere nel set di caratteri Unicode per aiutare a visualizzare uno qualsiasi dei sistemi di scrittura del mondo, attualmente su oltre 110,000 caratteri univoci, mentre con ASCII ogni carattere è codificato in una sequenza di byte singoli e il suo set di caratteri comprende non più di 128 caratteri univoci.

Quindi si traduce in questo, quando si usa grep su un file codificato in set di caratteri UTF-8 , deve abbinare ogni carattere con uno qualsiasi dei centomila caratteri unici, ma solo 128 in ASCII , quindi usa fgrep come

 LC_ALL=C fgrep -F -f file1.txt file2.txt 

Inoltre, lo stesso può essere adattato a Awk , dal momento che usa una corrispondenza regex con la chiamata match($0,i) , impostando il locale C potrebbe accelerare la corrispondenza delle stringhe.

 LC_ALL=C awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

Presupposti: 1. Si desidera eseguire questa ricerca solo sulla workstation locale. 2. Avere più core / CPU per sfruttare una ricerca parallela.

 parallel --pipepart -a file2.txt --block 10M fgrep -F -f file1.txt 

Ulteriori modifiche a seconda del contesto: A. Disabilita NLS con LANG = C (questo è già menzionato in un’altra risposta) B. Imposta un numero massimo di corrispondenze con il flag -m.

Nota: immagino che file2 sia ~ 4 GB e che la dimensione del blocco 10M sia ok, ma potrebbe essere necessario ottimizzare la dimensione del blocco per ottenere la corsa più veloce.

Questo script Perl ( a ) genera un modello regex:

 #!/usr/bin/perl use strict; use warnings; use Regexp::Assemble qw( ); chomp( my @ids = <> ); my $ra = Regexp::Assemble->new(); $ra->add(quotemeta($_)) for @ids; print("^[^|]*\\|(?:" . (re::regexp_pattern($ra->re()))[0] . ")\\|"); 

Ecco come può essere utilizzato:

 $ LC_ALL=C grep -P "$( a file1.txt )" file2.txt date1|foo1|number1 date2|foo2|number2 date1|bar1|number1 date2|bar2|number2 

Nota che lo script usa Regexp :: Assemble, quindi potresti aver bisogno di installarlo.

 sudo su cpan Regexp::Assemble 

Gli appunti:

  • A differenza delle soluzioni denominate BOC1, BOC2, codeforester_orig, gregory1, inian2, inian4 e oliv, la mia soluzione gestisce correttamente

     file1.txt foo1 file2.txt date1|foo12|number5 
  • La mia dovrebbe essere migliore della soluzione simile di @BOC perché il pattern è ottimizzato per ridurre il backtracking. (Il mio funziona anche se ci sono più di tre campi in file2.txt , mentre la soluzione collegata può fallire.)

  • Non so come si paragona alle soluzioni split + dictionary.

Un piccolo pezzo di codice Perl ha risolto il problema. Questo è l’approccio adottato:

  • memorizza le righe di file1.txt in un hash
  • leggere file2.txt riga per riga, analizzare ed estrarre il secondo campo
  • controlla se il campo estratto è nell’hash; se è così, stampa la linea

Ecco il codice:

 #!/usr/bin/perl -w use strict; if (scalar(@ARGV) != 2) { printf STDERR "Usage: fgrep.pl smallfile bigfile\n"; exit(2); } my ($small_file, $big_file) = ($ARGV[0], $ARGV[1]); my ($small_fp, $big_fp, %small_hash, $field); open($small_fp, "<", $small_file) || die "Can't open $small_file: " . $!; open($big_fp, "<", $big_file) || die "Can't open $big_file: " . $!; # store contents of small file in a hash while (<$small_fp>) { chomp; $small_hash{$_} = undef; } close($small_fp); # loop through big file and find matches while (<$big_fp>) { # no need for chomp $field = (split(/\|/, $_))[1]; if (defined($field) && exists($small_hash{$field})) { printf("%s", $_); } } close($big_fp); exit(0); 

Ho eseguito lo script di cui sopra con linee 14K in file1.txt e 1.3M righe in file2.txt. Finì in circa 13 secondi, producendo 126K partite. Ecco l’output del time per lo stesso:

 real 0m11.694s user 0m11.507s sys 0m0.174s 

Ho eseguito il codice awk @ Inian:

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

Era molto più lento della soluzione Perl, dal momento che è in loop 14K per ogni riga in file2.txt – il che è molto costoso. È stato interrotto dopo l’elaborazione dei record 592K di file2.txt e la produzione di righe corrispondenti a 40K. Ecco quanto ci è voluto:

 awk: illegal primary in regular expression 24/Nov/2016||592989 at 592989 input record number 675280, file file2.txt source line number 1 real 55m5.539s user 54m53.080s sys 0m5.095s 

Using @Inian’s other awk solution, which eliminates the looping issue:

 time awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk1.out real 0m39.966s user 0m37.916s sys 0m0.743s time LC_ALL=C awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk.out real 0m41.057s user 0m38.475s sys 0m0.904s 

awk is very impressive here, given that we didn’t have to write an entire program to do it.

I ran @oliv’s Python code as well. It took about 15 hours to complete the job, and looked like it produced the right results. Building a huge regex isn’t as efficient as using a hash lookup. Here the time output:

 real 895m14.862s user 806m59.219s sys 1m12.147s 

I tried to follow the suggestion to use parallel . However, it failed with fgrep: memory exhausted error, even with very small block sizes.


What surprised me was that fgrep was totally unsuitable for this. I aborted it after 22 hours and it produced about 100K matches. I wish fgrep had an option to force the content of -f file to be kept in a hash, just like what the Perl code did.

I didn’t check join approach – I didn’t want the additional overhead of sorting the files. Also, given fgrep ‘s poor performance, I don’t believe join would have done better than the Perl code.

Thanks everyone for your attention and responses.

Here is Perl solution that uses Inline::C to speed up the search for matching fields in the large file:

 use strict; use warnings; use Inline C => './search.c'; my $smallfile = 'file1.txt'; my $bigfile = 'file2.txt'; open my $fh, '<', $smallfile or die "Can't open $smallfile: $!"; my %word = map { chomp; $_ => 1 } <$fh>; search( $bigfile, \%word ); 

The search() sub routine is implemented in pure C using perlapi to look up keys in the small file dictionary %words :

search.c :

 #include  #include  #include  #include  #include  #define BLOCK_SIZE 8192 /* how much to read from file each time */ static char read_buf[BLOCK_SIZE + 1]; /* reads a block from file, returns -1 on error, 0 on EOF, else returns chars read, pointer to buf, and pointer to end of buf */ size_t read_block( int fd, char **ret_buf, char **end_buf ) { int ret; char *buf = read_buf; size_t len = BLOCK_SIZE; while (len != 0 && (ret = read(fd, buf, len)) != 0) { if (ret == -1) { if (errno == EINTR) continue; perror( "read" ); return ret; } len -= ret; buf += ret; } *end_buf = buf; *ret_buf = read_buf; return (size_t) (*end_buf - *ret_buf); } /* updates the line buffer with the char pointed to by cur, also updates cur */ int update_line_buffer( char **cur, char **line, size_t *llen, size_t max_line_len ) { if ( *llen > max_line_len ) { fprintf( stderr, "Too long line. Maximimum allowed line length is %ld\n", max_line_len ); return 0; } **line = **cur; (*line)++; (*llen)++; (*cur)++; return 1; } /* search for first pipe on a line (or next line if this is empty), assume line ptr points to beginning of line buffer. return 1 on success Return 0 if pipe could not be found for some reason, or if line buffer length was exceeded */ int search_field_start( int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len ) { char *line_start = *line; while (1) { if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return 0; } if ( **cur == '|' ) break; /* Currently we just ignore malformed lines ( lines that do not have a pipe, and empty lines in the input */ if ( **cur == '\n' ) { *line = line_start; *llen = 0; (*cur)++; } else { if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0; } } return 1; } /* assume cur points at starting pipe of field return -1 on read error, return 0 if field len was too large for buffer or line buffer length exceed, else return 1 and field, and length of field */ int copy_field( int fd, char **cur, char **end_buf, char *field, size_t *flen, char **line, size_t *llen, size_t max_field_len, size_t max_line_len ) { *flen = 0; while( 1 ) { if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0; if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return -1; } if ( **cur == '|' ) break; if ( *flen > max_field_len ) { printf( "Field width too large. Maximum allowed field width: %ld\n", max_field_len ); return 0; } *field++ = **cur; (*flen)++; } /* It is really not necessary to null-terminate the field since we return length of field and also field could contain internal null characters as well */ //*field = '\0'; return 1; } /* search to beginning of next line, return 0 on error, else return 1 */ int search_eol( int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len) { while (1) { if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return 0; } if ( !update_line_buffer( cur, line, llen, max_line_len ) ) return 0; if ( *(*cur-1) == '\n' ) { break; } } //**line = '\0'; // not necessary return 1; } #define MAX_FIELD_LEN 80 /* max number of characters allowed in a field */ #define MAX_LINE_LEN 80 /* max number of characters allowed on a line */ /* Get next field ( ie field #2 on a line). Fields are separated by pipes '|' in the input file. Also get the line of the field. Return 0 on error, on success: Move internal pointer to beginning of next line return 1 and the field. */ size_t get_field_and_line_fast( int fd, char *field, size_t *flen, char *line, size_t *llen ) { static char *cur = NULL; static char *end_buf = NULL; size_t res; if (cur == NULL) { res = read_block( fd, &cur, &end_buf ); if ( res <= 0 ) return 0; } *llen = 0; if ( !search_field_start( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN )) return 0; if ( (res = copy_field( fd, &cur, &end_buf, field, flen, &line, llen, MAX_FIELD_LEN, MAX_LINE_LEN ) ) <= 0) return 0; if ( !search_eol( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN ) ) return 0; return 1; } void search( char *filename, SV *href) { if( !SvROK( href ) || ( SvTYPE( SvRV( href ) ) != SVt_PVHV ) ) { croak( "Not a hash reference" ); } int fd = open (filename, O_RDONLY); if (fd == -1) { croak( "Could not open file '%s'", filename ); } char field[MAX_FIELD_LEN+1]; char line[MAX_LINE_LEN+1]; size_t flen, llen; HV *hash = (HV *)SvRV( href ); while ( get_field_and_line_fast( fd, field, &flen, line, &llen ) ) { if( hv_exists( hash, field, flen ) ) fwrite( line, sizeof(char), llen, stdout); } if (close(fd) == -1) croak( "Close failed" ); } 

Tests indicate that it is approximately 3 times faster than the fastest pure Perl solution (see method zdim2 in my other answer ) presented here.

Here is a Python solution using sets — roughly equivalent to a Perl key only hash or awk array in concept.

 #!/usr/bin/python import sys with open(sys.argv[1]) as f: tgt={e.rstrip() for e in f} with open(sys.argv[2]) as f: for line in f: cells=line.split("|") if cells[1] in tgt: print line.rstrip() 

When I run this on files of similar size, it runs in about 8 seconds.

Same speed as:

 $ awk 'FNR==NR{arr[$1]; next} $2 in arr{print $0}' FS="|" /tmp/f1 /tmp/f2 

Both the Python and awk solution here are full string match only; not a partial regex style match.

Since the awk solution is fast and POSIX compliant, that is the better answer.

A possible way is to use python :

 $ cat test.py import sys,re with open(sys.argv[1], "r") as f1: patterns = f1.read().splitlines() # read pattern from file1 without the trailing newline m = re.compile("|".join(patterns)) # create the regex with open(sys.argv[2], "r") as f2: for line in f2: if m.search(line) : print line, # print line from file2 if this one matches the regex 

e usalo in questo modo:

 python test.py file1.txt file2.txt 

Can you give a try to join ? Files must be sorted though…

 $ cat d.txt bar1 bar2 foo1 foo2 $ cat e.txt date1|bar1|number1 date2|bar2|number2 date3|bar3|number3 date1|foo1|number1 date2|foo2|number2 date3|foo3|number3 $ join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 d.txt e.txt date1|bar1|number1 date2|bar2|number2 date1|foo1|number1 date2|foo2|number2 

Small Update:
By using LC_ALL=C in front of join, things are really speed up as can be seen in the benchmark of Håkon Hægland

PS1: I have my doubts if join can be faster than grep -f …

Puoi anche usare Perl per questo:

Please note that this will hog memory and your machine/server better has some.

Sample Data:

 %[email protected] * /root/ga/pl> head file1.txt file2.txt ==> file1.txt <== foo1 foo2 ... bar1 bar2 ... ==> file2.txt <== date1|foo1|number1 date2|foo2|number2 date3|foo3|number3 ... date1|bar1|number1 date2|bar2|number2 date3|bar3|number3 %[email protected] * /root/ga/study/pl> 

Script Output: Script will produce final output in a file named output_comp .

 %[email protected] * /root/ga/pl> ./comp.pl file1.txt file2.txt ; cat output_comp date1|bar1|number1 date2|bar2|number2 date2|foo2|number2 date1|foo1|number1 %[email protected] * /root/ga/pl> 

script:

 %[email protected] * /root/ga/pl> cat comp.pl #!/usr/bin/perl use strict ; use warnings ; use Data::Dumper ; my ($file1,$file2) = @ARGV ; my $output = "output_comp" ; my %hash ; # This will store main comparison data. my %tmp ; # This will store already selected results, to be skipped. (scalar @ARGV != 2 ? (print "Need 2 files!\n") : ()) ? exit 1 : () ; # Read all files at once and use their name as the key. for (@ARGV) { open FH, "<$_" or die "Cannot open $_\n" ; while (my $line = ) {chomp $line ;$hash{$_}{$line} = "$line"} close FH ; } # Now we churn through the data and compare to generate # the sorted output in the output file. open FH, ">>$output" or die "Cannot open outfile!\n" ; foreach my $k1 (keys %{$hash{$file1}}){ foreach my $k2 (keys %{$hash{$file2}}){ if ($k1 =~ m/^.+?$k2.+?$/) { if (!defined $tmp{"$hash{$file2}{$k2}"}) { print FH "$hash{$file2}{$k2}\n" ; $tmp{"$hash{$file2}{$k2}"} = 1 ; } } } } close FH ; %[email protected] * /root/ga/pl> 

Grazie.

IMHO, grep is a good tool highly optimised for huge file2.txt but maybe not for so many patterns to search. I suggest to combine all the strings of file1.txt into a single huge regexp like \|bar1|bar2|foo1|foo2\|

 echo '\|'$(paste -s -d '|' file1.txt)'\|' > regexp1.txt grep -E -f regexp1.txt file2.txt > file.matched 

And of course LANG=C may help. Please give feedback or send your files so I can test myself.

I would use SQLite3 🙂 Maybe in-memory database or whatever. Import the files and use SQL query.

Using flex :

1: build the flex processor:

 $ awk 'NR==1{ printf "%%%%\n\n.*\\|(%s",$0 } { printf "|%s",$0 } END { print ")\\|.*\\n ECHO;\n.*\\n ;\n%%\n" }' file1.txt > a.fl 

2: compile it

 $ flex -Ca -F a.fl ; cc -O lex.yy.c -lfl 

3: and run

 $ a.out < file2.txt > out 

Compiling (cc …) is a slow process; this approach will pay just for cases of stable file1.txt

(In my machine) The times taken to run a search “100 in 10_000_000” test in this approach is 3 times faster than LC_ALL=C fgrep...

Though this thread is over, but all grep-alike methods between two files are gathered in this post, why not to add this awk alternative, similar (or even improved) to the bounty winning Inian’s awk solution:

 awk 'NR==FNR{a[$0]=1;next}a[$2]' patterns.txt FS="|" datafile.txt >matches.txt # For matches restricted on Field2 of datafile 

This is equivalent to Inian awk $2 in hash solution but it could be even faster due to the fact that we don’t ask awk to check if the whole hash array contains $2 of file2 – we just check if a[$2] has a value or not.

While reading the first patterns file appart from creating the hash array we assign also a value.

If $2 of datafile had been found before in patterns file, then a[$2] would have a value and thus will be printed because is not null.

if a[$2] of datafile returns no value(null) this is translated to false => no printing.

Extension to match any of the three fields of datafile:

 awk 'NR==FNR{a[$0]=1;next}(a[$1] || a[$2] || a[$3])' patterns.txt FS="|" datafile.txt >matches.txt. #Printed if any of the three fields of datafile match pattern. 

In both cases, applying LC_ALL=C in front of awk, seems to speed things up.

PS1: Offcourse this solution has also the pitfalls of all awk solutions. Is not a pattern matching. Is a direct / fixed matching between of the two files, like most of the solutions inhere.

PS2: In my poor machine benchmark using the small benchmark files of Håkon Hægland , i get about 20% better performance comparing to the awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt

setting language etc helps a little, perhaps.

otherwise I can not think of a magic solution to escape from your basic issue: the data is not structured, so you will have a search that comes down to the number of lines in file1 multiplied with the number of lines in file2.

put the billion lines in a database, and index it in a smart way, is the only speed up I can think of. that index would have to be very smart, though……

SImple solution is: have enough memory to fit everything in to. otherwise nothing much more you can do about this….