Filtra o arquivo pelo número da linha

Question

Dado um arquivo L com um número inteiro não negativo por linha e arquivo de texto F, qual seria uma maneira 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 na metade de uma implementação de command-in-question , mas eu gostaria de saber se também é possível usar algumas ferramentas do Unix aqui.

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

    

Answer 1

Com C omitindo 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;
    }
}

    

Answer 2

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

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"

    

Answer 3

Eu usaria awk :

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

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

    

Answer 4

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 são incluídos abaixo) com entrada de qualquer tamanho. Algumas notas sobre como:

• %código%
  • Como o objetivo da operação a seguir é obter o arquivo inteiro de export LC_ALL=C empilhado em linha com o arquivo ./F lineno, os únicos caracteres com os quais realmente precisamos nos preocupar são ASCII ./L dígitos e [0-9] dois pontos.
  • Por essa razão, é mais simples se preocupar em encontrar esses 11 caracteres em um conjunto de 128 possíveis do que se o UTF-8 estivesse envolvido.
• %código%
  • Isso insere a string : na cabeça de cada linha em stdin - ou grep -n '' .
• %código%
  • LINENO: não classifica seus arquivos de entrada, e em vez disso, (corretamente) presume que eles são pré-definidos e <./F os ordena em sort -t: -nmk1,1 ./L - ordem ordenada, ignorando basicamente qualquer coisa além de qualquer possível sort st ocorrendo -m caracteres de dois pontos de qualquer maneira.
  • Embora isso possa exigir algum espaço temporário para fazer (dependendo de quão distantes algumas seqüências podem ocorrer) , ele não exigirá muito em comparação a uma classificação adequada, e será muito rápido porque envolve zero backtracking.
  • -numerically produzirá um único fluxo onde qualquer lineno em -k1,1 imediatamente precederá as linhas correspondentes em -t: . As linhas de sort sempre vêm em primeiro lugar porque são mais curtas.
• %código%
  • Se a linha atual corresponder a ./L colon ./F elete da saída. Senão, imprima automaticamente a linha atual e ./L ext.
  • E assim sed /:/d\;n extrai a saída de /:/ para somente pares de linhas seqüenciais que não correspondem à vírgula e à linha seguinte - ou apenas a uma linha de d e o próximo.
• %código%
  • n sed comprime de saída aquelas de suas linhas de entrada que não contêm pelo menos uma de suas sort elimitadoras - e assim as linhas ./L são removidas completamente.
  • Para essas linhas, o primeiro cut -sd: -f2- delimitado por dois pontos percentuais cut é -s ausente - e assim vai todo o lineno de -d: inserido.

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

Eu criei alguns arquivos muito grandes:

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

... o qual coloca 5mil linhas em ./L e 1,5mil linhas aleatoriamente selecionadas em : . 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

Impresso:

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

(adicionei as barras invertidas)

Entre as soluções atualmente oferecidas aqui, esta é 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 -f aqui do meuh.

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

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

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

Mas esta não é a solução mais rápida. A solução mais rápida oferecida aqui, com as mãos para baixo, é o programa C . Eu chamei de cut . Depois de copiá-lo para o meu X clipboard, eu compilei 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

    

Answer 5

Apenas pela perfeição: podemos mesclar o excelente script awk na resposta de Stéphane Chazelas e o script perl na resposta do kos, mas sem manter toda a lista na memória, na esperança de que o perl seja mais rápido que o awk. (Eu mudei a ordem de args para coincidir com a 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;
        }
    }
}

    

Answer 6

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 ++;
    }
}

• carrega F.txt
• carrega L.txt
• Armazena cada linha de L.txt em uma matriz
• Lê F.txt linha por linha, rastreando seu número de linha atual e o índice de matriz atual; aumenta o número da linha atual de F.txt ; se o número da linha atual de F.txt corresponder ao conteúdo da matriz no índice da matriz atual, ele imprimirá a linha atual e aumentará o índice

Considerações sobre 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, considerando N ₁ como o número de linhas em F.txt e N ₂ como o número de linhas em L.txt , o loop while é executado no máximo N ₁ vezes, levando a 2N ₁ + N ₂ atribuições (obviamente assumindo N ₁ > N ₂ ), para 2N ₁ comparações e para N ₂ sub> impressões; dado igual ao custo de cada operação, o custo total para executar o loop while é 4N ₁ + 2N ₂ , 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 arquivo de 10 milhões de linhas F.txt contendo linhas aleatórias de 50 caracteres e um arquivo de 10 milhões de linhas L.txt 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

    

Answer 7

Esta solução perl é mais rápida do que as outras soluções awk ou perl em 20% ou mais, mas oviously não tão rápido 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

    

Answer 8

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 é classificado, você pode usar a união. Apenas numere cada linha em F.txt, junte os dois arquivos e remova o número da linha. Não há arquivos intermediários grandes são necessários.

Na verdade, o acima irá mangle 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 os espaços iniciais da saída "cat -n" e substitui a guia. O segundo sed remove o número da linha e "|".

    

Answer 9

Para completar, outra tentativa na join solution:

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

Isso funciona formatando a coluna de número de linha que a junção trabalha como comprimento fixo com zeros à esquerda, para que os números tenham sempre 15 dígitos. Isso contorna o problema de não gostar da ordem de classificação numérica normal, já que agora a coluna foi forçada a ser classificada como dicionário. nl é usado para adicionar números de linhas neste formato a F.txt. Infelizmente sed precisa ser usado para reformatar a numeração em L.txt.

Esta 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 em sed e 1/3 em join . Talvez haja uma melhor expressão sed ...

    

Answer 10

Como a resposta aceita é 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 estiver usando 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)