Grepping sobre um desempenho de arquivo enorme

Question

Eu tenho FILE_A, que tem mais de 300 mil linhas e FILE_B, que tem mais de 30 milhões de linhas. Eu criei um script bash que faz com que cada linha em FILE_A passe por FILE_B e grave o resultado do grep em um novo arquivo.

Todo este processo demora mais de 5 horas.

Estou procurando sugestões sobre se você vê alguma maneira de melhorar o desempenho do meu script.

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

123456789 
123455321

e FILE_B são assim:

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

Então, com o bash, eu tenho um loop while que escolhe a próxima linha em FILE_A e a passa em FILE_B. Quando o padrão é encontrado em FILE_B, escrevo para o resultado.txt.

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

Agradecemos antecipadamente por sua ajuda.

    

Answer 1

A chave para o desempenho é ler o arquivo enorme apenas uma vez.

Você pode passar vários padrões para o grep colocando-os em linhas separadas. Isso geralmente é feito dizendo ao grep para ler padrões de um arquivo:

grep -F -f 300KFile 30MFile

Isso exibe as correspondências na ordem do arquivo grande e imprime linhas que correspondem a vários padrões apenas uma vez. Além disso, isso procura padrões em qualquer lugar da linha; por exemplo, se o arquivo padrão contiver 1234 , as linhas como 123456,345678,2348962342 e 478912,1211138,1234 corresponderão.

Você pode restringir as correspondências exatas da coluna pré-processando o padrão. Por exemplo, se os padrões não contiverem nenhum caractere especial ()?*+\|[]{} :

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile

Se for importante manter apenas a primeira correspondência para cada padrão, faça um primeiro passo para extrair somente as linhas relevantes como acima, então faça uma segunda passagem em awk ou perl que rastreie padrões que já foram vistos.

<300KFile sed -e 's/^/(^|,)/' -e 's/$/($|,)/' |
grep -E -f - 30MFile |
perl -l -F, -ape '
    BEGIN {
        open P, "300KFile" or die;
        %patterns = map {chomp; $_=>1} <P>;
        close P;
    }
    foreach $c (@F) {
        if ($patterns{$c}) {
            print;
            delete $patterns{$c};
        }
    }
'

    

Answer 2

Você pode executar o seguinte?

grep -Ff FILE_A FILE_B > FILE_C

Agora você pode executar seu script apenas nos arquivos A e C.

Atualização: Aguarde ... Isso preserva o pedido?

Outra atualização: Mais alguns processos são necessários para manter o pedido. Isso me dá os mesmos resultados do seu roteiro original. Testado em 300 mil linhas em FILE_A e apenas 300 mil linhas em FILE_B, 125 minutos em comparação com 14 segundos.

#! /bin/bash
grep -Ff FILE_A FILE_B > FILE_B_TMP
grep -oFf FILE_A FILE_B_TMP > FILE_A_SHUFF
grep -Ff FILE_A_SHUFF FILE_A > FILE_A_TMP

while read -r line; do
   grep -F -m1 "$line" FILE_B_TMP
done < FILE_A_TMP > result.txt

    

Answer 3

Eu acredito que a comunicação pode ter um desempenho melhor:

comm -12 300KFile <(sed 's/,.*//' 30MFile)

ps. Não tenho certeza se a string 123123 fromm 300KFile deve corresponder à string gdwyedg,123123,hfsjdkfh no arquivo 30M. Como no seu script, ele combina, mas no meu script não.

    

Answer 4

Eu acredito que as soluções baseadas no grep ainda precisam comparar cada registro em FILE_A com cada registro em FILE_B. Como pelo menos N-1 registros em FILE_A não corresponderão a um registro específico em FILE_B, há muita redundância nessa abordagem. Se, por outro lado, os arquivos fossem classificados, seria possível descartar um grande número de testes para cada comparação. Por isso, algo como ....

#!/bin/bash

# NB a faster solution would be to sort the smaller file in a seperate process
# you might also want to set a buffer size for large files
sort $1 > /tmp/$$.a
sort $2 > /tmp/$$.b

join -j1 -t',' /tmp/$$.a /tmp/$$.b

rm -f /tmp/$$.?

(não testado)

Mas observe que a ordem das entradas será alterada, isso pressupõe que você deseja corresponder a uma coluna de dados específica em FILE_B e a classificação também apresenta uma sobrecarga, mas o resultado deve ser mais rápido para esses tamanhos de arquivo.