연습문제 풀이
외부 정렬에서 초기 run 수와 merge pass 수, 전체 블록 접근 비용을 계산하는 문제다.
그림보면 2번
M=3이었다
12/3 = 4
500만/40 = 125000
외부정렬의 비용계산
-
br: 정렬할 전체 블록 수 (block of records)
-
M: 사용 가능한 메모리 블록 수 (즉, 한 번에 메모리에 올릴 수 있는 block 수)
-
M-1: 한 번의 merge pass에서 병합 가능한 run 수 (M개의 블록 중 1개는 output 용도로 쓰고 M-1개로 merge 진행)
-
log(M-1)(br/M): merge pass 수 (M-1 way merge를 반복해서 전체를 하나로 만들기 위해 필요한 횟수)
-
ceil(br/M) : 초기 run 수
Comments