Insertionsort가 장착된 Quicksort(Recursive/Nonrecursive)에서 random원소가 1000개일때 가장 좋은 성능을 갖는 'M'값 구하기.
- 알고리즘 개론 -
김진홍 (964524)
결과:
Recursive Quicksort: M = 15
Nonrecursive Quicksort: M = 26
측정방법:
가장 좋은 M값을 구하기 위해서는 Quicksort(이하 Qsort)의 처리 속도를 정밀하게 검사할 수 있어야 한다. 하지만 Qsort의 average case에서의 진행 속도가 워낙 빨라서 1000개의 원소만으로는 시스템의 100분의 1초 타이머로써도 측정할 수 없다. 그래서 시간이 좀 걸리지만, 1000개의 원소를 2000번 Qsort하도록 하여 경과시간을 2000으로 나눔으로써 Qsort를 1번 실행할때의 시간을 알아내었다. 하지만 매번 Qsort하기전에 1000개의 모든 원소가 다시 난분포되어 있어야 average case가 보장이 되므로 매번 1000개의 원소를 재구성하게 되는데, 그렇기 때문에 2000으로 나누어 나오는 그 경과시간은 사실 1000개의 원소를 재구성 하는 시간과 Qsort하는 시간이 합쳐진 것이다. 난 Qsort만의 실행시간을 알고 싶었기 때문에, 1000개의 원소를 2000번 재구성하는 과정을 따로 측정하여 나온 시간을, Qsort를 2000번 처리하고 나온 시간에서 빼고 2000으로 나눔으로써 Qsort를 단 한번 실행했때의 속도를 어느정도 정밀하게 측정할 수 있었다.
측정시에 사용한 타이머로써 system이 매번 약 초당 18.2번 카운트를 하고 있는 데이타 영역을 직접 accessing함으로써 간편하게 경과시간을 측정할 수 있었다. 경과 시간을 측정하는 방법은 Qsort를 시작하기전에 그 데이타 영역의 수치를 읽고, Qsort가 끝나고 나서 바로 다시 읽은 다음에 그 두 값의 차이를 18.2로 나누면 경과 시간을 초시간으로 얻을 수 있다. 초당 비록 18.2번 카운트 하기 때문에 아주 정밀하진 않지만, 얻어진 그 두 값의 차이를 18.2로 나누면 상대적인 시간을 비교적 정밀하게 소수점까지 알아낼 수 있다.
먼저 결과를 보자:
주의:
아래 결과는 실제 output에서 마지막 부분에 해당. 실제 output은 느리며 또한 출력물이 길다.
또 아래 측정 결과는 필자 PC에서의 결과이므로 타 기종에서는 다를 수 있다. 하지만 최적의
M값이 변하는 일은 없다.
* Recursive Qsort일때 M을 2부터 41까지 측정함. 단위는 초.
[2] 0.002335 [3] 0.002170 [4] 0.002033 [5] 0.001978 [6] 0.001923 [7] 0.001896 [8] 0.001841
[9] 0.001841 [10] 0.001813 [11] 0.001813 [12] 0.001786 [13] 0.001786 [14] 0.001786
[15] 0.001786 [16] 0.001786 [17] 0.001786 [18] 0.001786 [19] 0.001813 [20] 0.001813
[21] 0.001813 [22] 0.001841 [23] 0.001841 [24] 0.001841 [25] 0.001868 [26] 0.001896
[27] 0.001896 [28] 0.001896 [29] 0.001923 [30] 0.001923 [31] 0.001951 [32] 0.001978
[33] 0.001978 [34] 0.002005 [35] 0.002033 [36] 0.002033 [37] 0.002060 [38] 0.002060
[39] 0.002088 [40] 0.002115 [41] 0.002143
위 결과에서 Qsort의 성능이 가장 좋아질 때가 M값이 12일 때부터 18까지 이다. 위 실험을 몇번에 걸쳐서 해 본 결과, 일반적으로 M이 12부터 18까지에서 상대적으로 최적의 성능을 보여 주었다. 그러므로 최적의 M값은 12과 18사이의 중간인 15라고 할 수 있다. (M값을 2부터 10단위로 점프해 검사해본 결과 M이 18이후로 계속해서 느려지는것을 알 수 있었으므로 M값을 41까지만 측정하였다.)
* Nonrecursive Qsort일때 M을 2부터 41까지 측정함. 단위는 초.
[2] 0.003077 [3] 0.002885 [4] 0.002747 [5] 0.002637 [6] 0.002555 [7] 0.002473 [8] 0.002390
[9] 0.002363 [10] 0.002308 [11] 0.002280 [12] 0.002225 [13] 0.002198 [14] 0.002198
[15] 0.002170 [16] 0.002143 [17] 0.002143 [18] 0.002115 [19] 0.002115 [20] 0.002115
[21] 0.002088 [22] 0.002088 [23] 0.002088 [24] 0.002088 [25] 0.002088 [26] 0.002088
[27] 0.002088 [28] 0.002088 [29] 0.002088 [30] 0.002088 [31] 0.002088 [32] 0.002115
[33] 0.002088 [34] 0.002115 [35] 0.002115 [36] 0.002115 [37] 0.002143 [38] 0.002143
[39] 0.002143 [40] 0.002170 [41] 0.002170
Nonrecursive일때는 Recursive일때보다 조금 더 복잡한 절차를 거치게 되므로 결과적으로 Recursive였을때 보다 느리다. 여기서는 M의 값이 Recursive에서 보다 뒤쳐져 21일 때부터 Qsort의 성능이 최적을 나타내기 시작하였고 31까지 계속 최고의 상태를 유지했다. 그 이후로의 M값에서는 결과적으로 점차 성능이 저하되기 시작하였다. 위 결과에서 M이 32에서 성능이 떨어지다가 33에서 다시 최적의 성능을 보이고 그 이후로 계속 성능이 저하되었는데, 33에서 잠시 성능이 좋아진 이유는 random원소가 일시적으로 그 구조에 좋도록 배열이 되었던것이라고 생각한다. Recursive에서 보다 최적의 M값이 뒤늦게 나온 이유는 Recursive에 비해 조금 복잡한 구조를 가져서 상대적으로 느린 Nonrecursive Qsort의 성능을 M값에서의 Insertionsort가 점차 보상하다가 결국 M이 21까지 가서야 Plus성능을 보였던 것이라고 생각된다. 최적의 M은 21과 31사이의 중간 값인 26이다.
* 아래 소스는 실제 Recursive/Nonrecursive Qsort를 구현한 것이다.
* 아래 프로그램은 현재 Recursive Qsort로 돌아가도록 되어있다. 그 Qsort를 호출하는 부분이 !!!!!!!!!!!!! 라고 주석이 되어있는 부분에 있는데, 그 밑에 Nonrecursive Qsort인 nrquicksort()가 주석문으로 만들어져 있다. 이 프로그램을 Nonrecursive Qsort로 돌아가게 하기 위해서는 Recursive Qsort인 quicksort()를 주석문으로 만들고, 주석문으로 되어 있는 nrquicksort()를 풀면 된다.
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <malloc.h>
void split(int *, int, int, int *);
void quicksort(int *, int, int);
void nrquicksort(int *, int, int);
void starttime(void);
float endtime(void);
void inssort(int *, int, int);
int pop(int *, int *);
void push(int, int);
#define TN 2000 /* 1000개의 원소를 반복해 계산할 횟수 */
#define N 1000 /* 원소의 수 */
#define TM 40 /* M의 값을 40회에 거쳐 검사한다. 2부터 41까지. */
int M = 2; /* 초기 M값 */
unsigned long far *tick=(unsigned long far *)0x0040006c; /* 타이머 카운트 데이타 영역 */
unsigned long st;
int insc=1;
int spc=1;
struct GoodM { /* 최적의 M값중 첫번째 것을 찾기 위해 사용할 구조 */
int M;
float T;
} GM[TM], TEMP;
struct list { /* Stack을 구현하기 위한 linked-list 구조 */
struct list *parent;
int d1, d2;
} *ind=NULL;
void main()
{
int arr[N];
float t1, t2;
int t, l, tl=0, sc=1, midx=0;
long t_spc=0, t_insc=0;
srand(*tick%0xffff); /* 난수 초기값을 다양하게 선택하기 위해... */
printf("Wait for 3secs to pass the background disk-writing by cacher...\n");
delay(3000); /* 프로그램이 작동하는 도중에 캐쉬가 backgroundwriting을
하게 되면 수행 속도를 측정하는데 지장이 생기므로
3초를 기다림. */
/* Estimate the time that take to make 1000000 random integer */
printf("Check randomizing time...\n");
starttime();
for (l=0; l<TN; l++)
for (t=0; t<N; t++) arr[t]=random(0xffff);
t1=endtime();
printf("Randomizing 1000x1000 ints took for %.3fsec!\n", t1);
printf("START... FROM M=2 TO 41\n");
while (tl < TM) {
starttime();
for (l=0; l<TN; l++) {
for (t=0; t<N; t++) arr[t]=random(0xffff);
/* !!!!!!!!!!!!!!!!!!!!!!! */
quicksort(arr, 0, N-1);
/* nrquicksort(arr, 0, N-1); */
t_spc+=spc;
t_insc+=insc;
spc=1;
insc=1;
}
t2=endtime();
printf("==================================================================[%03d]\n", sc++);
printf("The QSort took for <%.6f>sec for M = %d to be done.\n",(t2-t1)/TN, M);
printf("SPLIT-CALL AVR: %.1f, INSSORT-CALL AVR: %.1f\n", (float)t_spc/TN, (float)t_insc/TN);
GM[midx].M=M;
GM[midx].T=t2-t1;
t_spc=t_insc=0;
midx++;
M++;
tl++;
}
/* Find a M which has the smallest elaspsed time */
TEMP.T=GM[0].T;
for (t=1; t<midx; t++)
if (GM[t].T < TEMP.T) {
TEMP.T=GM[t].T;
TEMP.M=GM[t].M;
}
printf("\n");
for (t=0; t<TM; t++)
printf("[%d] %.6f\n", GM[t].M, GM[t].T/TN);
printf("\n\nTHE M WHICH HAS GOOD PERFORMANCE IS %d / %.6f\n", TEMP.M, TEMP.T/TN);
}
void starttime()
{
static unsigned long s;
/* timetick synchronizing */
s=*tick+10;
while (*tick < s);
/* save timetick */
st=*tick;
}
float endtime()
{
return (float)(labs(*tick-st)/18.2);
}
void inssort(int *arr, int left, int right) /* 삽입정렬 */
{
int t, i, tmp;
insc++;
for (t=left+1; t<=right; t++) {
tmp=arr[t];
for (i=t-1; i>=left && arr[i] > tmp; i--)
arr[i+1]=arr[i];
arr[i+1]=tmp;
}
}
void split(int *arr, int left, int right, int *sp)
{
int l=left, r=right+1, key;
int tmp;
if (left < right) {
spc++;
key=arr[left];
while(1) {
do l++; while (arr[l] < key);
do r--; while (arr[r] > key);
if (l < r) {
tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
} else break;
}
tmp=arr[left];
arr[left]=arr[r];
arr[r]=tmp;
}
*sp=r;
}
void quicksort(int *arr, int left, int right)
{
int sp;
if (right - left > M) {
if (left < right) {
split(arr, left, right, &sp);
quicksort(arr, left, sp-1);
quicksort(arr, sp+1, right);
}
} else inssort(arr, left, right);
}
void push(int d1, int d2)
{
struct list *entry;
entry=(struct list *)malloc(sizeof(*ind));
if (entry == NULL) {
printf("Not enough memory!\n");
exit(1);
}
entry->d1=d1;
entry->d2=d2;
entry->parent=ind;
ind=entry;
}
int pop(int *d1, int *d2)
{
struct list *entry;
if (ind == NULL) return 1;
*d1=ind->d1;
*d2=ind->d2;
entry=ind;
ind=ind->parent;
free(entry);
return 0;
}
void nrquicksort(int *arr, int left, int right)
{
int sp;
push(left, right);
while (!pop(&left, &right))
if (right - left > M) {
while (left < right) {
split(arr, left, right, &sp);
push(sp+1, right);
right=sp-1;
}
} else inssort(arr, left, right);
}