Melhorando o desempenho do grepping sobre um arquivo enorme

Eu tenho FILE_A, que possui mais de 300.000 linhas, e FILE_B, que possui mais de 30 milhões de linhas. Criei um script Bash que greps cada linha em FILE_A em FILE_B e grava o resultado do grep em um novo arquivo.

Todo esse processo leva mais de 5 horas.

Como posso melhorar o desempenho do meu script?

Estou usando grep -F -m 1como o comando grep. FILE_A aparece assim:

123456789 
123455321

e FILE_B é assim:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

Então, com o Bash, tenho um whileloop que escolhe a próxima linha em FILE_A e a coloca em FILE_B. Quando o padrão é encontrado em FILE_B, eu o escrevo no arquivo result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile

Tente usar grep --file==FILE_A. Ele quase certamente carrega os padrões na memória, o que significa que ele só procurará FILE_B uma vez.

grep -F -m1 --file==300KFile 30MFile

Aqui está uma resposta Perl para a posteridade. Eu faço isso rotineiramente para combinar linhas de 1 milhão a 30-35 milhões de linhas. Demora cerca de 10 segundos para terminar.

Primeiro, faça o hash do arquivo FILE_A:

my %simple_hash;
open my $first_file, '<', 'FILE_A' or die "What have you done?! $!";
while (<$first_file>) {
  chomp;                 ## Watch out for Windows newlines
  $simple_hash{$_} = 1;  ## There may be an even faster way to define this
}
close $first_file;

Então, se seu arquivo grande estiver delimitado e souber qual coluna seguir, verifique apenas a existência da chave de hash ao executar FILE_B, o que é muito, muito mais rápido do que verificar a correspondência de igualdade ou expressão regular:

open my $second_file, '<', 'FILE_B' or die "Oh no, not again.. $!";
while (<$second_file>) {
  my ($col1, undef) = split ',';
  if (exists($simple_hash{$col1}) {
    print $_;
  }
}
close $second_file;

Se o seu arquivo de destino maior não puder ser analisado de maneira adequada, esse script perderá seu valor, uma vez que grande parte de sua velocidade vem de não ter que ativar o mecanismo de expressão regular .

Se você não se importa com alguma programação mais envolvida, considere usar árvores de sufixos (ou uma variante).

Você pode pré-processar FILE_Busando o algoritmo de Ukkonen em tempo linear. Em seguida, você consulta cada linha no FILE_Atempo linear no comprimento da linha e obtém todos os números de linhas correspondentes (pode ser necessário adaptar um pouco a árvore) que você pode gravar em um arquivo de resultado.

Todo o procedimento é executado no tempo O (n + Nm) se n é o comprimento de FILE_B, Né o número de linhas em FILE_Ae m é o comprimento da linha mais longa FILE_A- esse é o tempo de execução essencialmente linear. Supera o tempo quadrático que sua abordagem original precisa por magnitudes.

Encontrei a --mmapbandeira recentemente, não tive a chance de testá-la, mas ficarei feliz em saber das suas descobertas. Aqui está a descrição da página de manual:

--mmap If  possible, use the mmap(2) system call to read input, instead
      of the default read(2) system call.  In some situations,  --mmap
      yields  better performance.  However, --mmap can cause undefined
      behavior (including core dumps) if an input file  shrinks  while
      grep is operating, or if an I/O error occurs.

Veja isto ou isto para mais informações sobre mmap.

Por que você não coloca esse arquivo em um banco de dados? Os bancos de dados são realmente bons para fazer uma junção eficiente de mesclagem, hash e loop aninhado dessa maneira. E eles são realmente bons em utilizar memória virtual