지난번 포스트에 이은, 결과 분석과 결론, 부록입니다. 분포수세기 정렬에 대해서 행한 추가실험 결과도 포함됩니다.
사실 결과 분석은 모두 간단한 선형 회귀분석에 의존했는데, 지금 와서 보면 조금 아쉬운 부분이 있습니다.
가령 알고리즘별로 추정한 절편을 비교하여 초기비용(overhead)을 비교한다든가 하는 식의 분석이 이루어졌다면 더 좋았을 듯하네요.
다음 포스트에는 실험에 사용한 코드를 올리겠습니다.
덧: 지난번 포스트 올린 후에 학교에서 접속해서 익스플로러로 보니 주석처리가 안 되고 표의 테두리도 이상하게 나오더군요. MS 워드에서 그냥 붙여넣기했을 뿐인데 왜 파폭에선 제대로 보여주고 익스플로러에선 제대로 못 보여주는지 모르겠습니다. MS는 자사에서 만든 프로그램에 대한 지원을 어째서 이렇게 못하는 걸까요-_-? 왜 옛날에 MS 인텔리포인트 마우스도 XP에서 드라이버를 자동으로 잡아내지 못했었죠. 장치관리자에 알 수 없는 장치-_- 이 따위로 나오고-_- 아니 자기네 회사에서 만든 마우스를 왜 알 수 없냔 말입니다-_-
1. 결과 분석
그래프(x축은 log(n)이다)를 보면 배운 결과대로 나왔음을 알 수 있다. 각각의 알고리즘에 대해 회귀분석한 결과는 다음과 같다. 모든 실험 결과 및 분석 결과는 별도의 엑셀 파일에 더 자세히 들어있다.
1) 삽입 정렬
그래프에서 보이듯 평균적으로, 그리고 최악의 경우 n2의 성능을 보이며, 정렬이 된 자료에 대해서는 선형 성능을 보인다. 실제로 엑셀로 회귀분석을 해보면 각각의 경우의 회귀식에 잘 맞아떨어진다(well-fitted). 다음 표에서 오른쪽 3열은 각각 정렬이 안 된 상태, 정렬이 된 상태, 역순으로 정렬된 상태를 의미하고, 회귀식은 1행의 경우 y=mn + b, 2행의 경우 y=mn2 + b이다. R2가 1에 가까울수록 모형의 설명력이 강함을 의미한다.
|
n |
m |
88.5217 |
0.0060 |
178.0101 |
|
b |
9.3893 |
0.0001 |
18.8473 | |
|
R^2 |
0.9270 |
0.9980 |
0.9272 | |
|
n^2 |
m |
0.0014 |
0.0000 |
0.0029 |
|
b |
0.0000 |
0.0000 |
0.0000 | |
|
R^2 |
1.0000 |
0.9244 |
1.0000 |
2) 병합 정렬
그래프에서도 보이듯, 별도의 기억장치를 사용하기 때문에 다른 n·log(n) 정렬 알고리즘에 비해 성능이 떨어진다. 그런데 정렬이 된 상태, 역순으로 정렬된 상태에 비해 정렬이 되지 않았을 때의 성능이 약간 느리게 측정되는 일이 일어났다. 알고리즘상 성능은 분명 θ(n)=n·log(n)이고 코드 또한 그렇게 작성했으므로, 이는 런타임 최적화가 일어났기 때문이 아닐까 싶다(if ~ else 문에서 한쪽 선택으로만 계속 분기하기 때문). 결과적으로 다음 표에서 보이듯 정렬된 상태, 역순으로 정렬된 상태일 때에는 선형에 가까운 성능으로 회귀되었다. 회귀식은 1행이 y=mn + b, 3행은 y=m(n·log(n)) + b이다(이론적으로는 빨간색 칸의 값이 노란색 칸보다 작아야 하는데 실제로는 빨간색 칸이 더 크게 나왔다).
|
n |
m |
0.8346 |
0.6355 |
0.6488 |
|
b |
0.0090 |
0.0045 |
0.0041 | |
|
R^2 |
0.9992 |
0.9996 |
0.9997 | |
|
n*log(n) |
m |
0.0522 |
0.0397 |
0.0405 |
|
b |
0.0005 |
0.0004 |
0.0006 | |
|
R^2 |
0.9994 |
0.9994 |
0.9987 |
3) 힙 정렬
힙 정렬은 안정성은 없지만 입력자료의 상태와 무관하고 최악의 경우에도 O(n·log(n)) 성능을 보여주기 때문에 실제로 가장 범용성 있는 정렬 알고리즘이 아닐까 싶다. 그래프를 보면, 입력자료 상태와 무관하게 꿋꿋하게 병합 정렬과 개선된 퀵 정렬 사이에 위치하고 있다. 회귀분석 결과 특이사항은 없다.
|
n*log(n) |
m |
0.0375 |
0.0331 |
0.0318 |
|
b |
0.0004 |
0.0001 |
0.0001 | |
|
R^2 |
0.9994 |
0.9999 |
1.0000 |
4) 퀵 정렬
퀵 정렬은 입력자료가 이미 정렬이 되어있거나 역순으로 정렬이 되어 있을 경우 O(n2)의 느린 성능을 내게 된다. 따라서 피봇(pivot)을 꼽는 방법에 대해 많은 연구가 이루어졌는데, 먼저 교재의 의사 코드대로 가장 우측값을 피봇으로 삼는 간단한 퀵 정렬을 구현해보았다(한편 강의 노트는 가장 좌측값을 피봇으로 삼는다). 그래프에서 보이듯 아주 분명하게, 정렬된 상태와 역순 정렬된 상태일 경우에는 O(n2)의 성능을 보인다. 특히 3번째 그래프를 보면 역순 정렬된 상태일 때는 삽입 정렬보다도 느리다는 사실을 알 수 있다. 이는 재귀로 인한 함수와 스택 사용 비용 때문이리라 생각된다.
|
n^2 |
m |
0.0000 |
0.0043 |
0.0036 |
|
b |
0.0000 |
0.0000 |
0.0000 | |
|
R^2 |
0.9403 |
1.0000 |
1.0000 | |
|
n*log(n) |
m |
0.0191 |
16.7853 |
14.0371 |
|
b |
0.0001 |
1.5283 |
1.2818 | |
|
R^2 |
0.9999 |
0.9452 |
0.9449 |
5) 분포수세기 정렬
음이 아닌 정수에만 사용할 수 있는 정렬 알고리즘으로서, 예상대로 입력자료와 무관하게 O(n)의 성능을 보이긴 했으나 전체적으로 매우 느린 성능을 보였다. 이는 입력자료의 범위를 4000000이라는 큰 수로 정했기 때문에 별도의 기억장치를 할당하는 데에 무시못할 시간이 소요되었기 때문으로 보인다.
|
n |
m |
0.4484 |
0.4037 |
0.4031 |
|
b |
0.0098 |
0.0124 |
0.0133 | |
|
R^2 |
0.9967 |
0.9934 |
0.9925 |
이에 입력자료의 수와 입력자료의 범위를 변화해가며 별도로 추가 실험을 했다. 정렬이 안 된 상태에 한하여 다소 작은 범위로 축소 실험했는데, 역시 5회 반복 측정후 최대값과 최소값은 빼고 평균을 내어 분석했다. 다음 결과 표에서 행은 입력자료의 개수 n이고, 열은 입력자료의 범위 k이다.
|
n k |
256 |
1024 |
4096 |
16384 |
65536 |
|
256 |
8 |
0 |
40 |
200 |
1066.7 |
|
512 |
0 |
8 |
64 |
200 |
1069.3 |
|
1024 |
37.333 |
32 |
72 |
224 |
1101.3 |
|
2048 |
72 |
64 |
128 |
296 |
1168 |
|
4096 |
136 |
160 |
232 |
418.67 |
1296 |
|
8192 |
296 |
320 |
421.33 |
648 |
1546.7 |
|
16384 |
576 |
632 |
840 |
1133.3 |
2098.7 |
|
32768 |
1357.3 |
1392 |
1690.7 |
2208 |
3402.7 |
|
65536 |
3114.7 |
2837.3 |
3770.7 |
4498.7 |
9314.7 |
위의 표를 바탕으로 n을 고정했을 때 k에 따른, 그리고 k를 고정했을 때 n에 따른 실행시간의 변화를 그래프로 나타내면 각각 다음과 같다. 선형에 가까운 모습을 보이고 있고, 뒤의 회귀분석 결과도 이를 입증한다.
분포수세기 정렬1
분포수세기 정렬2
분포수세기 정렬은 θ(n+k)이므로 n+k에 대하여 회귀분석한 결과 다음 표와 같이 선형으로 잘 회귀되었다. 각각 n을 고정했을 때 k에 따른, 그리고 k를 고정했을 때 n에 따른 회귀분석 결과이다.
|
m |
0.047 |
0.0435 |
0.0564 |
0.0656 |
0.1197 |
|
b |
0.0014 |
0.0004 |
0.0012 |
0.0009 |
0.0102 |
|
R^2 |
0.994 |
0.9995 |
0.9967 |
0.9987 |
0.9521 |
|
m |
b |
R^2 |
|
0.0165 |
0.0006 |
0.9963 |
|
0.0164 |
0.0006 |
0.9961 |
|
0.0165 |
0.0006 |
0.9955 |
|
0.017 |
0.0004 |
0.9983 |
|
0.0176 |
0.0002 |
0.9994 |
|
0.0189 |
0.0005 |
0.998 |
|
0.0223 |
0.0018 |
0.9804 |
|
0.0302 |
0.0032 |