다른 파일에 저장된 줄 번호를 기반으로 대용량 파일에서 줄을 추출하는 빠른 방법

다른 파일에 저장된 줄 번호를 기반으로 대용량 파일에서 줄을 추출하는 빠른 방법

800억 줄이 포함된 대용량 파일이 있습니다. 이제 몇 개의 행(약 10000개)을 추출하고 싶습니다. 행 번호를 알고 있으며 이를 처리하는 가장 빠른 방법은 무엇입니까?

이 줄을 추출하기 위해 줄 번호가 포함된 다른 파일을 사용할 수 있습니까? 줄 번호 파일의 줄 번호가 항상 연속적인 것은 아닙니다.

예를 들어 원본 파일은 다음과 같습니다.

0.1
0.2
0.3
0.4
...

줄 번호 파일:

1
3
4

산출:

0.1
0.3
0.4

답변1

다음은 그 이외의 대안과 일부 벤치마크입니다.Zhou Weijun의 답변에서.

join

data줄을 추출하려는 파일과 추출할 줄 수를 나열하는 파일이 있다고 가정하고 line_numbers출력의 정렬 순서가 중요하지 않은 경우 다음을 사용할 수 있습니다.

join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | cut -d ' ' -f 2-

그러면 파일의 행에 번호가 매겨지고 datapadded_line_numbers번째 필드(기본값)의 파일과 결합되며 공통 행이 인쇄됩니다(잘려진 결합된 필드 자체는 제외).

join입력 파일은 알파벳순으로 정렬되어야 합니다. 위 파일은 파일의 각 줄을 padded_line_numbers왼쪽으로 채워서 준비해야 합니다 . line_numbers예를 들어:

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers >padded_line_numbers

옵션 -w 12 -n rz과 인수는 nl앞에 0이 붙은 12자리 긴 숫자의 출력을 지시합니다.

출력의 정렬 순서가 line_numbers파일의 정렬 순서와 일치해야 하는 경우 다음을 사용할 수 있습니다.

join -1 2 -2 1 <(nl padded_line_numbers | sort -k 2,2) \
    <(nl -w 12 -n rz data) |
    sort -k 2,2n |
    cut -d ' ' -f 3-

padded_line_numbers파일에 번호를 매기고 결과를 두 번째 필드를 기준으로 알파벳순으로 정렬한 다음 번호 data가 매겨진 파일과 연결하고 결과를 원래 정렬 순서에 따라 숫자순으로 정렬합니다 padded_line_numbers.

여기서는 편의상 프로세스 대체를 사용합니다. 이에 의존할 수 없거나 의존하고 싶지 않고 중간 결과를 보관하기 위해 일반 파일을 만드는 데 필요한 저장 공간을 낭비할 의향이 없다면 명명된 파이프를 활용할 수 있습니다.

mkfifo padded_line_numbers
mkfifo numbered_data

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers | nl | sort -k 2,2 >padded_line_numbers &

nl -w 12 -n rz data >numbered_data &

join -1 2 -2 1 padded_line_numbers numbered_data | sort -k 2,2n | cut -d ' ' -f 3-

벤치마킹

문제의 특이성은 파일의 줄 수이므로 data적절한 양의 데이터로 대안을 테스트하는 것이 유용할 수 있다고 생각했습니다.

테스트에서는 32억 행이 있는 데이터 파일을 사용했습니다. 각 줄은 openssl enc및 를 사용하여 16진수 로 인코딩된 2바이트의 쓰레기이며 od -An -tx1 -w2다음을 사용하여 공백을 제거했습니다 tr -d ' '.

$ head -n 3 data
c15d
061d
5787

$ wc -l data
3221254963 data

이 파일은 GNU Coreutils를 사용하여 1에서 3,221,254,963 사이의 숫자 10,000개를 반복 없이 무작위로 선택하여 line_numbers생성되었습니다 .shuf

shuf -i 1-"$(wc -l <data)" -n 10000 >line_numbers

bash테스트 환경은 i7-2670QM Intel 쿼드 코어 프로세서, 16 ​​GiB 메모리, SSD 스토리지, GNU/Linux, 5.0 및 GNU 도구를 갖춘 노트북입니다 .
내가 측정한 유일한 차원은 time쉘 내장 함수를 통한 실행 시간이었습니다.

제가 여기서 고려하고 있는 것은 다음과 같습니다.

perl가장 빠른 것 같습니다.

$ time perl_script line_numbers data | wc -l
10000

real    14m51.597s
user    14m41.878s
sys     0m9.299s

awk성능은 꽤 좋아 보입니다.

$ time awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' line_numbers data | wc -l
10000

real    29m3.808s
user    28m52.616s
sys     0m10.709s

join, 또한 비슷한 것으로 보입니다.

$ time join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | wc -l
10000

real    28m24.053s
user    27m52.857s
sys     0m28.958s

위에서 언급한 정렬된 버전은 이 버전에 비해 성능 저하가 거의 없다는 점에 유의하세요.

마지막으로 sed눈에 띄게 느려진 것 같았습니다. 약 9시간 후에 종료했습니다.

$ time sed -nf <(sed 's/$/p/' line_numbers) data | wc -l
^C

real    551m12.747s
user    550m53.390s
sys     0m15.624s

답변2

이를 위해 Perl 스크립트를 사용하겠습니다. 나는 이것을 생각해 냈습니다 :

