Grep número enorme de padrões de arquivo enorme

Question

Eu tenho um arquivo que está crescendo cerca de 200.000 linhas por dia, e é formado com blocos de três linhas, como tal:

1358726575123       # key
    Joseph Muller   # name
    carpenter       # job
9973834728345
    Andres Smith
    student
7836472098652
    Mariah Anthony
    dentist

Agora, tenho outro arquivo do qual extraio cerca de 10.000 padrões de chave, como 1358726575123 . Em seguida, executo um loop for com esses padrões e tenho que verificá-los no primeiro arquivo. Se o arquivo não contiver esse padrão, salve o padrão em um terceiro arquivo para processamento adicional:

for number in $(grep -o '[0-9]\{12\}' file2); do  # finds about 10.000 keys
     if ! grep -q ^$number$ file1; then           # file1 is a huge file
         printf "$number\n" >>file3               # we'll process file3 later
     fi
done

O exemplo codifica um arquivo enorme 10.000 vezes, e eu executo esse loop sobre uma vez por minuto, durante o dia inteiro .

Como o arquivo enorme continua crescendo, o que posso fazer para tornar tudo isso mais rápido e economizar um pouco de CPU? Gostaria de saber se classificar o arquivo de alguma forma pela sua chave (em caso afirmativo, como?) Ou usando um banco de dados em vez de texto simples ajudaria ...

    

Answer 1

Esta resposta é baseada na resposta awk postada por potong ..
É duas vezes mais rápido que o método comm (no meu sistema), pelas mesmas 6 milhões de linhas no arquivo principal e 10 mil chaves ... (agora atualizado para usar FNR, NR)

Embora awk seja mais rápido que o seu sistema atual, e você e seu computador tenham algum espaço para respirar, esteja ciente de que quando o processamento de dados é tão intenso quanto você descreveu, você obterá os melhores resultados gerais mudar para um banco de dados dedicado; por exemplo. SQlite, MySQL ...

awk '{ if (/^[^0-9]/) { next }              # Skip lines which do not hold key values
       if (FNR==NR) { main[$0]=1 }          # Process keys from file "mainfile"
       else if (main[$0]==0) { keys[$0]=1 } # Process keys from file "keys"
     } END { for(key in keys) print key }' \
       "mainfile" "keys" >"keys.not-in-main"

# For 6 million lines in "mainfile" and 10 thousand keys in "keys"

# The awk  method
# time:
#   real    0m14.495s
#   user    0m14.457s
#   sys     0m0.044s

# The comm  method
# time:
#   real    0m27.976s
#   user    0m28.046s
#   sys     0m0.104s

Answer 2

O problema, claro, é que você execute grep no arquivo grande 10.000 vezes. Você deve ler os dois arquivos apenas uma vez. Se você quiser ficar de fora das linguagens de script, você pode fazer assim:

1. Extraia todos os números do arquivo 1 e classifique-os
2. Extraia todos os números do arquivo 2 e classifique-os
3. Executar comm nas listas classificadas para obter o que está apenas na segunda lista

Algo parecido com isto:

$ grep -o '^[0-9]\{12\}$' file1 | sort -u -o file1.sorted
$ grep -o  '[0-9]\{12\}'  file2 | sort -u -o file2.sorted
$ comm -13 file1.sorted file2.sorted > file3

Veja man comm .

Se você pudesse truncar o arquivo grande todos os dias (como um arquivo de log), você poderia manter um cache de números ordenados e não precisaria analisá-lo todo o tempo todo.

    

Answer 3

Sim, definitivamente use um banco de dados. Eles são feitos exatamente para tarefas como essa.

    

Answer 4

Isso pode funcionar para você:

 awk '/^[0-9]/{a[$0]++}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

EDITAR:

O script alterado para permitir duplicatas e chaves desconhecidas em ambos os arquivos ainda produz chaves do primeiro arquivo não presente no segundo:

 awk '/^[0-9]/{if(FNR==NR){a[$0]=1;next};if($0 in a){a[$0]=2}}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

    

Answer 5

Com tantos dados, você deve realmente mudar para um banco de dados. Enquanto isso, uma coisa que você deve fazer para chegar perto do desempenho decente é não pesquisar file1 separadamente para cada chave. Execute um único grep para extrair todas as chaves não excluídas de uma só vez. Como grep também retorna linhas que não contêm uma chave, filtre-as.

grep -o '[0-9]\{12\}' file2 |
grep -Fxv -f - file1 |
grep -vx '[0-9]\{12\}' >file3

( -Fx significa pesquisar linhas inteiras, literalmente. -f - significa ler uma lista de padrões da entrada padrão.)

    

Answer 6

Permita-me reforçar o que os outros disseram, "Leve-te a um banco de dados!"

Existem binários do MySQL disponíveis gratuitamente para a maioria das plataformas.

Por que não o SQLite? É baseado em memória, carregando um arquivo flat ao iniciá-lo e fechando-o quando terminar. Isso significa que, se o computador falhar ou o processo de SQLite desaparecer, o mesmo acontece com todos os dados.

Seu problema parece apenas algumas linhas de SQL e será executado em milissegundos!

Depois de instalar o MySQL (que eu recomendo sobre outras opções), eu gastaria $ 40 pelo da O'Reilly. SQL Cookbook por Anthony Molinaro, que tem muitos padrões de problemas, começando com simples SELECT * FROM table consultas e passando por agregações e várias associações.

    

