linux - parametros - example awk scripts



A maneira mais rápida de encontrar linhas de um arquivo de outro arquivo maior no Bash (11)

Aqui está a solução Perl usada Inline::C para acelerar a pesquisa de campos correspondentes no arquivo 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 );

A search() sub-rotina é implementada em C puro usando perlapi para procurar chaves no dicionário de arquivos pequenos %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" );

}

Os testes indicam que é aproximadamente três vezes mais rápido que a solução Perl pura mais rápida (consulte o método zdim2 na minha outra resposta ) apresentada aqui.

https://src-bin.com

Eu tenho dois arquivos, file1.txt e file2.txt . file1.txt possui cerca de 14 file2.txt linhas e file2.txt possui cerca de 2 bilhões. file1.txt possui um único campo f1 por linha, enquanto file2.txt possui 3 campos, de f1 a f3 , delimitados por | .

Quero encontrar todas as linhas do file2.txt que f1 do file1.txt corresponde à f2 do file2.txt (ou em qualquer lugar da linha, se não quisermos gastar tempo extra dividindo os valores do file2.txt ).

file1.txt (cerca de 14K linhas, não classificadas ):

foo1
foo2
...
bar1
bar2
...

file2.txt (cerca de 2 bilhões de linhas, não classificadas ):

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

Aqui está o que eu tentei e parece levar várias horas para executar:

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

Gostaria de saber se existe uma maneira melhor e mais rápida de fazer essa operação com os comandos comuns do Unix ou com um pequeno script.


Answer #1

Aqui está uma solução Python usando conjuntos - aproximadamente equivalente a uma matriz de hash ou awk de chave Perl apenas no conceito.

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

Quando executo isso em arquivos de tamanho semelhante, ele é executado em cerca de 8 segundos.

Mesma velocidade que:

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

Tanto a solução Python quanto a awk aqui são apenas correspondências completas; não é uma correspondência parcial no estilo regex.

Como a solução awk é rápida e compatível com POSIX, essa é a melhor resposta.


Answer #2

Este script Perl ( a ) gera um padrão 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] . ")\\|");

Veja como ele pode ser usado:

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

Observe que o script usa Regexp :: Assemble, portanto, você pode precisar instalá-lo.

sudo su
cpan Regexp::Assemble

Notas:

  • Ao contrário das soluções denominadas BOC1, BOC2, codeforester_orig, gregory1, inian2, inian4 e oliv, minha solução lida corretamente

    file1.txt
    foo1
    
    file2.txt
    date1|foo12|number5
  • O meu deve ser melhor do que a solution semelhante do @BOC, porque o padrão é otimizado para reduzir o retorno. (O meu também funciona se houver mais de três campos file2.txt , enquanto a solução vinculada pode falhar.)

  • Não sei como ele se compara às soluções split + dictionary.


Answer #3

Eu usaria SQLite3 :) Talvez banco de dados em memória ou o que quer. Importe os arquivos e use a consulta SQL.


Answer #4

Uma maneira possível é 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

e use-o assim:

python test.py file1.txt file2.txt

Answer #5

Usando flex :

1: construa o processador flex:

$ 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

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

3: e corra

$ a.out < file2.txt  > out

Compilar (cc ...) é um processo lento; essa abordagem pagará apenas pelos casos de file1.txt estável

(Na minha máquina) O tempo gasto para executar um teste "100 em 10_000_000" nessa abordagem é 3 vezes mais rápido que LC_ALL=C fgrep...


Answer #6

Você também pode usar o Perl para isso:

Observe que isso consumirá memória e sua máquina / servidor possui melhor.

Dados de amostra:

%[email protected] * /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
%[email protected] * /root/ga/study/pl>

Saída do script: o script produzirá a saída final em um arquivo chamado output_comp .

%[email protected] * /root/ga/pl> ./comp.pl  file1.txt file2.txt ; cat output_comp
date1|bar1|number1
date2|bar2|number2
date2|foo2|number2
date1|foo1|number1
%[email protected] * /root/ga/pl>

Roteiro:

%[email protected] * /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  ;
%[email protected] * /root/ga/pl>

Obrigado.


Answer #7

definir o idioma etc ajuda um pouco, talvez.

caso contrário, não consigo pensar em uma solução mágica para escapar do seu problema básico: os dados não estão estruturados; portanto, você terá uma pesquisa que se resume ao número de linhas no arquivo1 multiplicado pelo número de linhas no arquivo2.

colocar o bilhão de linhas em um banco de dados e indexá-lo de maneira inteligente é a única velocidade que consigo pensar. esse índice teria que ser muito inteligente, embora ......

A solução simples é: ter memória suficiente para ajustar tudo. caso contrário, nada mais do que você pode fazer sobre isso ....


Answer #8

