O Unix grep trabalha mais rápido com termos de pesquisa longos ou curtos?

Question

É mais rápido procurar termos de pesquisa longos ou curtos? Ou isso afeta a velocidade? Em outras palavras, você deve tornar os termos de pesquisa tão precisos quanto possível?

Existem mais de 100 000 ficheiros e cada ficheiro contém entre 20 e mais de 5000 linhas de dados. Normalmente, o grep é usado para encontrar apenas uma instância do termo de pesquisa.

Digamos que o termo de pesquisa seja SEARCHTERM , e será uma linha como esta:

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

É mais rápido procurar por "SEARCH" ou "SEARCHTERM"? Digamos que, nesse caso, não nos importamos se também encontrarmos correspondências em outras linhas não relacionadas.

É assim que eu faço atualmente:

grep NAD+DP 123* | grep SEARCHTERM

Mas eu acho bastante lento ainda. Geralmente, demora cerca de 3 a 5 minutos para encontrar os dados, mesmo quando conheço o nome do arquivo bruto, o que limita o intervalo a cerca de 10 000 arquivos.

Então, um termo de pesquisa mais longo ou mais curto ajudaria? Até onde eu sei, o grep procura por "blocos" de palavras de um certo tamanho?

    

Answer 1

Algum material de referência:

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.

de Por que o GNU grep é rápido .

The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). [...] In general, the algorithm runs faster as the pattern length increases.

de Algoritmo de pesquisa de strings Boyer – Moore .

Conclusão: use strings mais longas .

Agora, um pouco de referência para se divertir:

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v' # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

Resultados: 0,952s é a média para a string curta, 0,244s é a média para a string longa.

NB : O tamanho não é o único critério a ser considerado.

    

Answer 2

Você pode tentar usar SEARCH ou SEARCHTERM. Também tente alterar a ordem dos dois comandos grep. De qualquer forma, a única opção útil provavelmente será usar vários núcleos de CPU para uma pesquisa. Veja o comando parallel .

    

Answer 3

Eu não acho que especificar um termo de pesquisa mais específico o torne notavelmente mais rápido.

Com tantos arquivos para pesquisar, você precisa indexar seus dados para fazer pesquisas mais rapidamente.

Eu posso sugerir algumas maneiras:

• Crie um banco de dados (PostgreSQL ou MySQL), importe seus dados para o banco de dados - um arquivo em uma linha, adicione o índice FTS (pesquisa de texto completo). Crie algum utilitário para consultar o banco de dados.

• Importe dados para o banco de dados de maneira mais granular, provavelmente uma linha em uma linha (ou talvez mais de uma tabela), crie índices para que seus dados sejam pesquisáveis usando índices. Crie algum utilitário para consultar o banco de dados.

• Adicione seus arquivos ao repositório git , compacte-o usando git gc , use git grep para pesquisar. Na minha experiência, git grep pode ser mais rápido que o padrão grep por fator de 10x-100x.

Answer 4

Logicamente, um período mais curto exigirá menos tempo de CPU, já que grep estará fazendo

if (filechar[i] == pattern[i]) ...

menos vezes. Na realidade, eu diria que um grep seria ligado a E / S e não ligado à CPU, por isso não importa.