Gidhub BE Developer

정렬/합병 [ Part 2 ]

2018-04-17
goodGid

합병 단계

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

m-원 합병 (m-way merge)

  • 특징
    • m개(합병의 원 수)의 입력 파일을 동시에 처리하는 합병
    • 입력 파일 m개, 출력 파일 1개 : m+1개의 파일을 사용
    • 많은 입출력 : 한 패스에 합병이 끝나지 않으면 런들을 다시 분배하기 위해 복사,이동해야함
    • 이상적 정렬/합병 : m개의 런에 m개의 입력 파일 사용하여 한번의 m-원 합병을 적용
  • 2-원 합병의 경우
    • 한번 패스 후 : 합병된 런의 크기2배, 런의 수1/2배
    • N개의 런으로 분할된 파일 정렬 위한 패스 수 : LogN

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


6개의 런에 대한 3-원 합병


균형 합병 (Balanced Merge)

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

12개의 런에 대한 2-원 균형 합병


다단계 합병 (Polyphase Merge)

  • m-원 균형 합병 기법의 단점
    • 2m개 파일 필요 (m개 입력파일, m개 출력파일)
  • m-원 다단계 합병
    • m개의 입력 파일1개의 출력 파일
    • 입/출력 파일 수가 같지 않음 : 불균형 합병
    • 파일의 재분배필요 없고, 파일 수는 2m에서 m+1로 감소
    • 각 합병 단계(pass)에서
      • 입력 파일의 어느 하나가 공백이 될 때까지 런들을 합병
      • 공백이 된 입력 파일다음 합병 단계출력 파일이 됨

2-원 다단계 합병의 예


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


선택 트리 (Selection Tree) (1)

  • m개의 런을 하나의 큰 런으로 정렬
    • m개의 런 중 가장 작은 키 값의 레코드를 계속 선택, 출력
    • 선택 트리를 사용하여 비교 횟수를 줄일 수 있음
  • 선택 트리의 종류
    1. 승자 트리 (winner tree)
    2. 패자 트리 (loser tree)

선택 트리 (2)

  • 승자 트리
    • 완전 이진 트리
    • 각 단말 노드는 각 런의 최소 키 값 원소를 나타냄
    • 내부 노드는 그의 두 자식 중에서 작은 키 값을 가진 원소를 나타냄
    • 런이 8개인 경우 승자 트리 예
  • 승자 트리 구축 과정
    • 가장 작은 키 값을 가진 원소가 승자로 올라가는 토너먼트 경기로 표현
    • 트리의 각 내부 노드 :
      두 자식 노드 원소의 토너먼트 승자
    • 루트 노드 :
      전체 토너먼트 승자, 트리에서 가장 작은 키 값 가진 원소

선택 트리 (3)

  • 합병의 진행
    • 루트가 결정되는 대로 순서순차에 출력 (7)
    • 다음 원소
      즉 런 4의 키 값이 13인 원소가 승자트리 노드[11]로 들어감
    • 승자 트리를 다시 재구성 :
      노드 11에서부터 루트까지의 경로를 따라가면서 형제 노드 간 토너먼트 진행

선택 트리 (4)


선택 트리 (5)

  • 패자 트리 (Loser tree)
    • 루트 위에 0번 노드가 추가된 완전 이진 트리
  • 패자 트리 구축 과정
    • 단말 노드 : 각 런의 최소 키값 원소
    • 내부 노드
      • 두 자식 노드들이 부모노드에서 토너먼트 경기를 수행
      • 패자부모 노드에 남음
      • 승자그 위 부모 노드로 올라가서 다시 토너먼트 경기를 진행
    • 루트 노드
      • 패자는 1번 루트 노드에 남음
      • 승자는 전체 토너먼트의 승자로서 0번 노드로 올라가 출력

선택 트리 (6)

  • 합병의 진행
    • 출력된 원소가 속한 런 4의 다음 원소,
      즉 키값이 13인 원소를 패자트리 노드 11에 삽입
    • 패자 트리를 다시 재구성 :
      토너먼트는 노드 11에서부터 루트 노드 1까지의 경로를 따라 경기를 진행

Comments

Content