ch8) Consequential Processing and Sorting
Consequential 이란?
- 2개의 파일
- 어떠한 키에 대해서 sorted 되어있음
- 교집합과 합집합을 찾기 위해 사용 ( 결과 파일은 그 키에 대해 정렬이 되어 있어야 함)
- 교집합을 찾자!!
1. match를 찾아보자 ( 조건 : 효율적인 방법으로 찾아야 함, 중복된 key 값은 없음 )
(1) 효율을 따지지 않는다면, 가장 간단한 방법은 List1 각 요소마다 List2의 모든 요소와 비교
(2) 정렬이 되어 있으므로, List1의 첫 레코드와 List2의 첫 레코드를 비교
- 두 값이 동일하다면 결과 파일에 작성
- 그 다음 값들을 읽어옴 (CARTER, ANDERSON)
- 두 키를 비교 했을 때, 같지 않으면 List2의 다음 요소를 읽어옴 (C > A이기 때문에)
(CARTER와 같거나 더 큰 값이 나올 때까지 읽어와서 비교를 진행)
- 두 값이 동일하다면 결과 파일에 이어서 작성
=> 최대 m+n번 읽음
2. input()
(1) List1과 List2의 key값이 동일하기 때문에 하나만 저장
(2) List2의 값이 List1와 같거나 클 때까지 출력을 해줘야 함
(3) 키에 대해 정렬된 키값들을 구할 수 있음
K-way Merge
1. k개의 파일이 존재 (위의 예시는 k=2인 경우)
2. key에 대해 중복되는 값이 존재한다고 가정 (파일들 간에)
진행 방식 (k-way merge)
(1) k개의 key값 중에서 가장 작은 값을 구함 (각 파일 중 맨 처음에 위치)
(2) 가장 작은 것이 온 파일(A) 에서 start -> 그 다음 작은 key값을 찾음
(3) A의 다음 key값과 다른 파일들의 첫 번째 key값과 비교해서 그 중 작은 key 값(B)을 찾음
(4) B의 다음 key값과 다른 ~~~
(5) k-way merge와 방금 뽑은 가장 작은 값과 같다면 그 값이 존재하는 파일의 다음 값을 불러와서 다시 비교
집합 사이에 중복이 없는 경우
진행 방식 (No Duplicate Names)
(1) 위와 비슷한 방식 (but 중복이 존재하지 않음)
=> 가장 작은 값을 비교할 때 n-1번 연산이 듦
A Selection Tree
=> 초기에는 n-1번 비교 / 처음 실행하고 5번이 출력되고 난 후에는 위에 7과 11을 비교하는 과정은 필요가 없음
(5가 출력되고 그 다음 작은 값 6, 12 비교 후 6과 8 비교 후 6과 7 비교만 하면 됌) => 7번 비교하던 것을 3번으로 줄어듦
=> O(log2 k)
Heapsort (Internal sort)
1. binary tree여야 함 (항상 child node >= parent node) -> 힙 종류에 따라 다름
2. complete여야 함 (마지막 level을 제외하고는 모든 노드의 child의 개수는 2여야 함, child가 존재하면 왼쪽부터 채워져야 함)
3. 동해물과 함께 해야함
4. 그렇다면 백두산은 ?
Building Heap
1. 전체 레코드에 대해 heap 생성
- Disk에 있는 데이터 순서대로 불러와서 parent key값과 비교해서 parent key가 더 크면 변경
- 마지막 과정으로 정렬
2. 루트에 있는 데이터를 빼서 Disk에 순서대로 넣어줌 (루트에 있는 데이터가 빠지면 힙을 재구성) (반복) - 힙을 이용해서 정렬하는 과정
Heapsort의 장점
CPU 사용 job 과 Disk 사용 job
- 병렬 처리가 가능함
- Disk에 데이터를 읽는 동안에 CPU로 처리할 수 있다는 말임
- TIME Cost를 줄일 수 있음
- 동시에 할 수 있는 부분 -> Main memory에서 힙을 만드는 동안에 Disk에서 다음 레코드를 읽어오는 작업을 함
(record blocking을 활용하면 더 좋음)
-> 메인 메모리에 output buffer를 만들어서 레코드를 순차적으로 담은 후에 Disk에 보내줌 (Disk에서는 순차적으로 write하고, Main memory에서는 재정렬을 함)
버블 정렬 같은 경우에도 가능한가 ? 진행시켜 영차~
파일의 크기가 클 경우에 정렬하는 방법
- 디스크에서 파일을 잘게 쪼갠다. -> 쪼개진 조각을 메인 메모리에 올려서 정렬을 하고 결과를 디스크에 작성
(input buffer의 크기에 맞춰서 쪼갬)
- Internal Sort 이용
- 각 파일은 키에 대해 정렬되어 있음 -> merge함 => k-way merge 알고리즘을 이용!!
전체 과정에서 발생하는 Disk IO (Time Cost) 계산
가정 : single sequential access ( 쪼개진 조각을 순차적으로 읽을 때, sorting을 하고 write할 때 ) -> one seek
per access -> one rotational delay
- step2는 step1은 같은 비용 발생
- k-way merge 알고리즘 사용
- 하나의 블록은 10M/80 임 (하나의 레코드를 의미하는 것이 아님)
시간을 줄이는 법
1. Hardward를 향상시키는 방법
- Input buffer size를 크게 만들어 줌
- Output buffer size를 크게 만들어 줌
2. Dedicated Disk Drives의 개수를 증가시키기
- 병렬처리를 이용 (Disk 2에서 write를 하는 동안 Disk 1에서는 읽기 과정을 수행)
- 병렬처리를 이용 (k-way merge에서도 수행 가능 - ouptut에서 write하는 동안에 k-way merge 수행)
3. I/O channels의 수 증가시키기