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

manual de comandos de linux ubuntu (16)

Tengo dos archivos, file1.txt y file2.txt . file1.txt tiene aproximadamente 14K líneas y file2.txt tiene aproximadamente 2 mil millones. 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 pasar más tiempo dividiendo los valores de file2.txt ).

file1.txt (aproximadamente 14K líneas, sin clasificar ):

foo1 foo2 ... bar1 bar2 ...

file2.txt (alrededor de 2 mil millones de líneas, sin clasificar ):

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

Salida esperada:

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

Esto es lo que he intentado y parece que lleva varias horas ejecutarlo:

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.

¿Puedes intentarlo join ? Sin embargo, los archivos deben estar ordenados ...

$ 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

Pequeña actualización:
Al usar LC_ALL = C delante de join, las cosas se aceleran realmente como se puede ver en el punto de referencia de Håkon Hægland

PS1: Tengo mis dudas si unirse puede ser más rápido que grep -f ...

Aquí está la solución Perl que utiliza Inline::C para acelerar la búsqueda de campos coincidentes en el archivo grande:

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 );

La search() subrutina se implementa en C puro utilizando perlapi para buscar claves en el diccionario de archivos pequeños %words :

search.c :

#include <stdio.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h> #include <errno.h> #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 ( i.e. 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" ); }

Las pruebas indican que es aproximadamente 3 veces más rápido que la solución Perl pura más rápida (ver método zdim2 en mi otra respuesta ) presentada aquí.

Aquí hay una solución de Python que usa conjuntos, aproximadamente equivalente a una clave Perl solo hash o awk array en concepto.

#!/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()

Cuando ejecuto esto en archivos de tamaño similar, se ejecuta en aproximadamente 8 segundos.

Misma velocidad que:

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

Tanto la solución Python como la awk aquí solo coinciden con la cadena completa; no es una coincidencia de estilo regex parcial.

Dado que la solución awk es rápida y compatible con POSIX, esa es la mejor respuesta.

Aunque este hilo ha terminado, pero todos los métodos grep-like entre dos archivos se recopilan en esta publicación, ¿por qué no agregar esta alternativa awk, similar (o incluso mejorada) a la solución awk de Inian que gana recompensas:

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

Esto es equivalente a la $2 in hash solución Inian awk , pero podría ser aún más rápido debido al hecho de que no le pedimos a awk que verifique si toda la matriz hash contiene $ 2 del archivo2; solo verificamos si un [$ 2] tiene un valor o no.

Al leer el primer archivo de patrones, además de crear la matriz hash, también asignamos un valor.

Si $2 antes se hubiera encontrado un archivo de datos en el archivo de patrones, a[$2] tendría un valor y, por lo tanto, se imprimirá porque no es nulo.

si el a[$2] archivo de datos no devuelve ningún valor (nulo), esto se traduce en falso => sin impresión.

Extensión para coincidir con cualquiera de los tres campos del archivo de datos

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.

En ambos casos, aplicar LC_ALL = C delante de awk parece acelerar las cosas.

PS1: por supuesto, esta solución también tiene las trampas de todas las soluciones awk. No es una coincidencia de patrones. Es una coincidencia directa / fija entre los dos archivos, como la mayoría de las soluciones inherentes.

PS2: en mi pobre benchmark de máquina usando los pequeños archivos de benchmark de Håkon Hægland , obtengo aproximadamente un 20% de mejor rendimiento en comparación con el awk ''FNR==NR{hash[$1]; next}$2 in hash'' file1.txt FS=''|'' file2.txt

En mi humilde opinión, grep es una buena herramienta altamente optimizada para file2.txt enorme, pero tal vez no para tantos patrones para buscar. Sugiero combinar todas las cadenas de file1.txt en una única expresión regular enorme como / | bar1 | bar2 | foo1 | foo2 / |

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

Y, por supuesto, LANG = C puede ayudar. Por favor, envíe sus comentarios o envíe sus archivos para que pueda probarme a mí mismo.

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

#!/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
La mía debería ser mejor que la solution 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 file2.txt , mientras que la solución vinculada puede fallar).
No sé cómo se compara con las soluciones de división + diccionario.

También puedes usar Perl para esto:

Tenga en cuenta que esto acaparará la memoria y su máquina / servidor tiene mejor.

Data de muestra:

%_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>

Salida de la escritura: la escritura producirá última salida en un archivo llamado 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 = <FH>) {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.

Una forma posible es usar 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

Usando flex :

1: construya el procesador flexible:

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

2: compilarlo

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

3: y corre

$ a.out < file2.txt > out

Compilar (cc ...) es un proceso lento; este enfoque pagará solo por los casos de archivo estable1.txt

(En mi máquina) En este enfoque, el tiempo necesario para ejecutar una búsqueda "100 en 10_000_000" es 3 veces más rápido que LC_ALL=C fgrep...

Usaría SQLite3 :) Tal vez en la base de datos en memoria o lo que sea. Importe los archivos y use la consulta SQL.

configurar el idioma, etc., ayuda un poco, tal vez.

