Maneira mais rápida de encontrar linhas de um arquivo de outro arquivo maior no Bash

Eu tenho dois arquivos, file1.txt e file2.txt . file1.txt tem cerca de 14k linhas e file2.txt tem cerca de 2 bilhões. file1.txt tem um único campo f1 por linha enquanto o file2.txt possui 3 campos, f1 a f3 , delimitados por | .

Eu quero encontrar todas as linhas de file2.txt onde f1 de file1.txt corresponde f2 de file2.txt (ou em qualquer lugar na linha, se não queremos gastar tempo extra dividindo os valores de file2.txt ).

file1.txt (cerca de 14K linhas, não classificadas ):

 foo1 foo2 ... bar1 bar2 ... 

file2.txt (cerca de 2 bilhões de linhas, não classificadas ):

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

Saída esperada:

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

Aqui está o que eu tentei e parece levar várias horas para ser executado:

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

Gostaria de saber se existe uma maneira melhor e mais rápida de fazer essa operação com os comandos comuns do Unix ou com um script pequeno.

Uma solução Perl. [Veja a nota abaixo.]

Use um hash para o primeiro arquivo. Enquanto você lê o arquivo grande linha por linha, extraia o campo por regex (captura o primeiro padrão entre || ) ou split (pega a segunda palavra) e imprime se ele exists . Eles provavelmente diferem um pouco na velocidade (tempo deles). A verificação defined não é necessária no regex enquanto que para o uso split // (define-ou) esse curto-circuito.

 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; 

Evitar o ramo if e usar o curto-circuito é mais rápido, mas muito pouco. Em bilhões de linhas, esses ajustes se summ, mas novamente não muito. Pode (ou não) ser um pouquinho mais rápido para ler o pequeno arquivo linha por linha, em vez de no contexto de lista como acima, mas isso não deve ser perceptível.

Atualização escrita para STDOUT salva duas operações e eu repetidamente tempo para ser um pouco mais rápido do que gravar em um arquivo. Esse uso também é consistente com a maioria das ferramentas UNIX, então mudei para gravar em STDOUT . Em seguida, o teste de exists não é necessário e soltá-lo poupa uma operação. No entanto, eu sempre obtenho um melhor tempo de execução com ele , enquanto ele também transmite melhor o propósito. Ao todo estou deixando em. Graças a ikegami para comentários.

Nota A versão comentada é cerca de 50% mais rápida do que a outra, pelo meu benchmark abaixo. Ambos são dados porque são diferentes , um encontra o primeiro e o outro o segundo. Estou mantendo isso como uma opção mais genérica, já que a questão é ambígua sobre isso.


Algumas comparações (benchmark) [Atualizado para gravação em STDOUT , veja “Atualização” acima]

Existe uma extensa análise na resposta da HåkonHægland , que é o timing de uma série de soluções. Aqui está outra análise, comparando as duas soluções acima, a resposta do próprio OP, e o fgrep publicado, esperado para ser rápido e usado na pergunta e em muitas respostas.

Eu construo dados de teste da seguinte maneira. Um punhado de linhas do comprimento mais ou menos como mostrado são feitas com palavras aleatórias, para ambos os arquivos, para corresponder no segundo campo. Então, eu coloco essa “semente” para amostras de dados com linhas que não correspondem, para simular proporções entre tamanhos e correspondências citadas por OP: para linhas de 14K em arquivos pequenos existem 1.3M linhas no arquivo grande, produzindo correspondências de 126K . Em seguida, esses exemplos são gravados repetidamente para criar arquivos de dados completos como OPs, shuffle -ed cada vez usando List :: Util .

Todas as execuções comparadas abaixo produzem correspondências de 106_120 para os tamanhos de arquivo acima ( diff -ed para uma verificação), portanto a frequência de correspondência é próxima o suficiente. Eles são comparados chamando programas completos usando my $res = timethese(60 ...) . O resultado de cmpthese($res) na v5.16 são

         Avaliar regex c para dividir fgrep
 regex 1,05 / s - -23% -35% -44%
 c para 1,36 / s 30% - -16% -28%
 split 1,62 / s 54% 19% - -14%
 fgrep 1,89 / s 80% 39% 17% -

O fato de o fgrep programa C otimizado estar no topo não é surpreendente. O ” regex ” atras atrás de ” split ” pode ser devido à sobrecarga de ligar o motor para pequenas partidas, muitas vezes. Isso pode variar em relação às versões Perl, dadas as otimizações do mecanismo regex em evolução. Eu incluo a resposta @codeforester (” cfor “), uma vez que foi reivindicada a ser mais rápida, e seu atraso de 20% por trás da ” divisão ” muito semelhante é provavelmente devido a pequenas ineficiências espalhadas (veja um comentário abaixo desta resposta).

