Filtruj plik według numeru linii

Biorąc pod uwagę plik L z jedną nieujemną liczbą całkowitą na wiersz i plik tekstowy F, jaki byłby szybki sposób na zachowanie tylko tych wierszy w F, których numer pojawia się w pliku L?

Przykład:

$ 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

Szukam polecenia, które może obsłużyć plik L zawierający 500 milionów lub więcej wpisów; plik L jest sortowany numerycznie.

Uwaga: Jestem w połowie wdrażania, command-in-questionale zastanawiałem się, czy można tu również użyć niektórych narzędzi uniksowych.

Aktualizacja: Dziękuję za wszystkie odpowiedzi, dzisiaj wiele się nauczyłem! Chciałbym zaakceptować więcej niż jedną odpowiedź, ale nie jest to możliwe.

Z Cpominięciem istotnych komunikatów o błędach:

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

Używałbym awk, ale nie zapisywałbym całej zawartości L.txtw pamięci i robiłbym niepotrzebne wyszukiwanie 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"

grep -n | sort | sed | cut

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

To powinno działać dość szybko (niektóre testy czasowe są zawarte poniżej) z wejściem dowolnego rozmiaru. Kilka uwag na temat:

• export LC_ALL=C
  • Ponieważ celem następującej operacji jest ./Fułożenie całego pliku w stos z ./Lplikiem lineno, jedynymi znakami, o które naprawdę będziemy musieli się martwić, są [0-9]cyfry ASCII i :dwukropek.
  • Z tego powodu łatwiej jest martwić się znalezieniem tych 11 znaków w zestawie 128 możliwych niż w przypadku, gdy UTF-8 jest zaangażowany w inny sposób.
• grep -n ''
  • To wstawia ciąg LINENO:do nagłówka każdej linii w stdin - lub <./F.
• sort -t: -nmk1,1 ./L -
  • sortw ogóle zaniedbuje sortować swoje pliki wejściowe, a zamiast tego (poprawnie) zakłada, że ​​są one wstępnie sortowane i -mustawia je w -numericallyporządku posortowanym, ignorując w zasadzie wszystko poza jakimkolwiek potencjalnie -k1,1występującym -t:znakiem dwukropka.
  • Chociaż może to wymagać trochę przestrzeni tymczasowej (w zależności od tego, jak daleko mogą wystąpić pewne sekwencje) , nie będzie wymagało wiele w porównaniu z odpowiednim rodzajem i będzie bardzo szybkie, ponieważ wymaga zerowego śledzenia.
  • sortwyświetli pojedynczy strumień, w którym dowolne wejście lineno ./Lbędzie bezpośrednio poprzedzać odpowiednie wiersze w ./F. ./LLinie zawsze są na pierwszym miejscu, ponieważ są krótsze.
• sed /:/d\;n
  • Jeśli bieżący wiersz pasuje do /:/dwukropka, dusuń go z wyjścia. W przeciwnym razie automatycznie wydrukuj bieżącą i nzewnętrzną linię.
  • I tak sedprzycina sortwyniki tylko do sekwencyjnych par linii, które nie pasują do dwukropka i następnej linii - lub, tylko do linii od ./Li do następnej.
• cut -sd: -f2-
  • cut -swypisuje z wyjścia te z linii wejściowych, które nie zawierają co najmniej jednego z -d:łańcuchów eliminatora - a zatem ./Llinie są całkowicie przycinane.
  • W przypadku linii, które to robią, ich pierwszy :rozdzielony dwukropkami -fobszar jest cutnieobecny - podobnie jak wszystkie grepwstawione linie lineno.

mały test wejściowy

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

... generuje 5 wierszy próbek wejściowych. Następnie...

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

... drukuje ...

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

większe testy czasowe

Stworzyłem kilka całkiem dużych plików:

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

... które /tmp/Fwstawiają 5 mil linii i 1,5 mil linii losowo wybranych linii /tmp/L. Potem zrobiłem:

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

Wydrukowano:

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

(Dodałem tam odwrotne ukośniki)

Spośród obecnie oferowanych rozwiązań jest to najszybsze ze wszystkich, ale jedno w porównaniu z zestawem danych wygenerowanym powyżej na mojej maszynie. Z pozostałych tylko jeden był bliski rywalizacji o drugie miejsce, a to właśnie perl tutaj .

Nie jest to bynajmniej oryginalne oferowane rozwiązanie - skróciło 1/3 czasu realizacji dzięki poradom / inspiracjom oferowanym przez innych. Zobacz historię postów dla wolniejszych rozwiązań (ale dlaczego?) .

Warto również zauważyć, że niektóre inne odpowiedzi mogłyby równie dobrze konkurować, gdyby nie architektura wielu procesorów mojego systemu i jednoczesne wykonanie każdego z procesów w tym potoku. Wszystkie działają w tym samym czasie - każdy na własnym rdzeniu procesora - przekazując dane i wykonując niewielką część całości. To całkiem fajne.

