¿Unix grep funciona más rápido con términos de búsqueda largos o cortos?

8

¿Es más rápido buscar términos de búsqueda largos o cortos? ¿O afecta a la velocidad? En otras palabras, ¿debe hacer que los términos de búsqueda sean lo más exactos posible?

Hay más de 100 000 archivos y cada archivo contiene entre 20 y más de 5000 filas de datos. Por lo general, el grep se usa para encontrar solo una instancia del término de búsqueda.

Digamos que el término de búsqueda es SEARCHTERM, y estará en una fila como esta:

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

¿Es más rápido buscar "SEARCH" o "SEARCHTERM"? Digamos que en este caso no nos importa si también encontramos coincidencias en otras líneas no relacionadas.

Así es como lo hago actualmente:

grep NAD+DP 123* | grep SEARCHTERM

Pero lo encuentro bastante lento, aún. Por lo general, toma alrededor de 3-5 minutos encontrar los datos, incluso cuando conozco el nombre de archivo aproximado, lo que limita el rango a alrededor de 10 000 archivos.

Entonces, ¿ayudaría un término de búsqueda más largo o más corto? Hasta donde yo sé, grep busca "bloques" de palabras de cierta longitud?

Juha Untinen
fuente

Respuestas:

8

Algún material de referencia:

GNU grep usa el conocido algoritmo de Boyer-Moore, que busca primero la letra final de la cadena de destino, y usa una tabla de búsqueda para indicar qué tan adelante puede saltarse la entrada cada vez que encuentra un carácter que no coincide.

de qué GNU grep es rápida .

El algoritmo procesa previamente la cadena que se busca (el patrón), pero no la cadena que se busca (el texto). [...] En general, el algoritmo se ejecuta más rápido a medida que aumenta la longitud del patrón.

del algoritmo de búsqueda de cadenas Boyer – Moore .

Conclusión: use cadenas más largas .

Ahora, un poco de referencia para la diversión:

# 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 es el promedio de la cadena corta, 0.244s es el promedio de la cadena larga.

NB : La longitud no es el único criterio a tener en cuenta.

SylvainD
fuente
0

Puede probarlo usando SEARCH o SEARCHTERM. También intente cambiar el orden de los dos comandos grep. De todos modos, la única opción útil será probablemente usar varios núcleos de CPU para una búsqueda. Ver el parallelcomando.

golimar
fuente
0

No creo que especificar un término de búsqueda más específico lo haga notablemente más rápido.

Con tantos archivos para buscar, necesita indexar de alguna manera sus datos para agilizar la búsqueda.

Puedo sugerir algunas formas:

  • Cree una base de datos (PostgreSQL o MySQL), importe sus datos a la base de datos: un archivo en una fila, agregue el índice FTS (búsqueda de texto completo). Cree alguna utilidad para consultar la base de datos.

  • Importe datos a la base de datos de forma más granular, probablemente una línea en una fila (o tal vez más de una tabla), cree índices de modo que sus datos puedan buscarse utilizando índices. Cree alguna utilidad para consultar la base de datos.

  • Agregue sus archivos al gitrepositorio, compacte usando git gc, use git greppara buscar. En mi experiencia, git greppuede ser más rápido que el estándar greppor un factor de 10x-100x.

mvp
fuente
0

Lógicamente, un plazo más corto requerirá menos tiempo de CPU, como lo grephará

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

menos veces En realidad, supongo que a grepestaría unida a E / S y no a CPU, por lo que no importará.

Scott
fuente
1
Sorprendentemente, esto está mal ya que grep está utilizando un algoritmo realmente inteligente, consulte mi respuesta.
SylvainD
cuanto mayor sea la cadena de búsqueda, los más caracteres se puede omitir cuando se encuentra una desigualdad, por lo tanto, la búsqueda será más rápido
phuclv