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

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

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

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

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

	import os
	import shutil
	from math import inf
	from datetime import datetime, timedelta
	INPUT_FILE = 'input.txt'
	OUTPUT_FILE = 'output.txt'
	def print_progress_bar(time, percent, text, width):
	length = int(width * percent / 100)
	bar = '█' * length + '-' * (width - length)
	prefix = time.strftime('[%H:%M:%S]')
	percent_text = '{:.2f}'.format(percent)
	print(f'\r{prefix} {percent_text}% |{bar}| {text} ', end='\t')
	def human_byte_str(byte):
	prefix = 0
	while byte >= 1024:
	byte /= 1024
	prefix += 1
	return '{:.2f} {}B'.format(byte, "KMGTPEZY"[prefix-1] if prefix > 0 else '')
	def open_utf8(name, mode):
	return open(name, mode, encoding='utf-8')
	def sort_single(fname):
	with open_utf8(fname, 'r') as f:
	data = sorted(f.readlines())
	with open_utf8(fname, 'w') as f:
	f.writelines(data)
	return fname
	def fsort(in_name, out_name):
	BAR_WIDTH = 50
	TMP_DIR = 'fmerge.tmp'
	for _ in range(100):
	if not os.path.isdir(TMP_DIR): break
	TMP_DIR = f'fmerge.tmp{_}'
	os.mkdir(TMP_DIR)
	try:
	# create information
	seg = {}
	filesize = 0
	percent = 0
	time = datetime.now()
	with open_utf8(in_name, 'r') as f:
	pidx = 0
	while True:
	# ui update
	if time + timedelta(milliseconds=500) < datetime.now():
	time = datetime.now()
	pidx = (pidx + 1) % 3
	text = 'read {}'.format(human_byte_str(filesize)) + '.' * ((pidx % 3) + 1)
	print_progress_bar(time, percent, text, BAR_WIDTH)
	# file processing
	s = f.readline()
	if not s: break
	words = s.strip()
	if len(words) == 0: continue
	c = ord(s[0])
	size = len(s) * 4 - len(words)
	if c not in seg: seg[c] = 0
	seg[c] += size
	filesize += size
	# ui update
	print_progress_bar(datetime.now(), 0, 'calculating...', BAR_WIDTH)
	# calculate size of each segment
	ch2buc = {}
	buc_size = 0
	buc_limit = 128 * (1024 ** 2) # 128 MB
	buc_index = 0
	for idx, size in sorted(seg.items()):
	buc_size += size
	if buc_size < buc_limit:
	ch2buc[idx] = buc_index
	continue
	ch2buc[idx] = buc_index
	buc_size = 0
	buc_index += 1
	fseg_name = [f'{TMP_DIR}/{i}' for i in range(buc_index + 1)]
	# read and save into segment
	with open_utf8(in_name, 'r') as f:
	fseg = [open_utf8(name, 'w') for name in fseg_name]
	# divide
	cur_size = 0
	while True:
	# file processing
	s = f.readline()
	if not s: break
	words = s.strip()
	if len(words) == 0: continue
	cur_size += len(s) * 4 - len(words)
	fseg[ch2buc[ord(s[0])]].write(s)
	# ui update (~ 50%)
	if time + timedelta(milliseconds=500) < datetime.now():
	time = datetime.now()
	pidx = (pidx + 1) % 3
	percent = (cur_size / filesize) * 50
	print_progress_bar(datetime.now(), percent, 'processing.' + '.' * (pidx % 3), BAR_WIDTH)
	# conquer
	for i, fs in enumerate(fseg):
	fs.close()
	sort_single(fs.name)
	# ui update (50% ~ 80%)
	percent = 50 + (i / len(fseg)) * 30
	text = 'sorting ({}/{})'.format(i + 1, len(fseg))
	print_progress_bar(datetime.now(), percent, text, BAR_WIDTH)
	# append each segment to output
	with open_utf8(out_name, 'w') as fout:
	for i, name in enumerate(fseg_name):
	fseg = open_utf8(name, 'r')
	fout.writelines(fseg.readlines())
	fseg.close()
	os.remove(name)
	# ui update (80% ~)
	percent = 80 + (i / len(fseg_name)) * 20
	text = 'merging ({}/{})'.format(i + 1, len(fseg_name))
	print_progress_bar(datetime.now(), percent, text, BAR_WIDTH)
	print_progress_bar(datetime.now(), 100, 'finished', BAR_WIDTH)
	except:
	print('')
	print('failed')
	finally:
	if os.path.isdir(TMP_DIR):
	shutil.rmtree(TMP_DIR)
	print('')
	# run
	fsort(INPUT_FILE, OUTPUT_FILE)

view raw sort_large_file.py hosted with ❤ by GitHub

 

과정

메모리에 올릴 수 있는 만큼만 쪼개어서 올린 후, 각각을 정렬하고 다시 합친다.
여기서 "메모리에 올릴 수 있는 만큼"은 적당히 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