선택 심화: 런·다중 병합·외부 정렬

전체 자료가 메모리에 들어가지 않으면 파일을 나누어 처리해야 합니다. 목표는 정렬된 조각인 런을 만들고 각 런의 앞값만 비교하며 파일로 합치는 흐름을 이해하는 것입니다. 병합 정렬·힙·파일 실행 준비를 복습하세요.

개념과 약속

내부 정렬은 작업 자료가 주로 메모리에 있는 방식, 외부 정렬은 파일 등 외부 저장 장치의 자료를 제한된 메모리로 다루는 방식입니다. 청크는 한 번에 읽을 자료 묶음이고 런은 이미 정렬된 연속 조각입니다. 아래는 청크를 정렬해 임시 런 파일로 쓰고, heapq.merge로 k개 런의 앞값을 최소 힙에서 선택해 출력에 한 줄씩 쓰는 교육용 p-way 병합입니다.

런이 너무 많으면 일부 런씩 여러 단계로 병합해야 열린 파일 수·버퍼 한도를 지킵니다. polyphase 병합은 파일 역할과 런 수를 불균등하게 배치해 비어 있는 출력 파일의 역할을 바꾸며 진행하는 외부 정렬 스케줄입니다. 두 입력 파일의 단순 경우에는 피보나치형 런 수 분포와 부족분을 채우는 가상 런을 사용할 수 있습니다. 이는 이 본문의 모든 런을 한 번에 여는 구현과 다른 계획입니다. 실제 세 파일 스케줄·가상 런·순차 위치·I/O는 별도 polyphase 심화에서 구현하고 추적합니다.

파일 예제는 코드 파일 옆에 만든 전용 임시 폴더에서만 입력·출력을 생성합니다. 실제 자료 파일을 지정하지 않습니다. 함수의 출력 경로는 새 파일 또는 덮어써도 되는 학습 결과를 사용해야 합니다. 입력과 출력은 서로 다른 실파일이어야 합니다. 같은 경로와, 이미 존재하는 출력이 입력의 하드링크 별칭인 경우도 거부합니다.

chunk_size는 한 청크의 양의 Python 정수 개수입니다. bool·float·NaN은 거부합니다. 예를 들어 3.0도 이 함수의 입력 계약에서는 정수가 아닙니다. 자료 개수와 같은 len(chunk) == chunk_size 조건으로 런을 나누므로 파일을 읽기 전에 이 약속을 검사합니다.

손으로 상태 추적하기

청크 크기 3, 입력 [8,1,6,3,9,2,7]입니다.

병합은 앞값 1,2,7 중 1을 출력하고 해당 런의 다음 6을 후보로 넣습니다. 출력한 런만 앞으로 이동하고 다른 런의 후보는 그대로 둡니다. 소진은 더 읽을 값이 없어 그 런을 후보에서 제외한다는 뜻입니다.

후보는 각 활성 런에서 최대 앞값 하나입니다. 모든 런의 숫자를 하나의 목록으로 펼치지 않아도 [1,2,3,6,7,8,9]를 출력할 수 있습니다. 실제 heapq.merge가 한 런만 남으면 나머지를 바로 내보내는 내부 최적화와 관계없이, 위 표는 최소 앞값을 선택하는 병합의 논리적 순서입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

파일·지연 읽기 문법 준비

앞의 실행 준비는 Python 파일을 저장하고 실행하는 방법이었습니다. 이 실습에서는 프로그램이 별도의 숫자 자료 파일을 읽고 쓰므로 다음 역할을 추가로 알아야 합니다.

• Path는 파일이나 폴더의 경로를 다루는 객체입니다. 경로 객체 자체가 파일 내용 전체를 담는 것은 아닙니다. source.open(encoding="utf-8")은 읽기용 파일 스트림을 열고, for line in stream은 한 줄씩 읽습니다. int(line)은 그 줄의 숫자를 정수로 바꿉니다. 이 예제의 자료는 한 줄에 정수 하나입니다.
• with ... as ...:는 블록을 나갈 때 자원을 정리하는 문법입니다. 파일에서는 닫기를, TemporaryDirectory에서는 내부 임시 파일과 임시 폴더 삭제를 맡깁니다. 오류로 블록을 떠나도 정리합니다. 예제가 만든 상위 private-temp 폴더 자체는 남을 수 있지만 그 안의 개별 임시 폴더는 자동 정리됩니다.
• ExitStack은 개수가 실행 중 정해지는 여러 파일을 한 블록에서 관리합니다. stack.enter_context(path.open(...))으로 각 런을 열어 등록하면 with ExitStack()을 나갈 때 등록한 파일을 모두 닫습니다.
• (int(line) for line in stream)은 생성기 표현식입니다. 괄호 안의 모든 값을 즉시 만들지 않고 다음 값이 요청될 때 한 줄을 읽어 정수 하나를 줍니다. [int(line) for line in stream]처럼 대괄호로 바꾸면 해당 런을 즉시 목록으로 읽어 메모리 사용이 달라집니다. runs = [...]의 바깥 목록은 k개 생성기 객체를 보관하며, 전체 N개 정수를 보관하는 목록이 아닙니다.
• heapq.merge(*runs)는 이미 정렬된 반복자들을 지연 소비하며 합칩니다. *runs는 그 목록의 각 반복자를 별도 인자로 넘기는 문법입니다. 병합 힙에는 각 활성 런의 앞값이 최대 하나씩 들어갑니다. for value in ...가 다음 출력을 요청하면 가장 작은 앞값을 내보내고 그 런에서 다음 값을 읽습니다. 따라서 입력 런의 정렬 전제가 필요합니다.

