http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#C


c언어 코드를 보자.


#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
 
int main(int c, char **v)
{
while (--c > 1 && !fork());
sleep(c = atoi(v[c]));
printf("%d\n", c);
wait(0);
return 0;
}


갱장히 스트렌지하다.


살짝 고민해보면 부랄을 탁치게된다.


손오공이 숫자 카드 뭉치를 받고 분신술을 써서 가진 카드의 숫자만큼 잠을 주무시다가 일어나면서


자신의 카드를 외치는 그런 sort 알고리즘이 되시겠다. 갱장히 신박하다. 하지만 잘 돌아갈까?


하지만 이게 잘 돌아갈리가 없다는걸 느끼지. os의 스케줄러는 바쁘시다. 그외에 너무 변수가 많다.


얼마나 큰 array만큼 제대로 sort할 수 있을지 테스트해보자. 


집에 리눅스가 안 깔려있어서 왠지 c코드는 잘 컴파일이 안될것 같다. gcc면 다 fork를 지원해주던가? 졸업한지 오래되서 가물가물하다.


씹고 보고 뜯기 좋은 c++ 코드를 보자


#include <iostream>
#include <thread>
#include <vector>
#include <unistd.h>
 
using namespace std;
 
void sortThread( int x )
{
usleep( 10000 * x );
cout << x << " ";
}
 
int main()
{
vector<thread*> threads;
 
srand( ( unsigned )time( NULL ) );
 
cout << "unsorted:" << endl;
for( int x = 0; x < 15; x++ )
{
int r = rand() % 20 + 5;
cout << r << " ";
thread* t = new thread( sortThread, r );
threads.push_back( t );
}
cout << endl << endl << "sorted:" << endl;
 
for( vector<thread*>::iterator t = threads.begin(); t != threads.end(); t++ )
{
( *t )->join();
delete ( *t );
}
 
cout << endl << endl;
return 0;
}


사실 저기 헤더 하나 첨가해야한다. 그래. 그건 넘어가고 돌려본다.


unsorted:

13 22 16 14 12 8 7 14 5 22 14 16 11 10 19


sorted:

5 7 8 10 11 12 13 14 14 14 16 16 19 22 22



Process returned 0 (0x0)   execution time : 0.232 s

Press any key to continue.


0.232s 꼴랑 15개짜리 sort하는데 시간이 너무 오래 걸린다. 22짜리가 22milisec를 살았어도 오래 걸린다.

그래 원래 효율은 고자인 알고리즘이다. 하지만 정상작동한다. 이정도면 ok.

100개를 돌려보자.

unsorted:

14 12 17 7 24 16 20 18 5 8 5 7 15 8 5 13 6 9 7 14 7 7 24 8 10 8 14 14 7 14 19 14

 17 17 18 6 7 11 11 22 11 19 23 6 24 8 21 24 18 20 19 12 17 5 16 6 18 14 8 24 13

 5 9 21 7 24 19 5 14 21 6 10 11 22 6 6 11 5 16 14 10 20 15 14 7 21 5 10 8 16 11

9 8 21 6 19 14 7 24 12


sorted:

5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 6 7 7 7 7 7 7 8 7 8 8 8 7 8 8 8 9 8 9 9 10 10

10 10 11 11 11 12 11 11 11 12 13 12 13 14 14 14 14 14 14 14 14 14 14 15 14 16 15

 16 16 17 16 17 17 17 18 18 18 18 19 19 19 19 20 19 20 20 21 21 21 21 21 22 22 2

3 24 24 24 24 24 24 24



Process returned 0 (0x0)   execution time : 0.258 s

Press any key to continue.


슬슬 삐꾸가 나기 시작한다. 쓰레드 100개가 이쁘게 돌아가기는 쉽지 않다. 그래도 큰 삐꾸없이 돌아간다.

나중에 thread를 생성할때 참고하도록 한다.

1000개 갑니다.

unsorted:
8 22 19 17 13 21 22 11 15 18 21 7 24 23 19 13 6 12 7 6 9 6 6 10 24 14 20 15 8 15
 14 8 15 14 24 8 10 13 20 9 24 21 23 8 6 5 18 21 23 20 24 10 18 22 22 5 11 14 11
 7 23 22 8 11 16 8 23 23 12 20 16 7 15 9 8 24 19 20 14 13 20 22 10 23 5 18 24 6
5 11 24 17 13 7 15 6 16 20 10 15 24 6 14 8 17 9 16 7 12 24 21 12 6 19 17 12 24 5
 24 8 13 5 17 6 18 5 6 24 10 19 7 16 18 15 22 19 18 14 15 8 12 22 9 7 24 18 17 1
