[FP] 05. 화일의 정렬/합병
정렬/합병의 개요
정렬
- 내부 정렬 : 데이터가 적어서 메인 메모리 내에 모두 저장시켜 정렬 가능할 때. 레코드 판독, 기록에 걸리는 시간이 문제가 되지 않음. (메모리는 빠르기 때문)
- 외부 정렬 : 데이터가 많아서 메인 메모리의 용량을 초과 -> 보조 저장장치에 저장된 화일을 정렬
레코드 판독, 기록에 걸리는 시간이 중요 - 정렬/합병 : 런(run) : 하나의 화일을 여러 개로 분할하여 내부 정렬 기법으로 정렬시킨 각 서브 화일
합병(merge) : 런들을 합병하여 원하는 하나의 정렬된 화일로 만든다.
화일 정렬/합병 단계
- 정렬 단계 : 정렬할 화일의 레코드들을 지정된 길이의 서브 화일로 분할 후 정렬해 런을 만들어 입력 화일로 분해하는 단계
- 합병 단계 : 정렬된 런들을 합병 -> 더 큰 런으로 만듦 -> 큰 런을 다시 입력 화일로 재분배 -> 다시 합병
모든 레코드들이 하나의 런에 포함될 때까지 만드는 단계
런 생성 방법의 종류
정렬/합병 기법의 차별화 요소
- 적용하는 내부 정렬 방식
- 내부 정렬을 위해 할당된 메인 메모리의 크기
- 정렬된 런들의 보조 저장장치에서의 저장 분포
- 정렬/합병 단계에서 동시에 처리할 수 있는 런의 수
-> 위의 요소에 따라 런 수와 합병의 패스 수가 결정된다. - 패스 : 최종 화일 생성을 위해 반복적으로 실행한 과정
정렬/합병 기법의 성능 비교
- 정렬 단계에서 만들어지는 런의 수와 합병의 패스 수 비교
- 보조 저장장치에 대한 상대적 참조 빈도수 : 전체 레코드 집합에 대해 수행되어야 할 정렬/합병의 패스 수 비교
- 레코드들의 판독/기록 횟수
- 가능한 런의 길이를 길게 만들면 합병해야 될 런의 수는 최소화
- 동시에 합병할 수 있는 런의 수를 늘리면 합병의 패스 수는 감소
- 입력 런을 보조 저장장치에 분산 저장하면 합병에 필요한 입출력뿐만 아니라 부수적인 입출력 연산도 동반할 수 있음
m-원 합병
m개의 입력 화일을 동시에 처리하는 합병
m개의 입력 화일로부터 1개의 출력 화일을 생성
총 m+1개의 화일을 사용 / 입력 화일 수를 합병의 원 수(degree)라고 한다.
2원 합병 - 한 번의 패스를 실행하면 -> 합병된 런의 크기는 2배, 런의 개수는 절반이 된다.
2원 합병 - N개의 런으로 분할된 화일을 정렬하기 위한 패스 수 : ⌈ logN ⌉ / 2=1 / 3,4,5,6,7=2 / 8,9..=3
m개의 런을 하나의 큰 런으로 정렬시키는 작업
m개의 런(레코드) 중 가장 작은 키 값의 레코드를 계속 선택하고 출력한다.
간단하게 m-1번 비교를 하고 가장 작은 값의 키를 알아낼 수 있다.
선택 트리
선택 트리 구조를 이용하면 비교 횟수를 줄일 수 있다.
균형 합병
앞 패스에서 합병된 런을 생성할 때, 다음 패스의 입력 화일로 바로 사용할 수 있도록 미리 입력 화일로 분배해서 출력
즉, 출력 화일을 다음 단계의 입력 화일로 직접 사용한다.
- m-원 자연 합병 : m+1개의 화일 필요
- m-원 균형 합병 : 2m개의 화일 필요 (입력 화일 m개, 출력 화일 m개)
- 각 합병 단계 후 -> 런의 총 수는 합병 차수로 나눈 만큼 감소 / 런의 길이는 합병 차수의 두 배씩 증가 / O(logmN) (N은 초기 런의 수)
다단계 합병
화일 유휴 문제와 런의 단순 복사 문제(입력 화일에 1개의 런이 남게되면 단순히 출력화일로 복사하는 문제)를 개선
m개의 입력 화일과 1개의 출력 화일을 사용
입/출력 화일 수가 같지 않음 : ‘불균형’ 합병
초기 입력 화일에 대한 런의 ‘불균등’ 분배가 복잡
각 합병 단계 (pass)
- 입력 화일의 어느 하나가 공백이 될 때까지만 런들을 합병
- 공백이 된 입력 화일은 다음 합병 단계의 출력 화일이 됨
완전 피보나치 분배
- m-원 다단계 합병을 위한 초기의 런 수를 m차 피보나치 수열의 한 항이 되는 수가 되도록 생성
- 이 런들을 피보나치 분배 방법에 따라 분배
- 장점 : 합병 단계에서 마지막 패스를 제외하고는 각 패스가 끝날 때, 항상 하나의 입력 화일만 공백이 됨
합병을 위한 각 패스에서 입력 화일의 수는 항상 m이 됨
마지막 패스에서는 입력 화일이 모두 동시에 공백이 되면서 모든 런들이 출력 화일에 하나의 런으로 만들어짐
합병 단계에서 패스 수가 줄어듦
다른 예제 (3-원 다단계 합병, 처음 정렬 때 17개 런 생성)
계단식 합병
정렬/합병 과정에서 런들의 복사 작업을 줄이려는 불균형 합병의 또 다른 형태
초기 런 생성과 런의 분배가 중요 (완전 피보나치 분배)
합병을 위한 입력 화일 수가 m개에서 시작하여 m-1, m-2로 줄어 마지막 2개가 되면 한 주기가 끝남
- m개의 입력 화일로부터 m개의 런을 하나의 런으로 합병하여 출력 화일로 생성
- 입력 화일 하나가 공백이 되면 그 화일이 새로운 출력 화일이 되고 이전의 출력 화일은 대기
- 나머지 입력 화일들은 이 새 출력 화일에 합병된 런을 생성
- 2개의 입력 화일을 합병하는 단계가 되면 합병의 한 주기가 종료 / 한 주기에 각 레코드는 한 번씩만 처리
정렬/합병 유틸리티
정렬/합병은 많이 수행되는 연산이라 프로그램을 만들기보다 “정렬/합병 유틸리티”를 이용
(범용의 화일 정렬/합병 작업 지원)
유틸리티의 기능
- 하나 또는 그 이상의 화일 정렬
- 둘 또는 그 이상의 화일 합병
- 둘 또는 그 이상의 화일 정렬과 합병
정렬/합병 패키지 사용 시 명세 내용
- 정렬/합병할 화일의 이름
- 정렬/합병의 키 필드의 데이터 타입, 길이, 위치
- 키 필드들의 순서 (major에서 minor 순으로)
- 각 키 필드에 적용할 정렬 순서 (ASC, DES)
- 각 키 필드에 적용될 순서 기준
- 정렬/합병 결과를 수혹할 출력 화일의 이름
패키지에서 사용자 명세 사항 (더 세밀한 사항)
- 사용자가 정의한 정렬 순서 및 기준
- 내부 정렬 단계에서 사용할 알고리즘 (quicksort, heapsort 등)
- 합병 단계에서 사용할 알고리즘 (균형, 다단계, 계단식 등)
- 화일 사용 전/후에 필요한 동작 (rewind, unload 등)
- 합병 단계에서 입력 레코드가 올바른 순서로 되어 있는가의 검사
- 회복을 위한 체크 포인트/덤프 레코드를 사용하는 주기
- 예상 입력 레코드 수
저장 장치와 정렬/합병
- 합병 단계에서 사용되는 외부 저장 장치의 물리적 특성도 정렬/합병 시간에 영향
- 순차 접근만 허용되는 자기 테이프의 경우 : 각 화일이 서로 다른 릴에 저장 / 테이프 rewind 시간이 필요
- 임의 접근이 가능한 디스크의 경우
- 정렬/합병될 화일들이 하나의 디스크에 저장 : 디스크 입/출력 연산(탐구시간+회전지연시간)이 테이브(시작시간+ 정지시간)보다 더 많은 오버헤드를 수반. 그러나 테이프보다 훨씬 빠른 데이터 전송률로 보상
- 탐구와 회전 지연에 따른 접근 오버헤드 감축 방법 : 화일들을 2개 이상의 디스크로 분산시켜 입/출력 연산을
병렬처리 (병렬 처리를 위해서는 디스크마다 별도의 디스크 제어기가 있어야 함)