de lo contrario, no puedo pensar en una solución mágica para escapar de su problema básico: los datos no están estructurados, por lo que tendrá una búsqueda que se reduce al número de líneas en el archivo1 multiplicado por el número de líneas en el archivo2.

poner los mil millones de líneas en una base de datos, e indexarlo de manera inteligente, es la única velocidad que se me ocurre. Sin embargo, ese índice tendría que ser muy inteligente ...

La solución simple es: tener suficiente memoria para acomodar todo. de lo contrario, no se puede hacer mucho más al respecto ...

¿ 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 como lo sugiere 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 archivos con más de un millón de entradas. Aquí el problema es con la posibilidad de coincidencia en cualquier lugar a lo largo de la línea. Si lo mismo hubiera estado en una columna en particular (por ejemplo, solo $2 ), 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 establecida en su sistema. Parafraseando de la maravillosa respuesta de Stéphane Chazelas sobre el tema, puede acelerar las cosas bastante rápido configurando pasar la configuración regional LC_ALL=C al comando que se ejecuta 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 un entorno local específico

$ 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é impacta esto?

En pocas palabras, cuando se utiliza la locale C se utilizará de manera predeterminada el lenguaje base ASIX de Unix / Linux del servidor. Básicamente, cuando grep algo, de manera predeterminada tu configuración regional se internacionalizará y se configurará en UTF-8 , que puede representar todos los caracteres 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 se codifica en una secuencia de un solo byte y su conjunto de caracteres consta de no más de 128 caracteres únicos.

Entonces se traduce a esto, cuando se usa grep en un archivo codificado en el UTF-8 caracteres UTF-8 , debe 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 a Awk , ya que utiliza una coincidencia de regex con la llamada de match($0,i) , establecer la configuración regional 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

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 usar 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 aumentar el número de palabras sustancialmente para obtener resultados realistas (de acuerdo con el OP, el file1.txt original file1.txt contenía 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 solutions subcarpeta 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 la salida de 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 source )
codeforester_orig : Solución original presentada por @codeforested:

fgrep -f file1.txt file2.txt
dawg : solución de Python usando diccionario y línea dividida propuesta por @dawg (ver source )
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 source ). Esta solución requiere la compilación de la extensión c la primera vez que se ejecuta el código. No requiere recompilación cuando file1.txt o file2.txt . Nota: El tiempo utilizado para compilar la extensión c en la ejecución inicial no se incluye en los tiempos de ejecución presentados a continuación.
ikegami : Solución usando regexp ensamblado y usando grep -P como lo proporciona @ikegami. Nota: El regexp ensamblado se escribió en un archivo separado regexp_ikegami.txt , por lo que el tiempo de ejecución para generar el regexp 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 de @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 de @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 by @Inian (básicamente lo mismo que codeforester_orig con LC_ALL ):

LC_ALL=C fgrep -f file1.txt file2.txt
inian5 : quinta 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 generado por flexión compilado según lo propuesto por @JJoao (ver source ). Nota: La recompilación del ejecutable debe hacerse cada vez que file1.txt cambia. El tiempo utilizado para compilar el ejecutable no se incluye en los tiempos de ejecución presentados a continuación.
oliv : script Python proporcionado por @oliv (ver source )
Vasiliou : Usando 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 : Uso de la secuencia de comandos Perl proporcionada por @zdim (ver source ). Nota: Esto utiliza 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

Experimenté un poco con Gnu paralelo (ver la solución gregory1 arriba) 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 de igual tamaño y ejecutar un solo trabajo en cada uno de los 4 procesadores. Es posible que se necesiten más pruebas aquí. Entonces, para el primer caso de prueba donde file2.txt es 20M, configuré $block_size a 5M (ver la solución gregory1 arriba), mientras que para el caso más realista presentado a continuación donde file2.txt es 268M, se usó un $block_size de 67M.
Las soluciones BOC1 , BOC2 , codeforester_orig , inian1 , inian4 , inian5 y gregory1 utilizaron una coincidencia flexible. 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 utilizaron un archivo regexp1.txt modificado. Las líneas en el original regexp1.txt donde 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 en el campo # 2 utilizando exclusivamente la forma ^[^|]*/|foo1|foo2|...|fooN/| en lugar.

Luego, el resto de los métodos modificados codeforester_origB , inian1B , inian4B , inian5B y gregory1B usaron un file1.txt modificado1.txt. En lugar de una palabra literal por línea, el archivo modificado file1b.txt utilizó 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 de time devuelve tres veces diferentes llamadas real , user y sys . Primero usé user + sys , pero me di cuenta de que esto era incorrecto al usar el comando paralelo Gnu, por lo que el tiempo que se informa a continuación es la parte real devuelve el 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 resto del script está disponible here .

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 central.]

|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 (268 Mb de tamaño de archivo). Extraje 1000 palabras al azar 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 construí file2.txt la misma manera que se describe anteriormente para el primer caso de prueba. Tenga en cuenta que el archivo del diccionario estaba 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:

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 laptop Ubuntu 16.10 (CPU Intel Core i7-7500U a 2.70GHz)
Todo el estudio de referencia está disponible here .