줄 단위 소비와 파일의 내부 버퍼는 구분해야 합니다. Python 파일 객체는 읽기·쓰기 효율을 위해 별도 버퍼를 사용할 수 있어 디스크를 문자 하나씩 읽는다는 뜻이 아닙니다. 고정된 버퍼 크기와 작은 정수·줄 길이를 가정하면 청크 M개, 런 후보·객체·경로 k개와 k개 파일 버퍼가 주요 메모리입니다. 버퍼 크기를 키우거나 k개 파일을 한 번에 열 수 없다면 병합 폭을 줄여 여러 단계로 합쳐야 합니다. 출력은 destination.open("w", ...)에 한 줄씩 쓰며 해당 경로의 기존 내용은 덮어쓰므로 전용 학습 결과 파일만 사용합니다.

from contextlib import ExitStack
from pathlib import Path
from tempfile import TemporaryDirectory
import heapq

def external_sort_file(source, destination, chunk_size=3):
    source, destination = Path(source), Path(destination)
    if type(chunk_size) is not int or chunk_size < 1:
        raise ValueError("positive integer chunk size required")
    if source.resolve() == destination.resolve() or (source.exists() and destination.exists() and source.samefile(destination)):
        raise ValueError("distinct paths required")
    with TemporaryDirectory(prefix="algorithms-runs-") as temporary:
        run_paths, chunk = [], []
        with source.open(encoding="utf-8") as stream:
            for line in stream:
                chunk.append(int(line))
                if len(chunk) == chunk_size:
                    run_path = Path(temporary) / f"run-{len(run_paths)}.txt"
                    run_path.write_text("".join(f"{value}\n" for value in sorted(chunk)), encoding="utf-8")
                    run_paths.append(run_path)
                    chunk = []
        if chunk:
            run_path = Path(temporary) / f"run-{len(run_paths)}.txt"
            run_path.write_text("".join(f"{value}\n" for value in sorted(chunk)), encoding="utf-8")
            run_paths.append(run_path)
        with ExitStack() as stack:
            streams = [stack.enter_context(path.open(encoding="utf-8")) for path in run_paths]
            runs = [(int(line) for line in stream) for stream in streams]
            output = stack.enter_context(destination.open("w", encoding="utf-8"))
            for value in heapq.merge(*runs):
                output.write(f"{value}\n")


import tempfile
private_root = Path(__file__).resolve().parent / "private-temp"
private_root.mkdir(exist_ok=True)
tempfile.tempdir = str(private_root)
with TemporaryDirectory(prefix="lesson-example-", dir=private_root) as temporary:
    folder = Path(temporary)
    source = folder / "input.txt"
    destination = folder / "output.txt"
    source.write_text("8\n1\n6\n3\n9\n2\n7\n", encoding="utf-8")
    before = source.read_text(encoding="utf-8")
    external_sort_file(source, destination, chunk_size=3)
    print([int(line) for line in destination.read_text(encoding="utf-8").splitlines()])
    print(source.read_text(encoding="utf-8") == before)

실행 결과:

[1, 2, 3, 6, 7, 8, 9]
True

왜 맞고 언제 끝나는가

각 런은 내부 정렬로 오름차순입니다. 각 런의 앞값이 그 런의 남은 최소이므로 그들 중 최소는 남은 전체의 최소입니다. 출력할 때 해당 런만 진행하면 정렬된 결과와 원소 개수를 보존합니다. 모든 입력을 유한하게 읽고 각 출력이 남은 원소를 줄여 종료합니다. context manager는 임시 런 파일을 정리하고 열린 파일을 닫습니다.

비용과 적용 범위

N개, 청크 M, 런 k≈ceil(N/M)에서 런 생성의 읽기·정렬 비용은 O(N log(M+1)), 병합의 읽기·비교·출력 비용은 O(N log(k+1))로 설명할 수 있습니다. +1은 청크나 런이 하나여도 N개를 읽고 쓰는 선형 비용을 포함합니다. 이 구현은 대략 O(M+k) 데이터 상태와 k개 열린 파일을 요구합니다. 파일 객체 버퍼·런 경로 저장 비용도 있습니다. 디스크 읽기·쓰기 횟수는 외부 정렬의 주요 비용이므로 RAM 연산 횟수만으로 대용량 성능을 단정하지 않습니다.

스스로 풀어 보기

1. 청크 크기 2에서 위 일곱 숫자로 만들어지는 네 런을 쓰세요.
2. 런이 백만 개이면 이 예제 함수를 그대로 쓰기 어려운 이유를 두 가지 쓰세요.

힌트

1. 원본의 두 개씩을 나누어 각각 정렬합니다.
2. 한 런당 앞 후보와 열린 스트림이 필요합니다.

해설

1. [1,8], [3,6], [2,9], [7]입니다.
2. 파일 디스크립터 한도를 넘을 수 있고 후보·버퍼·경로 메모리도 커집니다. 병합 폭을 제한한 여러 단계의 병합 계획이 필요합니다.

흔한 오해

RAM 전체에 입력을 올리지 않는다고 공간이 완전히 상수인 것은 아닙니다. 청크와 런 수, 버퍼를 모두 봐야 합니다.

복습과 다음 연결

다음 이중 연결은 DFS를 이용한 선택 심화입니다. 자료 구조별 요구를 종합하려면 알고리즘 선택으로 이어가세요.