직접 정렬할 일이 거의 없어 요즘은 이런 함수를 잘 쓰지 않지만 그래도 정렬은 알고리즘의 기본 중의 기본이다. 통계 프로그램을 작성하다 정렬 루틴을 쓸 일이 있어 별 생각없이 qsort를 사용했는데 반복 횟수가 워낙 많다 보니 성능이 제대로 나오지 않았다. C++의 sort는 좀 더 빠른가 싶어 테스트해 봤다.
간단한 Win32 어플리케이션 하나 만들고 마우스 왼쪽, 오른쪽에 각각 qsort와 sort를 호출해 보았다. 1억번 반복한 후 경과 시간을 출력하는 방식이다.
int compare(const void* a, const void* b)
{
if (*(int *)a == *(int *)b) return 0;
if (*(int*)a > *(int*)b) return 1;
return -1;
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT iMessage, WPARAM wParam, LPARAM lParam)
{
HDC hdc;
PAINTSTRUCT ps;
int ar[] = { 5, 6, 10, 2, 20, 1, 12, 16, 3, 19, 4, 8, 18, 11, 17, 7, 13, 9, 15, 14};
int ar2[20];
DWORD st, ed;
TCHAR str[128];
switch (iMessage) {
case WM_CREATE:
hWndMain = hWnd;
return 0;
case WM_PAINT:
hdc = BeginPaint(hWnd, &ps);
EndPaint(hWnd, &ps);
return 0;
case WM_LBUTTONDOWN:
st = GetTickCount();
for (int i = 0; i < 100000000; i++) {
memcpy(ar2, ar, sizeof(ar));
sort(&ar2[0], &ar2[sizeof(ar) / sizeof(ar[0])]);
}
ed = GetTickCount();
wsprintf(str, TEXT("%d"), ed - st);
SetWindowText(hWnd, str);
return 0;
case WM_RBUTTONDOWN:
st = GetTickCount();
for (int i = 0; i < 100000000; i++) {
memcpy(ar2, ar, sizeof(ar));
qsort(&ar2[0], sizeof(ar)/sizeof(ar[0]), sizeof(int), compare);
}
ed = GetTickCount();
wsprintf(str, TEXT("%d"), ed - st);
SetWindowText(hWnd, str);
return 0;
case WM_DESTROY:
PostQuitMessage(0);
return 0;
}
return(DefWindowProc(hWnd, iMessage, wParam, lParam));
}
공정한 비교를 위해 20개의 무작위 난수 배열을 생성하고 매번 이걸 복사해서 다시 정렬한다. 기정렬 상태에 따라 알고리즘 실행 속도에 차이가 있고 16개 미만도 실행 방식이 달라지기 때문이다.
qsort는 개수를 지정하는데 비해 sort는 끝 위치를 지정하고 끝은 범위에서 제외됨을 유의해야 한다. STL은 항상 끝은 포함되지 않는다. 20개를 1억번 복사 및 정렬한 후 경과 시간을 측정했다.
qsort : 47.3초
sort : 4.6초
거의 10배 정도 차이가 난다. memcpy 호출이 있어 순수한 정렬 속도만은 아니지만 대충봐도 차이가 많음을 알 수 있다. 배열 크기가 바뀌면 달라질 수도 있어 크기를 5로 줄인 후 다시 측정해 봤다.
qsort : 5.75초
sort : 0.81초
대략 7배 차이난다. 어쨌거나 sort가 더 빠르다. qsort는 C 함수고 sort는 C++ 함수인데 예상과 달리 C 함수가 더 느리다. 그 이유는 다음과 같다.
- qsort는 비교를 위해 compare를 호출하여 함수 호출 오버헤드가 있다. sort는 less 또는 greater 함수 객체로 비교하는데 이 코드가 인라인 처리되어 오버헤더가 없다.
- qsort는 임의의 대상을 정렬하기 위해 비교 함수로 void * 주소를 넘긴다. 비교 함수는 이걸 다시 대상의 타입으로 캐스팅한 후 비교하니 느리다. sort는 템플릿 기반이어서 타입이 이미 정해져 있으며 정수는 값 자체를 바로 비교한다.
퀵소트가 빠른 알고리즘인 건 맞지만 요소의 배열 상태나 크기 등에 영향을 받아 최악의 경우는 효율이 심하게 떨어진다. sort는 삽입, 힙, 퀵 세 가지 알고리즘을 개수와 상황에 따라 조합해서 적용한 introsort 알고리즘을 사용한다. 16개 이하면 삽입 정렬을 쓰고 그 이상이면 퀵이나 힙을 쓰도록 되어 있어 빠르다.
혹시나 해서 직접 삽입 정렬 알고리즘을 인라인으로 구현해 봤는데 sort 함수와 속도가 거의 비슷하다. sort는 개수가 작으면 삽입 정렬을 쓰도록 되어 있어 20개 정도면 차이가 없는 편이다. qsort는 단순해 보여도 비교 함수를 호출하는 불이익이 있어 그다지 효율적이지는 않다. 앞으로 정렬은 sort로 실행하도록 하자.
개발자의 천국 SoEn
|
|