Suposiciones: 1. Desea ejecutar esta búsqueda solo en su estación de trabajo local. 2. Tiene múltiples núcleos / cpus para aprovechar una búsqueda paralela.

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

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

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

Un pequeño fragmento de código Perl resolvió el problema. Este es el enfoque adoptado:

almacenar las líneas de file1.txt en un hash
leer file2.txt línea por línea, analizar y extraer 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 unos 13 segundos, produciendo 126K partidos. Aquí está la salida de time 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 se repite 14K por cada línea en file2.txt, lo cual es realmente costoso. Abortó después de procesar 592K registros de file2.txt y producir 40K líneas coincidentes. Este es el tiempo que tardó:

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

Usando la otra solución awk @ Inian, que elimina el problema de bucle:

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 es muy impresionante aquí, dado que no tuvimos que escribir un programa completo para hacerlo.

También ejecuté el código Python de @ oliv. Tomó alrededor de 15 horas completar el trabajo, y parecía que producía los resultados correctos. Construir una expresión regular enorme no es tan eficiente como usar una búsqueda hash. Aquí la time salida:

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

Traté de seguir la sugerencia de usar parallel . Sin embargo, falló con fgrep: memory exhausted error, incluso con tamaños de bloque muy pequeños.

Lo que me sorprendió fue que fgrep era totalmente inadecuado para esto. Lo aborté después de 22 horas y produjo alrededor de 100K coincidencias. Desearía fgrep tener una opción para forzar que el contenido -f file se mantenga en un hash, al igual que lo que hizo el código Perl.

No verifiqué el join enfoque: no quería la sobrecarga adicional de ordenar los archivos. Además, dado fgrep el bajo rendimiento, no creo join que hubiera sido mejor que el código Perl.

Gracias a todos por su atención y respuestas.

Una solución de Perl. [Ver nota a continuación.]

Use un hash para el primer archivo. A medida que lee el archivo grande línea por línea, extraiga el campo mediante expresiones regulares (captura el primer patrón entre || ) o split (obtiene la segunda palabra) e imprima si exists . Es probable que difieran un poco en velocidad (cronometran). La verificación defined no es necesaria en la expresión regular mientras que para el uso split // (definido o) que cortocircuita.

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 rama if y usar el cortocircuito es más rápido, pero muy poco. En miles de millones de líneas, estos ajustes se suman, pero nuevamente no demasiado. Puede (o no) ser 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 escritura en STDOUT guarda dos operaciones y repetidamente lo cronometro para que sea 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 de exists no es necesaria y soltarla ahorra una operación. Sin embargo, siempre obtengo un mejor tiempo de ejecución, mientras que también transmite mejor el propósito. 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 se dan porque son diferentes , uno encuentra la primera coincidencia y el otro el segundo campo. Lo mantengo así como una opción más genérica, ya que la pregunta es ambigua al respecto.

Algunas comparaciones (punto de referencia) [Actualizado para escribir en STDOUT , ver "Actualización" arriba]

Hay un extenso análisis en la respuesta de HåkonHægland , cronometrando una ejecución de la mayoría de las soluciones. Aquí hay otra toma, comparando las dos soluciones anteriores, la propia respuesta del OP y la publicada fgrep , que se espera sea rápida y utilizada en la pregunta y en muchas respuestas.

Construyo datos de prueba de la siguiente manera. Un puñado de líneas de la longitud aproximadamente como se muestra están hechas con palabras aleatorias, para ambos archivos, para que coincidan en el segundo campo. Luego relleno esta "semilla" para muestras de datos con líneas que no coinciden, por lo que para imitar las proporciones entre tamaños y coincidencias citadas por OP: para 14K líneas en archivo pequeño hay 1.3M líneas en el archivo grande, produciendo 126K coincidencias. Luego, estas muestras se escriben repetidamente para construir archivos de datos completos como OP, shuffle cada vez usando List::Util .

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

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

El hecho de que el fgrep optimizado del programa C fgrep en la cima no es sorprendente. El retraso de " regex " detrás de " split " puede deberse a la sobrecarga de arrancar el motor para pequeños partidos, muchas veces. Esto puede variar con respecto a las versiones de Perl, dada la evolución de las optimizaciones del motor regex. Incluyo la respuesta de @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 (vea un comentario debajo de esta respuesta). ^†

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

La experiencia del OP de fgrep muy lento es sorprendente. Dados los tiempos de ejecución citados, un orden de magnitud más lento que el anterior, supongo que hay un viejo sistema al que "culpar".

Aunque esto está completamente basado en E / S, existen beneficios de concurrencia al colocarlo en múltiples núcleos y esperaría una buena aceleración, hasta un factor de unos pocos.

^{† Por} desgracia, el comentario se eliminó (?). En resumen: uso innecesario de un escalar (costos), de una rama if , de defined , de printf lugar de print (lento). Estos son importantes para la eficiencia en 2 mil millones de líneas.