'분류 전체보기' 카테고리의 글 목록 (14 Page)

분류 전체보기

Insertion Sorting의 시간 측정 2012.07.16
Array의 메모리 할당시 정적할당과 동적할당 차이는 얼마나 될까? 2012.07.16
temp 변수를 사용하지 않는 Swap Function 2012.07.15

Insertion Sorting의 시간 측정

신쫄이후리스 2012. 7. 16. 13:27

2012. 7. 16. 13:27

삽입정렬, (Insertion Sorting)을 이용하여 1,000,000개의 랜덤한 숫자를 생성한 뒤 Insertion Sorting을 통해 정렬한뒤

시간을 측정해 보았다.

또한 정렬되기 전 랜덤하게 생성된 숫자들을 before.txt 라는 파일에 저장하고,

정렬이 완료된 숫자는 after.txt라는 파일에 저장하여 두 파일을 비교 해 보았다.

Sorting을 진행한 총 시간은 1059.978 sec 즉, 17분 6663초 정도가 소요 되었다.

before.txt파일과 after.txt 파일을 비교해 보면 정렬 또한 제대로 된 것을 확인 할 수 있다.

데이터의 양에 따른 Sorting 시간을 측정해 보았는데

일정 양을 넘어가면 Sorting 시간이 기하급수적으로 증가하는 모습을 볼 수 있었다.

다음 포스팅에는 Selection Sorting을 이용한 정렬 시간과 이에대한 결과로 Insertion Sorting과의 비교를 해 보도록 하겠다.

소스 코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define arrSize 500000

int main(void)
{
	//int arr[arrSize];
	
	int cnt=0, i=0;
	int temp, move_index;
	FILE *fp;
	FILE *fp_out;
	clock_t chktime;

// arrSize 만큼 메모리를 할당한다. (4byte integer 형 배열)
	int* arr = (int*)malloc(sizeof(int)*arrSize);
	if(arr==NULL)
	{
		printf("메모리 할당 실패\n");
		exit(1);
	}

srand(time(NULL));

fp = fopen("before.txt","w");
	fp_out = fopen("after.txt","w");

printf("0~%d 까지의 랜덤값 생성 시작 --- OK\n",arrSize);
	// 랜덤값 생성
	for(cnt=0;cnt<arrSize;cnt++)
	{
		arr[cnt] = rand()%arrSize+1; // 0~arrSize 범위의 랜덤값 생성후 배열에 저장
		fprintf(fp,"%d ",arr[cnt]); // 생성된 랜덤값을 파일에 생성
	} 
	// 랜덤값을 배열에 저장과 함께 파일에도 저장한다.
	
	printf("0~%d 까지의 랜덤값 파일 저장 --- OK\n",arrSize);

// Insertion Sort 사용

printf("Sorting 시작 --- OK\n");
	chktime = clock(); // 시작 시간 저장

for(i=1;i<arrSize;i++)
	{
		temp = arr[i];
		move_index=i-1;

while(move_index >= 0 && arr[move_index] > temp)
		{
			arr[move_index+1] = arr[move_index];
			move_index--;
		}
		arr[move_index+1] = temp;
	}

printf("Sorting 종료 --- OK\n");
	chktime = clock() - chktime; // 종료시간저장

// Sorting 이후의 값을 저장

for(cnt=0;cnt<arrSize;cnt++)
	{
		fprintf(fp_out,"%d ",arr[cnt]); // 생성된 랜덤값을 파일에 생성
	} 
	printf("Sorting 이후 값 저장 --- OK\n");
	printf("Sorting 수행시간 : %f\n",(double)chktime/CLOCKS_PER_SEC);

free(arr); // 할당되었던 메모리를 free 시킨다.
	
	fclose(fp);
	fclose(fp_out);
	// 파일을 close 시켜준다.

return 0;
}

저작자표시 비영리 변경금지

'Computer Science > 자료구조' 카테고리의 다른 글

Binary Search (2) - Iterative 방식으로 값 찾기 (0)	2012.07.17
Binary Search (1) - 동작 방식 (0)	2012.07.17
Selection Sorting의 시간 측정 (0)	2012.07.16
Array의 메모리 할당시 정적할당과 동적할당 차이는 얼마나 될까? (0)	2012.07.16
temp 변수를 사용하지 않는 Swap Function (0)	2012.07.15

Array의 메모리 할당시 정적할당과 동적할당 차이는 얼마나 될까?

신쫄이후리스 2012. 7. 16. 13:06

2012. 7. 16. 13:06