#!/usr/bin/perl

# usage: thisscript linenumberslist.txt contentsfile

unless (open(IN, $ARGV[0])) {
        die "Can't open list of line numbers file '$ARGV[0]'\n";
}
my %linenumbers = ();
while (<IN>) {
        chomp;
        $linenumbers{$_} = 1;
}

unless (open(IN, $ARGV[1])) {
        die "Can't open contents file '$ARGV[1]'\n";
}
$. = 0;
while (<IN>) {
        print if defined $linenumbers{$.};
}

exit;

먼저 관심 있는 행 번호 목록을 연관 배열로 읽습니다. 여기서 행 번호는 키입니다. chomp줄 끝, $_즉 줄 자체에서 개행 문자를 제거합니다.

다음으로 데이터 파일이 열리고 행 번호가 행 번호 배열의 기존 키인 경우 행이 인쇄됩니다.

이것은 $.Perl의 라인 번호 카운터로, 라인을 읽을 때마다 증가합니다. 이는 파일 전체에 걸쳐 계산되므로 데이터 파일의 행을 읽기 전에 이를 0으로 재설정했습니다.

이것은 아마도 "perl" 스타일로 더 많이 작성할 수 있지만 저는 더 읽기 쉽게 만드는 것을 선호합니다.

추출하는 행 목록이 매우 큰 경우 이는 가장 효율적인 방법이 아닐 수 있지만 Perl은 일반적으로 이러한 작업에 매우 효율적이라는 것을 알았습니다.

나열된 순서대로(즉, 순서가 아닌) 행을 추출해야 하는 경우에는 더 복잡해집니다.

답변3

라이너의 경우 다음을 사용하십시오 sed.

sed -nf <(sed 's/$/p/' linenumberfile) contentfile

원래 순서를 유지하려면 linenumberfile다음을 수행하십시오.

sed -nf <(sed 's/$/p/' linenumberfile) contentfile | paste <(nl linenumberfile | sort -n -k 2,2) - | sort -n -k 1,1 | cut -f 3-

설명하다:

sed 's/$/p/' linenumberfile

sed지정된 줄을 인쇄하는 스크립트를 생성합니다 . 그런 다음 스크립트는 실제 인쇄를 수행하기 위해 sed( -n패턴 공간의 기본 인쇄를 억제하기 위해) 다른 스크립트에 공급됩니다. 콘텐츠 파일은 한 줄씩 처리 되므로 sed출력 순서는 콘텐츠 파일과 동일합니다. 이는원패스 프로세스그래서 속도가 허용 가능하기를 바랍니다.

프로세스 속도를 높이기 위해 이를 변경 하고 p생성된 스크립트 끝에 {p;b}추가할 수 있습니다.qsed

줄 번호 파일의 줄 순서를 유지하려면 nl"줄 번호"를 사용하여 줄 번호 파일에 추가하세요. 그래서 줄 번호 파일

4
5
2

될 것입니다

1 4
2 5
3 2

첫 번째 열은 파일의 원래 줄 번호 순서를 기록합니다.

그런 다음 "줄 번호"가 포함된 파일 sorted 및 pasted를 에 출력합니다 sed.

3 2    content_of_line2
1 4    content_of_line4
2 5    content_of_line5

그런 다음 sort첫 번째 열을 ed를 수행하는 키로 사용하고 마지막으로

1 4    content_of_line4
2 5    content_of_line5
3 2    content_of_line2

마지막으로 cut2개의 추가 열을 삭제하는 데 사용되었습니다.

벤치마킹

sed몇 개의 행에서 가장 잘 작동하는 것 같지만 이는 perl질문에 지정된 10000개 행에 대한 접근 방식입니다.

$ cat /proc/cpuinfo | grep -A 4 -m 1 processor
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 60
model name  : Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

$ wc -l linenumber
10 linenumber

$ wc -l content
8982457 content

$ file content
content: ASCII text

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"    
real    0m0.791s
user    0m0.661s
sys     0m0.133s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.061s
user    0m2.908s
sys     0m0.152s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.706s
user    0m1.582s
sys     0m0.124s

$ ./genlinenumber.py 100 > linenumber
$ wc -l linenumber
100 linenumber

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"
real    0m3.326s
user    0m3.164s
sys     0m0.164s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.055s
user    0m2.890s
sys     0m0.164s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.769s
user    0m1.604s
sys     0m0.165s

줄의 순서를 유지해야 하는 경우 |시간이 무시될 정도로 첫 번째 줄 다음에 명령을 사용할 수 있습니다.

$ ./genlinenumber.py 10000 > linenumber
$ wc -l linenumber
10000 linenumber

$ time bash -c "./ln.pl linenumber content > extract"
real    0m1.933s
user    0m1.791s
sys     0m0.141s

$ time bash -c "paste <(nl linenumber | sort -n -k 2,2) extract | sort -n -k 1,1 | cut -f 3- > /dev/null"
real    0m0.018s
user    0m0.012s
sys     0m0.005s

답변4

micha@linux-micha: /tmp
$ cat numbers.txt
1
2
4
5

micha@linux-micha: /tmp
$ cat sentences.txt
alpha
bravo
charlie
delta
echo
foxtrott

micha@linux-micha: /tmp
$ awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' numbers.txt sentences.txt
alpha
bravo
delta
echo

관련 정보