← 질문 목록
#364깊이 0
K-way 병합에서 K를 증가시킬 때 발생하는 문제는 무엇인가?
자료구조 · 알고리즘
K를 증가시키면 힙 연산 비용이 늘어나고 디스크 무작위 접근이 증가하는 문제다.
| 기준 | K가 작을 때 | K가 클 때 |
|---|---|---|
| 병합 패스 수 | 많아진다 | 줄어든다 |
| 런당 버퍼 크기 | 크다 | 작다 |
| 디스크 I/O | 순차 접근 위주다 | 무작위 접근이 늘어난다 |
K가 커질수록 전체 병합 패스 수는 줄어든다. 대신 각 요소를 고르는 힙 높이가 자라 CPU 연산이 늘어난다.
한정된 메모리에서 K를 늘리면 런당 버퍼 크기가 줄어든다. 버퍼가 작으면 디스크 I/O가 자주 발생해 탐색 시간이 길어진다.
패스 수 감소 효과보다 CPU 비용과 디스크 탐색 손실이 더 커지면 전체 성능이 떨어진다.