La forma más rápida de encontrar líneas de un archivo de otro archivo más grande en Bash

Tengo dos archivos, file1.txt y file2.txt . file1.txt tiene aproximadamente 14K líneas y file2.txt tiene aproximadamente 2 billones. file1.txt tiene un solo campo f1 por línea, mientras que file2.txt tiene 3 campos, f1 a f3 , delimitados por | .

Quiero encontrar todas las líneas de file2.txt donde f1 de file1.txt coincide con f2 de file2.txt (o en cualquier lugar de la línea si no queremos file2.txt más tiempo dividiendo los valores de file2.txt ).

archivo1.txt (alrededor de 14K líneas, no ordenadas ):

 foo1 foo2 ... bar1 bar2 ... 

archivo2.txt (alrededor de 2 mil millones de líneas, no ordenadas ):

 date1|foo1|number1 date2|foo2|number2 ... date1|bar1|number1 date2|bar2|number2 ... 

Resultado esperado:

 date1|foo1|number1 date2|foo2|number2 ... date1|bar1|number1 date2|bar2|number2 ... 

Esto es lo que he intentado y parece que me llevará varias horas ejecutar:

 fgrep -F -f file1.txt file2.txt > file.matched 

Me pregunto si hay una manera mejor y más rápida de hacer esta operación con los comandos comunes de Unix o con un pequeño script.

Una solución Perl. [Ver la Nota a continuación.]

Use un hash para el primer archivo. Mientras lee el archivo grande línea por línea, extraiga el campo por expresiones regulares (captura el primer patrón entre || ) o split (obtiene la segunda palabra) e imprímalo si exists . Probablemente difieren un poco en velocidad (cronometralos). La verificación defined no es necesaria en la expresión regular mientras que para el uso split // (definido-o) que los cortocircuitos.

 use warnings; use strict; # If 'prog smallfile bigfile' is the preferred use die "Usage: $0 smallfile bigfile\n" if @ARGV != 2; my ($smallfile, $bigfile) = @ARGV; open my $fh, '<', $smallfile or die "Can't open $smallfile: $!"; my %word = map { chomp; $_ => 1 } <$fh>; open $fh, '<', $bigfile or die "Can't open $bigfile: $!"; while (<$fh>) { exists $word{ (/\|([^|]+)/)[0] } && print; # Or #exists $word{ (split /\|/)[1] // '' } && print; } close $fh; 

Evitar la twig if y usar el cortocircuito es más rápido, pero solo muy poco. En miles de millones de líneas estos ajustes se sumn, pero de nuevo no demasiado. Puede ser (o no) un poco más rápido leer el archivo pequeño línea por línea, en lugar de en el contexto de la lista como se indicó anteriormente, pero esto no debería ser notable.

Actualizar Escribir en STDOUT guarda dos operaciones y repetidas veces muestro que es un poco más rápido que escribir en un archivo. Tal uso también es consistente con la mayoría de las herramientas de UNIX, así que cambié para escribir en STDOUT . A continuación, la prueba exists no es necesaria y descartarla ahorra una operación. Sin embargo, constantemente obtengo mejores tiempos de ejecución con él , mientras que también transmite el propósito mejor. En total, lo dejo. Gracias a ikegami por sus comentarios.

Nota La versión comentada es aproximadamente un 50% más rápida que la otra, según mi punto de referencia a continuación. Ambos son dados porque son diferentes , uno encontrando el primer partido y el otro el segundo campo. Lo mantengo de esta manera como una opción más genérica, ya que la pregunta es ambigua sobre eso.


Algunas comparaciones (punto de referencia) [Actualizado para escribir en STDOUT , ver “Actualizar” arriba]

Hay un extenso análisis en la respuesta de HåkonHægland , cronometrando una carrera de la mayoría de las soluciones. Aquí hay otra toma, una evaluación comparativa de las dos soluciones anteriores, la propia respuesta del OP y el publicado fgrep one, que se espera sea rápido y se use en la pregunta y en muchas respuestas.

Construyo datos de prueba de la siguiente manera. Un puñado de líneas de la longitud más o menos como se muestra se hacen con palabras aleatorias, para ambos archivos, por lo que coinciden en el segundo campo. Luego relleno esta “semilla” para muestras de datos con líneas que no coinciden, para simular relaciones entre tamaños y coincidencias citadas por OP: para líneas de 14K en archivos pequeños, hay líneas de 1.3M en el archivo grande, dando 126K coincidencias. A continuación, estas muestras se escriben repetidamente para comstackr archivos de datos completos como OP, se shuffle cada vez que se usa List :: Util .

Todas las ejecuciones comparadas a continuación producen 106_120 coincidencias para los tamaños de archivo anteriores (diferentes para un control), por lo que la frecuencia de coincidencia es lo suficientemente cerca. Se my $res = timethese(60 ...) llamando a progtwigs completos usando my $res = timethese(60 ...) . El resultado de cmpthese($res) en v5.16 es

         Rate regex cfor split fgrep
 expresión regular 1.05 / s - -23% -35% -44%
 cfor 1.36 / s 30% - -16% -28%
 división 1.62 / s 54% 19% - -14%
 fgrep 1.89 / s 80% 39% 17% -

El hecho de que el C-program fgrep llegue a la cima no es sorprendente. El retraso ” regex ” detrás de ” split ” puede deberse a la sobrecarga de arrancar el motor para las cerillas pequeñas, muchas veces. Esto puede variar según las versiones de Perl, teniendo en cuenta la evolución de las optimizaciones del motor regex. Incluyo la respuesta @codeforester (” cfor “) ya que se afirmó que era la más rápida, y su retraso del 20% detrás de la ” división ” muy similar probablemente se deba a pequeñas ineficiencias dispersas (ver un comentario debajo de esta respuesta).

