[파일 처리] 05 화일의 정렬/합병

 

1. 정렬/합병의 개요

1) 정렬

① 내부 정렬

- 데이터가 적어서 메인 메모리 내에 모두 저장시켜 정렬 가능할 때

② 외부 정렬

- 데이터가 많아서 메인 메모리의 용량을 초과해 보조 저장 장치에 저장된 화일을 정렬할 때

- 레코드 판독, 기록에 걸리는 시간이 중요

- 정렬/합병 : 런 이용(하나의 화일을 여러 개의 서브 화일로 나누어 내부 정렬 기법을 사용해 정렬시킨 화일)

 

2) 화일 정렬/합병

ⓐ 정렬 단계 : 정렬할 화일의 레코드들을 서브화일로 분할해서 정렬하여 런을 만들어 입력 파일로 분배

ⓑ 합병 단계 : 정렬된 런들을 합병해 보다 큰 런으로 만들고 다시 입력 파일로 재분배하여 합병해 모든 레코드들이 하나의 런에 포함되도록 만드는 단계

ⓒ 런 : 정렬된 서브파일

 

3) 정렬 단계

ⓐ 런 생성 방법

⑴ 내부 정렬 

> 런 생성 방법

- 파일을 n개 레코드씩 분할

- 분할된 레코드들을 내부 정렬 기법으로 정렬

> 특징 : 제일 마지막 런을 제외하고 모두 길이가 같다

* 입력데이터가 들어오고, 버퍼의 크기를 5라고 가정하면 5개씩 데이터를 분할하여 런을 만들어 정렬한다. 그리고 합병

 

⑵ 자연 선택

- 버퍼의 크기를 5라고 했을 때, 예비 저장소의 크기도 5 

> 방법

ⓐ 입력 파일에서 버퍼에 m개 레코드 판독

ⓑ 버퍼에서 키 값이 가장 작은 레코드 선택해 출력

ⓒ 입력 파일에서 다음 레코드 판독해 출력된 레코드와 대체 

- 만약 입력 레코드 키값 < 출력 레코드 키값 이라면, 그 레코드는 예비저장소에 저장(동결)

- 동결된 레코드는 제외하고 다시 입력 파일에서 데이터 판독하며 런을 생성

- 예비저장소가 꽉차면 동결된 레코드들이 메모리(버퍼)로 와서 다시 판독과정

> 특징

- 내부 정렬과 달리 입력 파일의 일부 정렬된 레코드들의 순서를 이용

- 내부 정렬보다 런의 길이가 김 => 런의 개수가 줄어들어서 합병 과정 비용 줄임

- 런의 평균 예상 길이 : 2m

 

4) 런 생성 방법 비교

> 내부 정렬

- 마지막 런 제외하고 모든 런의 길이가 같음

- 런의 길이를 예측할 수 있으므로 합병 알고리즘이 간단

> 자연 선택

- 내부 정렬보다 더 긴 런을 생성할 수 있음

- 예비 장소로의 입출력이 문제가 됨

- 긴 런 생성에 따른 효율화가 예비 장소 비용보다 이익이 될 수 있음

 

5) 화일 정렬/합병 방법의 차이점

- 차이점을 나타내는 매개변수: 메인 메모리 크기, 정렬된 런의 보저장의 저장분포, 동시처리 런의 수

- 정렬/합병 기법의 성능 : 매개 변수에 따라 런의 수, 합병의 패스 수 결정됨(정렬합병 몇번하는지)

- 레코드 판독/기록 횟수 성능에 영향을 미치는 요인 : 런의 길이 크게=> 런의 수 최소화, 동시에 합병할 수있는 런의 수를 늘리면 합병의 패스 수는 감소

 

2. m-원 합병

1) 특징

- m개의 입력 파일을 동시에 처리하는 합병

- 입력파일 m개, 출력파일 1개 : m+1개의 파일을 사용

- 많은 입출력 : 한 패스에 합병이 끝나지 않으면 런들을 다시 분배하기 위해 복사, 이동해야함

 

2) 2-원 합병의 경우

- 한번 패스후 : 합병된 런의 크기는 2배, 런의 개수는 1/2개

- n개의 런으로 분할된 파일 정렬을 위한 패스 수 : log2N

