주어진 두 입력 파일에서 공통 문자열 검색

두 개의 파일 크기가 각각 20GB입니다. 나는 그들 사이에 공통적 인 문자열을 검색해야한다. 문자열의 최대 길이는 20 바이트라고 가정합니다. 그래서 이것을 해결하기 위해 다음과 같은 알고리즘을 사용하고 있습니다. 쿼드 코어 i3 CPU를 장착 한 8GB RAM 시스템을 사용하고 있습니다. 주어진 두 입력 파일에서 공통 문자열 검색

sort the files using any suitable sorting utility 
open files A and B for reading 
read wordA from A 
read wordB from B 
while (A not EOF and B not EOF) 
{ 
    if (wordA < wordB) 
     read wordA from A 
    else if (wordA > wordB) 
     read wordB from B 
    else 
     /* match found, store it into some other files */ 
     write wordA into output 
     read wordA from A 
}

는 위에서 언급 한 시스템 구성에 성공적으로 갔다하지만 기가 바이트 RAM, 6 코어 i3 프로세서와 120기가바이트의 사용 가능한 디스크 공간 ... 내 시스템이 종료되었다 추락 여러 차례의 시스템에서이 알고리즘을 실행할 때. 왜 이런 일이 일어나는거야?

Plz이 plm을 해결하는 다른 방법을 알려주세요! 성능을 향상시킬 수 있습니까?

출처

2012-01-31 Gopal

의사가 구현의 –

@Duck "는 segfault 아웃에 대해 우리에게 아무것도 알 수 없습니다를 기억?" 어떻게 된 일인지 모르겠다. 사실 내가 8Gb RAM으로 이것을 실행할 때 대략 1.2GB RAM 공간과 0 % swape 공간을 사용하고 있었기 때문에 6Gb RAM에서도 작동해야한다고 생각합니다.하지만 그 이유는 무엇입니까 ?? – Gopal

@MitchWheat 그렇습니다. 구현에 관해서는 아무 말도하지 않고 위의 algo를 다른 시스템 구성과 함께 실행할 수있는 방법은 어떤 시스템에서도 실행할 수있는 다른 더 나은 논리입니까? – Gopal

예, 당신은 극적으로 awk으로 매우 짧은 awk 1 - 라이너

awk 'FNR==NR{a[$0]++;next}a[$0]' file1 file2

를 사용하여 성능을 향상시킬 수 있습니다 우선으로 정렬 할 필요없이 고유의 라인을 찾을 수 있습니다. 당신은 당신이 일반 라인으로 무엇을하고 싶었는지를 말하지 않았으므로 나는 당신이 그것을 인쇄하고 싶다고 생각했습니다.

만 공통 줄을 인쇄하려면 에 상관없이 당신이 사용할 수있는 반복 횟수 번 :

awk 'FNR==NR{a[$0]=1;next}a[$0]-- > 0' file1 file2

출처

2012-01-31 04:10:09 SiegeX

좋아 그것은 잘 보였다 u는 왜 그리고 얼마나에 대해 명확히 수 있습니다 보다 나은? – Gopal

@ Gopal 내가 미리 발음 할 필요가 없다고 언급 했으므로 작업에서 제거 된 파일을 두 번 완전히 실행합니다. 당신이 대답 할 수있는 질문은 얼마나 나은지. – SiegeX

주어진 두 입력 파일에서 공통 문자열 검색

답변

관련 문제