5. 화일의 정렬/합병.

Presentation on theme: "5. 화일의 정렬/합병."— Presentation transcript:

1 5. 화일의 정렬/합병

2  정렬/합병의 개요 정렬(sorting) 내부 정렬(internal sorting)
데이타가 적어서 메인 메모리 내에 모두 저장시켜 정렬 가능할 때 레코드 판독, 기록에 걸리는 시간이 문제되지 않는다. 외부 정렬(external sorting) 데이타가 많아서 메인 메모리의 용량을 초과하여 보조 저장장치에 저장된 화일을 정렬할 때 레코드 판독, 기록에 걸리는 시간이 중요 정렬/합병(sort/merge) 런(run) : 하나의 화일을 여러 개로 분할하여 내부 정렬 기법으로 정렬시킨 서브화일(subfile) 런들을 합병(merge)하여 원하는 하나의 정렬된 화일로 만든다.

3 ▶ 합병의 기본 논리 시 작 서브화일 1 에서 처음 키 을 읽어라 2 를 의 EOF 에 도착했는가 ? 1 < 레코드를
정렬된 화일에 출력하라 다음 합병화일에 수록하라 정렬된 YES 끝 NO ▶ 합병의 기본 논리

4 ▶ 화일 정렬/합병 단계 정렬 단계(sort phase) 합병 단계(merge phase)
정렬할 화일의 레코드들을 지정된 길이의 서브화일로 분할해서 정렬하여 런(run)을 만들어 입력 화일로 분배하는 단계 합병 단계(merge phase) 정렬된 런들을 합병해서 보다 큰 런으로 만들고, 이것들을 다시 입력 화일로 재분배하여 합병하는 방식으로 모든 레코드들이 하나의 런에 포함되도록 만드는 단계

5 ▶ 정렬 단계 런 생성 방법 입력 화일(레코드 키 값)의 예 내부 정렬 (internal sort)
대체 선택 (replacement selection) 자연 선택 (natural selection) 입력 화일(레코드 키 값)의 예

6 (1) 내부 정렬 (internal sort)
런 생성 방법 1. 화일을 n레코드씩 분할 2. 분할된 레코드들을 내부 정렬 기법으로 정렬 런 생성 결과 마지막 런을 제외하고 모두 길이가 동일 n=5인 경우 런 1 : 런 2 : 런 3 : 런 4 : 런 5 : 런 6 : 런 7 : 런 8 : 런 9 : 런 10 : 런 11 :

7 (2) 대체 선택 (replacement selection)
런 생성 방법 입력 화일에서 버퍼에 m개의 레코드를 판독하고 첫 번째 런 생성을 시작 2. 버퍼로부터 키 값이 가장 작은 레코드를 선정해서 출력 3. 입력 화일에서 다음 레코드를 판독해 출력된 레코드와 대체 if (입력 레코드의 키 값 < 출력된 레코드의 키 값) then 레코드에 “동결(frozen)”로 표시 동결된 레코드는 단계 2의 선정 작업 대상에서 제외 동결되지 않은 레코드가 있으면 단계 2부터 실행 4. 동결된 레코드들을 모두 해제하고 단계 2로 돌아가 새로운 런을 생성 특징 내부 정렬과 달리 입력 화일의 일부 정렬된 레코드들의 순서를 이용 내부 정렬을 이용한 경우보다 런의 길이가 길다. 런의 평균 예상 길이: 2m

8 (2) 대체 선택 (replacement selection)
런 1 : 런 2 : 런 3 : 런 4 : 런 5 : 런 6 :

9 ▶ 대체 선택 알고리즘 replacementSelection() // 대체 선택 알고리즘
// Buffer[] : 버퍼-레코드 배열 // written[] : 해당 버퍼 레코드가 출력되었는지를 나타내는 플래그 배열 // frozen[] : 해당 버퍼 레코드가 동결되었는지를 나타내는 플래그 배열 // lastKey : 마지막으로 런에 출력된 레코드 키 값 // input : 입력 화일 for (i ← 0; i < m; i++) written[i] ← true; i ← 0; do { readFrom(Buffer[i], input); written[i]←false; i ← i + 1; } while (i < m && !end-of-file(input) ); // 런들을 생성 while (!end-of-file(input)) { // 새로운 런을 생성 // 동결 플래그 초기화 if (!written[i]) frozen[i] ← false;