ex) 6개의 런에 대한 2-원 합병

ex) 6개 런에 대한 3-원 합병

 

3. 균형 합병

1) 특징

- m-원 합병은 화일의 재분배시 많은 I/O를 필요

- 출력 시, 미리 다음 단계에 사용할 입력 화일로 재분배 => 출력 화일을 다음 단계의 입력 화일로 직접사용

- m-원 합병이 m+1개의 화일이 필요한 반면, m원 균형 합병은 2m개의 화일이 필요

> 각 합병 단계후

- 런의 총수는 합병 차수로 나눈 만큼 감소

- 런의 길이는 합병 차수 배씩 증가

- 초기 런의 수가 N일 때 합병 패스 수는 O(logmN)

 

4. 다단계 합병

1) m-원 균형 합병 기법의 단점

- 2m개의 화일 필요

 

2) m-원 다단계 합병

- m개의 입력화일과 1개의 출력화일

- 입/출력 화일 수가 같지않음 : "불균형" 합병

- 화일의 재분배가 필요 없고, 화일 수는 2m에서 m+1로 줄어듬

- 각 합병 단계에서 입력화일이 어느 하나가 공백이 될 때까지 런들을 합병, 공백 입력 화일이 다음 합병단계 출력화일 

 

3) 2-원 다단계 합병의 초기 런 분배 방법

ⓐ 런 수의 변화(m=2) : 1, 1, 2, 3, 4, 8, 13, ...  👉 피보나치 수열

ⓑ 초기 런 분배 방법(m=2, 런의 수=5)

- 완전 피보나치 분배

- 5개 런의 2-원 다단계 합병에서 런 수의 변화

	정렬 단계	1차 합병	2차 합병	3차 합병
화일 1	3	1	0	1
화일 2	2	0	1	0
화일 3	0	2	1	0
런 합계	5	3	2	1

4) 3-원 다단계 합병

<생략>

 

5. 선택 트리

1) 방법 : m개의 런 중 가장 작은 키 값의 레코드를 계속 선택, 출력

👉 선택 트리를 사용함으로써 비교횟수를 줄일 수 있음

2) 종류

ⓐ 승자 트리

- 완전 이진트리, 각 단말 노드는 각 런의 최소 키값의 원소

- 내부 노드는 그의 두 자식 중 작은 키 값을 가진 원소를 나타냄

> 구축 과정

- 가장 작은 키 값을 가진 원소가 승자로 올라가는 토너먼트 경기 방식

- 결국 루트노드가 가장 작은 키값을 가짐

> 합병 과정

- 루트가 결정되는대로 순서 순차에 출력

- 해당 원소가 있는 런의 다음 원소가 승자 트리 노드로 들어가서 재구성 된다. 다시 토너먼트 진행

> m개의 런에서 가장 작은 키값으 선택하는 비교 횟수

- 선택 트리 사용 안할 경우 : 반복해서 m-1번 비교

- 선택 트리 사용하는 경우 : 처음만 m-1번 비교, 이후 반복해서 log2M번 비교

 

ⓑ 패자 트리

- 루트 위에 0번 노드가 추가된 완전 이진트리

> 구축 과정

- 단말 노드 : 각 런의 최소 키값 원소

- 내부 노드 : 두 자식 노드들이 부모노드에서 토너먼트 경기 수행, 패자는 부모 노드에 남음

                 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경기를 수행 

- 루트 노드 : 패자는 1번 루트 노드에 남음, 승자는 전체 토너먼트의 승자로 0번 노드로 올라가 출력됨

> 합병 진행 : 출력된 원소가 속한 런의 담원소를 패자 트리 노드에 삽입, 패자 트리노드를 재구성 한다.

 

6. 정렬/합병 유틸리티

1) 범용의 화일 정렬/합병 작업을 지원

 

2) 유틸리티의 기능

- 하나 또는 그 이상의 화일 정렬

- 둘 또는 그 이상의 화일 합병

- 둘 또는 그 이상의 화일 정렬과 합병

 

3) 정렬/합병 유틸리티 패키지 사용시 명세 내용

- 화일 이름, 데이터 타입, 길이, 위치, 키 필드 순서, 배열 순서, 출력 화일 이름 등