본문으로 바로가기

2021.03.30 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부#10 (순차화일)

 

화일 처리 및 응용 공부#10 (순차화일)

2021.03.26 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #9 (버퍼) 이전에 배운 내용도 확인해보자. 순차 화일 스트림화일  - 데이터가 하나의 연속된 바이트 스트림으로 구성됨  - 연속적

thesauro.tistory.com


합병단계

입력단계에서 나눠진 런을 합병하는 단계

 

- m-원합합병

- 균형 합병

- 다단계 합병

- 계단식 합병

 

 

 

m-원 합병

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

- m개의 입력 화일로 부터 하나의 출력 화일을 생성

  - 총 m+1개의 화일을 사용

  - 입력화일 수를 합병의 원 수(degree) 라함

  - 한패스에 합병이 끝나지 않으면 런들을 입력 화일로 다시 분배하기 위해 복사와 이동을 해야함

 

2- 원 합병의 경우

- 한번의 패스 : 합병된 런의 크기는 2배, 런의 수는 반

 - N개의 런으로 분할된 화일 정렬 윈한 패스수 : [log2(N)]

 

2-원 합병 과정
2원 합병 단계(2)

 

3원 합병에 경우 4차 과정에서 부족한 런수는 생량되는걸 알 수 있다.

 

 

선택트리

m개의 런을 하나의 큰런으로 정렬

 - m개의 런 중 가장 작은 키 값의 레코드를 계속 선택, 출력

 - 간단한 방법 : m-1번 비교

 

- 선택트리 : 비교횟수를 줄일 수있음

- 승자트리, 패자트리

 

선택트리 알고리즘

r1이 r2랑 비교해서 작으면.. r3와 비교.. 또 작으면.. r4랑 비교... 해서 r1이 최종적으로 작으면 r1을 최솟값, 그외에는 마지막에 비교한 r5를 최솟값에 넣는 식...

 

 

승자트리

 

완전히 2갈래노 나누어서 표현되는 완전 이진 트리 구조이다.

각 노드는 토너먼트 마냥 작은값을 최상위로 올린다.

 

맨위에 노드를 루트노드

가운데를 내부노드

맨 아래 노드를 단말노드

라고 한다.

 

다음 단계 승리트리

 

후에 다음단계에선 7이 출력되므로 [11]자리에 13이 들어가서 다시 트리를 형성한다.

[7,9,10,10,,,,,,,,]

 

 

패자 트리

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

단말 노드 : 각런의 최소 키값을 가진 원소

내부 노드 : 토너먼트의 승자대신 패자원소

루트노드 : 결승 토너먼트의 패자

0번 노드 : 전체 승자(루트위에 별도로 표시)

 

승자 노트랑 다르게 패자가 올라간다. (승자는 다르게 별도위치에 저장된다.)
별도에 장소에 승자는 저장됨

균형 합병

m-원 합병의 단점 : 화일의 재분배에 많은 I/O가 필요하다.

- 출력할 때, 미리 다음 단계에 사용할 입력 화일로 재분배

  m-원 자연합병 : m+1개의 화일 필요

  m-원 균형합병 : 2m 개의 화일 필요 (m입력화일, m출력화일)

 

각 합병 단계 후

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

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

 - O(logm[N]), N : 초기런의수 (빅오기법)

 

 

2원 균형합병

 

2원 합병과 다르계 합병후 런 화일 출력도 2개로 나눠진다.
2원 균형합병(2)

m-원 균형 합병

 - 2m개의 화일이 필요함(m개입력화일 + m개 출력화일)

 - 단점 ; 하나의 합병된런이 생성되는 동안 m-1개의 파일은 항상 유휴상태를 가짐

 

 

 

m-원 다단계 합병

 

m-원 다단계합병

 - 화일 유휴 문제와 런의 단순 복사 문제를 개선(m원 합병, 균형합병 단점 개선)

 - m 개의 입력화일과 1개의 출력 화일을 사용

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

 - 초기 입력 화일에 대한 런의 "불균등" 분배가 복잡

 

다단계 합병 예시

재분배 과정이 사라짐, 알고리즘이 복잡한편이다. 공백화일이 출력받을 화일 역활로됨

 

 

m원 합병, m원 균형합병, m원 다단계 합병 요약

요약 이미지

다단계에 경우 한개씩 나눠서 공백에 화일에 담아지므로 3번화일이 공백이 된순간 담아지는 화일을 담당하게 되고 3- 4는 서로 바꿔서 2차 합병 단계를 거친다. 이경우 2는 2개의 런, 1은 3개의 런만 남아져서 2차 합병단계를 걸친다.

 

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

언제나 합병단계 하나에 하나의 파일만 공백을 유지함.

 

더보기

완전 피보나치 분배

으악 내머리... 2원 다단계 합병을 참고하면서 확인하자

 

완전 피보나치 분배

 

다음 분배마다 이전 화일의 갯수만큼 분배하는 수가 늘어난다. 화일 1의 경우 R1,R6,R7 이런 식...

 

다단계 방식과 마찬가지로 합병단계 도중 하나의 화일만 공백이 된다.

추가적을 합병을 위한 각 패스에서 입력화일 수는 항상 m이 된다.

 

 합병단계
자원 아껴쓰기를 위해 우리의 뇌를 파괴시키며 효율을 찾고 있다...

 

정렬/합병 유틸리티

  • 범용의 화일 정렬/합병 작업을 지원
  • 하나, 그 이상의 화일 정렬
  • 둘 또는 그 이상의 화일 합병
  • 둘 또는 그 이상의 화일 정렬과 합병

 

정렬/합병 패키지 사용시 명세 내용

  1. 정렬/합별할 화일의 이름
  2. 정렬/합별의 키 필드의 데이타 타입, 길이, 위치
  3. 키 필드들의 순서
  4. 각 키 필드에 적용할 정렬 순서
  5. 각 키 필드에 적용될 순서 기준
  6. 정렬/합병 결과를 수록할 출력 화일의 이름

패키지에서의 명세사항


느낀점 : 중간고사도 다가오니 이전 내용에서 배운 RUN을 다시 이해해보고 트리, 합병, I/O 관련한것도 다시 이해하자