매우 큰 파일에서 키별로 줄 추출

사용하기에 충분히 효율적이어야 합니다 awk. 키 조회 시간이 키 수(조회 테이블의 수(예에서는 상대적으로 작음))에 따라 대수적으로 확장되는 내장 연관 배열을 제공합니다.

귀하의 의견은 다음과 같습니다:

42M * log2(1.5M) -> 42M * 20 key comparisons 

(여기서 M은 10^6을 나타냄)

awk가 해시 테이블을 사용하는 경우 각 키 조회에는 고정된 시간만 소요됩니다.

효율적인 awk 기반 솔루션의 예(기본 필드 구분 기호 사용):

$ awk 'ARGIND == 1 { a[$1] = 1; next } a[$1] { print $0 }' keys.dat largefile.dat

두 입력이 모두 정렬되므로 보다 효율적인 스크립트를 작성할 수 있습니다(런타임은 두 입력 파일 크기에 따라 선형적으로 확장됩니다). 그러나 프로그래밍에는 시간이 더 걸립니다.

또는 입력으로 정렬이 필요한 파일을 사용할 수 있습니다 join. 제한 사항은 키를 알파벳순으로 정렬해야 한다는 것입니다. 출력 형식을 조정해야 할 수도 있습니다. 예를 들어:

$ join -j1 keys.dat largefile.dat

-t필드 구분자를 구성하고 -o출력 형식을 조정하는 데 사용됩니다 .

이는 입력 크기에 따라 선형 시간으로 실행되어야 합니다.

이 방법은 다음을 사용합니다.고정 길이 길이키는 레코드의 첫 번째 바이트부터 시작됩니다.

임시 필드 구분 기호로 (또는 고유한 단일 바이트 문자)를 사용하면 \x01레코드를 더 쉽게 조작할 수 있습니다 .

join -t$'\x01' <(sed -r 's/.{9}/&\x01/' main) <(cut -b -9 keys) |sed -r 's/(.{9})./\1/'

막스 슐렙치거의 awk이 예는 45,000,000개 레코드의 경우 더 빠르지만 더 큰 파일의 경우에는 실패합니다. 여유 메모리가 얼마나 있나요?

결과는 다음과 같습니다.

45,000,000 unique records, 1,500,000 keys
=========================
awk

real    0m31.971s
user    0m28.782s
sys     0m2.972s

join

real    0m53.733s
user    0m54.255s
sys     0m0.708s

(2x45) 90,000,000 records, 1,500,000 keys
=========================
awk
awk: (FILENAME=main2 FNR=54334297) fatal: assoc_lookup: bucket->ahname_str: can't allocate 11 bytes of memory (Cannot allocate memory)

join

real    1m35.306s
user    1m34.754s
sys     0m1.344s

===================

라인 기반 파일이라고 가정하면 grep꽤 잘 작동할 것입니다. 고정 문자열 -f keyfile에 합계를 사용하세요.-F

grep -F -f keys textfile

참고: 아래 의견에서 오탐지에 대한 PeterO의 경고를 참고하세요.