Isso não é muito diferente, embora haja certas variações em hardware e software e em detalhes de dados. Eu corri isto em Perls e máquinas diferentes, e a diferença notável é que em alguns casos o fgrep era de fato uma ordem de grandeza mais rápida .

A experiência do OP em fgrep muito lento é surpreendente. Considerando os tempos de execução cotados, ordem de grandeza mais lenta que a anterior, acho que há um sistema antigo para “culpar”.

Mesmo que isso seja completamente baseado em E / S, há benefícios simultâneos de colocá-lo em múltiplos núcleos e eu esperaria uma boa aceleração, até um fator de poucos.

Eu tentei fazer uma comparação entre alguns dos methods apresentados aqui.

Primeiro, criei um script Perl para gerar os arquivos de input file1.txt e file2.txt . Para comparar algumas das soluções, certifiquei-me de que as palavras de file1.txt só pudessem aparecer no segundo campo em file2.txt . Também para poder usar a solução de join apresentada por @GeorgeVasiliou, classifiquei file1.txt e file2.txt . Atualmente eu gerava os arquivos de input com base em apenas 75 palavras aleatórias (tiradas de https://www.randomlists.com/random-words ). Apenas 5 dessas 75 palavras foram usadas no file1.txt As 70 palavras restantes foram usadas para preencher os campos no file2.txt . Pode ser necessário aumentar substancialmente o número de palavras para obter resultados realistas (de acordo com o OP, o file1.txt original1.txt continha 14000 palavras). Nos testes abaixo eu usei um file2.txt com 1000000 (1 milhão) linhas. O script também gera o arquivo regexp1.txt requerido pela solução grep do @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 ); } 

Em seguida, criei uma solutions subpasta com todos os casos de teste:

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

Aqui, os arquivos out.txt são a saída dos greps para cada solução. Os scripts run.sh a solução para o caso de teste fornecido.

Notas sobre as diferentes soluções

  • BOC1 : Primeira solução apresentada pelo @BOC

     grep -E -f regexp1.txt file2.txt 
  • BOC2 : Segunda solução sugerida pelo @BOC:

     LC_ALL=C grep -E -f regexp1.txt file2.txt 
  • codeforester : Solução Perl aceita por @codeforester (ver fonte )

  • codeforester_orig : Solução original apresentada por @codeforested:

     fgrep -f file1.txt file2.txt 
  • dawg : solução Python usando dictionary e linha dividida proposta por @dawg (ver fonte )

  • gregory1 : solução usando o Gnu Parallel sugerido por @gregory

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

    Veja a nota abaixo sobre como escolher $block_size .

  • hakon1 : solução Perl fornecida por @ HåkonHægland (ver fonte ). Essa solução requer a compilation da extensão c na primeira vez em que o código é executado. Não requer recompilation quando file1.txt ou file2.txt alterado. Nota: O tempo usado para compilar a extensão c na execução inicial não é incluído nos tempos de execução apresentados abaixo.

  • ikegami : Solução usando o regexp montado e usando grep -P como dado por @ikegami. Nota: O regexp montado foi gravado em um arquivo separado regexp_ikegami.txt , portanto, o tempo de execução da geração do regexp não está incluído na comparação abaixo. Este é o código usado:

     regexp=$(< "regexp_ikegami.txt") grep -P "$regexp" file2.txt 
  • inian1 : Primeira solução por @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 : Segunda solução por @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 : Terceira solução da @Inian verificando apenas o campo de $2 :

     awk 'FNR==NR{ hash[$1]; next } $2 in hash' file1.txt FS='|' file2.txt 
  • inian4 : 4th soultion by @Inian (basicamente o mesmo que codeforester_orig com LC_ALL ):

     LC_ALL=C fgrep -f file1.txt file2.txt 
  • inian5 : 5ª solução de @Inian (igual a inian1 mas com 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 : O mesmo que inian3 mas com LC_ALL=C Obrigado a @GeorgeVasiliou por sugestão.

  • jjoao : Código C compilado em flex, conforme proposto por @JJoao (veja fonte ). Nota: Recompilation do exectuable deve ser feita cada vez que file1.txt muda. O tempo usado para compilar o executável não está incluído nos tempos de execução apresentados abaixo.

  • oliv : script Python fornecido por @oliv (ver fonte )

  • Vasiliou : Usando join como sugerido por @GeorgeVasiliou:

     join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 file1.txt file2.txt 
  • Vasiliou2 : O mesmo que Vasiliou mas com LC_ALL=C

  • zdim : Usando o script Perl fornecido por @zdim (veja fonte ). Nota: Isso usa a versão de pesquisa do regexp (em vez da solução de linha dividida).

  • zdim2 : O mesmo que zdim exceto que ele usa a function split vez da pesquisa regexp para o campo em file2.txt .

Notas

  1. Eu experimentei um pouco com o Gnu paralelo (veja a solução gregory1 acima) para determinar o tamanho ideal de bloco para a minha CPU. Eu tenho 4 núcleos e, atualmente, parece que a melhor opção é dividir o arquivo ( file2.txt ) em 4 partes iguais e executar um único trabalho em cada um dos 4 processadores. Mais testes podem ser necessários aqui. Portanto, para o primeiro caso de teste em que file2.txt é 20M, defino $block_size para 5M (consulte a solução gregory1 acima), enquanto para o caso mais realista apresentado abaixo em que file2.txt é 268M, foi usado $block_size block_size de 67M.

  2. As soluções BOC1 , BOC2 , codeforester_orig , inian1 , inian4 , inian5 e gregory1 todas usavam correspondência fraca. Isso significa que as palavras do file1.txt não precisam corresponder exatamente ao campo # 2 do file2.txt . Uma partida em qualquer lugar da linha foi aceita. Como esse comportamento dificultou sua comparação com os outros methods, alguns methods modificados também foram introduzidos. Os dois primeiros methods chamados BOC1B e BOC2B usaram um arquivo regexp1.txt modificado. As linhas no regexp1.txt original, onde no formato \|foo1|foo2|...|fooN\| que corresponderia às palavras em qualquer limite de campo. O arquivo modificado, regexp1b.txt , ancorou a correspondência no campo # 2 usando exclusivamente o formato ^[^|]*\|foo1|foo2|...|fooN\| em vez de.

    Em seguida, o restante dos methods modificados codeforester_origB , inian1B , inian4B , inian5B e gregory1B usou um file1.txt modificado. Em vez de uma palavra literal por linha, o arquivo modificado file1b.txt usava um regex por linha no formulário:

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

    e, além disso, fgrep -f foi substituído por grep -E -f para esses methods.

Executando os testes

Aqui está o script usado para executar todos os testes. Ele usa o comando Bash time para registrar o tempo gasto para cada script. Note que o comando time retorna três vezes diferentes chamadas real , user e sys . Primeiro usei user + sys , mas percebi que isso estava incorreto ao usar o comando paralelo do Gnu, então o tempo reportado abaixo é agora a parte real retornada pelo time . Veja esta pergunta para mais informações sobre os diferentes tempos retornados pelo time .

O primeiro teste é executado com file1.txt contendo 5 linhas e file2.txt contendo linhas de 1000000 . Aqui estão as primeiras 52 linhas do script run_all.pl , o restante do script está disponível aqui .

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

Resultados

Aqui está a saída da execução dos testes:

 $ 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 [...] 

Resumo

[Os resultados obtidos por @Vasiliou são mostrados na coluna do meio.]

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

Um caso de teste mais realista

Eu então criei um caso mais realista com file1.txt com 100 palavras e file2.txt com 10 milhões de linhas (tamanho de arquivo de 268Mb). Eu extraí 1000 palavras aleatórias do dictionary em /usr/share/dict/american-english usando shuf -n1000 /usr/share/dict/american-english > words.txt seguida, extraímos 100 dessas palavras em file1.txt e, em seguida, construímos file2.txt da mesma maneira descrita acima para o primeiro caso de teste. Observe que o arquivo de dictionary era codificado em UTF-8 e words.txt todos os caracteres não-ASCII do words.txt .

Então eu corro o teste sem os três methods mais lentos do caso anterior. inian1 seja, inian1 , inian2 e inian5 ficaram de fora. Aqui estão os novos resultados:

 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

As soluções baseadas no grep estavam procurando uma correspondência na linha inteira, então nesse caso elas continham algumas correspondências falsas: os methods codeforester_orig , BOC1 , BOC2 , gregory1 , inian4 e oliv extraíam 1.087.609 linhas de 10.000.000 linhas, enquanto os outros methods extraiu as 997.993 linhas corretas do file2.txt .

Notas

  • Eu testei isso no meu laptop Ubuntu 16.10 (CPU Intel Core i7-7500U @ 2.70GHz)

  • Todo o estudo de benchmark está disponível aqui .

Você tentou Awk que poderia acelerar um pouco as coisas:

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

(ou) usando a function index() no Awk como sugerido pelos comentários de Benjamin W. , abaixo

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

(ou) uma correspondência de regex mais direta, como sugerido por Ed Morton nos comentários,

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

é tudo o que você precisa. Eu estou supondo que isso será mais rápido, mas não exatamente certo em arquivos com milhões de inputs. Aqui o problema é com a correspondência de possibilidade em qualquer lugar ao longo da linha. Se o mesmo tivesse ocorrido em alguma coluna específica (por exemplo, digamos $2 ), uma abordagem mais rápida poderia ser

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

Além disso, você pode acelerar as coisas jogando com o locale definido no seu sistema. Parafraseando a resposta deste maravilhoso Stéphane Chazelas sobre o assunto, você pode acelerar as coisas muito rapidamente configurando passando o local LC_ALL=C para o comando sendo executado localmente .

Em qualquer sistema baseado em GNU , os padrões para o 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= 

Com uma variável LC_ALL , você pode definir todas as variables ​​do tipo LC_ uma vez para uma localidade especificada

 $ 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 

Então, o que isso afeta?

Simplificando, ao usar o locale C , o padrão será a linguagem Unix / Linux base do servidor do ASCII . Basicamente, quando você faz alguma coisa, por padrão sua localidade será internacionalizada e configurada como UTF-8 , que pode representar todos os caracteres do conjunto de caracteres Unicode para ajudar a exibir qualquer sistema de escrita do mundo, atualmente com mais de 110,000 caracteres únicos. enquanto que com o ASCII cada caractere é codificado em uma única sequência de bytes e seu conjunto de caracteres não possui mais de 128 caracteres únicos.

Então, isso se traduz em que, ao usar o grep em um arquivo codificado no conjunto de caracteres UTF-8 , ele precisa corresponder a cada caractere com qualquer um dos cem mil caracteres únicos, mas apenas 128 em ASCII , portanto use seu fgrep como

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

Além disso, o mesmo pode ser adaptado ao Awk , uma vez que ele usa uma correspondência de regex com a match($0,i) , definindo que a região C pode acelerar a correspondência de seqüência de caracteres.

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

Suposições: 1. Você deseja executar esta pesquisa apenas em sua estação de trabalho local. 2. Você tem vários núcleos / CPUs para aproveitar uma pesquisa paralela.

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

Alguns ajustes adicionais, dependendo do contexto: A. Desativar NLS com LANG = C (isso já é mencionado em outra resposta) B. Defina um número máximo de correspondências com o sinalizador -m.

Nota: Eu estou supondo que o arquivo2 é ~ 4GB e o tamanho do bloco de 10M é ok, mas você pode precisar otimizar o tamanho do bloco para obter a execução mais rápida.

Este script Perl ( a ) gera um padrão de expressão regular:

 #!/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] . ")\\|"); 

Veja como isso pode ser usado:

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

Observe que o script usa o Regexp :: Assemble, portanto, talvez seja necessário instalá-lo.

 sudo su cpan Regexp::Assemble 

Notas:

  • Ao contrário das soluções chamadas BOC1, BOC2, codeforester_orig, gregory1, inian2, inian4 e oliv, minha solução manipula corretamente

     file1.txt foo1 file2.txt date1|foo12|number5 
  • O meu deve ser melhor do que a solução similar do @BOC porque o padrão é otimizado para reduzir o retrocesso. (O meu também funciona se houver mais de três campos no file2.txt , enquanto a solução vinculada pode falhar.)

  • Não sei como se compara às soluções split + dictionary.

Um pequeno pedaço de código Perl resolveu o problema. Essa é a abordagem adotada:

  • armazenar as linhas do file1.txt em um hash
  • leia file2.txt linha por linha, analise e extraia o segundo campo
  • verifique se o campo extraído está no hash; se sim, imprima a linha

Aqui está o código:

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

Eu corri o script acima com 14k linhas no arquivo1.txt e 1.3M linhas no arquivo2.txt. Terminou em cerca de 13 segundos, produzindo 126K correspondências. Aqui está a saída de time para o mesmo:

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

Eu corri código awk @ Inian:

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

It was way slower than the Perl solution, since it is looping 14K times for each line in file2.txt – which is really expensive. It aborted after processing 592K records of file2.txt and producing 40K matched lines. Here is how long it took:

 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 usá-lo assim:

 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 …

Você também pode usar o Perl para isso:

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

Sample Data:

 %_STATION@gaurav * /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 %_STATION@gaurav * /root/ga/study/pl> 

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

 %_STATION@gaurav * /root/ga/pl> ./comp.pl file1.txt file2.txt ; cat output_comp date1|bar1|number1 date2|bar2|number2 date2|foo2|number2 date1|foo1|number1 %_STATION@gaurav * /root/ga/pl> 

Roteiro:

 %_STATION@gaurav * /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 ; %_STATION@gaurav * /root/ga/pl> 

Obrigado.

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