Esto no es asombrosamente diferente, mientras que hay variaciones seguras entre hardware y software y sobre detalles de datos. Ejecuté esto en diferentes Perls y máquinas, y la notable diferencia es que, en algunos casos, fgrep era de hecho un orden de magnitud más rápido .

La experiencia de OP de fgrep muy lento es sorprendente. Teniendo en cuenta los tiempos de ejecución citados, orden de magnitud más lento que el anterior, supongo que hay un viejo sistema para “culpar”.

Aunque esto se basa completamente en E / S, existen beneficios de simultaneidad al colocarlo en varios núcleos y esperaría una buena aceleración, hasta un factor de unos pocos.

He intentado hacer una comparación entre algunos de los métodos presentados aquí.

Primero creé un script Perl para generar los archivos de entrada file1.txt y file2.txt . Para comparar algunas de las soluciones, me aseguré de que las palabras de file1.txt solo pudieran aparecer en el segundo campo en file2.txt . También para poder utilizar la solución de join presentada por @GeorgeVasiliou, ordené file1.txt y file2.txt . Actualmente generé los archivos de entrada basados ​​en solo 75 palabras aleatorias (tomadas de https://www.randomlists.com/random-words ). Solo 5 de estas 75 palabras se usaron en file1.txt las 70 palabras restantes se usaron para completar los campos en file2.txt . Puede ser necesario boost sustancialmente el número de palabras para obtener resultados realistas (según OP, el file1.txt original contiene 14000 palabras). En las pruebas a continuación, utilicé un file2.txt con 1000000 (1 millón) de líneas. El script también genera el archivo regexp1.txt requerido por la solución grep de @BOC.

gen_input_files.pl :

 #! /usr/bin/env perl use feature qw(say); use strict; use warnings; use Data::Printer; use Getopt::Long; GetOptions ("num_lines=i" => \my $nlines ) or die("Error in command line arguments\n"); # Generated random words from site: https://www.randomlists.com/random-words my $word_filename = 'words.txt'; # 75 random words my $num_match_words = 5; my $num_file2_lines = $nlines || 1_000_000; my $file2_words_per_line = 3; my $file2_match_field_no = 2; my $file1_filename = 'file1.txt'; my $file2_filename = 'file2.txt'; my $file1_regex_fn = 'regexp1.txt'; say "generating $num_file2_lines lines.."; my ( $words1, $words2 ) = get_words( $word_filename, $num_match_words ); write_file1( $file1_filename, $words2 ); write_file2( $file2_filename, $words1, $words2, $num_file2_lines, $file2_words_per_line, $file2_match_field_no ); write_BOC_regexp_file( $file1_regex_fn, $words2 ); sub write_BOC_regexp_file { my ( $fn, $words ) = @_; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh '\\|' . (join "|", @$words) . '\\|'; close $fh; } sub write_file2 { my ( $fn, $words1, $words2, $nlines, $words_per_line, $field_no ) = @_; my $nwords1 = scalar @$words1; my $nwords2 = scalar @$words2; my @lines; for (1..$nlines) { my @words_line; my $key; for (1..$words_per_line) { my $word; if ( $_ != $field_no ) { my $index = int (rand $nwords1); $word = @{ $words1 }[$index]; } else { my $index = int (rand($nwords1 + $nwords2) ); if ( $index < $nwords2 ) { $word = @{ $words2 }[$index]; } else { $word = @{ $words1 }[$index - $nwords2]; } $key = $word; } push @words_line, $word; } push @lines, [$key, (join "|", @words_line)]; } @lines = map { $_->[1] } sort { $a->[0] cmp $b->[0] } @lines; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh (join "\n", @lines); close $fh; } sub write_file1 { my ( $fn, $words ) = @_; open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!"; print $fh (join "\n", sort @$words); close $fh; } sub get_words { my ( $fn, $N ) = @_; open( my $fh, '<', $fn ) or die "Could not open file '$fn': $!"; my @words = map {chomp $_; $_} <$fh>; close $fh; my @words1 = @words[$N..$#words]; my @words2 = @words[0..($N - 1)]; return ( \@words1, \@words2 ); } 

A continuación, creé una subcarpeta de solutions con todos los casos de prueba:

 $ tree solutions/ solutions/ ├── BOC1 │  ├── out.txt │  └── run.sh ├── BOC2 │  ├── out.txt │  └── run.sh ├── codeforester │  ├── out.txt │  ├── run.pl │  └── run.sh [...] 

Aquí los archivos out.txt son el resultado de los greps para cada solución. Los scripts run.sh ejecutan la solución para el caso de prueba dado.

Notas sobre las diferentes soluciones

  • BOC1 : primera solución presentada por @BOC

     grep -E -f regexp1.txt file2.txt 
  • BOC2 : Segunda solución sugerida por @BOC:

     LC_ALL=C grep -E -f regexp1.txt file2.txt 
  • codeforester : Solución Perl aceptada por @codeforester (ver fuente )

  • codeforester_orig : solución original presentada por @codeforested:

     fgrep -f file1.txt file2.txt 
  • dawg : solución de Python utilizando el diccionario y la línea dividida propuesta por @dawg (ver fuente )

  • gregory1 : solución usando Gnu Parallel sugerido por @gregory

     parallel -k --pipepart -a file2.txt --block "$block_size" fgrep -F -f file1.txt 

    Consulte la nota a continuación sobre cómo elegir $block_size .

  • hakon1 : solución Perl proporcionada por @ HåkonHægland (ver fuente ). Esta solución requiere la comstackción de la c-extensión la primera vez que se ejecuta el código. No requiere recomstackción cuando se file1.txt o file2.txt . Nota: El tiempo utilizado para comstackr la extensión c en la ejecución inicial no se incluye en los tiempos de ejecución que se presentan a continuación.

  • ikegami : solución que usa ikegami ensambladas y usa grep -P como lo indica @ikegami. Nota: La regexp_ikegami.txt ensamblada se escribió en un archivo separado regexp_ikegami.txt , por lo que el tiempo de ejecución de generar la regexp_ikegami.txt no se incluye en la comparación a continuación. Este es el código utilizado:

     regexp=$(< "regexp_ikegami.txt") grep -P "$regexp" file2.txt 
  • inian1 : Primera solución por @Inian usando match()

     awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (match($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian2 : Segunda solución por @Inian usando index()

     awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (index($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian3 : Tercera solución por @Inian comprobando solo el campo $2 :

     awk 'FNR==NR{ hash[$1]; next } $2 in hash' file1.txt FS='|' file2.txt 
  • inian4 : 4th soultion por @Inian (básicamente lo mismo que codeforester_orig con LC_ALL ):

     LC_ALL=C fgrep -f file1.txt file2.txt 
  • inian5 : 5ª solución de @Inian (igual que inian1 pero con LC_ALL ):

     LC_ALL=C awk 'FNR==NR{ hash[$1]; next } { for (i in hash) if (match($0,i)) {print; break} }' file1.txt FS='|' file2.txt 
  • inian6 : Igual que inian3 pero con LC_ALL=C Gracias a @GeorgeVasiliou por su sugerencia.

  • jjoao : código C comstackdo y generado por flexión según lo propuesto por @JJoao (ver fuente ). Nota: La recomstackción del exectuable debe hacerse cada vez que cambie el file1.txt . El tiempo utilizado para comstackr el ejecutable no está incluido en los tiempos de ejecución que se presentan a continuación.

  • oliv : script de Python proporcionado por @oliv (ver fuente )

  • Vasiliou : Usar join como lo sugiere @GeorgeVasiliou:

     join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 file1.txt file2.txt 
  • Vasiliou2 : Igual que Vasiliou pero con LC_ALL=C

  • zdim : utilizando el script Perl proporcionado por @zdim (ver fuente ). Nota: Esto usa la versión de búsqueda regexp (en lugar de la solución de línea dividida).

  • zdim2 : Igual que zdim excepto que usa la función de split lugar de la búsqueda de file2.txt para el campo en file2.txt .

Notas

  1. Experimenté un poco con Gnu en paralelo (vea la solución de gregory1 anterior) para determinar el tamaño de bloque óptimo para mi CPU. Tengo 4 núcleos, y actualmente parece que la opción óptima es dividir el archivo ( file2.txt ) en 4 fragmentos del mismo tamaño y ejecutar un solo trabajo en cada uno de los 4 procesadores. Se pueden necesitar más pruebas aquí. Entonces para el primer caso de prueba donde file2.txt es 20M, configuro $block_size a 5M (vea la solución gregory1 anterior), mientras que para el caso más realista presentado a continuación donde file2.txt es 268M, se usó un $block_size de 67M.

  2. Las soluciones BOC1 , BOC2 , codeforester_orig , inian1 , inian4 , inian5 y gregory1 todas usaron coincidencias sueltas. Lo que significa que las palabras de file1.txt no tenían que coincidir exactamente en el campo # 2 de file2.txt . Se aceptó un partido en cualquier lugar de la línea. Como este comportamiento dificultaba la comparación con los otros métodos, también se introdujeron algunos métodos modificados. Los primeros dos métodos llamados BOC1B y BOC2B usaron un archivo regexp1.txt modificado. Las líneas en el regexp1.txt original en el formulario \|foo1|foo2|...|fooN\| que coincidiría con las palabras en cualquier límite de campo. El archivo modificado, regexp1b.txt , ancló la coincidencia con el campo # 2 exclusivamente con la forma ^[^|]*\|foo1|foo2|...|fooN\| en lugar.

    Luego, el rest de los métodos modificados codeforester_origB , inian1B , inian4B , inian5B y gregory1B usaron un file1.txt modificado. En lugar de una palabra literal por línea, el archivo modificado file1b.txt usó una expresión regular por línea en el formulario:

      ^[^|]*\|word1\| ^[^|]*\|word2\| ^[^|]*\|word3\| [...] 

    y además, fgrep -f fue reemplazado por grep -E -f para estos métodos.

Ejecutando las pruebas

Aquí está el script utilizado para ejecutar todas las pruebas. Utiliza el comando Bash time para registrar el tiempo dedicado a cada script. Tenga en cuenta que el comando time devuelve tres veces diferentes call real , user y sys . Primero usé user + sys , pero me di cuenta de que esto era incorrecto al usar el comando paralelo de Gnu, por lo que la hora indicada a continuación ahora es la parte real devuelta por time . Consulte esta pregunta para obtener más información sobre los diferentes tiempos devueltos por el time .

La primera prueba se ejecuta con file1.txt contiene 5 líneas y file2.txt contiene 1000000 líneas. Aquí están las primeras 52 líneas del script run_all.pl , el rest del script está disponible aquí .

run_all.pl

 #! /usr/bin/env perl use feature qw(say); use strict; use warnings; use Cwd; use Getopt::Long; use Data::Printer; use FGB::Common; use List::Util qw(max shuffle); use Number::Bytes::Human qw(format_bytes); use Sys::Info; GetOptions ( "verbose" => \my $verbose, "check" => \my $check, "single-case=s" => \my $case, "expected=i" => \my $expected_no_lines, ) or die("Error in command line arguments\n"); my $test_dir = 'solutions'; my $output_file = 'out.txt'; my $wc_expected = $expected_no_lines; # expected number of output lines my $tests = get_test_names( $test_dir, $case ); my $file2_size = get_file2_size(); my $num_cpus = Sys::Info->new()->device( CPU => () )->count; chdir $test_dir; my $cmd = 'run.sh'; my @times; for my $case (@$tests) { my $savedir = getcwd(); chdir $case; say "Running '$case'.."; my $arg = get_cmd_args( $case, $file2_size, $num_cpus ); my $output = `bash -c "{ time -p $cmd $arg; } 2>&1"`; my ($user, $sys, $real ) = get_run_times( $output ); print_timings( $user, $sys, $real ) if $verbose; check_output_is_ok( $output_file, $wc_expected, $verbose, $check ); print "\n" if $verbose; push @times, $real; #push @times, $user + $sys; # this is wrong when using Gnu parallel chdir $savedir; } say "Done.\n"; print_summary( $tests, \@times ); 

Resultados

Aquí está el resultado de ejecutar las pruebas:

 $ run_all.pl --verbose Running 'inian3'.. ..finished in 0.45 seconds ( user: 0.44, sys: 0.00 ) ..no of output lines: 66711 Running 'inian2'.. ..finished in 0.73 seconds ( user: 0.73, sys: 0.00 ) ..no of output lines: 66711 Running 'Vasiliou'.. ..finished in 0.09 seconds ( user: 0.08, sys: 0.00 ) ..no of output lines: 66711 Running 'codeforester_orig'.. ..finished in 0.05 seconds ( user: 0.05, sys: 0.00 ) ..no of output lines: 66711 Running 'codeforester'.. ..finished in 0.45 seconds ( user: 0.44, sys: 0.01 ) ..no of output lines: 66711 [...] 

Resumen

[Los resultados obtenidos por @Vasiliou se muestran en la columna del medio.]

  |Vasiliou My Benchmark |Results | Details -------------------------------|---------|---------------------- inian4 : 0.04s |0.22s | LC_ALL fgrep -f [loose] codeforester_orig : 0.05s | | fgrep -f [loose] Vasiliou2 : 0.06s |0.16s | [LC_ALL join [requires sorted files]] BOC1 : 0.06s | | grep -E [loose] BOC2 : 0.07s |15s | LC_ALL grep -E [loose] BOC2B : 0.07s | | LC_ALL grep -E [strict] inian4B : 0.08s | | LC_ALL grep -E -f [strict] Vasiliou : 0.08s |0.23s | [join [requires sorted files]] gregory1B : 0.08s | | [parallel + grep -E -f [strict]] ikegami : 0.1s | | grep -P gregory1 : 0.11s |0.5s | [parallel + fgrep -f [loose]] hakon1 : 0.14s | | [perl + c] BOC1B : 0.14s | | grep -E [strict] jjoao : 0.21s | | [compiled flex generated c code] inian6 : 0.26s |0.7s | [LC_ALL awk + split+dict] codeforester_origB : 0.28s | | grep -E -f [strict] dawg : 0.35s | | [python + split+dict] inian3 : 0.44s |1.1s | [awk + split+dict] zdim2 : 0.4s | | [perl + split+dict] codeforester : 0.45s | | [perl + split+dict] oliv : 0.5s | | [python + compiled regex + re.search()] zdim : 0.61s | | [perl + regexp+dict] inian2 : 0.73s |1.7s | [awk + index($0,i)] inian5 : 18.12s | | [LC_ALL awk + match($0,i) [loose]] inian1 : 19.46s | | [awk + match($0,i) [loose]] inian5B : 42.27s | | [LC_ALL awk + match($0,i) [strict]] inian1B : 85.67s | | [awk + match($0,i) [strict]] Vasiliou Results : 2 X CPU Intel 2 Duo T6570 @ 2.10GHz - 2Gb RAM-Debian Testing 64bit- kernel 4.9.0.1 - no cpu freq scaling. 

Un caso de prueba más realista

Luego creé un caso más realista con file1.txt con 100 palabras y file2.txt con 10 millones de líneas (tamaño de archivo de 268Mb). Extraje 1000 palabras aleatorias del diccionario en /usr/share/dict/american-english usando shuf -n1000 /usr/share/dict/american-english > words.txt luego shuf -n1000 /usr/share/dict/american-english > words.txt 100 de estas palabras en file1.txt y luego construyo file2.txt la misma manera que se describió anteriormente para el primer caso de prueba. Tenga en cuenta que el archivo de diccionario está codificado en UTF-8, y words.txt todos los caracteres que no son ASCII de las words.txt .

Luego ejecuto la prueba sin los tres métodos más lentos del caso anterior. Es decir, inian1 , inian2 e inian5 quedaron fuera. Aquí están los nuevos resultados:

 gregory1 : 0.86s | [parallel + fgrep -f [loose]] Vasiliou2 : 0.94s | [LC_ALL join [requires sorted files]] inian4B : 1.12s | LC_ALL grep -E -f [strict] BOC2B : 1.13s | LC_ALL grep -E [strict] BOC2 : 1.15s | LC_ALL grep -E [loose] BOC1 : 1.18s | grep -E [loose] ikegami : 1.33s | grep -P Vasiliou : 1.37s | [join [requires sorted files]] hakon1 : 1.44s | [perl + c] inian4 : 2.18s | LC_ALL fgrep -f [loose] codeforester_orig : 2.2s | fgrep -f [loose] inian6 : 2.82s | [LC_ALL awk + split+dict] jjoao : 3.09s | [compiled flex generated c code] dawg : 3.54s | [python + split+dict] zdim2 : 4.21s | [perl + split+dict] codeforester : 4.67s | [perl + split+dict] inian3 : 5.52s | [awk + split+dict] zdim : 6.55s | [perl + regexp+dict] gregory1B : 45.36s | [parallel + grep -E -f [strict]] oliv : 60.35s | [python + compiled regex + re.search()] BOC1B : 74.71s | grep -E [strict] codeforester_origB : 75.52s | grep -E -f [strict] 

Nota

Las soluciones basadas en grep buscaban una coincidencia en toda la línea, por lo que en este caso contenían algunas coincidencias falsas: los métodos codeforester_orig , BOC1 , BOC2 , gregory1 , inian4 y oliv extrajeron 1.087.609 líneas de 10.000.000 líneas, mientras que los otros métodos extrajo las 997.993 líneas correctas de file2.txt .

Notas

  • Probé esto en mi computadora portátil Ubuntu 16.10 (CPU Intel Core i7-7500U a 2.70 GHz)

  • El estudio de referencia completo está disponible aquí .

¿ Awk que podría acelerar un poco las cosas?

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

(o) usando la función index() en Awk como lo sugieren los comentarios de Benjamin W. , a continuación

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (index($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

(o) una coincidencia de expresiones regulares más directa según lo sugerido por Ed Morton en los comentarios,

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if ($0~i) {print; break}}' file1.txt FS='|' file2.txt 

es todo lo que necesitas. Supongo que esto será más rápido pero no exactamente seguro en los archivos con más de un millón de entradas. Aquí el problema es con la coincidencia de posibilidades en cualquier parte de la línea. Si hubiera estado igual en cualquier columna en particular (por ejemplo, digamos $2 solo), un enfoque más rápido podría ser

 awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt 

También podría acelerar las cosas jugando con la locale en su sistema. Parafraseando la maravillosa respuesta de Stéphane Chazelas sobre el tema, puedes acelerar las cosas bastante rápido configurando pasar el entorno local LC_ALL=C al comando que se está ejecutando localmente .

En cualquier sistema basado en GNU , los valores predeterminados para la locale

 $ locale LANG=en_US.UTF-8 LC_CTYPE="en_US.UTF-8" LC_NUMERIC="en_US.UTF-8" LC_TIME="en_US.UTF-8" LC_COLLATE="en_US.UTF-8" LC_MONETARY="en_US.UTF-8" LC_MESSAGES="en_US.UTF-8" LC_PAPER="en_US.UTF-8" LC_NAME="en_US.UTF-8" LC_ADDRESS="en_US.UTF-8" LC_TELEPHONE="en_US.UTF-8" LC_MEASUREMENT="en_US.UTF-8" LC_IDENTIFICATION="en_US.UTF-8" LC_ALL= 

Con una variable LC_ALL , puede establecer todas las variables de tipo LC_ a la vez en una configuración regional especificada

 $ LC_ALL=C locale LANG=en_US.UTF-8 LC_CTYPE="C" LC_NUMERIC="C" LC_TIME="C" LC_COLLATE="C" LC_MONETARY="C" LC_MESSAGES="C" LC_PAPER="C" LC_NAME="C" LC_ADDRESS="C" LC_TELEPHONE="C" LC_MEASUREMENT="C" LC_IDENTIFICATION="C" LC_ALL=C 

Entonces, ¿qué impacto tiene esto?

En pocas palabras, al usar la locale C se utilizará de manera predeterminada el lenguaje base ASCII de Unix / Linux del servidor. Básicamente cuando grep algo, de forma predeterminada su configuración regional se internacionalizará y se establecerá en UTF-8 , que puede representar a todos los personajes en el conjunto de caracteres Unicode para ayudar a mostrar cualquiera de los sistemas de escritura del mundo, actualmente más de 110,000 caracteres únicos, mientras que con ASCII cada carácter está codificado en una secuencia de un solo byte y su conjunto de caracteres comprende de no más de 128 caracteres únicos.

Por lo tanto, esto se traduce en esto, cuando se utiliza grep en un archivo codificado en el UTF-8 caracteres UTF-8 , necesita hacer coincidir cada carácter con cualquiera de los cien mil caracteres únicos, pero solo 128 en ASCII , así que use su fgrep como

 LC_ALL=C fgrep -F -f file1.txt file2.txt 

Además, lo mismo se puede adaptar al Awk , ya que utiliza una coincidencia de regex con la llamada de match($0,i) , establecer la configuración regional de C podría acelerar la coincidencia de cadenas.

 LC_ALL=C awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

Supuestos: 1. Desea ejecutar esta búsqueda solo en su estación de trabajo local. 2. Tienes varios núcleos / CPU para aprovechar una búsqueda paralela.

 parallel --pipepart -a file2.txt --block 10M fgrep -F -f file1.txt 

Algunos ajustes adicionales dependiendo del contexto: A. Deshabilitar NLS con LANG = C (esto ya se menciona en otra respuesta) B. Establecer un número máximo de coincidencias con el indicador -m.

Nota: Supongo que el archivo2 tiene ~ 4GB y el tamaño del bloque de 10M está bien, pero es posible que necesite optimizar el tamaño del bloque para obtener la ejecución más rápida.

Este script de Perl ( a ) genera un patrón de expresiones regulares:

 #!/usr/bin/perl use strict; use warnings; use Regexp::Assemble qw( ); chomp( my @ids = <> ); my $ra = Regexp::Assemble->new(); $ra->add(quotemeta($_)) for @ids; print("^[^|]*\\|(?:" . (re::regexp_pattern($ra->re()))[0] . ")\\|"); 

Así es como se puede usar:

 $ LC_ALL=C grep -P "$( a file1.txt )" file2.txt date1|foo1|number1 date2|foo2|number2 date1|bar1|number1 date2|bar2|number2 

Tenga en cuenta que el script usa Regexp :: Assemble, por lo que es posible que deba instalarlo.

 sudo su cpan Regexp::Assemble 

Notas:

  • A diferencia de las soluciones denominadas BOC1, BOC2, codeforester_orig, gregory1, inian2, inian4 y oliv, mi solución maneja correctamente

     file1.txt foo1 file2.txt date1|foo12|number5 
  • El mío debería ser mejor que la solución similar de @BOC porque el patrón está optimizado para reducir el retroceso. (El mío también funciona si hay más de tres campos en file2.txt , mientras que la solución vinculada puede fallar).

  • No sé cómo se compara con las soluciones de división + diccionario.

Una pequeña porción del código Perl resolvió el problema. Este es el enfoque adoptado:

  • almacena las líneas de file1.txt en un hash
  • lea file2.txt línea por línea, analice y extraiga el segundo campo
  • compruebe si el campo extraído está en el hash; si es así, imprima la línea

Aquí está el código:

 #!/usr/bin/perl -w use strict; if (scalar(@ARGV) != 2) { printf STDERR "Usage: fgrep.pl smallfile bigfile\n"; exit(2); } my ($small_file, $big_file) = ($ARGV[0], $ARGV[1]); my ($small_fp, $big_fp, %small_hash, $field); open($small_fp, "<", $small_file) || die "Can't open $small_file: " . $!; open($big_fp, "<", $big_file) || die "Can't open $big_file: " . $!; # store contents of small file in a hash while (<$small_fp>) { chomp; $small_hash{$_} = undef; } close($small_fp); # loop through big file and find matches while (<$big_fp>) { # no need for chomp $field = (split(/\|/, $_))[1]; if (defined($field) && exists($small_hash{$field})) { printf("%s", $_); } } close($big_fp); exit(0); 

Ejecuté el script anterior con 14K líneas en file1.txt y 1.3M líneas en file2.txt. Terminó en aproximadamente 13 segundos, produciendo 126K coincidencias. Aquí está el time salida para el mismo:

 real 0m11.694s user 0m11.507s sys 0m0.174s 

Ejecuté el código awk @ Inian:

 awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt 

Fue mucho más lento que la solución Perl, ya que está girando 14K veces para cada línea en file2.txt, lo cual es realmente costoso. Se abortó después de procesar 592K registros de file2.txt y producir 40K líneas coincidentes. Aquí está cuánto tiempo tomó:

 awk: illegal primary in regular expression 24/Nov/2016||592989 at 592989 input record number 675280, file file2.txt source line number 1 real 55m5.539s user 54m53.080s sys 0m5.095s 

Using @Inian’s other awk solution, which eliminates the looping issue:

 time awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk1.out real 0m39.966s user 0m37.916s sys 0m0.743s time LC_ALL=C awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk.out real 0m41.057s user 0m38.475s sys 0m0.904s 

awk is very impressive here, given that we didn’t have to write an entire program to do it.

I ran @oliv’s Python code as well. It took about 15 hours to complete the job, and looked like it produced the right results. Building a huge regex isn’t as efficient as using a hash lookup. Here the time output:

 real 895m14.862s user 806m59.219s sys 1m12.147s 

I tried to follow the suggestion to use parallel . However, it failed with fgrep: memory exhausted error, even with very small block sizes.


What surprised me was that fgrep was totally unsuitable for this. I aborted it after 22 hours and it produced about 100K matches. I wish fgrep had an option to force the content of -f file to be kept in a hash, just like what the Perl code did.

I didn’t check join approach – I didn’t want the additional overhead of sorting the files. Also, given fgrep ‘s poor performance, I don’t believe join would have done better than the Perl code.

Thanks everyone for your attention and responses.

Here is Perl solution that uses Inline::C to speed up the search for matching fields in the large file:

 use strict; use warnings; use Inline C => './search.c'; my $smallfile = 'file1.txt'; my $bigfile = 'file2.txt'; open my $fh, '<', $smallfile or die "Can't open $smallfile: $!"; my %word = map { chomp; $_ => 1 } <$fh>; search( $bigfile, \%word ); 

The search() sub routine is implemented in pure C using perlapi to look up keys in the small file dictionary %words :

search.c :

 #include  #include  #include  #include  #include  #define BLOCK_SIZE 8192 /* how much to read from file each time */ static char read_buf[BLOCK_SIZE + 1]; /* reads a block from file, returns -1 on error, 0 on EOF, else returns chars read, pointer to buf, and pointer to end of buf */ size_t read_block( int fd, char **ret_buf, char **end_buf ) { int ret; char *buf = read_buf; size_t len = BLOCK_SIZE; while (len != 0 && (ret = read(fd, buf, len)) != 0) { if (ret == -1) { if (errno == EINTR) continue; perror( "read" ); return ret; } len -= ret; buf += ret; } *end_buf = buf; *ret_buf = read_buf; return (size_t) (*end_buf - *ret_buf); } /* updates the line buffer with the char pointed to by cur, also updates cur */ int update_line_buffer( char **cur, char **line, size_t *llen, size_t max_line_len ) { if ( *llen > max_line_len ) { fprintf( stderr, "Too long line. Maximimum allowed line length is %ld\n", max_line_len ); return 0; } **line = **cur; (*line)++; (*llen)++; (*cur)++; return 1; } /* search for first pipe on a line (or next line if this is empty), assume line ptr points to beginning of line buffer. return 1 on success Return 0 if pipe could not be found for some reason, or if line buffer length was exceeded */ int search_field_start( int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len ) { char *line_start = *line; while (1) { if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return 0; } if ( **cur == '|' ) break; /* Currently we just ignore malformed lines ( lines that do not have a pipe, and empty lines in the input */ if ( **cur == '\n' ) { *line = line_start; *llen = 0; (*cur)++; } else { if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0; } } return 1; } /* assume cur points at starting pipe of field return -1 on read error, return 0 if field len was too large for buffer or line buffer length exceed, else return 1 and field, and length of field */ int copy_field( int fd, char **cur, char **end_buf, char *field, size_t *flen, char **line, size_t *llen, size_t max_field_len, size_t max_line_len ) { *flen = 0; while( 1 ) { if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0; if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return -1; } if ( **cur == '|' ) break; if ( *flen > max_field_len ) { printf( "Field width too large. Maximum allowed field width: %ld\n", max_field_len ); return 0; } *field++ = **cur; (*flen)++; } /* It is really not necessary to null-terminate the field since we return length of field and also field could contain internal null characters as well */ //*field = '\0'; return 1; } /* search to beginning of next line, return 0 on error, else return 1 */ int search_eol( int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len) { while (1) { if ( *cur >= *end_buf ) { size_t res = read_block( fd, cur, end_buf ); if (res <= 0) return 0; } if ( !update_line_buffer( cur, line, llen, max_line_len ) ) return 0; if ( *(*cur-1) == '\n' ) { break; } } //**line = '\0'; // not necessary return 1; } #define MAX_FIELD_LEN 80 /* max number of characters allowed in a field */ #define MAX_LINE_LEN 80 /* max number of characters allowed on a line */ /* Get next field ( ie field #2 on a line). Fields are separated by pipes '|' in the input file. Also get the line of the field. Return 0 on error, on success: Move internal pointer to beginning of next line return 1 and the field. */ size_t get_field_and_line_fast( int fd, char *field, size_t *flen, char *line, size_t *llen ) { static char *cur = NULL; static char *end_buf = NULL; size_t res; if (cur == NULL) { res = read_block( fd, &cur, &end_buf ); if ( res <= 0 ) return 0; } *llen = 0; if ( !search_field_start( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN )) return 0; if ( (res = copy_field( fd, &cur, &end_buf, field, flen, &line, llen, MAX_FIELD_LEN, MAX_LINE_LEN ) ) <= 0) return 0; if ( !search_eol( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN ) ) return 0; return 1; } void search( char *filename, SV *href) { if( !SvROK( href ) || ( SvTYPE( SvRV( href ) ) != SVt_PVHV ) ) { croak( "Not a hash reference" ); } int fd = open (filename, O_RDONLY); if (fd == -1) { croak( "Could not open file '%s'", filename ); } char field[MAX_FIELD_LEN+1]; char line[MAX_LINE_LEN+1]; size_t flen, llen; HV *hash = (HV *)SvRV( href ); while ( get_field_and_line_fast( fd, field, &flen, line, &llen ) ) { if( hv_exists( hash, field, flen ) ) fwrite( line, sizeof(char), llen, stdout); } if (close(fd) == -1) croak( "Close failed" ); } 

Tests indicate that it is approximately 3 times faster than the fastest pure Perl solution (see method zdim2 in my other answer ) presented here.

Here is a Python solution using sets — roughly equivalent to a Perl key only hash or awk array in concept.

 #!/usr/bin/python import sys with open(sys.argv[1]) as f: tgt={e.rstrip() for e in f} with open(sys.argv[2]) as f: for line in f: cells=line.split("|") if cells[1] in tgt: print line.rstrip() 

When I run this on files of similar size, it runs in about 8 seconds.

Same speed as:

 $ awk 'FNR==NR{arr[$1]; next} $2 in arr{print $0}' FS="|" /tmp/f1 /tmp/f2 

Both the Python and awk solution here are full string match only; not a partial regex style match.

Since the awk solution is fast and POSIX compliant, that is the better answer.

A possible way is to use python :

 $ cat test.py import sys,re with open(sys.argv[1], "r") as f1: patterns = f1.read().splitlines() # read pattern from file1 without the trailing newline m = re.compile("|".join(patterns)) # create the regex with open(sys.argv[2], "r") as f2: for line in f2: if m.search(line) : print line, # print line from file2 if this one matches the regex 

y úsalo así:

 python test.py file1.txt file2.txt 

Can you give a try to join ? Files must be sorted though…

 $ cat d.txt bar1 bar2 foo1 foo2 $ cat e.txt date1|bar1|number1 date2|bar2|number2 date3|bar3|number3 date1|foo1|number1 date2|foo2|number2 date3|foo3|number3 $ join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 d.txt e.txt date1|bar1|number1 date2|bar2|number2 date1|foo1|number1 date2|foo2|number2 

Small Update:
By using LC_ALL=C in front of join, things are really speed up as can be seen in the benchmark of Håkon Hægland

PS1: I have my doubts if join can be faster than grep -f …

También puedes usar Perl para esto:

Please note that this will hog memory and your machine/server better has some.

Sample Data:

 %_STATION@gaurav * /root/ga/pl> head file1.txt file2.txt ==> file1.txt <== foo1 foo2 ... bar1 bar2 ... ==> file2.txt <== date1|foo1|number1 date2|foo2|number2 date3|foo3|number3 ... date1|bar1|number1 date2|bar2|number2 date3|bar3|number3 %_STATION@gaurav * /root/ga/study/pl> 

Script Output: Script will produce final output in a file named output_comp .

 %_STATION@gaurav * /root/ga/pl> ./comp.pl file1.txt file2.txt ; cat output_comp date1|bar1|number1 date2|bar2|number2 date2|foo2|number2 date1|foo1|number1 %_STATION@gaurav * /root/ga/pl> 

Guión:

 %_STATION@gaurav * /root/ga/pl> cat comp.pl #!/usr/bin/perl use strict ; use warnings ; use Data::Dumper ; my ($file1,$file2) = @ARGV ; my $output = "output_comp" ; my %hash ; # This will store main comparison data. my %tmp ; # This will store already selected results, to be skipped. (scalar @ARGV != 2 ? (print "Need 2 files!\n") : ()) ? exit 1 : () ; # Read all files at once and use their name as the key. for (@ARGV) { open FH, "<$_" or die "Cannot open $_\n" ; while (my $line = ) {chomp $line ;$hash{$_}{$line} = "$line"} close FH ; } # Now we churn through the data and compare to generate # the sorted output in the output file. open FH, ">>$output" or die "Cannot open outfile!\n" ; foreach my $k1 (keys %{$hash{$file1}}){ foreach my $k2 (keys %{$hash{$file2}}){ if ($k1 =~ m/^.+?$k2.+?$/) { if (!defined $tmp{"$hash{$file2}{$k2}"}) { print FH "$hash{$file2}{$k2}\n" ; $tmp{"$hash{$file2}{$k2}"} = 1 ; } } } } close FH ; %_STATION@gaurav * /root/ga/pl> 

Gracias.

IMHO, grep is a good tool highly optimised for huge file2.txt but maybe not for so many patterns to search. I suggest to combine all the strings of file1.txt into a single huge regexp like \|bar1|bar2|foo1|foo2\|

 echo '\|'$(paste -s -d '|' file1.txt)'\|' > regexp1.txt grep -E -f regexp1.txt file2.txt > file.matched 

And of course LANG=C may help. Please give feedback or send your files so I can test myself.

I would use SQLite3 🙂 Maybe in-memory database or whatever. Import the files and use SQL query.

Using flex :

1: build the flex processor:

 $ awk 'NR==1{ printf "%%%%\n\n.*\\|(%s",$0 } { printf "|%s",$0 } END { print ")\\|.*\\n ECHO;\n.*\\n ;\n%%\n" }' file1.txt > a.fl 

2: compile it

 $ flex -Ca -F a.fl ; cc -O lex.yy.c -lfl 

3: and run

 $ a.out < file2.txt > out 

Compiling (cc …) is a slow process; this approach will pay just for cases of stable file1.txt

(In my machine) The times taken to run a search “100 in 10_000_000” test in this approach is 3 times faster than LC_ALL=C fgrep...

Though this thread is over, but all grep-alike methods between two files are gathered in this post, why not to add this awk alternative, similar (or even improved) to the bounty winning Inian’s awk solution:

 awk 'NR==FNR{a[$0]=1;next}a[$2]' patterns.txt FS="|" datafile.txt >matches.txt # For matches restricted on Field2 of datafile 

This is equivalent to Inian awk $2 in hash solution but it could be even faster due to the fact that we don’t ask awk to check if the whole hash array contains $2 of file2 – we just check if a[$2] has a value or not.

While reading the first patterns file appart from creating the hash array we assign also a value.

If $2 of datafile had been found before in patterns file, then a[$2] would have a value and thus will be printed because is not null.

if a[$2] of datafile returns no value(null) this is translated to false => no printing.

Extension to match any of the three fields of datafile:

 awk 'NR==FNR{a[$0]=1;next}(a[$1] || a[$2] || a[$3])' patterns.txt FS="|" datafile.txt >matches.txt. #Printed if any of the three fields of datafile match pattern. 

In both cases, applying LC_ALL=C in front of awk, seems to speed things up.

PS1: Offcourse this solution has also the pitfalls of all awk solutions. Is not a pattern matching. Is a direct / fixed matching between of the two files, like most of the solutions inhere.

PS2: In my poor machine benchmark using the small benchmark files of Håkon Hægland , i get about 20% better performance comparing to the awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt

setting language etc helps a little, perhaps.

otherwise I can not think of a magic solution to escape from your basic issue: the data is not structured, so you will have a search that comes down to the number of lines in file1 multiplied with the number of lines in file2.

put the billion lines in a database, and index it in a smart way, is the only speed up I can think of. that index would have to be very smart, though……

SImple solution is: have enough memory to fit everything in to. otherwise nothing much more you can do about this….