큰 파일 내용 정렬은 어떻게 정렬할까? (How to sort lines of a large text file)

파일 내용이 10GB가 되는 것은 어떻게 정렬할까?

메모리에 올릴 수 있는 크기가 한정되어 있기 때문에, 10GB 짜리의 큰 파일을 한번에 읽어서 quick sort 같은 인메모리(in-memory) 정렬을 할 수 없다.

Linux/Mac에는 sort 라는 명령어가 있고, Windows에서는 git bash를 깔면 사용할 수 있다.

이미 있는 커맨드인지 모르고 python으로 직접 구현했다.

 

과정

메모리에 올릴 수 있는 만큼만 쪼개어서 올린 후, 각각을 정렬하고 다시 합친다.
여기서 "메모리에 올릴 수 있는 만큼"은 적당히 128MB로 설정했다.

이를 자세히 각 단계별로 쪼개면 이렇다.

1. 준비 - 나눠 담을 크기를 계산
2. 분리 - 큰 세그먼트 단위로 나누어 쪼개어 담는다.
3. 정렬 - 쪼개진 각 파일을 정렬
4. 병합 - 순서대로 정렬되어 있는 파일을 순차적으로 합친다.

(1) 파일을 한번 쭉 훑으면서 각 줄의 첫 글자와 그 길이가 어느 정도인지 대략적으로 파악한다.
이렇게 등장한 첫 글자를 기준으로, counting sort와 비슷하게 정해진 구간에 몰아줄 것이다.
등장한 첫 글자들을, 대략적으로 파악했던 크기를 합하여 다시 128MB 단위가 될 수 있도록 묶어준다.
예를 들어, "가~"부터 "걷~"은 0번 세그먼트, "걸~"부터 "겹~"은 1번 세그먼트, ... 와 같은 식이다.

(2) 다시 원본을 처음부터 읽으면서, 각 세그먼트 번호의 파일에 적는다. "가~"는 0번 파일에, "걸~"은 1번 파일에 적는 식이다.
당장은 각 파일의 내용이 뒤죽박죽일 수 있으나, 다음 단계에서 해결된다.

(3) 쪼개어서 저장했던 내용(0번, 1번, ... 파일)을 각각 열어서 정렬한 상태로 바꾼다.

(4) 순서대로 합치고, 임시로 작성했던 세그먼트 번호의 파일들을 지운다.

 

결과

파일 정렬의 전/후

1GB를 정렬.gif

sort 커맨드와 시간 비교:

	1.5MB	512MB	1GB	5GB
sort	544 ms	1m 32s	3m 14s	14m 25s
sort_large_file.py	662 ms	1m 54s	2m 25s	14m 53s

몇 번 돌려보고 평균 값을 기록했는데, 오차가 조금 있으나 대체로 비슷한 시간을 보였다.
built-in 커맨드와 속도의 차이가 없다는 것이 꽤 의미있는 경험이다.

sort 커맨드는 CPU 를 거의 100% 가까이 사용했지만, 스크립트는 128MB + a 정도만 사용했다.

시간이 걸리는 부분을 보았더니, 정렬이나 합치는 과정보다는 전체를 2번 읽는 것이 가장 오래 걸렸다. 역시 File I/O는 비싼 작업이다.

 

환경

• Windows 10 Home 64bit build 19043
• Python 3.6.5
• 16GB RAM (8GB * 2 slot)
• 512GB SSD (SAMSUNG MZVLW512HMJP-000)
• VS Code 1.59.1