[화일처리론] 대규모 데이터의 외부 정렬 알고리즘 설계 및 비교

소개글

[화일처리론] 대규모 데이터의 외부 정렬 알고리즘 설계 및 비교에 대한 보고서 자료입니다.

목차

1. 문제 기술
2. 분석
3. 설계방법
① 각 외부정렬 기법을 수행함에 있어서 공통적인 부분과 독립적인 부분으로 구분하여 함수로 구성될 수 있도록 설계
② 수행시간 및 런의 수, 런의 크기 비교, 분석을 위해 각각의 외부정렬 기법 수행시 이를 출력하는 루틴 삽입.
③ 외부 정렬 기법 구조
④ 병합과정 - 균형합병 구조
⑤ 전체 프로그램 구성

4. Make
① 외부정렬 소스파일 계층구조
② makefile 작성 : sort.make
③ make 툴 사용 결과

5. 프로그램 리스트

6. 결과
① 프로그램 수행결과 출력화면
② 외부정렬 결과 출력 파일
-
7. 토의 및 개선 사항

본문내용

1. 문제 기술
○ 주어진 데이터를 내부정렬, 대체선택, 자연선택을 이용하여 외부정렬 기법을 설계하고 구현.
○ 내부정렬시 각 런의 크기는 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 으로 구분, 각 런의 크기에 대해 비교
○ 테스트 결과는 각각의 외부정렬 기법에 대하여 아래와 같은 기준으로 비교분석
- 런의 수에 대한 수행 시간
- 각 외부정렬 기법에 대한 가장 큰 런의 크기 및 가장 작은 런의 크기
○ GNU gcc 컴파일러를 사용하고 make 도구를 사용해서 수행

2. 분석
정렬/합병과정은 큰 데이터를 외부정렬 기법에 따른 규칙에 맞게 작은 런으로 쪼갠 다음(이때 각각의 특성에 맞게 정렬됨)에 다시 합병하여 정렬된 원래 크기의 파일을 만드는 것이 목적이다.
○ 각 외부정렬기법 분석 및 정리
- 내부정렬 : 런의 크기만큼 레코드를 잘라서 런을 생성, 정렬
- 대체선택 : 런의 크기만큼 버퍼에 데이터를 삽입하고, 최소값을 검색하여
출력하고 다음값을 대체 한다. 이때 출력한 값 보다 작으면,
동결을 표시하고 동결을 제외한 값에서 최소의 값을 찾는 과정
을 반복한다. 동결이 런의 크기만큼 생기면(즉, 모두 동결이 되
면) 런을 종료하고, 다음 런을 생성하여 위의 과정을 반복한다.
- 자연선택 : 런의 크기만큼 버퍼에 데이터를 삽입하고, 최소값을 검색하여
출력하고 다음값을 대체 한다. 이때 출력한 값 보다 작으면,
그 값을 외부 예비 저장장소에 보낸다.(크기는 런의 크기와 동일)
그리고, 출력 값 보다 큰 값이 나올 때 까지 다음 값을 비교한다
(다음 값 또한 출력 값 보다 작으면 예비 저장소로 보내는 과정
을 반복). 출력 값 보다 큰 값이 나오면 출력한 자리에 그 값을
대체한다.
예비 저장소가 가득차면(런 크기만큼) 현재 버퍼의 내용을 정렬
해서 생성중인 런 뒤에 붙인 다음 런을 종료하고, 외부 저장소의
내용을 버퍼로 복사한 새로운 런을 생성하여 다음 처음과 같은
과정을 반복한다.
이 때, 예비 저장소가 찼을 때 런을 마무리 하는게 아니라, 레코드를
가져와서 예비저장소에 넣으려고 할 때, 넣을 공간이 없으면 런을
마무리 해야 된다. 두 경우 상이하게 다른 결과가 나온다.
다음 레코드의 크기는 불러오기 전에는 알 수 없으며, 만약 출 력값보다 크다면 계속해서 런을 만들어 나가야하기 때문이다.
○ 합병하는 과정 분석 및 정리
- 균형합병 분석 : 런을 두 개의 파일로 병합한 다음(1번 2번 화일) 동일 인덱스에 존재하는 런을 합병하여 홀수 런은 새로운 파일(3번)에 짝수 런은 새로운 파일(4번)에 출력. 이렇게 발생한 3번, 4번 파일을 다시 동일한 방법으로 합병하여 1번 2번 파일에 재기록 하여 파일이 하나가 될 때까지 반복.
- 각 외부정렬 기법에 대해 발생한 런을 홀수 짝수 번호대로 나눠서 두 개의 파일로 묶은 다음 균형합병 방식으로 정렬/합병.
- 정렬과정에서 런의 개수를 카운트하고 균형합병 함수에 리턴하여 처리.
○ 파일 입출력 과정과 문제 분석
- 외부 저장장치에 주어진 데이터 파일을 읽어오고 정렬/합병해서 다시 파일에 기록해야 하므로 파일 입출력 과정이 필요.
- 정렬 과정에서 런 생성과 합병과정 중간의 임시 파일 생성을 위한 파일 입출력 과정도 추가적으로 필요.
- 외부 저장장치에 대한 파일 입·출력시 메모리 내 연산시보다 많은 시간이 소모.
- 각 기법 및 런의 크기에 따른 비교의 목적은 속도에 있으므로, 속도 저하에 큰 영향을 주는 파일 입·출력 연산을 최소화.
○ 전체적인 프로그램 구조
- 각 외부정렬 기법은 공통적으로 사용되는 부분과 독립적으로 사용되는 부분으로 나누어서 함수로 처리.
- 런의 크기를 입력받아 각 외부정렬 기법에 동일하게 적용시켜 수행.
- 지정된 데이터를 읽고 각 외부정렬 기법에 따라 정렬/합병 과정을 수행한 다음에 수행시간, 런의 수, 가장 큰 런의 크기, 가장 작은 런의 크기 출력.
○ make 도구

키워드

합병 정렬,   파일처리론,   화일처리론,   외부정렬,   알고리즘,   make