Answer 7

Não tenho certeza se esse é o resultado exato que você está procurando, mas provavelmente a maneira mais fácil é:

grep -o '[0-9]\{12\}' file2 | sed 's/.*/^&$/' > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Você também pode usar:

sed -ne '/.*\([0-9]\{12\}.*/^$/p' file2 > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Cada um deles cria um arquivo de padrão temporário que é usado para obter os números do arquivo grande ( file1 ).

    

Answer 8

Concordo plenamente com você ao obter um banco de dados (o MySQL é bastante fácil de usar). Até que você comece a correr, eu gosto da solução comm do Angus, mas muitas pessoas estão tentando com grep e errando que eu pensei em mostrar a (ou pelo menos uma) maneira correta de fazer isso com grep .

grep -o '[0-9]\{12\}' keyfile | grep -v -f <(grep -o '^[0-9]\{12\}' bigfile) 

O primeiro grep obtém as chaves. O terceiro grep (no <(...) ) pega todas as chaves usadas no arquivo grande, e o <(...) passa como um arquivo como um argumento para -f no segundo grep. Isso faz com que o segundo grep o use como uma lista de linhas a serem correspondidas. Em seguida, ele usa isso para corresponder a sua entrada (a lista de chaves) do canal (primeiro grep ) e imprime todas as chaves extraídas do arquivo de chaves e não ( -v ) do arquivo grande.

É claro que você pode fazer isso com arquivos temporários que você precisa acompanhar e lembre-se de excluir:

grep -o '[0-9]\{12\}'  keyfile >allkeys
grep -o '^[0-9]\{12\}' bigfile >usedkeys
grep -v -f usedkeys allkeys

Isso imprime todas as linhas em allkeys que não aparecem em usedkeys .

    

Answer 9

O arquivo de chave não muda? Então você deve evitar pesquisar as entradas antigas de novo e de novo.

Com tail -f , você pode obter a saída de um arquivo crescente.

tail -f growingfile | grep -f keyfile 

grep -f lê os padrões de um arquivo, uma linha como um padrão.

    

Answer 10

Não postarei minha resposta porque pensei que essa quantidade de dados não deveria ser processada com um shell script, e a resposta certa para usar um banco de dados já foi dada. Mas desde agora existem outras 7 abordagens ...

Lê o primeiro arquivo na memória, em seguida, consulta o segundo arquivo em busca de números e verifica se os valores estão armazenados na memória. Deve ser mais rápido do que vários grep s, se você tiver memória suficiente para carregar o arquivo inteiro, isto é.

declare -a record
while read key
do
    read name
    read job
    record[$key]="$name:$job"
done < file1

for number in $(grep -o '[0-9]\{12\}' file2)
do
    [[ -n ${mylist[$number]} ]] || echo $number >> file3
done

    

Answer 11

Concordo com @ jan-steinman que você deve usar um banco de dados para esse tipo de tarefa. Há muitas maneiras de hackear uma solução com um script de shell, como as outras respostas mostram, mas fazê-lo dessa maneira levará a muita miséria se você for usar e manter o código por qualquer período de tempo maior que apenas um projeto de lançamento de um dia.

Supondo que você esteja em uma caixa do Linux, provavelmente você instalou o Python por padrão, o que inclui a biblioteca sqlite3 a partir do Python v2.5. Você pode verificar sua versão do Python com:

% python -V
Python 2.7.2+

Eu recomendo usar biblioteca sqlite3 porque é uma solução simples baseada em arquivo que existe para todas as plataformas (incluindo dentro do seu navegador da Web!) e não requer que um servidor seja instalado. Essencialmente, configuração zero e manutenção zero.

Abaixo está um script python simples que irá analisar o formato de arquivo que você deu como um exemplo e, em seguida, faz uma simples consulta "selecionar todos" e gera todos os resultados armazenados no banco de dados.

#!/usr/bin/env python

import sqlite3
import sys

dbname = '/tmp/simple.db'
filename = '/tmp/input.txt'
with sqlite3.connect(dbname) as conn:
    conn.execute('''create table if not exists people (key integer primary key, name text, job text)''')
    with open(filename) as f:
        for key in f:
            key = key.strip()
            name = f.next().strip()
            job = f.next().strip()
            try:
                conn.execute('''insert into people values (?,?,?)''', (key, name, job))
            except sqlite3.IntegrityError:
                sys.stderr.write('record already exists: %s, %s, %s\n' % (key, name, job))
    cur = conn.cursor()

    # get all people
    cur.execute('''select * from people''')
    for row in cur:
        print row

    # get just two specific people
    person_list = [1358726575123, 9973834728345]
    cur.execute('''select * from people where key in (?,?)''', person_list)
    for row in cur:
        print row

    # a more general way to get however many people are in the list
    person_list = [1358726575123, 9973834728345]
    template = ','.join(['?'] * len(person_list))
    cur.execute('''select * from people where key in (%s)''' % (template), person_list)
    for row in cur:
        print row

Sim, isso significa que você precisará aprender um pouco de SQL , mas valerá a pena a longo prazo. Além disso, em vez de analisar seus arquivos de log, talvez você possa gravar dados diretamente no banco de dados sqlite.