9 22 19 22 17 12 18 12 22 19 20 5 14 19 16 8 18 17 20 12 11 13 11 17 20 8 5 21 1
5 8 23 6 10 13 24 22 7 22 8 7 24 24 13 11 5 10 15 7 8 6 20 16 14 11 8 14 11 8 17
 21 9 19 18 12 6 21 17 20 23 6 6 21 10 12 23 18 18 13 13 7 16 20 24 14 10 7 13 2
3 9 7 23 17 20 20 12 23 15 8 17 12 13 20 13 21 6 12 18 9 16 20 17 19 8 24 22 14
7 6 23 22 22 17 17 13 23 8 16 20 20 19 13 6 9 10 16 13 5 23 10 12 21 20 11 13 9
14 13 21 11 8 13 8 5 15 18 21 5 18 14 21 19 13 23 10 23 13 19 20 11 14 24 11 7 1
3 19 16 23 9 22 13 9 12 15 14 11 13 23 9 7 16 11 12 6 19 21 9 18 20 19 22 16 17
19 18 8 6 10 12 13 17 523  7 16 22 18 14 512  14 14 13 13 18 6 15 18 8 11 21 11
5 23 11 19 11 16 14 13 8 7 17 13 24 19 8 5 13 7 21 6 24 15 6 513  15 6 13 23 20
19 6 10 19 612  22 612  15 11 21 12 17 9 9 22 19 11 5 5 6 17 23 6 14 5 24 19 8 8
 11 11 15 18 21 9 7 21 21 17 7 8 15 18 15 22 19 21 8 16 10 9 5 67  518  13 13 23
 9 6 712  10 617  7 22 10 18 55 65   6 20 15 10 19 15 22 15 16 24 6 106  21 12 1
0 9 13 619  12 511  23 9 23 6 14 8 15 5 15 10 14 7 19 10 17 8 22 21 7 21 8 16 10
 6 13 14 13 6 23 23 23 17 15 24 23 8 12 10 78  22 8 14 12 18 7 15 13 15 16 824
18 89  7 11 6 24 6 8 11 22 22 19 22 14 819  6 13 8 14 18 66  716  13 22 8 5 5 14
 824  6 15 17 13 9 66 8 7  23 23 12 11 9 6 6 8 24 16 13 7 6 6 6 10 23 15 14 23 1
3 8 10 14 12 10 23 923  11 6 20 6 23 24 89  13 18 9 22 10 5 11 7 6 9 8 10 13 15
7 8 10 18 16 20 18 712  14 11 21 20 15 57 5 16  10 20 823  5 19 9 10 5 17 20 6 1
5 17 15 18 24 8 12 13 24 19 10 10 6 8 21 17 11 8 8 8 10 9 21 10 22 7 136  10 16
8 12 7 9 18 22 10 21 815  18 5 22 78 7 7  85  8 18 24 8 19 518  21 95  11 17 20
11 17 10 18 16 10 9 24 5 17 13 14 15 718  23 18 22 7 18 611  10 12 19 17 14 19 7
 22 6 22 17 17 19 12 9 8 21 6 6 8 19 10 17 11 18 8 24 1611 6 11  5 10 19 15 23 9
 7 7 24 12 5 12 8 23 24 14 16 116  713  12 23 8 7 9 6 12 8 14 11 13 21 19 5 7 5
20 10 21 9 8 13 21 19 19 17 7 1710  8 7 12 19 20 10 6 6 7 13 11 23 11 21 10 8 5
18 8 5 11 9 8 13 21 17 6 24 22 12 15 9 10 12 17 21 13 7 10 19 23 7 59 7 6  17 18
 6 18 13 8 11 5 16 11 19 6 7 12 13 5 6 23 12 24 21 21 5 98 13 8 12 12 6  21 23 1
1 12 22 24 9 16 516  9 12 10 6 19 687 11  5  11 18 6 14 87  12 11 6 15 8 21 14 8
 12 20 610 13 14 8 9 12  13 14 11 57  12 13 9 16 5 10 8 9 23 14 19 14 6 15 9 11
14 14 6 15 21 10 12 17 10 12 21 10 19 6 9 13 19 9 8 8 6 23 12 13 14 17 615  11 6
 12 5 8 5 6 8 10 13 14 22 6 15 6 12 9 9 20 20 9 12 6 6 6 7 6 16 13 22 1915 14 15
  15 24 6910 9  13 6  15 5 11 14 13 16 11 15 21 8 24 5 11 8 11 9 23 13 1414 5 9
 8 11 9 17 5 15 15 10 12 23 9 23 511 9  11 12 7 21 14 9 989 12  5 14  18 10 815
