☰

한 파일의 줄을 다른 파일의 줄과 일치시킵니다.

tag-icon • tag-icon linux awk sed grep gawk
한 파일의 줄을 다른 파일의 줄과 일치시킵니다.

나는 다소 큰 목록(1백만 개 정도)과 또 다른 큰 목록(17GB)을 가지고 있으며 다음과 같이 list1의 줄을 구분된 file2의 첫 번째 부분과 일치시켜야 합니다.

목록 1:

98433259@34
90345394@43
94335053@23

목록 2

54353456@35:nancy
98433259@34:jack
94335053@23:james
32409533@86:robert

산출:

98433259@34:jack
94335053@23:james

grep -Fwf list1 list2를 시도했지만 너무 느렸습니다.

이 작업을 수행하는 더 빠른 방법이 있나요?

답변1

너무 느린? 무엇을 기대할 수 있나요? 파일 크기를 12MB로 가정하면 약 100만 줄이 됩니다. 이제 다른 파일의 각 줄에 대해 전체 파일을 스캔해야 합니다. 10번 중 9번은 비교가 첫 번째 바이트 이후에 중지된다고 주장할 수 있지만, 그럼에도 불구하고 다음 개행 문자를 계속 검색해야 하므로 사실상 두 번째 파일의 모든 줄에 대해 첫 번째 파일의 모든 바이트가 통과합니다. CPU.

이제 두 번째 파일에는 10억 줄이 있을 수 있습니다. 따라서 12MB를 10억 ​​번 스캔해야 하는데, 이는 12엑사바이트입니다! 이제 데스크탑에 8MB의 L3 캐시가 있는 경우 해당 12MB는 맞지 않으며 RAM에서 가져와야 합니다. 다행히 요즘에는 RAM 속도가 빨라서 컴퓨터의 유효 처리량이 20GB/s일 수도 있습니다. 올바르게 계산하면 20GB/s에서 12 Exebyte에 액세스하는 데 600.000초가 걸립니다. 10,000분. 167시간. 7 일. 일주일.

그런데 느린게 아니라 정말 빠릅니다! 너무 어려운 작업이기 때문에 시간이 오래 걸립니다.

더 빠르게 진행하려면 해당 목적에 맞게 설계된 도구가 필요합니다. 작동하지 않을 것이므로 직접 작성하십시오.

어떻게? 및 같은 빠른 언어를 사용하여 Cfile1 데이터를 먼저 정리하면 모든 데이터를 스캔할 필요가 없습니다. 각 레코드를 트리에 넣습니다. 루트에는 첫 번째 숫자에 따라 하위 트리에 대한 10개의 포인터가 있습니다. 널 포인터가 잎이 없음을 나타내지 않는 한 각 하위 트리에는 하위 트리에 대한 10개의 추가 포인터가 있습니다.

이제 file2를 스캔할 때 첫 번째 바이트를 얻고 해당 숫자를 기반으로 포인터를 얻고 해당 하위 트리에서 두 번째 숫자에 대한 포인터를 선택하는 등의 작업을 수행합니다. 8비트 숫자와 64비트 포인터를 사용하면 최악의 경우(일치하는 항목 찾기) 64바이트와 이름에 저장된 바이트만 로드하면 됩니다. 한 줄에 80바이트, 10억 번 하면 80GB가 되며 4초 만에 메모리에서 가져옵니다. 더 좋은 것 같죠?

이것이 더 빠른 방법이지만 UNIX와는 아무 관련이 없습니다. 이와 같은 프로그램을 작성하는 방법을 모른다면 StackOverflow에 물어보세요. 여기를 참고하시면 됩니다.

관련 정보