altair의 프로젝트 일기
qsort 함수 분석 본문
정렬 알고리즘을 살펴보다보면 C언어에서 라이브러리에 퀵 정렬 함수가 있다는 것을 알게 된다. 이번에 정렬 알고리즘을 배우면서 qsort 함수를 실행하고 내가 직접 구현한 퀵 정렬과 그 실행시간을 비교할 기회가 있었다.
가장 간단한 퀵 정렬 알고리즘은 최악의 경우 \(O(n^2)\) 의 시간 복잡도를 갖는다. 정렬되지 않은 배열을 정렬할 때 $$log_{2}n$$의 재귀 단계를 가지지만, 피벗을 기준으로 파티션이 극단적으로 나뉠 때는 $$n^2$$의 단계를 갖는다.
많이 쓰이는 힙 정렬은 비록 퀵 정렬보다 살짝 느리지만 이런 최악의 경우를 갖지 않고 항상 안정적인 시간 복잡도를 갖는다는 장점이 있다.
이번 프로젝트에서 확인했던 일반적인 퀵 정렬 알고리즘의 실행시간은 다음과 같다. 데이터 개수는 5만개로 하였다.
- 정렬되지 않은 배열(일반적인 경우)
| 시행 | 시간 |
|---|---|
| 1 | 0.018301 |
| 2 | 0.024061 |
| 3 | 0.023780 |
| 4 | 0.021898 |
| 5 | 0.021349 |
- 정렬된 배열(최악의 경우)
| 시행 | 시간 |
|---|---|
| 1 | 6.159308 |
| 2 | 6.295298 |
| 3 | 6.714806 |
| 4 | 6.275795 |
| 5 | 8.014508 |
표에서 보다시피 입력으로 이미 정렬된 배열이 들어왔을때 퀵 정렬은 일반적인 경우에 비해 말도 안되는 성능 하락을 보인다. 퀵 정렬은 필연적으로 이런 최악의 경우를 피하기 위해 알고리즘을 적절히 편집할 필요가 있다.
C언어 라이브러리 stdlib에 있는 qsort는 놀랍게도 이런 정렬된 배열을 입력으로 주었을 때도 수행시간이 증가하지 않았을 뿐만 아니라, 오히려 줄어들기까지 했다.
- 정렬되지 않은 배열을 qsort에 넣었을 때
| 시행 | 시간 |
|---|---|
| 1 | 0.002869 |
| 2 | 0.002074 |
| 3 | 0.002466 |
| 4 | 0.002613 |
| 5 | 0.002080 |
정렬되지 않은 일반적인 경우에서의 수행시간보다 열 배는 적은 시간을 사용했다.
어리지만 그래도 코드를 쓰는 사람으로서 이를 능가하지는 못할 망정 따라잡고 싶은 마음이 들었다. 생각해보면 이미 정렬된 데이터를 다시 정렬하고자 할 때 수행시간이 늘어나는 것 자체가 직관적으로 이해되지 않는다. 이미 정렬되어 있다면 데이터 요소의 비교는 어쩔 수 없다고 해도 그 이동은 확연히 줄어들 것이라고 여기기 마련이다. 그렇다면 퀵 정렬에서 성능을 향상시킬 수 있는 방법이 어떤 것이 있을까? 퀵 정렬에서 피벗으로 범위의 중간값을 선택하거나, 배열을 무작위로 섞은 뒤 정렬하는 방법도 있을 것이다. 또한 스택 오버플로우의 위험을 갖는 재귀호출이 아닌 스택을 사용하는 방법도 있다. 이 세가지 방법을 모두 구현해보았다.
먼저 입력받은 배열을 뒤섞고 정렬하는 퀵 정렬의 수행시간을 보았다.
| 시행 | 시간 |
|---|---|
| 1 | 0.030819 |
| 2 | 0.027320 |
| 3 | 0.030205 |
| 4 | 0.027480 |
| 5 | 0.029770 |
의에서 보였던 최악의 경우는 벗어났지만 수행시간이 늘어났다. 데이터의 셔플에서 수행시간을 까먹은 것으로 보인다. 최종적인 시간 복잡도는 $$O(nlog_{2}n)$$에서 벗어나지 않지만, $$O(n)$$을 갖는 셔플 과정을 포함하면서 미세한 성능차이를 보이는 듯 하다.
다음으로 스택을 사용하는 퀵 정렬을 구현하고 피벗을 범위의 중간 값으로 선택하는 함수의 수행시간은 다음과 같다.
- 스택 + 중간 요소가 피벗
| 시행 | 시간 |
|---|---|
| 1 | 0.007939 |
| 2 | 0.009103 |
| 3 | 0.009826 |
| 4 | 0.009826 |
| 5 | 0.008822 |
위의 시도보다 평균적으로 놀라운 만큼 수행 시간 감소가 있었다. 의도적으로 정렬된 데이터를 입력으로 주었기 때문에 해당 퀵 정렬의 분할 함수는 항상 최고의 피벗을 선택할 것이고 이동시킬 데이터의 개수도 가장 적을 것이다. 하지만 여전히 최악의 경우가 존재한다. 선택한 배열 요소가 탐색 범위 내의 극단값이라면 여전히 비효율적인 분할이 발생할 것이다. 그리고 여전히, qsort보다 많은 시간을 사용한다.
도대체 qsort는 어떤 방법을 썼길래 그렇게 안정적으로 적은 시간을 사용할 수 있을까? qsort 함수는 stdlib.h, C언어 표준 라이브러리에 정의되어있다. GNU C 라이브러리인 glibc를 참조하였다. glibc의 메뉴얼은 여기에서 확인할 수 있다.
glibc에는 stdlib.h가 있고 여기에 qsort 함수의 원형이 구현되어 있다. 다음은 그 원형이다.
extern void qsort (void *__base, size_t __nmemb, size_t __size, __compar_fn_t __compar) __nonnull ((1, 4));정렬할 배열, 배열의 크기, 배열 요소의 크기, 배열을 비교할 비교 함수를 인자로 받는다. qsort의 용법에 대한 자세한 설명은 생략하겠다.
또한 glibc의 stdlib에는 qsort.c가 구현되어 있다. 모든 소스코드를 보이기에는 너무 길고 복잡하니 간단하게 먼저 주석을 확인해보았다.
/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:
1. Non-recursive, using an explicit stack of pointer that store the
next array partition to sort. To save time, this maximum amount
of space required to store an array of SIZE_MAX is allocated on the
stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
Pretty cheap, actually.
2. Chose the pivot element using a median-of-three decision tree.
This reduces the probability of selecting a bad pivot value and
eliminates certain extraneous comparisons.
3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
insertion sort to order the MAX_THRESH items within each partition.
This is a big win, since insertion sort is faster for small, mostly
sorted array segments.
4. The larger of the two sub-partitions is always pushed onto the
stack first, with the algorithm then concentrating on the
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */해당 소스 코드 주석에는 qsort 함수의 대략적인 구현 방법이 적혀있다. 간단하게 풀어쓰자면 다음과 같다.
- 비-재귀적(스택)으로 구현하였다.
- 세 값 중 중간값을 피벗으로 설정하였다.
- 일정 크기 이하로 정렬할 파티션이 줄어들면 삽입 정렬을 하였다.
- 피벗으로 나뉜 두 파티션 중 더 큰 파티션이 먼저 스택에 들어간다. 더 작은 파티션이 더 빨리 처리된다.
위 내용을 중심으로 코드를 살펴보자.
- 스택
스택을 사용하여 퀵 정렬을 구현하는 것도 이전에 해보았다. 하지만 스택 관련 함수들을 호출하는 과정에서 성능하락이 나타났다. 결과적으로 재귀를 사용하여 구현한 퀵 정렬과 수행 시간에서 별 차이가 없었다. 하지만 qsort는 스택 함수들을 매크로로 구현하였다.
#define STACK_SIZE (CHAR_BIT * sizeof (size_t))
#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
#define STACK_NOT_EMPTY (stack < top)스택을 일반적인 구조체와 함수가 아닌 매크로로 구현함으로써 함수의 호출을 발생시키지 않아 성능 향상을 이루어냈다. 또한 필요없는 스택 연산들을 구현하지 않은 것도 볼 수 있다.
- 피벗
/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
skips a comparison for both the LEFT_PTR and RIGHT_PTR in
the while loops. */
char *lo = base_ptr;
char *hi = &lo[size * (total_elems - 1)];
char *mid = lo + size * ((hi - lo) / size >> 1);
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
SWAP (mid, hi, size);
else
goto jump_over;
if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
jump_over:;퀵 정렬은 근본적으로 그 최악의 경우를 졔외하지 못한다. 하지만 그 확률을 낮출 수 있다. 위 코드는 스택이 비어있지 않다면 매번 반복되며 정렬하고자 하는 범위에서 중간 값을 찾는 과정이다. 그 중간값은 median-of-three이며 파티션의 첫 번째 요소와 맨 끝 요소, 그리고 중간에 있는 요소 중 중간값을 찾는다. 그리고 해당 값이 파티션을 나눌 피벗이 된다. 만약 세 요소가 모두 극단값을 갖는다면 어쩔 수 없이 나쁜 피벗을 선택하게 된다. 하지만 그 확률을 충분히 줄일 수 있다. 전체 데이터 개수 $$n$$에 대하여 세 값이 모두 극단값일 확률은 $$\frac{1}{n^{3}}$$이다. 단 하나의 값을 골랐을 때 그 값이 극단값일 확률이 $$\frac{1}{n}$$인 것을 생각하면 확연히 적은 확률이고 따라서 상대적으로 믿을만한 피벗이라고 할 수 있다.
- 단계의 축소
가장 이상적인 모습의 퀵정렬은 $$log_{2}n$$의 단계를 가진다. 즉 정렬해야 할 파티션은 매 단계가 지날 때마다 두 배씩 늘어난다. 그렇다면 이 경우 맨 마지막 파티션 분열은 바로 그전 단계의 두 배가 될 것이며, 퀵 정렬만을 사용한다면 고작 2,3개의 요소를 갖는 파티션이지만 나누어야 하는 것이다. 요소가 몇 개 없는 배열을 정렬할 때 삽입정렬이 괜찮은 성능을 보이는 것을 고려하면, 파티션 분열 단계를 너무 깊이 들어가지 않고 일정 이상 요소를 갖는다면 이를 삽입정렬로 정렬하는 것이 성능 향상을 이끌어낼 것이다.
/* Once the BASE_PTR array is partially sorted by quicksort the rest
is completely sorted using insertion sort, since this is efficient
for partitions below MAX_THRESH size. BASE_PTR points to the beginning
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
#define min(x, y) ((x) < (y) ? (x) : (y))
{
char *const end_ptr = &base_ptr[size * (total_elems - 1)];
char *tmp_ptr = base_ptr;
char *thresh = min(end_ptr, base_ptr + max_thresh);
char *run_ptr;
/* Find smallest element in first threshold and place it at the
array's beginning. This is the smallest array element,
and the operation speeds up insertion sort's inner loop. */
for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr = run_ptr;
if (tmp_ptr != base_ptr)
SWAP (tmp_ptr, base_ptr, size);
/* Insertion sort, running from left-hand-side up to right-hand-side. */
run_ptr = base_ptr + size;
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr -= size;
tmp_ptr += size;
if (tmp_ptr != run_ptr)
{
char *trav;
trav = run_ptr + size;
while (--trav >= run_ptr)
{
char c = *trav;
char *hi, *lo;
for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
*hi = *lo;
*hi = c;
}
}
}
}- 나뉜 두 파티션 중 더 작은 파티션부터 계산한다.
이는 결론적으로 스택의 크기가 $$log_{2}n$$ 이하가 되는 것을 보장한다. 두 파티션 중 큰 파티션만 스택에 들어간다면, 정렬된 첫 번째 파티션이 등장할 때가 바로 스택에 가장 많은 파티션이 존재할 것이다. 정렬되어 정렬 대상에서 제외될 수록 스택의 필요 크기는 작아지게 된다. 그리고 정렬된 첫 번째 파티션이 등장할 때 가장 많은 파티션이 스택에 들어가는 경우는 모든 파티션이 균등하게 나누어졌을 때일 것이다. 균등하게 분할되지 않고 한쪽이 더 크다면 그만큼 작은 파티션이 생기고 따라서 정렬된 첫 파티션이 더 빨리 등장할 것이기 때문이다.
예를 들어 16개의 요소를 가진 배열을 위 방법으로 정렬한다고 해보자. 모든 파티션은 균등하게 분배된다는 가정하에, 다음 단계를 거치게 될 것이다.
| 1단계 | 2단계 | 3단계 | 4단계 |
|---|---|---|---|
| 15 | |||
| 13, 14 | 13, 14 | ||
| 9, 12 | 9, 12 | 9, 12 | |
| 1, 8 | 1, 8 | 1, 8 | 1, 8 |
1단계에서는 파티션을 반으로 나누었다. 그 중 한 파티션을 계산하고 하나는 스택에 푸쉬했다. 2단계 역시 마찬가지이고, 3단계 역시 마찬가지이다. 4단계에서 16은 정렬된 파티션이고 15는 아직까지 정렬 여부를 확인하지 않았다고 가정했다. 처음의 파티션을 계속 반으로 나누는 과정이니, 마지막 단계의 총 파티션 수는 $$log_{2}4$$이다.
그리고 직관적으로 알 수 있다시피 한 파티션이 다른 하나보다 크면 클수록 전체 파티션 수는 더욱 작아질 것이다. 이를 일반화하면 더 작은 파티션을 먼저 계산할 때, 가능한 최대 파티션 스택 개수는 $$log_{2}n$$이다.
만약 qsort함수에서처럼 일정 범위 크기의 파티션은 선택정렬을 사용해 정렬한다면 어떻게 될까?
위의 예시를 16개의 요소가 아닌 64개의 요소라고 가정하고 무조건적인 균등 분할이 이루어진다고 하자. 그렇다면 스택에 존재 가능한 총 파티션 수는 $$log_{2}64 = 6$$개일 것이다. 하지만 만약 4개 이하의 크기를 가진 파티션은 선택정렬을 한다면? 이는 곧 64개의 요소가 아닌 16개의 요소를 가진 배열을 정렬하는 것과 같다. 따라서 가능한 총 파티션 수는 $$log_{2}(64/4) = 4$$와 같다. 이를 전체 데이터 개수 n과 최소 파티션 크기 k에 대하여 일반화하면, 가능한 총 파티션의 수(=필요한 스택의 크기)는 $$log_{2}(n/k)$$이다.
마무리
GNU C 라이브러리의 qsort는 살펴본 방법과 같이 구현되었고 꽤 좋은 성능을 보인다. 하지만 반대로 Apple의 다윈(XNU)커널 BSD 부분의 qsort는 스택이 아닌 재귀를 사용하여 구현되어있다. 재귀는 분명 스택 오버플로우의 위험을 내포하고 있지만, 위에서 보다시피 퀵 정렬에서 그 단계는 특정한 방법을 사용하여 $$log_{2}n$$이하로 줄일 수 있다. 따라서 극단적인 크기의 자료(일반적인 컴퓨터는 다 담을 수도 없을 정도의)를 정렬하는 것이 아니라면 걱정할 필요도 없이 안전한 범위의 재귀 단계만을 사용하게 된다. 이 qsort 또한 나중에 다루어보고 싶다.
항상 내가 스스로 구현해보기 바쁜 나머지 남이 작성한 코드를 살펴보고 분석할 기회가 별로 없었다. 바퀴의 재발명도 필요하지만 남이 만든 바퀴를 분석하고 가져와서 쓸 줄도 알아야한다. 그런 점이 나름 힘든 경험이었다. 내가 작성하지 않은 코드가 너무 어색하고 눈에 잘 들어오지 않았다. 이런 어쩌면 쓸데없어 보이는 분석이 그런 내 약점을 보완해 줄 수 있지 않나 싶다.
'IT > 알고리즘' 카테고리의 다른 글
| 최단경로 탐색 알고리즘 비교 (0) | 2021.10.24 |
|---|---|
| 미로 생성 알고리즘 (0) | 2021.10.24 |