Filtrar arquivo por número de linha

17

Dado um arquivo L com um número inteiro não negativo por linha e o arquivo de texto F, qual seria a maneira mais rápida de manter apenas essas linhas em F, cujo número de linha aparece no arquivo L?

Exemplo:

$ cat L.txt
1
3

$ cat F.txt
Hello World
Hallo Welt
Hola mundo

$ command-in-question -x L.txt F.txt
Hello World
Hola mundo

Estou procurando um comando que possa manipular um arquivo L com 500 milhões ou mais de entradas; o arquivo L é classificado numericamente.

Nota: Estou no meio de uma implementação para um, command-in-questionmas eu apenas me perguntei se seria possível usar algumas ferramentas Unix aqui também.


Atualização: Obrigado por todas as respostas, eu aprendi muito hoje! Gostaria de aceitar mais uma resposta, mas isso não é possível.

miku
fonte
Quantas linhas existem no arquivo F?
Peter.O
11
Existem, pelo menos, tantas linhas como em F em L.
miku

Respostas:

8

Com a Comissão de mensagens de erro significativas:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {

    FILE *L;
    FILE *F;

    unsigned int to_print;
    unsigned int current = 0;
    char *line = NULL;
    size_t len = 0;

    if ((L = fopen(argv[1], "r")) == NULL) {
        return 1;
    } else if ((F = fopen(argv[2], "r")) == NULL) {
        fclose(L);
        return 1;
    } else {

        while (fscanf(L, "%u", &to_print) > 0) {
            while (getline(&line, &len, F) != -1 && ++current != to_print);
            if (current == to_print) {
                printf("%s", line);
            }
        }

        free(line);
        fclose(L);
        fclose(F);
        return 0;
    }
}
FloHimself
fonte
2
Esta é a resposta de melhor desempenho aqui. Pelo menos é assim pelos meus testes. No caso de alguém estiver interessado, eu compilei como: xsel -bo | cc -xc - -o cselect. E funcionou - ele só precisa das duas libs.
mikeserv
11
Obrigado, isso é ótimo! Espero que você não se importe, mas agrupei seu código em uma pequena ferramenta .
Miku
11
@ miku Vá em frente, estou feliz por poder ajudar. Percebi que você aumentou LINE_MAXem sua versão, então provavelmente trabalha com linhas muito grandes em seus arquivos. Atualizei o A com uma versão usando getline()para remover o limite de tamanho da linha.
FloHimself
@ FlloHimself, bem, obrigado novamente :) De fato, algumas linhas de entrada podem exceder LINE_MAX, então getlineparece correto.
Miku
10

Eu usaria awk, mas não armazenaria todo o conteúdo da L.txtmemória e faria pesquisas desnecessárias de hash ;-).

list=L.txt file=F.txt
LIST="$list" awk '
  function nextline() {
    if ((getline n < list) <=0) exit
  }
  BEGIN{
    list = ENVIRON["LIST"]
    nextline()
  }
  NR == n {
    print
    nextline()
  }' < "$file"
Stéphane Chazelas
fonte
Exatamente, tentei mapas de hash e eles excederiam a memória; bitsets comprarão mais espaço para você; mas, usando o fato de que a entrada é classificada, você pode se livrar completamente desse problema (de espaço).
Miku
11
@Janis; Não é que apenas um caso de bom padrão prática de codificação: Não rígidos literais de código - use variáveis em vez ... (mais flexível e menos propenso a erros, e mais fácil de manter)
Peter.O
11
@ StéphaneChazelas: É necessário pré-inicialização circuito de n, de outro modo (como está) que perde 1emL.txt
Peter.O
11
@ Peter.O, opa, foi com isso que eu tentei resolver por NR> = n, mas estava errado. Deve ser melhor agora.
Stéphane Chazelas
11
@ Janis, a ideia era que, se esse código fosse incorporado em um command-in-questionscript, não seria possível incorporar o nome do arquivo no código. -v list="$opt_x"também não funciona por causa do processamento de barra invertida feito pelo awk nele. É por isso que eu uso o ENVIRON aqui.
Stéphane Chazelas
10