ale najszybszym rozwiązaniem jest ...

Ale to nie jest najszybsze rozwiązanie. Najszybszym rozwiązaniem oferowanym tutaj, ręce w dół, jest program C . Nazwałem to cselect. Po skopiowaniu go do mojego schowka X skompilowałem go w następujący sposób:

xsel -bo | cc -xc - -o cselect

Potem zrobiłem:

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

... a wyniki były ...

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

Użyłbym awk:

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

Aktualizacja: wykonałem pomiary wydajności; wydaje się, że ta wersja skaluje się jeszcze lepiej przy bardzo dużych zestawach danych (jak w przypadku podanych wymagań), ponieważ porównanie jest bardzo szybkie i nadmiernie rekompensuje wysiłek konieczny do zbudowania tabeli skrótów.

Dla kompletności: możemy połączyć doskonały skrypt awk w odpowiedzi Stéphane'a Chazelasa i skrypt perla w odpowiedzi kos, ale bez zachowania całej listy w pamięci, w nadziei, że perl może być szybszy niż awk. (Zmieniłem kolejność argumentów, aby pasowała do pierwotnego pytania).

#!/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;
        }
    }
}

Napisałem prosty skrypt Perla, aby to zrobić:

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

• Masa F.txt
• Masa L.txt
• Przechowuje każdą linię L.txtw tablicy
• Odczytuje F.txtwiersz po wierszu, śledząc jego bieżący numer wiersza i bieżący indeks tablicy; zwiększa F.txtbieżący numer linii; jeśli F.txtbieżący numer linii pasuje do zawartości tablicy przy bieżącym indeksie tablicy, drukuje bieżącą linię i zwiększa indeks

Uwagi dotyczące kosztów i złożoności :

Biorąc pod uwagę koszt wykonania przypisań, koszt dokonania porównań i koszt wydrukowania linii, biorąc pod uwagę N ₁ jako liczbę linii F.txti N ₂ jako liczbę linii L.txt, whilepętla działa najwyżej N ₁ razy, prowadząc do przypisań 2N ₁ + N ₂ (oczywiście przy założeniu N ₁ > N ₂ ), porównań 2N ₁ i wydruków N ₂ ; podany jako równy koszt każdej operacji, całkowity koszt uruchomienia whilepętli wynosi 4N ₁ + 2N ₂ , co prowadzi do złożoności skryptu O (N).

Przetestuj plik wejściowy o wielkości 10 milionów wierszy :

Używając pliku 10 milionów linii F.txtzawierającego losowe linie o długości 50 znaków oraz pliku 10 milionów linii L.txtzawierającego liczby od 1 do 10000000 (najgorszy scenariusz):

~/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

Ten roztwór perlowy jest szybszy niż inne roztwory awk lub perl o około 20%, ale owalnie nie tak szybki jak roztwór w 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

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

Ponieważ L.txt jest posortowane, możesz użyć join. Po prostu numeruj każdą linię w F.txt, połącz dwa pliki, a następnie usuń numer linii. Nie są potrzebne duże pliki pośrednie.

W rzeczywistości powyższe spowoduje zmieszanie linii danych, zastępując całą białą spację jedną spacją. Aby linia pozostała nienaruszona, musisz wybrać jako separator znak, który nie pojawia się w twoich danych, np. „|”. Cmd jest wtedy

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

Pierwszy sed usuwa początkowe spacje z wyjścia „cat -n” i zastępuje tabulator. Drugi sed usuwa numer linii i „|”.

Dla kompletności kolejna próba joinrozwiązania:

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

Działa to poprzez sformatowanie kolumny z numerem wiersza, która się łączy, jako stałej długości z wiodącymi zerami, dzięki czemu liczby mają zawsze 15 cyfr. To omija problem łączenia, który nie lubi normalnej numerycznej kolejności sortowania, ponieważ kolumna została skutecznie zmuszona do sortowania słownikowego. nlsłuży do dodawania numerów wierszy w tym formacie do F.txt. Niestety sednależy go użyć do sformatowania numeracji w języku L.txt.

To podejście wydaje się działać poprawnie na danych testowych wygenerowanych przy użyciu metody @ mikeserv. Ale wciąż jest bardzo wolny - rozwiązanie c jest 60 razy szybsze na moim komputerze. około 2/3 czasu spędza w, seda 1/3 w join. Być może istnieje lepszy wyraz sed ...

Ponieważ zaakceptowana odpowiedź jest w języku C, uznałem, że można wrzucić tutaj rozwiązanie python:

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

W przypadku korzystania z zewnętrznej biblioteki, takiej jak numpy, rozwiązanie wyglądałoby jeszcze bardziej elegancko:

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)