O greix do Unix funciona mais rápido com termos de pesquisa longos ou curtos?

8

É 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 o mais preciso possível?

Existem mais de 100 000 arquivos e cada arquivo 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 SEARCHTERMe ele será seguido assim:

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

É mais rápido procurar "SEARCH" ou "SEARCHTERM"? Digamos que, neste 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 acho isso muito lento, ainda. Geralmente, leva cerca de 3-5 minutos para encontrar os dados, mesmo quando eu conheço o nome do arquivo bruto, que limita o intervalo a cerca de 10.000 arquivos.

Então, um termo de pesquisa maior ou menor ajudaria? Até onde eu sei, o grep procura por "blocos" de palavras de um determinado comprimento?

Juha Untinen
fonte

Respostas:

8

Algum material de referência:

O GNU grep usa o conhecido algoritmo Boyer-Moore, que procura primeiro a letra final da string de destino, e usa uma tabela de pesquisa para dizer a que distância ele pode pular a entrada sempre que encontrar um caracter não correspondente.

de Por que o GNU grep é rápido .

O algoritmo processa previamente a sequência que está sendo pesquisada (o padrão), mas não a sequência que está sendo pesquisada (o texto). [...] Em geral, o algoritmo roda mais rápido à medida que o comprimento do padrão aumenta.

do algoritmo de pesquisa de string de Boyer-Moore .

Conclusão: Use seqüências 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 da cadeia curta, 0.244s é a média da cadeia longa.

NB : O comprimento não é o único critério a ser levado em consideração.

SylvainD
fonte
0

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

golimar
fonte
0

Não acho que especificar um termo de pesquisa mais específico o torne visivelmente mais rápido.

Com tantos arquivos para pesquisar, você precisa, de alguma forma, indexar seus dados para acelerar a pesquisa.

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 de modo que seus dados sejam pesquisáveis ​​usando índices. Crie algum utilitário para consultar o banco de dados.

  • Adicione seus arquivos ao gitrepositório, compacte-o usando git gc, use git greppara pesquisar. Na minha experiência, git greppode ser mais rápido que o padrão greppor fator de 10x-100x.

mvp
fonte
0

Logicamente, um curto prazo vai exigir menos tempo de CPU, como grepvai fazer

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

menos vezes. Na realidade, eu acho que a grepseria ligada à E / S e não à CPU, por isso não importa.

Scott
fonte
11
Surpreendentemente, isso está errado, pois o grep está usando um algoritmo realmente inteligente, consulte a minha resposta.
SylvainD
quanto mais longa a cadeia de pesquisa, os mais caracteres que pode pular quando ele encontra uma incompatibilidade, portanto, a busca será mais rápido
phuclv