두 개의 큰 파일 비교

Question

두 파일의 차이점을 파일에 쓰는 프로그램을 작성해야합니다. 프로그램은 600MB 파일을 13.464.448 회선 이상으로 반복해야하며, grep이 다른 파일에서 true를 반환하는지 확인한 다음 그 결과를 다른 파일에 씁니다. 약 1.000.000 개의 레코드로 빠른 테스트를 작성했는데 한 시간 이상 걸렸으므로이 방법이 9 시간 이상 걸릴 수 있습니다.

이 작업을 수행하는 방법에 대한 권장 사항이 있습니까? 내가 사용해야하는 특정 언어? 나는 bash 나 python으로 할 계획이었습니다.

미리 감사드립니다.

[편집 1] : 미안하지만, 두 파일의 차이점을 말할 때 나는 diff를 의미하지는 않습니다. 결과 파일의 형식이 다릅니다.

논리는이 같은 비트 :

파일 A가 파일 B는 내가 FILE A에서 읽을 현재 행을 선택 파일 B에 grep을 만 13 이상의 선

가 297.599 선, 그 줄이 파일 B에 있으면 결과 파일에 그 줄을 씁니다. 그건 그렇고, 파일 A와 파일 B는 서로 다른 형식을 가지고 있습니다. 결과 파일의 형식은 File A입니다.

[편집 2] : 나는 실행해야하는 모든 컴퓨터에 Python을 설치할 필요가 없도록 bash 솔루션을 이상적으로 만들 것을 요청 받았습니다. 에.

이 내 curent 구현이 bash는 방법은 완료하는 데 10 시간 이상 걸리는

#!/bin/bash 

LAST_TTP=`ls -ltr TTP_*.txt | tail -1 | awk '{ print $9 }'` 
LAST_EXP=`ls -ltr *.SSMT | tail -1 | awk '{ print $9 }'` 

while read -r line; do 
    MATCH="$(grep $line $LAST_EXP)" 
    echo "line: $line, match: $MATCH" 

    # if not empty 
    if [ ! -z "$MATCH" ] 
    then 
     echo $MATCH >> result 
    fi 

done < $LAST_TTP 

. bash에서 더 효율적으로 만드는 방법에 대한 제안이 있습니까?

미리 감사드립니다.

Answer 1

O (n²) 성능으로 이어지는 목록 대신 목록을보고 계실 것입니다. 시도 :

with open('b') as b: 
    blines = set(b) 
with open('a') as a: 
    with open('result', 'w') as result: 
    for line in a: 
     if line not in blines: 
     result.write(line) 

균일하게 오랫동안 (그리고 지나치게 긴 줄)을 가정 할 때,이 구현의 성능 (때문에 Pyton's set being extremely fast에, 상각) O(|A| + |B|)입니다. 메모리 요구량은 O(|B|)이지만 크게 1보다 큰 인수가 있습니다.

출력의 줄 순서가 중요하지 않은 경우 두 파일을 모두 정렬 한 다음 줄 단위로 비교할 수도 있습니다. 성능은 O(|A| log |A| + B log |B|)입니다. 메모리 요구량은 O(|A|+|B|),보다 정확하게는 |A| + |B|입니다.

Answer 2

각 입력 파일을 정렬하십시오. 이제 각각에서 한 줄을 읽으십시오. 한 줄이 다른 줄보다 작 으면 그 줄을 차이로 출력하고 그 줄에서 다음 줄을 읽습니다. 두 줄이 같은지 비교하면 두 파일의 다음 줄을 읽습니다. 한 파일의 끝까지 읽으면 다른 파일의 모든 행이 다릅니다.

시작한 O (n^2) 알고리즘과는 대조적으로 O (n log n) 알고리즘입니다.phihag 년대 @

grep --fixed-strings --file=file_B file_A > result_file 

그러나 모두와 Ronsam의 답변이 더 나은 솔루션입니다 @ 마크 :

Answer 3

귀하의 구현은 할 것 같다.

또한 무거운 총을 사용하려는 경우 해결책은 hadoop과 같은 map-reduce 프레임 워크를위한 좋은 후보입니다.

Answer 4

join 명령은 원하는 작업도 수행합니다. 조인을 사용하면 두 파일을 모두 위로 정렬해야합니다. -v 옵션은 테스트 할 수없는 줄마다 줄을 인쇄합니다.

그래서 당신은

같은 것이 아래 -v 1 sortedfile1 sortedfile2

(당신이 조인의 맨 페이지를 참조하십시오, 파일 형식에 따라 조인 옵션을 설정해야합니다)

에 가입 할 것 예제에서는 두 번째 resp를 사용하여 test1.txt 및 test2.txt 파일을 조인합니다. 조인의 첫 번째 필드 정렬 명령을 사용하여 파일을 미리 정렬했다고 가정합니다. -v 1 옵션은 test1.txt의 행을 조인 할 수없는 경우에만 출력합니다.

 
>cat test1.txt 
a 1 2 
b 2 3 

> cat test2.txt 
1 x 
4 x 

> join -v 1 -1 2 -2 1 test1.txt test2.txt 
2 b 3 

> join -v 1 -1 2 -2 1 -o 1.1 1.2 1.3 test1.txt test2.txt 
b 2 3 

정렬 및 결합 모두 큰 파일과 잘 작동합니다.

Answer 5

나는 comm 명령을 고려할 것이다. GREP은 항상

comm -2 -3 <(sort file1) <(sort file2) 

Answer 6

당신은 grep을 중지하여 스크립트를 약간 속도를 높일 수 있습니다 선형 검색을 수행 할 때 그것은 첫 경기를 발견하면 그 적절한의 경우는 정렬 된 데이터로 작업하기 때문에 그것은 그렙보다 더 빨리해야 당신의 필요합니다.

grep이 지원하는 경우 을 사용하십시오.

당신의 문제는 당신이 grep을 거의 300,000 번 산란시키고 매회 1300 만 라인 이상을 읽는 것입니다.

첫 번째 일치시를 중지하면 약간의 도움이되지만 모든 임원의 오버 헤드도 큰 요인입니다. 파이썬으로 구현하면이 문제가 해결됩니다.

스크립트에서 파일을 선택하는 방법은 BashFAQ/003 및 Parsing ls을 참조하십시오. 파일의

awk 'NR==FNR { arrA[$0]; next } $0 in arrA' file_A file_B > result

순서 (... file_A file_B) 명령 행에서 매우 중요하다

Answer 7

또한 AWK를 사용할 수 있습니다.