grep -n | sort | sed | cut

(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F

Isso deve funcionar muito rapidamente (alguns testes cronometrados estão incluídos abaixo) com entradas de qualquer tamanho. Algumas notas sobre como:

  • export LC_ALL=C
    • Como o objetivo da operação a seguir é colocar o arquivo inteiro ./Fempilhado em linha com ./Lo arquivo lineno, os únicos caracteres com os quais realmente precisamos nos preocupar são os [0-9]dígitos ASCII e os :dois pontos.
    • Por esse motivo, é mais simples se preocupar em encontrar esses 11 caracteres em um conjunto de 128 possíveis do que se o UTF-8 estiver envolvido.
  • grep -n ''
    • Isso insere a string LINENO:na cabeça de cada linha em stdin - ou <./F.
  • sort -t: -nmk1,1 ./L -
    • sortnegligências para classificar seus arquivos de entrada em tudo, e em vez disso (corretamente) presume que eles são pré-classificados e -mErges-los em -numericallyordem de classificação, ignorando basicamente qualquer coisa além de qualquer possível -k1,1ocorrendo st -t:carácter dois pontos de qualquer maneira.
    • Embora isso possa exigir algum espaço temporário (dependendo da distância que algumas sequências possam ocorrer) , não exigirá muito em comparação com uma classificação adequada e será muito rápido porque envolve zero retorno.
    • sortproduzirá um único fluxo no qual qualquer linha de entrada ./Lprecederá imediatamente as linhas correspondentes ./F. ./LAs linhas de sempre vêm primeiro porque são mais curtas.
  • sed /:/d\;n
    • Se a linha atual corresponder a /:/dois pontos, delimine-a da saída. Senão, imprima automaticamente a nlinha atual e ext.
    • E assim sedpoda sorta saída apenas para pares de linhas sequenciais que não correspondem a dois pontos e à seguinte linha - ou, apenas a uma linha de ./Le depois a seguinte.
  • cut -sd: -f2-
    • cut -ssuprime da saída as linhas de entrada que não contêm pelo menos uma de suas -d:seqüências de elimitadores - e, portanto ./L, as linhas são completamente removidas.
    • Para essas linhas, o primeiro campo :delimitado por dois pontos -festá cutausente - e o mesmo ocorre com todos grepos lineno inseridos.

teste de entrada pequena

seq 5 | sed -ne'2,3!w /tmp/L
        s/.*/a-z &\& 0-9/p' >/tmp/F

... gera 5 linhas de entrada de amostra. Então...

(   export LC_ALL=C; </tmp/F \
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)|  head - /tmp[FL]

... imprime ...

==> standard input <==
a-z 1& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/F <==
a-z 1& 0-9
a-z 2& 0-9
a-z 3& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/L <==
1
4
5

testes cronometrados maiores

Criei alguns arquivos bastante grandes:

seq 5000000 | tee /tmp/F |
sort -R | head -n1500000 |
sort -n >/tmp/L

... que coloca linhas de 5mil e linhas de /tmp/F1,5mil selecionadas aleatoriamente /tmp/L. Eu então fiz:

time \
(   export LC_ALL=C
    grep -n ''   | sort -t:  -nmk1,1 ./L - |
    sed /:/d\;n  | cut  -sd: -f2-
)   <./F |wc - l

Imprimiu:

1500000
grep -n '' \
    0.82s user 0.05s system 73% cpu 1.185 total
sort -t: -nmk1,1 /tmp/L - \
    0.92s user 0.11s system 86% cpu 1.185 total
sed /:/d\;n \
    1.02s user 0.14s system 98% cpu 1.185 total
cut -sd: -f2- \
    0.79s user 0.17s system 80% cpu 1.184 total
wc -l \
    0.05s user 0.07s system 10% cpu 1.183 total

(Eu adicionei as barras invertidas lá)

Entre as soluções atualmente oferecidas aqui, essa é a mais rápida de todas, exceto uma quando comparada com o conjunto de dados gerado acima na minha máquina. Dos outros, apenas um chegou perto de disputar o segundo lugar, e esse é o meuh perl aqui .

Esta não é de forma alguma a solução original oferecida - ela perdeu um terço do seu tempo de execução graças a conselhos / inspiração oferecidos por outros. Veja o histórico de publicações para soluções mais lentas (mas por quê?) .

Além disso, vale a pena notar que algumas outras respostas podem muito bem apresentar-se melhor se não fossem a arquitetura de várias CPUs do meu sistema e a execução simultânea de cada um dos processos nesse pipeline. Todos eles trabalham ao mesmo tempo - cada um no seu próprio núcleo de processador - passando os dados e fazendo sua pequena parte do todo. É muito legal.

mas a solução mais rápida é ...

Mas não é a solução mais rápida. A solução mais rápida oferecido aqui, mãos para baixo, é o programa C . Eu chamei cselect. Depois de copiá-lo para minha área de transferência do X, compilei-o como:

xsel -bo | cc -xc - -o cselect

Eu então fiz:

time \
    ./cselect /tmp/L /tmp/F |
wc -l

... e os resultados foram ...

1500000
./cselect /tmp/L /tmp/F  \
    0.50s user 0.05s system 99% cpu 0.551 total
wc -l \
    0.05s user 0.05s system 19% cpu 0.551 total
mikeserv
fonte
11
Você pode torná-lo muito mais rápido (quase tão rápido quanto o meu em sistemas multi-core) com sed -ne'/:/!{n;p;}' | cut -d: -f2-, em vez desed -ne'/:/!N;/\n/s/[^:]*://p'
Stéphane Chazelas
@ StéphaneChazelas - você pode obter melhores resultados se alternar seds - o que sedeu estou usando é a herança sed- você pode ver o aliasvalor nos timeresultados. A propósito, meu pacote de herança é compilado estaticamente em relação a uma musl libc - cuja implementação de regex é baseada no TRE . Quando eu o troco para o GNU sed- e o executo sem cut- ele adiciona um segundo inteiro ao tempo de conclusão (2,8 segundos) - aumenta em mais de um terço. E isso é apenas 0,3 segundos mais rápido que o seu no meu sistema.
mikeserv
11
sort -mnao contrário sort -nmk1,1poderia ser melhor como você não precisa fazer a divisão aqui (não testado)
Stéphane Chazelas
@ StéphaneChazelas - sim, pensei o mesmo e tentei de todas as maneiras. -né especificado apenas para fazer a primeira string numérica de uma linha, então imaginei, ok -mnou -nme, por qualquer motivo, as únicas vezes em que ele caiu abaixo de 2 s no tempo de conclusão foi quando adicionei todas as opções como estão. É estranho - e é a razão pela qual ontem não adotei -m- eu sabia o que era, mas parecia funcionar como algum tipo de otimização automática. Curiosamente, a herança sorttem uma -zopção de cadeia de comprimento, que só se aplica a -[cm]....
mikeserv
-nnão é a primeira sequência numérica na linha . Apenas considera a linha como um número, portanto, abc 123seria 0. Portanto, não pode ser menos eficiente do que com #-t: -k1,1
Stéphane Chazelas 14/15/15
9

Eu usaria awk:

awk 'NR==FNR {a[$1]; next}; FNR in a' L.txt F.txt

Atualização: eu fiz medidas de desempenho; parece que esta versão é ainda melhor com conjuntos de dados muito grandes (como é o caso dos requisitos declarados), pois a comparação é muito rápida e compensa demais o esforço necessário para criar a tabela de hash.

Janis
fonte
11
@miku; Sim, é uma boa solução compacta. Mas uma ressalva; nem todos os awks podem lidar com conjuntos de dados tão grandes. - Estou usando o GNU awke não há problemas; o teste com 500 milhões de linhas de dados levou 7 minutos.
Janis
11
Isso é bastante lento (por comparação) real 16m3.468s- user 15m48.447s- sys 0m10.725s. Ele usou 3,3 GB de RAM testando um tamanho de 1/10 de polegada Lcom 50.000.000 de linhas; e Fcom 500.000.000 de linhas - contra o tempo de despertar ansioso de Stéphane Chazelas: real 2m11.637s- user 2m2.748s- sys 0m6.424s- Não estou usando uma caixa rápida, mas a comparação é interessante.
Peter.O
@ Peter.O; Obrigado pelos dados! Era de esperar uma velocidade mais lenta, dado que (no meu próprio caso de teste) meio bilhão de linhas foram armazenadas em uma matriz associativa. (Foi por isso que comentei "(+1)" acima na proposta de Stephane.) - Embora eu estivesse surpreso que essa solução concisa ainda estivesse processando 1 milhão de linhas por segundo! Eu acho que faz desse padrão de código (por causa de sua simplicidade!) Uma opção viável, e especificamente em casos com tamanhos de dados menos extremos.
Janis
Definitivamente, é uma solução viável. Nos dados de teste que usei (5mil linhas / 1,5mil L), o seu foi concluído em pouco mais de 4 segundos - apenas um segundo atrás da resposta de Stephane. O código usado para geração do conjunto de teste é na minha resposta, mas é na maior parte apenas seqde saída e, em seguida, uma menor, subconjunto seleccionado aleatoriamente do mesmo em L .
mikeserv
11
Acabei de fazer mais algumas medidas de desempenho com um tamanho de arquivo de dados de 500 milhões de linhas e um tamanho de arquivo principal de 50 milhões e resp. 500 milhões de linhas, com uma observação notável. Com o arquivo-chave menor, os tempos são de 4 min (Stephane) vs. 8 min (Janis), enquanto que com o arquivo-chave maior, são 19 min (Stephane) vs. 12 min (Janis).
Janis
3

Apenas para completar: podemos mesclar o excelente script awk na resposta de Stéphane Chazelas, e o script perl na resposta de kos, mas sem manter a lista inteira na memória, na esperança de que o perl possa ser mais rápido que o awk. (Alterei a ordem dos argumentos para corresponder à pergunta original).

#!/usr/bin/env perl
use strict;

die "Usage: $0 l f\n" if $#ARGV+1 != 2;
open(L,$ARGV[0]) or die "$ARGV[0]: $!";
open(F,$ARGV[1]) or die "$ARGV[1]: $!";

while(my $number = <L>){
    #chop $number;
    while (<F>) {
        if($. == $number){
            print;
            last;
        }
    }
}
meuh
fonte
Isso é muito mais rápido que o awk. É quase tão rápido quanto o meu - eu testei as três vezes agora e cada vez o meu manipulava meu conjunto de testes de linha de 5mil em 1,8 ... segundos e o seu 1,9 ... segundos de cada vez. O código gen do conjunto de testes está na minha resposta, se você se importa, mas o ponto é que é muito bom. Além do mais, a saída está correta - eu ainda não posso fazer o awktrabalho ... Ainda assim, ambas as nossas respostas são envergonhadas pelas da FloHimself .
mikeserv
@ MikeServ, devemos ter diferentes awks. Na sua amostra, recebo 1,4s com gawk (4s para Janis '), 0,9s com mawk, 1,7s com esta solução perl, 2,3s com kos', 4,5s com o seu (GNU sed) e 1,4s com o seu ( GNU sed) e minha melhoria sugerida (e 0,5s para a solução C).
Stéphane Chazelas
@mikeserv, ah! claro que com a sua abordagem, a localidade faz a diferença. Para baixo de 4.5s para 2.3s aqui quando se muda de UFT-8 para C.
Stéphane Chazelas
3

Eu escrevi um script Perl simples para fazer isso:

Usage: script.pl inputfile_f inputfile_f

#!/usr/bin/env perl

$number_arguments = $#ARGV + 1;
if ($number_arguments != 2) {
    die "Usage: script.pl inputfile_f inputfile_l\n";
}

open($f, '<', $ARGV[0])
    or die "$ARGV[0]: Not found\n";
open($l, '<', $ARGV[1])
    or die "$ARGV[1]: Not found\n";

@line_numbers = <$l>;

while ($line = <$f>) {
    $count_f ++;
    if ($count_f == @line_numbers[$count_l]) {
        print $line;
        $count_l ++;
    }
}
  • Cargas F.txt
  • Cargas L.txt
  • Armazena cada linha L.txtem uma matriz
  • F.txtlinha por linha, rastreando seu número de linha atual e o índice atual da matriz; aumenta o F.txtnúmero da linha atual; se o F.txtnúmero da linha atual corresponder ao conteúdo da matriz no índice atual da matriz, ele imprimirá a linha atual e aumentará o índice

Considerações de custo e complexidade :

Considerando o custo para fazer as atribuições, o custo para fazer as comparações e o custo para imprimir as linhas, dado N 1 como o número de linhas F.txte N 2 como o número de linhas L.txt, o whileloop é executado no máximo N 1 vezes, levando a atribuições 2N 1 + N 2 (obviamente assumindo N 1 > N 2 ), comparações 2N 1 e impressões de N 2 ; dado como igual ao custo de cada operação, o custo total para executar o whileloop é 4N 1 + 2N 2 , o que leva a uma complexidade do script de O (N).

Teste em um arquivo de entrada de 10 milhões de linhas :

Usando um F.txtarquivo de 10 milhões de linhas contendo linhas aleatórias de 50 caracteres e um L.txtarquivo de 10 milhões de linhas contendo números de 1 a 10000000 (pior cenário):

~/tmp$ for ((i=0; i<3; i++)); do time ./script.pl F.txt L.txt > output; done

real    0m15.628s
user    0m13.396s
sys 0m2.180s

real    0m16.001s
user    0m13.376s
sys 0m2.436s

real    0m16.153s
user    0m13.564s
sys 0m2.304s
kos
fonte
2

Essa solução perl é mais rápida do que as outras soluções awk ou perl em 20% ou mais, mas não é tão rápida quanto a solução em C.

perl -e '
  open L, shift or die $!;
  open F, shift or die $!;
  exit if ! ($n = <L>);
  while (1) {
    $_ = <F>;
    next if $. != $n;
    print;
    exit if ! ($n = <L>);
  }
' -- L F
jrw32982 suporta Monica
fonte
0
cat <<! >L.txt
1
3
!

cat <<! >F.txt
Hello World
Hallo Welt
Hola mundo
!

cmd(){
 L=$1 F=$2
 cat -n $F |
 join $L - |
 sed 's/[^ ]* //'
}

cmd L.txt F.txt
Hello World
Hola mundo

Como L.txt está classificado, você pode usar join. Apenas numere cada linha em F.txt, junte os dois arquivos e remova o número da linha. Nenhum arquivo intermediário grande é necessário.

Na verdade, o acima irá alterar suas linhas de dados, substituindo todo o espaço em branco por um único espaço. Para manter a linha intacta, você precisa escolher como delimitador algum caractere que não apareça nos seus dados, por exemplo, "|". O cmd é então

cmd(){
 L=$1 F=$2
 cat -n $F |
 sed 's/^ *//;s/\t/|/' |
 join -t'|' $L - |
 sed 's/[^|]*|//'
}

O primeiro sed remove espaços à esquerda da saída "cat -n" e substitui a guia. O segundo sed remove o número da linha e "|".

meuh
fonte
Receio que isso não funcione em arquivos maiores. Precisa de <10 linhas. Eu tive a mesma idéia e tentei, join L.txt <(nl F.txt )mas não funcionará em arquivos grandes. Bem-vindo ao site, a propósito, nem sempre recebemos respostas tão claras e bem formatadas de novos usuários!
terdon
@terdon, Sim, uma pena que join/ commnão possa funcionar com entradas classificadas numericamente.
Stéphane Chazelas
@terdon: Eu segui sua liderança (agora excluída) e tentei join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-- Foi lento! - e mesmo quando eu alimentei os arquivos preparados com as teclas preenchidas com 0 join -t' ' L.txt F.txt | cut -d' ' -f2- , ainda era lento (não incluindo o tempo de preparação) - mais lento que a awkresposta de @Janis (onde eu postei um comentário sobre o tempo real gasto para ambos resposta de his e @ StéphaneChazelas '
Peter.O
@ Peter.O sim. Tentei uma abordagem semelhante que evita um dos awks, mas não consegui encontrar uma maneira de fazê-lo funcionar e valer a pena.
terdon
@terdon e outros: O tempo real para a substituição do processojoin + foi contra Stéphane Chazelas ' usando 50 milhões de linhas, 500 milhões de linhas. awk printf real 20m11.663s user 19m35.093s sys 0m10.513sreal 2m11.637s user 2m2.748s sys 0m6.424sLF
Peter.O
0

Para completar, outra tentativa de joinsolução:

sed -r 's/^/00000000000000/;s/[0-9]*([0-9]{15})/\1/' /tmp/L | join <( nl -w15 -nrz /tmp/F ) - | cut -d' ' -f2-

Isso funciona formatando a coluna de número de linha que une funciona como comprimento fixo com zeros à esquerda, para que os números tenham sempre 15 dígitos. Isso contorna o problema de associação, não gostando da ordem de classificação numérica normal, pois a coluna agora foi efetivamente forçada a ser uma classificação de dicionário. nlé usado para adicionar números de linha nesse formato ao F.txt. Infelizmente, sedprecisa ser usado para reformatar a numeração em L.txt.

Essa abordagem parece funcionar bem nos dados de teste gerados usando o método @ mikeserv. Mas ainda é muito lento - a solução c é 60x mais rápida na minha máquina. cerca de 2/3 do tempo é gasto sede 1/3 pol join. Talvez exista uma melhor expressão de sed ...

Trauma Digital
fonte
Ok - mas por que estamos acrescentando todos os zeros? Estou tentando sentir isso. Além disso, nlé super legal, mas você não pode usá-lo com robustez em entradas não testadas. Uma das coisas que o torna tão legal é seu elimitador de página lógica -d . Por padrão, se houver alguma linha na entrada que consiste apenas das seqüências de caracteres :\` (mas sem o túmulo à direita) 1, 2, 3 ou três vezes seguidas, suas contagens ficarão um pouco loucas. Experimente com ele - é bem legal. Especialmente ter um olhar para o que acontece quando nl` lê uma linha com a corda 1 delimitador e depois outra w / 3 ou 2
mikeserv
0

Como a resposta aceita está em C, concluí que não há problema em lançar uma solução python aqui:

# Read mask
with open('L.txt', 'r') as f:
    mask = [int(line_num) for line_num in f.read().splitlines()]

# Filter input file
filtered_lines = []
with open('F.txt', 'r') as f:
    for i, line in enumerate(f.read().splitlines()):
        if (i+1) in mask:
            filtered_lines.append(line)

# Write newly filtered file
with open('F_filtered.txt', 'w') as f:
    for line in filtered_lines:
        f.write('%s\n' % line)

Se usar uma biblioteca externa como numpy, uma solução pareceria ainda mais elegante:

import numpy as np

with open('L.txt', 'r') as f:
    mask = np.array([int(line_num)-1 for line_num in f.read().splitlines()])

with open('F.txt', 'r') as f:
    lines = np.array(f.read().splitlines())
filtered_lines = lines[mask]

with open('F_filtered.txt', 'w') as f:
    for line in filtered_lines:
        f.write('%s\n' % line)
AlexG
fonte