달력

2

« 2016/2 »

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
2016. 2. 27. 17:55

알고리듬 성능비교 - Selection Sort 공부하는 것2016. 2. 27. 17:55

회사에서 요구하는 자격조건을 만족시키기 위해서 알고리듬을 공부해야한다.

공부하는 것은 싫어하지는 않지만, 그동안 내가 개발에 필요한 알고리듬은 천재적인 어떤 사람들이 만들어 놓은 Library를 이용하는 된다고 생각해서, 만들어 놓을 것을 잘 파악해서 내가 필요한 곳에 적절하게 사용하면 된다라고 생각해 왔고, 이러한 나의 생각은 지금까지도 변함이 없다.

그런데, 대학 생활 이후로는 크게 관심을 가지지 않았었는데, 다시 되집어 가면서 보아야 하는 상황이 나에게 왔다. 

뭐, 그래도 즐기면서 하면되니까, 즐겁게 하련다.


아래의 코드는 "창의적 알고리듬"에 나오는 코드인데, 이를 조금 개선해 보았다.

코드는 다음과 같다. (코드는 짦기 때문에 따로 설명하지 않았다.)

[코드 1: 개선전]

#include "stdafx.h"

#include <stdlib.h>

#include <time.h>


int n, S[100000];


void print_array()

{

for (int i = 0; i < n; i++)

{

printf("%d ", S[i]);

}

printf("\n");

}


void swap(int ai, int bi)

{

int t = S[ai];

S[ai] = S[bi];

S[bi] = t;

}


void selection_sort(void)

{

for (int i = 0; i < n; i++)

{

for (int j = i + 1; j < n; j++)

{

if (S[i] > S[j])

{

swap(i, j);

}

}

}

}


void selection_sort(void)

{

int idx = 0;


for (int i = 0; i < n; i++)

{

idx = i;

for (int j = idx + 1; j < n; j++)

{

if (S[idx] > S[j])

{

idx = j;

}

}

swap(idx, i);

}

}


int main()

{

srand(time(NULL));

scanf("%d", &n);


for (int i = 0; i < n; i++)

{

S[i] = rand();

}


int start = clock();

selection_sort();


printf("result=%.3lf(sec)\n", (double)(clock() - start) / CLOCKS_PER_SEC);

    

print_array();

return 0;

}


아래 코드는 위 코드에서 swap함수를 호출하는 부분에서 비교 결과에 대한 array index값을 변수에 저장하여 swap()함수의 호출수를 줄였다. (아래 "코드 2"의 붉은 박스 부분 참조)

[코드 2: 개선후]

#include "stdafx.h"

#include <stdlib.h>

#include <time.h>


int n, S[100000];


void print_array()

{

for (int i = 0; i < n; i++)

{

printf("%d ", S[i]);

}

printf("\n");

}


void swap(int ai, int bi)

{

int t = S[ai];

S[ai] = S[bi];

S[bi] = t;

}



void selection_sort2(void)

{

int idx = 0;


for (int i = 0; i < n; i++)

{

idx = i;

for (int j = idx + 1; j < n; j++)

{

if (S[idx] > S[j])

{

idx = j;

}

}

swap(idx, i);

}

}


int main()

{

srand(time(NULL));

scanf("%d", &n);


for (int i = 0; i < n; i++)

{

S[i] = rand();

}


int start = clock();

selection_sort2();


printf("result=%.3lf(sec)\n", (double)(clock() - start) / CLOCKS_PER_SEC);

    

print_array();

return 0;

}

PC의 성능에 따라 다르겠지만, 코드를 실행하여, 100개에 대해서는 거의 같은 성능을 보이나, 1000개 이상에서는 성능차이가 보인다.

내 PC에서 1000개에 대해 소팅을 실행할 경우에, 
"[코드 1]"은 0.013초가 결렸고, "[코드 2]"는 0.002초로 걸린다. 약 6배정도 "[코드 2]"가 빠른 결과를 가져온다고 볼수 있다.

   


'공부하는 것' 카테고리의 다른 글

요즘 내가 공부하는 것  (1) 2019.06.07
Visual Studio Code 1.0 정식 Released  (2) 2016.04.16
Byte and Bit에 대해서...  (0) 2009.10.20
GRails 공부 자료들...  (0) 2009.10.04
Silverlight 3 Released  (0) 2009.07.11
:
Posted by 행복상자

최근에 AWS와 node.js를 이용하여, 프로젝트를 진행하고 있다.

이전에 Azure룰 개인적으로 이용하곤 했는데, AWS는 실제 개발과 운영의 업무가 나누어져 있어서 나는 누군가가 만들어준 인스턴스를 이용하기만 하였지, 직접 하나 하나 건들일 일이 없었다. 

그런데, 지난 1월 7일에 Amazon 한국 리젼이 오픈을 하게되면서, 나도 개인 계정을 만들어 인스턴스를 생성하고, 몇몇 기능들와 서비스들을 이용해 보고 있다. 

최근에는 S3에 파일을 업로드 하거나, 다운 받는 코드를 AWS Lambda를 이용해서 실행하도록 만들었는데, Lambda는 AWS의 S3로 새로운 파일을 올리거나 받을때, 이벤트에 따라 필요한 코드를 실행할 수 있도록 도와주는 기능인데, 따로 서버를 운영하지 않아도(돈을 아낄수 있어서 좋다.) 된다.


아래는 AWS S3로 mytest.txt라는 파이을 zlib를 이용하여 압축을 한후에, S3로 업로드하는 

코드이다.

var AWS = require('aws-sdk');

AWS.config.loadFromPath('./config.json');


var s3 = new AWS.S3({ region: 'ap-northeast-2' }); 

var fs = require('fs');

var zlib = require('zlib');


var body = fs.createReadStream('C:/mytest.txt').pipe(zlib.createGzip());

var s3obj = new AWS.S3({params: {Bucket: 'seoulbucket9999', Key: 'myKey.zip'}});

s3obj.upload({Body: body}).

  on('httpUploadProgress', function(event) { console.log(event); }).

  send(function(err, data) { console.log(err, data) });


간략하세 설명을 하면  첫줄의 'var AWS = require('aws-sdk');'는 aws-sdk 패키지를 npm을 이용해서 설치한 후에 실행할때 넣어주면 된다. 

명령은 다음과 같다.  (사용을 위해서는 윈도우와 리눅스 또는 맥에 node와 npm 패키지가 이미 설치 되어져 있어야 한다.)

npm install aws-sdk

그리고,  'AWS.config.loadFromPath('./config.json');' 는 S3에 필요한 Access-key와 secret key를 별도의 config파일에 저장해서 가져오는 기능이다. 


마지막으로 아래의 코드는 로컬에 있는 mytest.txt 파일을 zlib를 이용하여 압축해서 S3에 올리는 코드이다. 

var body = fs.createReadStream('C:/mytest.txt').pipe(zlib.createGzip());

var s3obj = new AWS.S3({params: {Bucket: 'seoulbucket9999', Key: 'myKey.zip'}});

s3obj.upload({Body: body}).

  on('httpUploadProgress', function(event) { console.log(event); }).

  send(function(err, data) { console.log(err, data) });


:
Posted by 행복상자