11 15 5 8  16 11 5 15 15 10 15 7 17 8 18 13 9 13 5 23 7 8 12 9 15 5 198  14 13 1
316 7 15 13 15  11 1411 11  16 5 12 11 9 16 10 13 17 11 13 17 5 14 16 10 20 20 5
 12 8 13 10 24 10 7 14 2310 13 12  16 9 15 24 1013 11 9 7 16 15  13 1810  8 13 2
0 12 1511 6  10 13 6 9 7 20 2015 10 13 12 11 5 13  14 9 11 22 16 7 10 18 14 610
13 13  23 19 5 9 5 15 16 8 10 5 1820 13  5 13 20 21 14 13 10 7 17 14 8 16 5 14 9
 9 12 12 75 17 12 5 8 17 9  13 19 618 13  11 17 24 11 21 20 13 18 16 14 15 13 20
 88 6 20 14 5  15 157  7 8 5 12 18 9 18 819 14 13 15 17 13  17 7 18 13 24 10 16
7 221214 17 5 13 19 13  521 17   6 18 10 14 10 9 13 718  17 11 17 16 8 1010 11 7
 12 10 6  16 8 9 12 8

sorted:
14 6 8 10 1818 10 6  18 14 14 17 6 15 18 11 17 10 14 19 13 12 7 8 18 16 9 13 15
18 710 12  11 20 6 10 16 10 20 16 5 11 19 8 9 20 13 8 14 11 19 15 19 12 20 17 13
 10 17 19 21 5 18 19 20 16 15 18 19 18 19 1315 5 9 17 21 12  20 8 5 6 13 17 11 1
6 17 21 9 15 6 5 8 6 16 16 21 13 20 5 12 14 13 13 14 10 15 15 16 914 15 19 13 8
5 820 22 18  22  11 13 5 20 12 14 10 15 20 11 8 15 15 13 17 13 21 17 12 10 14 14
 915 15 22 20  22 14 18 18 22 10 55 17 16  20 5 11 15 22 13 19 14 23 14 15 15 21
 12 7 18 16 19 17 18 13 9823 18 11  17 23 12 11 714 9 20   15 22 18 23 11 5 18 1
7 21 23 16 19 23 22 20 20 22 21 19 12 10 6 2212 5 19 13  24 22 12 15710 21 9 9 1
7 20 9 20 23 19   24 820 24 20 16 19  19 22 24 12 10 22 7 15 20 24 9 16 17 15 18
 9 18 9 12 19 11 24 19 20 16 915 15 18 14 24 13 9 21 13 11 24 17  19 24 18 19 12
 11 23 13 20 14 19 24 24 13 12 24 21 16 15 19 24 21 12 13 21 16 17 24 21 11 9 10
 19 23 14 8 23 7 22 15 14 10 22 18 9 13 21 20 22 18 19 11 12 12 24 16 24 18 19 2
4 11 9 11 23 19 21 12 8 23 15 8 23 17 13 17 16 10 22 21 17 20 23 12 23 22 21 10
18 8 9 19 23 22 18 19 24 18 16 13 21 21 915 23 23 21 14  16 1711 13 17 10 14 212
3 14   18 17 14 23 24 9 14 17 22 22 21 17 17 18 23 17 18 13 18 23 18 21 12 21 15
 22 19 18 24 1818  22 19 16 23 18 20 15 17 22 15 17 14 23 10 11 20 13 16 16 18 1
3 20 22 14 17 15 17 19 20 24 14 24 23 20 17 16 13 22 19 19 13 19 22 15 22 22 23
15 23 18 21 22 19 24 19 12 15 23 20 23 14 23 23 15 18 14 18 16 21 19 2415 15 22
21 19 13 19 19 17  15 16 21 17 18 14 21 23 23 19 24 23 23 14 15 16 14 23 23 19 2
3 13 22 24 20 20 24 21 15 22 19 22 24 17 23 15 24 16 16 21 22 21 19 14 21 24 17
22 22 19 19 15 21 15 21 15 20 16 21 17 18 23 24 24 21 21 19 18 21 24 2223  21 23
 24 16 23 20 20 16 21 18 21 23 22 24 19 18 24 24 23 17 23 17 23 21 24 18 19 21 1
8 20 20 22 18 23 22 18 24 20 24 19 20 23 20 20 20 20 23 20 20 23 23 21 24 23 24
21 22 21 23 23 24 22 24 24 24


Process returned 0 (0x0)   execution time : 0.444 s
Press any key to continue.

sorting은 나발이고 쓰레드도 1000개 못 만든다. 만약 c버전으로 했으면 더 난리가 났을꺼다.

사실 thead는 프로그램하면서 꼭 써야하는 것이기도 하지만 만악의 근원이기도 하지.

thread의 문제점중에 갯수가 많아지면 더 꼬인다는걸 다시 확인하는 정도의 테스트였다하겠다.