Pressupostos: 1. Você deseja executar esta pesquisa apenas na estação de trabalho local. 2. Você tem vários núcleos / cpus para aproveitar uma pesquisa paralela.

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

Alguns ajustes adicionais, dependendo do contexto: A. Desative o NLS com LANG = C (isso já foi mencionado em outra resposta) B. Defina um número máximo de correspondências com o sinalizador -m.

Nota: Suponho que o arquivo2 tenha ~ 4 GB e o tamanho do bloco de 10M esteja ok, mas pode ser necessário otimizar o tamanho do bloco para obter a execução mais rápida.


Answer #9

Um pequeno pedaço de código Perl resolveu o problema. Esta é a abordagem adotada:

  • armazene as linhas de file1.txt em um hash
  • leia file2.txt linha por linha, analise e extraia o segundo campo
  • verifique se o campo extraído está no hash; Nesse caso, imprima a linha

Aqui está o 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);

Eu executei o script acima com 14K linhas no arquivo1.txt e 1.3M linhas no arquivo2.txt. Terminou em cerca de 13 segundos, produzindo 126 mil correspondências. Aqui está a saída de time para o mesmo:

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

Corri o código awk do @ Inian:

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

Era muito mais lento que a solução Perl, pois está repetindo 14K vezes para cada linha no arquivo2.txt - o que é realmente caro. Ele foi interrompido após o processamento de 592K registros do file2.txt e a produção de 40K linhas correspondentes. Aqui está quanto tempo levou:

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 a outra solução awk @ Inian, que elimina o problema de loop:

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 é muito impressionante aqui, já que não precisamos escrever um programa inteiro para isso.

Corri o código Python do @ oliv também. Demorou cerca de 15 horas para concluir o trabalho e parecia que produziu os resultados certos. Construir um regex enorme não é tão eficiente quanto usar uma pesquisa de hash. Aqui a time saída:

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

Tentei seguir a sugestão de usar parallel . No entanto, falhou com fgrep: memory exhausted erro, mesmo com tamanhos de bloco muito pequenos.

O que me surpreendeu foi que fgrep era totalmente inadequado para isso. Abortei-o após 22 horas e produziu cerca de 100 mil correspondências. Eu gostaria que fgrep tivesse uma opção para forçar o conteúdo -f file a ser mantido em um hash, exatamente como o código Perl fez.

Não verifiquei a join abordagem - não queria a sobrecarga adicional de classificar os arquivos. Além disso, dado fgrep o fraco desempenho, não acredito join que teria feito melhor que o código Perl.

Obrigado a todos por sua atenção e respostas.


Answer #10

Você tentou o Awk que poderia acelerar um pouco as coisas:

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

(ou) usando a função index() no Awk como sugerido pelos comentários de Benjamin W. , abaixo

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

(ou) uma correspondência de regex mais direta, conforme sugerido por Ed Morton nos comentários,

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

é tudo o que você precisa. Suponho que isso será mais rápido, mas não exatamente certo em arquivos com mais de um milhão de entradas. Aqui o problema está na possibilidade de corresponder em qualquer lugar ao longo da linha. Se o mesmo estivesse em qualquer coluna em particular (por exemplo, digamos, $2 ), uma abordagem mais rápida poderia

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

Além disso, você pode acelerar as coisas jogando com o locale do locale definido no seu sistema. Parafraseando a maravilhosa resposta de Stéphane Chazelas sobre o assunto, você pode acelerar as coisas rapidamente, definindo a passagem do LC_ALL=C idioma LC_ALL=C para o comando que está sendo executado localmente .

Em qualquer sistema baseado em GNU , os padrões para o locale do 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=

Com uma variável LC_ALL , você pode definir todas as variáveis ​​do tipo LC_ uma vez para um código de idioma especificado

$ 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

Então, o que isso afeta?

Simplificando, ao usar o locale C , o padrão será o locale C base do servidor Unix / Linux ASCII . Basicamente, quando você grep alguma coisa, por padrão, seu local será internacionalizado e definido como UTF-8 , que pode representar todos os caracteres no conjunto de caracteres Unicode para ajudar a exibir qualquer sistema de escrita do mundo, atualmente com mais de 110,000 caracteres únicos, enquanto que com ASCII cada caractere é codificado em uma sequência de bytes simples e seu conjunto de caracteres é composto por não mais que 128 caracteres únicos.

Portanto, isso se traduz no seguinte: ao usar grep em um arquivo codificado no conjunto de caracteres UTF-8 , ele precisa corresponder cada caractere a qualquer um dos cem mil caracteres únicos, mas apenas 128 no ASCII ; portanto, use seu fgrep como

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

Além disso, o mesmo pode ser adaptado ao Awk , já que ele usa uma correspondência de regex com a chamada de match($0,i) , definir o C idioma C poderia acelerar a correspondência de cadeia.

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




grep