☰

줄 번호로 파일 필터링

tag-icon • tag-icon text-processing filter high-performance
줄 번호로 파일 필터링

줄당 음수가 아닌 정수가 있는 파일 L과 텍스트 파일 F가 주어지면 줄 번호가 파일 L에 나타나는 F의 줄만 유지하는 빠른 방법이 있습니까?

예:

$ 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

5억 개 이상의 항목이 있는 파일 L을 처리할 수 있는 명령을 찾고 있습니다. 파일 L은 숫자로 정렬됩니다.

참고: 저는 의 절반을 구현하고 있지만 command-in-question여기서도 일부 Unix 도구를 사용할 수 있는지 궁금합니다.

업데이트: 모든 답변에 감사드립니다. 오늘 많은 것을 배웠습니다! 여러 답변을 받아들이고 싶지만 불가능합니다.

현재 답변에서 가장 빠른 솔루션을 선택하여 독립형 도구에 넣었습니다.필터 라인.

답변1

grep -n | sort | sed | cut

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

곧 작동할 거예요(아래에 일부 시간 제한 테스트가 포함되어 있음)원하는 크기를 입력하세요. 참고할 사항은 다음과 같습니다.

  • export LC_ALL=C
    • 다음 작업의 목적은 lineno를 ./F사용하여 ./L전체 파일을 인라인으로 스택하는 것이므로 실제로 걱정해야 할 문자는 ASCII [0-9]숫자와 :콜론뿐입니다.
    • 따라서 UTF-8과 관련된 경우보다 128개의 가능한 집합 중에서 이러한 11개 문자를 찾는 것이 더 쉽습니다.
  • grep -n ''
    • 그러면 문자열이 삽입됩니다.LINENO:stdin으로 - 또는 <./F.
  • sort -t: -nmk1,1 ./L -
    • sort입력 파일 정렬을 전혀 무시하고 대신(옳은)사전 정렬되어 있다고 가정하고 정렬된 순서로 -m정렬합니다 . 기본적으로 가능한 콜론 문자 이외의 모든 항목은 -numerically무시됩니다 -k1,1.-t:
    • 완료하려면 임시 공간이 필요할 수 있지만(일부 시퀀스가 ​​얼마나 멀리 발생할 수 있는지에 따라 다름), 적절한 정렬에 비해 많은 것이 필요하지 않으며 역추적이 전혀 발생하지 않으므로 매우 빠릅니다.
    • sort./L의 해당 라인이 lineno 바로 앞에 오는 스트림을 출력합니다 ./F. ./L의 줄은 더 짧기 때문에 항상 먼저 나열됩니다.
  • sed /:/d\;n
    • 현재 줄이 콜론과 일치하면 출력에서 ​​제거 /:/됩니다 . d그렇지 않으면 현재 줄과 n다음 줄이 자동으로 인쇄됩니다.
    • 따라서 출력을 sed다음으로 다듬습니다.sort오직콜론 및 다음 줄과 일치하지 않거나 ./L다음 줄에만 일치하는 연속 줄 쌍입니다.
  • cut -sd: -f2-
    • cut -s-d:구분 기호 문자열 중 하나 이상을 포함하지 않는 입력 행을 출력에서 ​​억제하여 ./L행이 완전히 잘립니다.
    • 이를 수행하는 행의 경우 :콜론으로 구분된 첫 번째 필드가 사라지고 -f삽입된 모든 lineno cut도 마찬가지입니다 .grep

작은 입력 테스트

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

...5줄의 샘플 입력을 생성합니다. 그 다음에...

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

...인쇄...

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

더 큰 시간 제한 테스트

꽤 큰 파일을 여러 개 만들었습니다.

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

...그 안에 500만 개의 행을 넣고 /tmp/F, 그 안에 무작위로 선택된 150만 개의 행을 /tmp/L넣었습니다.

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

다음과 같이 인쇄됩니다.

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

(거기에 백슬래시를 추가했습니다)

이는 현재 제공되는 모든 솔루션 중에서 가장 빠르지만, 위에서 생성된 데이터 세트와 비교할 때 가장 빠르지는 않습니다. 다른 사람들 중 단 한 명만이 2위 경쟁에 가까웠고, 그것은 Meuh의 것이었습니다.perl 여기.

이것은 결코 원래 제공된 솔루션이 아니었습니다. 다른 사람들이 제공한 조언/영감 덕분에 실행 시간이 1/3로 단축되었습니다. 느린 솔루션에 대해서는 게시물 기록을 참조하세요.(그런데 왜?).

또한 내 시스템의 다중 CPU 아키텍처와 이 파이프라인에서 각 프로세스의 동시 실행이 아니었다면 다른 답변 중 일부가 더 나았을 수도 있다는 점은 주목할 가치가 있습니다. 이들 모두는 각각 자체 프로세서 코어에서 동시에 작동하여 데이터를 전달하고 전체의 작은 부분을 완성합니다. 정말 멋지다.

하지만 가장 빠른 해결책은...

그러나 이것이 가장 빠른 해결책은 아닙니다. 의심할 여지 없이 여기서 제공되는 가장 빠른 솔루션은 다음과 같습니다.C 프로그램. 나는 그것을 부른다 cselect. X 클립보드에 복사한 후 다음과 같이 컴파일했습니다.

xsel -bo | cc -xc - -o cselect

그런 다음 나는 다음을 수행했습니다.

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

...결과가...

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

답변2

나는 을 사용할 것이지만 awk전체 내용을 L.txt메모리에 저장하지 않고 불필요한 해시 조회를 수행합니다 ;-).

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"

답변3

나는 다음을 사용할 것이다 awk:

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

업데이트: 성능 측정을 수행했습니다. 비교가 매우 빠르고 해시 테이블을 구축하는 데 필요한 작업을 과도하게 보상하기 때문에 이 버전은 매우 큰 데이터 세트에 대해 더 잘 확장되는 것 같습니다(명시된 요구 사항의 경우). .

답변4

완전성을 위해 Stéphane Chazelas의 답변에 있는 훌륭한 awk 스크립트와 kos의 답변에 있는 Perl 스크립트를 결합할 수 있지만 전체 목록을 메모리에 유지하지 않고 Perl이 awk보다 빠를 수 있기를 바랍니다. (원래 질문과 일치하도록 매개변수 순서를 변경했습니다.)

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

관련 정보