10 ▶ 대체 선택 알고리즘 while (any unfrozen records remain) { // 레코드 하나를 런에 출력
select smallest unfrozen record Buffer[s]; appendToRun(Buffer[s]); lastKey ← Buffer[s].key; written[s] ← true; frozen[s] ← true; if (!end-of-file(input)) { readFrom(Buffer[s], input); written[s] ← false; if (Buffer[s].key > lastKey) frozen[s] ← false; } // 버퍼에 있는 나머지 레코드들을 출력 appendToRun(unwritten Buffer[] records in ascending key order); end replacementSelection()

11 (3) 자연 선택 (natural selection)
특징 동결된 레코드들을 버퍼에 유지하지 않고 보조 저장장치의 저장소(reservoir)에 별도 저장 하나의 런 생성 작업은 저장소가 꽉 차거나 입력 화일의 끝에 도달할 때까지 계속 런을 길게 만들어 런 수를 줄임으로써 합병 비용을 줄임 런 생성 결과(버퍼 크기(m)=5, 저장소 크기(m)’=5) 런 1 : 런 2 : 런 3 : 런 4 : 런 5 :

12 ▶ 자연 선택 알고리즘 naturalSelection() // 자연 선택 알고리즘
// m, m' : 버퍼와 저장소의 크기(레코드 수) // Buffer[] : 버퍼-레코드 배열 // written[] : 해당 버퍼 레코드가 출력되었는지를 나타내는 플래그 배열 // reservoir-count : 저장소에 저장된 레코드 수 // spaceFull : 저장소의 만원을 나타내는 플래그 // lastKey : 마지막으로 출력된 레코드 키 값 // input : 입력 화일 for ( i ← 0; i < m; i++) written[i] ← true; i ← 0; do { readFrom(Buffer[i], input); written[i] ← false; i ← i + 1; } while (i < m && (!end-of-file(input) ); reservoir-count ← 0; // 화일로부터 레코드를 읽어 런에 출력 do { // 런 하나를 생성 spaceFull ← false; do { // 레코드 하나를 출력 select smallest unwritten record Buffer[s]; appendToRun(Buffer[s]); lastKey ← Buffer[s].key; written[s] ← true;

13 ▶ 자연 선택 알고리즘 do { if (!end-of-file(input)) {
readFrom(Buffer[s], input); if (Buffer[s].key ≥ lastKey) { written[s] ← false; } else { move Buffer[s] to reservoir; reservoir-count ← reservoir-count + 1; if (reservoir-count = m') spaceFull← true; } } while (written[s] && !spaceFull && !end-of-file(input)); } while (!end-of-file(input) && !spaceFull); appendToRun(unwritten Buffer[] records in ascending key order); setTrue(corresponding elements of written[]); // 다음 런을 생성하기 위해 버퍼 정리 if (reservoir-count >0) { res-records ← min(reservoir-count, m); for (i ← 0; i < res-records; i++) { moveTo(a record from reservoir, Buffer[i]); written[i] ← false; reservoir-count ← reservoir-count - 1; if (Buffer[] not full && !end-of-file(input)) { fillBuffer(with records from input); setFalse(corresponding elements of written[]); } while (unwritten records exist in Buffer[]); end naturalSelection()

14 ▶ 런 생성 방법의 비교 내부 정렬 대체 선택 자연 선택 마지막 런을 제외하고 모든 런들의 길이가 같음
런의 길이를 예측할 수 있으므로 합병 알고리즘이 간단 대체 선택 내부 정렬보다 평균적으로 훨씬 긴 런을 생성 런의 길이가 길수록 합병 비용이 적음 런의 길이가 일정치 않아 정렬/합병 알고리즘이 복잡 자연 선택 앞의 두 방법보다 더 긴 런을 생성할 수 있음 저장소로의 입출력이 문제가 됨 긴 런 생성에 따른 효율화가 저장소 전송 비용보다 이익이 될 수도 있음

15 ▶ 정렬/합병 기법의 차이 정렬/합병 기법의 차별화 요소 이런 요소에 따라 런의 수와 합병의 패스(pass) 수가 결정
적용하는 내부 정렬 방식 내부정렬을 위해 할당된 메인 메모리의 크기 정렬된 런들의 보조 저장장치에서의 저장 분포 정렬/합병 단계에서 동시에 처리할 수 있는 런의 수 이런 요소에 따라 런의 수와 합병의 패스(pass) 수가 결정 패스(pass): 최종 화일 생성을 위한 반복적 실행 과정 정렬/합병 기법의 성능 비교 정렬 단계에서 만들어지는 런의 수와 합병의 패스 수 비교 보조 저장장치에 대한 상대적 참조 빈도수(reference frequency) 전체 레코드 집합에 대해 수행되어야 할 정렬/합병의 패스 수 비교 레코드들의 판독/기록 횟 수 가능한 런의 길이를 길게 만들면 합병해야 될 런의 수는 최소화 동시에 합병할 수 있는 런의 수를 늘리면 합병의 패스 수는 감소 입력 런을 보조 저장장치에 분산 저장하면 합병에 필요한 입출력뿐만 아니라 부수적인 입출력 연산도 동반

16 ▶ 합병 단계 합병 수행 방법 m-원 합병(m-way merge) 균형 합병(balanced merge)
다단계 합병(polyphase merge) 계단식 합병(cascade merge)

17  m-원 합병(m-way merge) 특징 2-원 합병의 경우 m개의 입력 화일을 동시에 처리하는 합병
입력 화일 수를 합병의 원 수(degree)라 함 많은 입출력 : 한 패스에 합병이 끝나지 않으면 런들을 입력 화일로 다시 분배하기 위해 복사와 이동을 해야 함 이상적 정렬/합병 : m개의 런에 m개의 입력 화일을 사용하여 한번의 m-원 합병으로 완료 2-원 합병의 경우 한번의 패스 : 합병된 런의 크기는 2배, 런의 수는 반 N개의 런으로 분할된 화일 정렬 위한 패스 수 :

18 ▶ 6 개의 런에 대한 2-원 합병 (2개의 입력 화일과 1개의 출력 화일) (1) 정렬단계 1000 레코드 씩 정렬된
6개의 런 1 내부 정렬 6000 레코드 정렬된 6개의 런을 2개의 입력 화일로 분배 (2) 1차 합병 런5 런3 런1 1-1000 1 런(1+2) 런(3+4) 런(5+6) 1차 합병 3 런6 런4 런2 2 에 있는 3개의 런을 2개의 입력 화일로 분배 3 (3) 2차 합병 1 2차 합병 2 3 런 (5+6) 런(1+2) 런(3+4) 런( ) 런(5+6) (4) 3차 합병 (2개의 입력 화일과 1개의 출력 화일) 3차 합병 3 런( ) 런(5+6) 런( ) 1 2

19 ▶12개의 런에 대한 2-원 합병 (1) 정렬단계 1 내부 정렬 500레코드 씩 정렬된 12개의 런 6000 레코드
정렬된 12개의 런을 2개의 입력 화일로 분배 (2) 1차 합병 런(1+2) 런(3+4) ..... 런(11+12) 런11 런9 ...... 런1 1 1차 합병 3 런12 런10 ...... 런2 2 에 있는 6개의 런을 2개의 입력 화일로 분배 3 (3) 2차 합병 런(9+10) 런(5+6) 런(1+2) 1 런( ) 런( ) 런( ) 2차 합병 3 런(11+12) 런(7+8) 런(3+4) 2 에 있는 3개의 런을 2개의 입력 화일로 분배 3

20 ▶12개의 런에 대한 2-원 합병 (4) 3차 합병 런(1+2+3+4) 런(9+10+11+12) 1 3차 합병 2
(4) 3차 합병 런( ) 런( ) 1 3차 합병 2 런( ) 런( ) 런( ) (5) 4차 합병 런( ) 1 4차 합병 2 3 런( ) 런( )

21 ▶ 6개의 런에 대한 3-원 합병 (3개의 입력 화일과 1개의 출력 화일) (1) 정렬단계 내부 정렬 1000레코드 씩 정렬된
6000 레코드 정렬된 6개의 런을 3개의 입력 화일로 분배 (2) 1차 합병 런4 런1 1 런(1+2+3) 런(4+5+6) 런5 런2 1차 합병 4 2 런6 런3 3 에 있는 런을 3개의 입력 화일로 분배( 이 경우에는 2개의 화일만 사용됨) 4 (3) 2차 합병 런(1+2+3) 1 런( ) 2차 합병 3 런(4+5+6) 2 (3개의 입력 화일과 1개의 출력 화일)

22 ▶ m-원 합병 알고리즘 mWayMerge() // m-원 합병 알고리즘 // m : 입력 화일의 수
// FILE[] : 화일 배열 // outfilenum : 출력 화일을 포함하는 화일 배열의 인덱스 // r : 현 단계에서 합병되지 않고 입력 화일에 남아 있는 런 수 // runcount : 현 단계에서 생성된 런의 수 // 합병 단계 do { openFile(FILE[1], ..., FILE[m]); // for reading openFile(FILE[m+1]); // for writing runcount ← 0; mergeRuns(FILE[1], ..., FILE[m] ⇒ FILE[m+1]); runcount ← runcount + 1; } while (!end-of-file on any one input file); // 합병되지 않고 입력 화일에 남아 있는 런 수의 계산 및 // 다음 단계의 출력 화일 선택 r ← 0; for (i ← m; i ≥ 1; i--) { if (!end-of-file(FILE[i])) r ← r + 1; else outfilenum ← i; } runcount ← runcount + r;

23 // 화일을 배열에 재할당 FILE[1], ..., FILE[m+1] ← FILE[1], ..., FILE[outfilenum-1], FILE[outfilenum+1], ..., FILE[m+1], ..., FILE[outfilenum]; closeFile(FILE[1], ..., FILE[m]); // 런들의 분산 단계 openFile(FILE[m]); // for reading openFile(FILE[1], ..., FILE[m-1]); // for writing // FILE[1], ..., FILE[m] 내의 런 수의 차이가 1 이하가 되도록 //⌈runcount/m⌉,⌈runcount/m⌉- 1,⌈runcount/m⌉- 2개씩의 런들을 배분 i ← 0; k ← m *⌈runcount/m⌉- runcount; do { i ← i + 1; if (k = 0) { if (end-of-file(FILE[i])) move(⌈runcount/m⌉ runs, from FILE[m] to FILE[i]); else move ((⌈runcount/m⌉- 1) runs, from FILE[m] to FILE[i]); } else { k ← k - 1; move((⌈runcount/m⌉- 1) runs, from FILE[m] to FILE[i]); else move ((⌈runcount/m⌉- 2) runs, from FILE[m] to FILE[i]); } } while (i ≠ m-1); } while (runcount ≠ 1); // 정렬된 최종 목표 화일은 FILE[m] end mWayMerge()

24 ▶ 선택 트리(selection tree) (1)
m개의 런을 하나의 큰 런으로 정렬 m개의 런(레코드) 중 가장 작은 키 값의 레코드를 계속 선택, 출력 간단한 방법 : m-1번 비교 선택 트리 : 비교 횟수를 줄일 수 있음 선택 트리의 종류 승자 트리(winner tree) 패자 트리(loser tree)

25 선택 트리 (2) 승자 트리(winner tree) 특징 런이 8개(k=8)인 경우 승자 트리 예 완전 이진 트리
각 단말 노드는 각 런의 최소 키 값 원소를 나타냄 내부 노드는 그의 두 자식 중에서 가장 작은 키 값을 가진 원소를 나타냄 런이 8개(k=8)인 경우 승자 트리 예 7 10 [4] 11 21 9 18 [6] 50 [15] [5] [7] [3] [2] [1] [8] [9] [10] [11] [12] [13] [14] 16 런 1 22 28 2 24 3 13 26 4 20 5 12 6 52 59 19 8 30 23

26 선택 트리 (3) 승자 트리 구축 과정 승자 트리의 표현 합병의 진행
가장 작은 키 값을 가진 원소가 승자로 올라가는 토너먼트 경기로 표현 트리의 각 내부 노드: 두 자식 노드 원소의 토너먼트 승자 루트 노드: 전체 토너먼트 승자, 즉 트리에서 가장 작은 키 값 가진 원소 승자 트리의 표현 승자 트리는 완전 이원 트리이기 때문에 순차 표현이 유리 인덱스 값이 i인 노드의 두 자식 인덱스는 2i와 2i+1 합병의 진행 루트가 결정되는 대로 순서순차에 출력 (여기선 7) 다음 원소 즉 키 값이 13인 원소가 승자 트리로 들어감 승자 트리를 다시 재구성 노드 11에서부터 루트까지의 경로를 따라가면서 형제 노드간 토너먼트 진행

27 선택 트리 (4) 이런 방식으로 순서 순차 구축을 계속함 다시 만들어진 승자 트리의 예 23 9 10 13 [4] 11 21
18 [6] 50 [15] [5] [7] [3] [2] [1] [8] [9] [10] [11] [12] [13] [14] 16 런 1 22 28 2 24 3 26 30 4 20 5 12 6 52 59 7 19 8

28 선택 트리 (5) 패자 트리(loser tree) 루트 위에 0번 노드가 추가된 완전 이원 트리 성질
(1) 단말 노드 :각 런의 최소 키 값을 가진 원소 (2) 내부 노드 : 토너먼트의 승자대신 패자 원소 (3) 루트(1번 노드) : 결승 토너먼트의 패자 (4) 0번 노드 : 전체 승자(루트 위에 별도로 위치)

29 선택 트리 (6) 런이 8개(k=8)인 패자 트리의 예 9 10 11 21 [4] 7 18 50 [6] [15] [5] [7]
23 9 10 11 21 [4] 7 18 50 [6] [15] [5] [7] [3] [2] [1] [8] [9] [10] [11] [12] [13] [14] 16 런 1 22 28 2 24 3 13 26 4 20 5 12 6 52 59 19 8 30 [0] 출력

30 선택 트리 (7) 패자 트리 구축 과정 합병의 진행 단말 노드: 각 런의 최소 키 값 원소 내부 노드 1번 루트 노드
두 자식 노드들이 부모노드에서 토너먼트 경기를 수행 패자는 부모 노드에 남음 승자는 그 위 부모 노드로 올라가서 다시 토너먼트 경기를 계속 1번 루트 노드 마찬가지로 패자는 1번 루트 노드에 남음 승자는 전체 토너먼트의 승자로서 0번 노드로 올라가 순서순차에 출력됨 합병의 진행 출력된 원소가 속한 런 4의 다음 원소, 즉 키 값이 13인 원소를 패자 트리 노드 11에 삽입 패자 트리를 다시 재구성 토너먼트는 노드 11에서부터 루트 노드 1까지의 경로를 따라 경기를 진행 다만 경기는 형제 노드 대신 형식상 부모 노드와 경기를 함

31  균형 합병 (balanced merge)
M-원 합병의 단점 : 화일의 재분배에 많은 I/O 필요 균형합병 출력할 때, 미리 다음 단계에 사용할 입력 화일로 재분배 즉, 출력 화일을 다음 단계의 입력 화일로 직접 사용 m-원 자연합병 : m + 1 개의 화일 필요 m-원 균형합병 : 2m 개의 화일 필요 (m 입력화일, m 출력화일) 각 합병 단계 후 런의 총수는 합병 차수로 나눈 만큼 감소 런의 길이는 합병 차수의 두 배씩 증가 O(logm N) , N : 초기 런의 수

32 ▶ 12개의 런에 대한 2-원 균형 합병 1 (1) 정렬단계 내부 정렬 1000레코드 씩 정렬된 6개의 런 6000 레코드
생성된 12개의 런을 2개의 화일에 분배 (2) 1차 합병 런(1+2) 런(5+6) 런(9+10) 런11 런 런1 1 1차 합병 2 3 4 런(3+4) 런(7+8) 런(11+12) 런12 런 런2 (3) 2차 합병 런(1+2) 런(5+6) 런(9+10) 런( ) 런( ) 3 2차 합병 4 1 2 런(3+4) 런(7+8) 런(11+12) 런( )

33 ▶ 12개의 런에 대한 2-원 균형 합병 (4) 3차 합병 런(1+2+3+4) 런(9+10+11+12) 1 3차 합병 2 3
(4) 3차 합병 런( ) 런( ) 1 3차 합병 2 3 4 런( ) 런( ) 런( ) (5) 4차 합병 런( ) 런( ) 런( ) 3 4차 합병 4 1 주의 런(1)은 4번 판독/기록되었음.

34 ▶ m-원 균형 합병 알고리즘 balancedMerge() // m-원 균형합병 알고리즘
// m : 입력 화일 수(모두 2m개의 화일 사용) // FILE[] : 화일 배열 // input-set-first : 현 단계에서 입력과 출력 세트를 구분하기 위한 플래그 // base : 출력 화일 세트의 첫 번째 화일 번호 // outfilenum : 현 단계의 출력 화일 번호 // runcount : 현 단계에서 생성된 런의 수 input-set-first ← false; do { if (input-set-first) { openFile(FILE[1], ..., FILE[m]); // for reading; openFile(FILE[m+1], ...,FILE[2m]); // for writing; base ← m + 1; } else { input-set-first ← true; openFile(FILE[1], ..., FILE[m]); // for writing; openFile(FILE[m+1], ...,FILE[2m]); // for reading; base ← 1; }

35 ▶ m-원 균형 합병 알고리즘 // 합병 단계의 수행 outfilenum ← 0; runcount ← 0; do {
mergeRun(input files ⇒ FILE[base+outfilenum]); runcount ← runcount + 1; outfilenum ← (outfilenum + 1) % m; } while (!end-of-file on all input files); rewind(input files and output files); } while (runcount ≠ 1); // input-set-first가 true면 최종 정렬 화일은 m+1, // false면 최종 정렬 화일은 1 end balancedMerge()

36  다단계 합병 (Polyphase Merge)
2m개의 화일이 필요(m개 입력화일, m개 출력화일) 단점 :하나의 합병된 런이 생성되는 동안 m-1 개의 파일은 항상 유휴 상태 m-원 다단계 합병(m-way polyphase merge) 화일 유휴 문제와 런의 단순 복사 문제를 개선 m 개의 입력 화일과 1 개의 출력 화일을 사용 입/출력 화일 수가 같지 않음 : "불균형" 합병 초기 입력 화일에 대한 런의 “불균등” 분배가 복잡 각 합병 단계(pass) 입력 화일의 어느 하나가 공백이 될 때까지만 런들을 합병 공백이 된 입력 화일은 다음 합병 단계의 출력 화일이 됨

37 ▶ 2-원 다단계 합병의 예 화일1 : 화일2 : 화일3 : 화일1 : 화일2 : 화일3 : 공백 공백 (a) 정렬 단계 결과 (b) 1차 합병 결과 화일1 : 화일2 : 화일3 : 화일1 : 화일2 : 화일3 : 공백 공백 공백 (c) 2차 합병 결과 (d) 3차 합병 결과

38 ★ 2-원 다단계 합병에서 런 수의 변화 각 합병 단계 마다 하나의 입력 화일만 공백이 됨 정렬 단계 1차 합병 2차 합병
3차 합병 화일 1 3 1 1 화일 2 2 1 화일 3 2 1 런합계 5 3 2 1

39 ▶ 초기 생성할 런 수의 결정 방법 3-원 다단계 합병을 위한 런 수(m = 3)
[1, 1, 1], 3, 5, 9, 17, 31, … 3차(m=3) 피보나치(Fibonacci) 수열 Ti = Ti-1 + Ti-2 + Ti-3, i > 3 Ti = 1, i ≤ 3 m차 피보나치 수열 Ti = 1 , i ≤ m

40 ★ 완전 피보나치 런 분배 방법 (m = 3) 원으로 표시된 수를 다음 단계의 다른 화일에 합산시킴 1 차 2 차 3 차 4
7 화일2 1 2 2 6 화일3 1 2 4 4 런 수 3 5 9 17

41 ▶ 완전 피보나치 분배 m-원 다단계 합병을 위한 초기의 런 수를 m차 피보나치 수열의 한 항이 되는 수가 되도록 생성
이 런들을 피보나치 분배 방법에 따라 분배 완전 피보나치 분배의 장점 합병 단계에서 마지막 패스를 제외하고는 각 패스가 끝날 때 항상 하나의 입력 화일만 공백이 됨 합병을 위한 각 패스에서 입력 화일 수는 항상 m이 됨 마지막 패스에서는 입력 화일이 모두 동시에 공백이 되면서 모든 런들이 출력 화일에 하나의 런으로 만들어짐 합병 단계에서 패스 수가 줄어듬

42 ▶ 3-원 다단계 합병 정렬 단계 런1, 런6, 런7, 런10, 런11, 런12, 런13 1 런2, 런4, 런14, 런15, 런 16, 런17 내부 정렬 2 런3, 런5, 런8, 런9 6000 레코드 3 1차 합병 7개의 런 6개의 런 4개의 런 1 화일 은 공백이 됨 3 2 1차 합병 4 4개의 런 3 2차 합병 4개의 런 3개의 런 2개의 런 4 1 2차 합병 3 화일 는 공백이 됨 2 2 2개의 런 3차 합병 2개의 런 1개의 런 3 화일 은 공백이 됨 1 4 3차 합병 2 1 1개의 런 4차 합병 1개의 런 2 화일 는 공백이 됨 3 4차 합병 1 2 3 4 4 1개의 런

43 ★ 각 합병 단계에서 화일 당 런 수의 변화 초기 런에 대한 완전 피보나치 분배 방법의 역순 정렬 단계 4차 합병 3차 합병
2차 합병 1차 합병 7 1 3 6 2 4 17 5 9 화일 1 화일 2 화일 3 화일 4 런 합 계

44 ▶ 3-원 다단계 합병의 예 화일1 : 화일2 : 화일3 : 화일4 : 화일1 : 화일2 : 화일3 : 화일4 : 공백 공백 (a) 정렬 단계 결과 (b) 1차 합병 결과 화일1 : 화일2 : 화일3 : 화일4 : 공백 공백 공백 (c) 2차 합병 결과

45 ▶ m-원 다단계 합병 알고리즘 polyphaseMerge() // m-원 다단계 합병 알고리즘 // m : 입력 화일의 수
     // FILE[]   : 화일 배열      // 입력 화일에는 피보나치 분배 방법으로 런들이 분배되었다고 가정     // 화일 준비     for (i ← 1; i ≤ m; i++)          openFile(FILE[i]);   // for reading;     openFile(FILE[m+1]);     // for writing;     // 합병 단계     do {         do {             mergeRun(FILE[1], ..., FILE[m] ⇒ FILE[m+1]);         } while (!end-of-file(FILE[m]));         rewind(FILE[m] and FILE[m+1]);         closeFile(FILE[m] and FILE[m+1]);         openFile(FILE[m+1]);          // for reading         openFile(FILE[m]);           // for writing         // 화일을 배열에 재할당         FILE[1], FILE[2], ..., FILE[m+1]                 ← FILE[m+1], FILE[1], ..., FILE[m];     } while (!end-of-file on all files on FILE[2], ..., FILE[m]);     // 정렬된 최종 목표 화일은 FILE[1] end polyphaseMerge()

46  계단식 합병 (Cascade Merge)
정렬/합병 과정에서 런들의 복사 작업을 줄이려는 불균형 합병의 또 다른 형태 m-원 계단식 합병(m-way cascade merge) 초기 런 생성과 런의 분배가 중요(완전 피보나치 분배) 합병을 위한 입력 화일 수가 m개에서 시작하여 m-1, m-2, …, 로 줄어들어 마지막 2개로 될 때 한 주기가 끝남 합병 단계 m개의 입력 화일로부터 m개의 런을 하나의 런으로 합병하여 출력 화일로 생성 입력 화일 하나가 공백이 되면 이 화일이 새로운 출력 화일로 되고 이전의 출력 화일은 대기 나머지 입력 화일들은 이 새로운 출력 화일로 합병된 런을 생성 2개의 입력 화일을 합병하는 단계가 되면 합병의 한 주기가 종료 한 주기에 각 레코드는 한번씩만 처리

47 ▶ 3-원 계단식 합병 화일1 : 화일2 : 화일3 : 화일4 : 화일1 : 화일2 : 화일3 : 화일4 : 공백 공백 (a) 정렬 단계 결과 (b) 합병 1주기 1차 합병 결과 화일1 : 화일2 : 화일3 : 화일4 : 화일1 : 화일2 : 화일3 : 화일4 : 공백 공백 공백 공백 공백 (c) 합병 1주기 2차 합병 결과 (d) 합병 2주기 1차 합병 결과

48 ▶ 3-원 계단식 합병 합병 1주기 7개의 런 6개의 런 4개의 런 1 1 주기 패스 1 화일 은 공백 3 화일 는 대기 4
화일 은 공백 3 화일 는 대기 4 2 4 4개의 런 3 3개의 런 2개의 런 화일 는 공백 2 화일 은 대기 3 1 1 주기 패스 2 3 2 2개의 런 합병 2주기 4개의 런 2개의 런 1개의 런 4 2 주기 패스 1 화일 은 공백 1 화일 는 대기 2 3 2 1개의 런 1 3개의 런 1개의 런 화일 은 공백 4 2 주기 패스 2 3 1 3 화일 은 대기 1개의 런 1 합병 3주기 2개의 런 1개의 런 4 3 주기 패스 1 화일 과 는 공백 1 2 2 3 화일 은 대기 1개의 런 1 3 합병 4주기 1개의 런 4 주기 패스 1 3 1 화일 는 공백 2 3 4 4 1개의 런

49 ▶ m-원 계단식 합병 알고리즘 cascadeMerge() // m-원 계단식 합병 알고리즘 // m : 입력 화일의 수
     // FILE[]   :화일 배열     // 입력 화일에는 완전 피보나치 분배에 따라 런들이 분배되어 있다고 가정     // 화일의 준비     for (i ← 1; i ≤ m; i++)          openFile(FILE[i]);   // for reading;     openFile(FILE[m+1]);     // for writing;     // 합병 단계     do {         i ← 0;         do {             i ← i + 1;             do {                     mergeRuns(FILE[1], ..., FILE[m-i+1] ⇒ FILE[m-i+2]);             } while (!end-of-file(FILE[m-i+1]));             rewind(FILE[m-i+1] and FILE[m-i+2]);             closeFile(FILE[m-i+1] and FILE[m-i+2]);             // 하나 이상의 화일이 비었을 경우 해당 단계를 생략함             empty-file ← true;             k ← 1;

50 ▶ m-원 계단식 합병 알고리즘 while (empty-file && i < m-1) {
                if (end-of-file(FILE[m-i+1-k])) {                     i ← i + 1;                     k ← k + 1;                     rewind(FILE[m-i+1-k]);                     closeFile(FILE[m-i+1-k]);                 } else empty-file ← false; }             // 다음 단계의 출력 화일 준비             openFile(FILE[m-i+1]);           // for writing         } while (i ≠ m-1);         // 화일을 런 수의 내림차순으로 정렬한 후 배열에 재할당         reallocateFiles(FILE[1], ..., FILE[m+1],                 run count of FILE[1] ≥ run count of FILE[2] ≥                 ... ≥ run count of FILE[m+1]);                // 남은 화일 수의 재조정         no-more-empty ← false;         do {             if (end-of-file(FILE[k]))    m ← m - 1;             else no-more-empty ← true;         } while (m ≠ 1 && !no-more-empty);     } while (m ≠ 1);     // 최종 정렬된 목표 화일은 FILE[1] end cascadeMerge()

51  정렬/합병 유틸리티 정렬/합병 유틸리티(utility)를 이용 유틸리티의 기능 정렬/합병 패키지 사용시 명세 내용
 정렬/합병 유틸리티 정렬/합병 유틸리티(utility)를 이용 범용의 화일 정렬/합병 작업을 지원 유틸리티의 기능 (1) 하나 또는 그 이상의 화일 정렬 (2) 둘 또는 그 이상의 화일 합병 (3) 둘 또는 그 이상의 화일 정렬과 합병 정렬/합병 패키지 사용시 명세 내용 (1) 정렬/합병할 화일의 이름 (2) 정렬/합병의 키 필드의 데이타 타입, 길이, 위치 (3) 키 필드들의 순서(major에서 minor 순으로) (4) 각 키 필드에 적용할 정렬 순서 (ASC, 또는 DES) (5) 각 키 필드에 적용될 순서 기준 (6) 정렬/합병 결과를 수록할 출력 화일의 이름

52 ▶ 패키지에서 사용자 명세 사항 (1) 사용자가 정의한 정렬 순서 및 기준 (2) 내부 정렬 단계에서 사용할 알고리즘
(예 : quicksort, heapsort) (3) 합병 단계에서 사용할 알고리즘 (예 : 균형, 다단계, 계단식 합병) (4) 화일 사용 전후에 필요한 동작(예 : rewind, unload) (5) 합병 단계에서 입력 레코드가 올바른 순서로 되어 있는가의 검사 (6) 회복을 위한 체크 포인트(check point)/덤프 레코드(dump record)를 사용하는 주기 (7) 예상 입력 레코드 수

53 ▶ 유틸리티를 이용한 정렬/합병의 예 ★ job control command
/ / SORTNOW EXEC SORTMRG / / SORTIN DD DSN = name of input file, ...., / / DISP = (OLD, KEEP) / / SORTOUT DD DSN = name of output file, ..., / / DISP = (NEW, KEEP) / / SYSIN DD * SORT FIELDS=(1,4,CH,A,20,10,CH,D), FILEZ=E2000 / * SORTMRG(input-filename, output-filename) ... SORT, VAR = POLY FILE, INPUT = name(CU), OUTPUT = name(R) FIELD, DEPT(1,4,ASCII6), SALEDATE(20, 10, ASCII6) KEY, DEPT(A,ASCII6), SALEDATE(D, ASCII6) ★ job control command

54  저장장치와 정렬/합병 합병 단계에서 사용되는 외부 저장장치의 물리적 특성도 정렬/합병 시간에 영향
순차 접근만 허용되는 자기 테이프의 경우 각 화일이 서로 다른 릴에 저장 테이프 rewind 시간이 필요 임의 접근이 가능한 디스크의 경우 정렬/합병될 화일들이 하나의 디스크에 저장 디스크 입/출력 연산(탐구시간 + 회전지연시간)이 테이프(시작 시간 + 정지시간)보다 더 많은 오버헤드를 수반. 그러나 테이프보다 훨씬 빠른 데이타 전송률로 보상 탐구와 회전 지연에 따른 접근 오버헤드 감축 방법 화일들을 2개 이상의 디스크로 분산시켜 입/출력 연산을 병렬처리 화일의 입/출력 요구를 병렬로 처리하기 위해서는 디스크마다 별도의 디스크 제어기가 있어야 됨