Extraindo linhas por chave de um arquivo muito grande

Question

Eu tenho um arquivo de texto de linha de 42M. Os nove primeiros caracteres de cada linha são uma tecla numérica. Qual é a maneira mais eficiente de extrair apenas as linhas cuja chave existe em outra lista de aproximadamente 1,5 milhões de chaves? O arquivo e a lista de chaves são classificados.

    

Answer 1

Usar awk deve ser eficiente o suficiente - fornece matrizes associativas incorporadas, em que o tempo de pesquisa da chave é logaritmicamente proporcional ao número de chaves (de sua tabela de consulta - que é relativamente pequena no seu exemplo).

Para sua entrada, isso seria:

42M * log2(1.5M) -> 42M * 20 key comparisons 

(onde M significa 10 ^ 6)

No caso do seu awk usar tabelas de hash, cada consulta de chave custaria apenas uma quantidade de tempo constante.

Um exemplo de uma solução eficiente baseada no awk (usando o separador de campo padrão):

$ awk 'ARGIND == 1 { a[$1] = 1; next } a[$1] { print $0 }' keys.dat largefile.dat

Como as duas entradas estão ordenadas, você pode escrever um script que seja mais eficiente (com um tempo de execução dimensionado linearmente com os dois tamanhos de arquivo de entrada). Mas custaria mais tempo programá-lo.

Ou você pode usar join , que espera arquivos classificados como entrada - restrição é que sua chave precisa ser classificada em ordem alfabética - e talvez você precise ajustar o formato de saída. Por exemplo:

$ join -j1 keys.dat largefile.dat

Use -t para configurar o separador de campos e -o para ajustar o formato de saída.

Isso deve ser executado no tempo linear ao tamanho da entrada.

    

Answer 2

Observe que esse método usa o comprimento de uma chave de comprimento fixo que começa no primeiro byte do registro.

Ao usar \x01 (ou qualquer caractere único de byte único) como um separador de campo temporário, os registros podem ser manipulados com mais facilidade.

join -t$'\x01' <(sed -r 's/.{9}/&\x01/' main) <(cut -b -9 keys) |sed -r 's/(.{9}).//'

O exemplo do

maxschlepzig awk foi mais rápido para 45.000.000 de registros, mas falhou em um arquivo maior. Quanta RAM livre você tem?

Aqui estão os resultados:

45,000,000 unique records, 1,500,000 keys
=========================
awk

real    0m31.971s
user    0m28.782s
sys     0m2.972s

join

real    0m53.733s
user    0m54.255s
sys     0m0.708s

(2x45) 90,000,000 records, 1,500,000 keys
=========================
awk
awk: (FILENAME=main2 FNR=54334297) fatal: assoc_lookup: bucket->ahname_str: can't allocate 11 bytes of memory (Cannot allocate memory)

join

real    1m35.306s
user    1m34.754s
sys     0m1.344s

===================

    

Answer 3

Supondo que seja um arquivo baseado em linha, grep deve ser bastante eficiente. Use -f keyfile e -F para strings fixas:

grep -F -f keys textfile

Nota: preste atenção ao aviso sobre falsos positivos de PeterO nos comentários abaixo.