외부 정렬(디스크 병합) 패스 계산기

메모리에 한꺼번에 올릴 수 없는 데이터를 디스크를 오가며 정렬하는 방법입니다. 먼저 메모리에 들어가는 만큼 읽어 정렬해 되쓰고(런 만들기), 그렇게 만든 정렬된 조각들을 여러 개씩 열어 합치기를 되풀이합니다. 100GB 파일을 1GB 메모리로 정렬하는 것 같은 일이 여기 해당합니다.

런 개수 R = ⌈파일/메모리⌉이고, 병합 차수 k로 합칠 때마다 런이 1/k로 줄어드므로 병합 패스는 ⌈log_k R⌉입니다. 여기에 런을 만드는 첫 패스를 더하면 총 패스가 됩니다. 어느 패스든 파일 전체를 한 번 읽고 한 번 쓰므로, 총 입출력은 2 × 파일 크기 × 총 패스로 딱 떨어집니다.

버퍼가 작아져서 안 됩니다. 병합하는 동안 입력 런 k개와 출력 하나가 메모리를 나눠 쓰므로 스트림 하나당 버퍼가 메모리/(k+1)입니다. k를 키워 버퍼가 디스크 블록 몇 개 크기로 쪼그라들면 한 번에 읽는 양이 줄어 순차 읽기가 임의 접근으로 바뀌고, 회전 디스크에서 이 차이는 두 자릿수입니다. 그래서 실무의 k는 패스를 가장 줄이는 값이 아니라 버퍼가 충분한 한도 안에서 가장 큰 값으로 정합니다.

런을 길게 만드는 기법입니다. 메모리를 채우고 정렬해 통째로 비우는 대신, 힙을 유지하면서 가장 작은 값을 계속 내보내되 새로 읽은 값이 방금 내보낸 값보다 크면 이번 런에 끼워 넣습니다. 무작위 입력에서 런 길이의 기댓값이 메모리의 두 배가 되는 것이 알려져 있어 런 수가 절반이 됩니다. 런이 절반이면 병합 패스가 하나 줄어드는 경우가 생기고, 그때는 파일 크기의 두 배만큼 입출력이 통째로 사라집니다.

패스 수와 총 입출력을 세는 계산은 같지만 버퍼 크기의 무게가 다릅니다. SSD는 탐색 시간이 없다시피 해서 버퍼가 작아질 때의 손해가 회전 디스크만큼 크지 않고, 그래서 k를 더 크게 잡을 수 있습니다. 다만 큐 깊이와 쓰기 증폭이라는 다른 제약이 생기므로 무한정 올릴 수 있는 것은 아닙니다.

런을 모두 한꺼번에 열면 됩니다. 즉 k가 런 개수 이상이어야 하고, 이 계산기가 그 값을 「한 패스로 끝내려면 필요한 k」로 보여 줍니다. 그때 총 입출력은 파일 크기의 네 배(런 만들기에서 2배, 병합에서 2배)로 최소가 됩니다. 다만 그만한 k에서 버퍼가 남아나는지를 먼저 확인해야 합니다.

전송되지 않습니다. 모든 계산이 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.