Array를 정적할당할때와 동적할당으로 할 때 최대한 만들 수 있는 사이즈는 얼마나 될 까? 실험을 해 보았다.

그전에 먼저 정적할당이란

와 같이 직접 코드 작성시에 메모리 사이즈를 할당해 주는 것이고, 이는 메모리의 STACK 영역에 compile time시 메모리가 할당된다.

동적할당이란

와 같이 흔히들 malloc, calloc으로 알고 있는 방법으로 메모리 사이즈를 할당해 주는 것으로 메모리의 HEAP 영역에 올라가며

running time에 메모리를 할당할 수 있다.
따라서 동적할당을 사용하면 프로그램을 동작하는 도중에 메모리의 사이즈를 유동적으로 조절할 수 있다.

본론으로 들어가서 두 방법으로 메모리를 최대한 생성할 수 있을만큼 생성해 보았다.

참고로, 실험을 한 컴퓨터의 RAM 사이즈는 8GB이다.

정적으로 생성을 했을 때에는 약 2,000,000개 정도의 Array를 생성할 수 있었고 이후에는 에러가 발생하였다.

동적할당을 이용했을 때에는 약 399,000,000개 정도의 Array를 생성 할 수 있었다.

동작 환경에 따라서 조금씩 변화가 있었고, 작은 단위까지 숫자를 바꾸어 가며 생성해 보지는 않았지만 위의 숫자만 봐도 할당할 수 있는 공간의 차이는 꽤 발생하는것을 확인할 수 있었다.

저작자표시 비영리 변경금지

'Computer Science > 자료구조' 카테고리의 다른 글

Binary Search (2) - Iterative 방식으로 값 찾기 (0)	2012.07.17
Binary Search (1) - 동작 방식 (0)	2012.07.17
Selection Sorting의 시간 측정 (0)	2012.07.16
Insertion Sorting의 시간 측정 (0)	2012.07.16
temp 변수를 사용하지 않는 Swap Function (0)	2012.07.15

temp 변수를 사용하지 않는 Swap Function

신쫄이후리스 2012. 7. 15. 02:56

2012. 7. 15. 02:56

보통의 Swap 함수를 구현한다고 하면 두개의 변수를 포인터로 받아와 함수 내에서 temp 변수를 사용하는게 일반적이다.

void swap(int *pa, int *pb) {
    int temp;
    temp = *pa;
    *pa = *pb;
    *pb = temp;
}

하지만 temp변수를 사용하지 않고 Swap 함수를 구현할 수도 있다.

void swap(int *pa, int *pb) {	// without temp
    *pa = *pa + *pb; // a의 값에 b를 더한다.
    *pb = *pa - *pb; // b에는 a에서 b를 뺀 값을 저장한다. (즉, 처음 a의 값이 된다.)
    *pa = *pa - *pb; // a에는 처음 a와 b가 더해진 값에서 b를 뺀다 (b는 바뀐 a값이 저장되어 있다.)
    // 결국 a에는 처음 b의 값이 저장된것처럼 된다. 
}

다음과 같이 구현하면 temp 변수를 사용하지 않은채로 Swap 함수를 구현할 수 있다.

이 두가지 방법에 차이가 있을지에 대해 측정해 보기 위해 Microsec 단위로 연산 시간을 비교해 보았다.

먼저 temp 변수를 사용하였을 때에는

보통 0~1 microsec 의 시간을 보였고,

temp변수를 사용하지 않았을 때에는

비슷한 시간을 보였다.

좀더 작은 단위로 측정해 본다면 다른 결과를 보일 수 도 있겠지만 보통 1 microsec 내에서 연산되는 결과를 확인할 수 있었다.

결론적으로 temp변수를 사용할때와 사용하지 않을 때의 차이는 시간적인 면에서는 별 차이를 나타내지 않고,

다만 temp 변수로 인한 integer 메모리 하나의 차이정도가 생기지 않을 까 라고 생각해 보았다.

저작자표시

'Computer Science > 자료구조' 카테고리의 다른 글

Binary Search (2) - Iterative 방식으로 값 찾기 (0)	2012.07.17
Binary Search (1) - 동작 방식 (0)	2012.07.17
Selection Sorting의 시간 측정 (0)	2012.07.16
Insertion Sorting의 시간 측정 (0)	2012.07.16
Array의 메모리 할당시 정적할당과 동적할당 차이는 얼마나 될까? (0)	2012.07.16

PREV 이전 1 ···11 12 13 14 NEXT 다음

BLOG. 2won0