Mejora del rendimiento para grepping sobre un archivo enorme

10

Tengo FILE_A que tiene más de 300,000 líneas y FILE_B que tiene más de 30 millones de líneas. Creé un script Bash que agrupa cada línea en FILE_A en FILE_B y escribe el resultado del grep en un nuevo archivo.

Todo este proceso lleva más de 5 horas.

¿Cómo puedo mejorar el rendimiento de mi script?

Estoy usando grep -F -m 1como el comando grep. FILE_A tiene este aspecto:

123456789 
123455321

y FILE_B es así:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

Entonces, con Bash tengo un whilebucle que selecciona la siguiente línea en FILE_A y la ajusta en FILE_B. Cuando el patrón se encuentra en FILE_B, lo escribo en el archivo result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile
rogerio_marcio
fuente

Respuestas:

17

Intenta usar grep --file==FILE_A. Es casi seguro que carga los patrones en la memoria, lo que significa que solo escaneará FILE_B una vez.

grep -F -m1 --file==300KFile 30MFile
Gort the Robot
fuente
Esto funcionaría solo suponiendo que tengo suficiente memoria, ¿verdad?
rogerio_marcio
Honestamente, no lo he probado en archivos de ese tamaño, pero creo que debería mejorar drásticamente tu velocidad. Si está en una máquina moderna, no debería tener problemas para guardar un archivo de 300K en la memoria. (O una de 30M para el caso.)
Gort the Robot
cuando utilicé la opción -f (--file) básicamente recreé el 30MFile. ¿Estoy haciendo algo mal?
rogerio_marcio
Hmmm ... ¿quizás el archivo 300K tenía una línea en blanco?
Gort the Robot
justo en el lugar! ¡eso fue todo! eso funcionó perfectamente, ¡terminó en 30 segundos! ¡¡gracias!!
rogerio_marcio
2

Aquí hay una respuesta de Perl para la posteridad. Rutinariamente hago esto para hacer coincidir líneas de 1M con líneas de 30-35M. Tarda alrededor de 10 segundos en terminar.

Primero, hash up FILE_A:

my %simple_hash;
open my $first_file, '<', 'FILE_A' or die "What have you done?! $!";
while (<$first_file>) {
  chomp;                 ## Watch out for Windows newlines
  $simple_hash{$_} = 1;  ## There may be an even faster way to define this
}
close $first_file;

Luego, si su archivo grande está delimitado y sabe qué columna debe seguir, verifique solo la existencia de la clave hash mientras ejecuta FILE_B, que es mucho, mucho más rápido que verificar la igualdad o la coincidencia de expresiones regulares:

open my $second_file, '<', 'FILE_B' or die "Oh no, not again.. $!";
while (<$second_file>) {
  my ($col1, undef) = split ',';
  if (exists($simple_hash{$col1}) {
    print $_;
  }
}
close $second_file;

Si su archivo de destino más grande no se puede analizar bien, entonces este script pierde su valor ya que gran parte de su velocidad proviene de no tener que encender el motor de expresión regular .

Menta
fuente
1

Si no le importa una programación más complicada, considere usar árboles de sufijos (o una variante).

Puede preprocesar FILE_Busando el algoritmo de Ukkonen en tiempo lineal. Luego, consulta cada línea en el FILE_Atiempo lineal en la longitud de la línea y obtiene todos los números de línea que coinciden (puede que necesite adaptar el árbol un poco) que puede escribir en un archivo de resultados.

Todo el procedimiento se ejecuta en el tiempo O (n + Nm) si n es la longitud de FILE_B, Nes el número de líneas FILE_Ay m es la longitud de la línea más larga FILE_A, esto es esencialmente tiempo de ejecución lineal. Supera el tiempo cuadrático que tu enfoque original necesita por magnitud.

Rafael
fuente
1

Encontré la --mmapbandera últimamente, no tuve la oportunidad de probarla, pero estaré feliz de escuchar sus hallazgos. Aquí está la descripción de la página del manual:

--mmap If  possible, use the mmap(2) system call to read input, instead
      of the default read(2) system call.  In some situations,  --mmap
      yields  better performance.  However, --mmap can cause undefined
      behavior (including core dumps) if an input file  shrinks  while
      grep is operating, or if an I/O error occurs.

Vea esto o esto para obtener más información sobre mmap.

Ramzi Kahil
fuente
Definitivamente voy a intentarlo y te diré cómo va. ¿Qué tan probable es que encuentre un volcado de núcleo?
rogerio_marcio
@rogerio_marcio Bueno, según entiendo el hombre, "si el archivo se encoge mientras grep está funcionando o si se produce un error de E / S". Probablemente no, pero deberías saberlo mejor. (Si, como supongo, el archivo no se ha tocado mientras grep, esto no debería suceder)
Ramzi Kahil
Para probar que la --mmapdosis no arroja nada, recomendaría una carrera con --mmapy otra sin. Y luego use wcpara ver que tiene la misma cantidad de salida: esta debería ser una prueba sólida teniendo en cuenta que ejecutamos 2 veces grep, y solo difería un indicador.
Ramzi Kahil
@rogerio_marcio ¿Has probado esto? Alguna idea?
Ramzi Kahil
-1

¿por qué no pones ese archivo en una base de datos? Las bases de datos son realmente buenas para hacer una combinación eficiente, hash, unión de bucle anidado como esta. Y son muy buenos para utilizar la memoria virtual.

Andyz Smith
fuente
Todo lo que está haciendo con todas las otras respuestas es reinventar la rueda de la base de datos
Andyz Smith