BLOG. 2won0

2차원 배열을 생성하고 배열 전체의 20%에만 임의의 수가 저장되게 만들어 보았다.

int** InputValue(int *valueCount) {
	int** arr;
	int i,j,rannum;
	int count = 0;

	arr = (int**)malloc(sizeof(int)*MAXSIZE);
	for(i=0;i<MAXSIZE;i++)
	{
		arr[i] = (int*)malloc(sizeof(int)*MAXSIZE);
	} // 2차원 배열 동적할당 선언

	srand(time(NULL));

	// <- 값 입력
	for(i=0;i<MAXSIZE;i++)
	{
		for(j=0;j<MAXSIZE;j++) 
		{
			// 전체 배열중 20%에만 원소를 저장시킨다.
			rannum = rand()%100;
			if(rannum<20) {
				arr[i][j] = (rand()%100)+1; // 값을 저장할 때는 1~100 범위의 숫자를 저장한다. 
				count++; // 값이 입력될때 마다 카운트를 1씩 증가시켜
						 // Sparse Matrix에 값이 몇개 저장되었는지 카운트 한다.
			}
			else
			{
				arr[i][j] = 0; // 나머지 배열의 원소에는 0을 저장한다.
			}

		}

	}
	// ->

	*valueCount = count; // 생성된 Value의 수를 참조를 통하여 저장한다.
	
	return arr;

}

main함수에서 

int **arr;

이라는 변수를 더블포인터 변수를 선언하고

arr = InputValue(&valueCount);

식으로 연결시켜 주었다. valueCount는 몇개의 값이 생성되었는지 알기 위한 변수로 메인에서 선언해주고 InputValue함수에

주소만 넘겨주었다.

배열 전체의 20%에만 값을 할당하기 위해 0~99 범위의 랜덤한 숫자를 생성하고 20보다 작을때만 값이 입력되게 만들었는데

이에 대한 검증은 따로 하도록 하겠다.

결론적으로 InputValue함수를 통해 생성된 2차원배열을 파일에 찍어보면 다음과 같이 제대로 생성됨을 볼 수 있었다.

이는 MAXSIZE를 15000으로 해서 15000 x 15000 사이즈의 2차원 배열이 생성되었을 때이다.

파일사이즈가 커서 메모장으로는 열리지도 않는다 ㅋㅋ

이제 생성된 2차원 배열을 희소행렬 표현방식으로 저장해 보았다.

typedef struct spsmt { int row; int col; int value; } spsmt; // 희소행렬 정보를 위한 구조체 ... ... ... spsmt* makeSpsMatrix(int valueSize, int** arrData) { spsmt *mt = (spsmt*)malloc(valueSize*sizeof(spsmt)); // valueSize만큼 구조체 배열의 메모리 동적 할당 int i,j; int mtCount = 1; // Matrix Count. index 0은 희소행렬 정보이기 때문에 1부터 시작한다. mt[0].row = MAXSIZE; mt[0].col = MAXSIZE; mt[0].value = valueSize; // 배열의 첫번째 값은 희소행렬에 대한 정보 입력 // 원본 데이터인 2차원 배열의 값을 비교해 보며 0이 아닐때, 즉 값이 있을때는 희소행렬 표현으로 바꿔준다. for(i=0;i<MAXSIZE;i++) { for(j=0;j<MAXSIZE;j++) { if(arrData[i][j] != 0) { mt[mtCount].row = i; // arrData의 행정보 mt[mtCount].col = j; // arrData의 열정보 mt[mtCount].value = arrData[i][j]; // arrData의 값 // 각각 정보를 저장한다. mtCount++; // 희소행렬 index를 1씩 증가시켜준다. } } } return mt; }

 

15000 x 15000 사이즈에 value가 45049011개인 희소행렬이 제대로 저장된 것을 확인 할 수 있었다.

 

 

 

2차원 배열과 희소행렬의 결과값을 비교해서 검증해 보면

 

 

 

Sparse Matrix, 희소행렬이란 행렬의 원소로 0이 많은 것을 의미한다.

즉 2차원 배열로 Matrix를 만들고, 원소들 중 0이 많이 있을 때 0을 위한 저장공간이 아깝기 때문에

이러한 메모리를 절약하기 위해 사용한다.

예를들어 다음과 같은 2차원 배열이 있다고 할 때

불필요하게 0을 저장하는 공간이 많아지기 때문에

다음과 같이 표현하는 것이다.

이는 구조체를 이용해서 배열을 만들어 주면 간단하게 1차원 배열로도 값을 표현해 낼 수 있다.

[0]번 인덱스에는 원래의 2차원 배열이 몇행 몇열로 이루어 져있고 값이 몇개인지가 저장되고,

[1]번 인덱스 부터 row값을 기준으로 0이 아닌 값들의 위치와 값이 저장된다.

마지막으로 Binary Search를 Recursive한 방식, 즉 재귀적인 방법으로 구현해 보았다.

메인함수는 Binary Search (2) 와 같으며 Recursive 함수만 추가적으로 작성하였다.

차이점이 있다면 return시에 함수를 다시 call 하게 되는 것인데, 함수의 인자로 mid 값을 이용하는 것이 중요한 것 같다.

예를들어 찾고자 하는 값이 중간값 (arr[mid]) 보다 크다면 head index로 mid+1을 넘겨주는것,

찾고자 하는 값이 중간값보다 작다면 tail index로 mid-1을 넘겨주는 것이다.

그리고 찾고자 하는 값이 중간값과 같다면 1을 리턴하면서 함수가 종료된다.

아... 하면서 매번 느끼지만 Recursive는 어려운것 같다...

어쨌든 이러한 방식으로 구현을 한 뒤 Iterative 함수를 사용했을때와 Recursive 함수를 사용했을때의 시간을 측정하고

비교해보았다.

6753 이라는 숫자를 검색하였을 때

먼저 Iterative한 방식에서는

3 microsec의 시간이 측정되었으며

Recursive한 방식에서는

역시 3 microsec의 시간이 측정되었다.

이는 속도상 큰 차이를 보이지 않음을 알 수 있었다.

하지만 내가 비교해본 숫자의 크기는 비교적 작은 단위이기 때문에 인터넷에서 검색을 좀 해보고 찾아봤는데

재귀함수는 보통 일정한 수행속도를 가지고, 반복문은 수행횟수에 따라서 수행속도가 길어질 수 있다고 한다.

그리고 궁금한점은 재귀함수를 사용하면 계속해서 함수가 STACK영역에 올라오게 될 텐데 메모리에 영향을 주는건 없을지...

이것도 좀 궁금증이 생기는것 같다.

그리고 무엇보다도 피부로 느끼는건 ㅋㅋ 재귀함수는 아직 어렵게 느껴진다...

하지만 이러한 과제를 하다보면 가끔은 재귀함수로 구현할때 더 쉽게 구현되는 것들이 있다. 예를들어서 Tree에서

Preorder, Postorder, Inorder 방식으로 Tree를 탐색하는 것이라던지... ㅋ 이런건 재귀함수가 더쉬운것 같다.

Tree에 대해서는 나중에 다시 포스팅 하도록 하겠다!

Binary Search (1) 에서 생성된 10,000개의 정수를 가지고 원하는 값을 찾아내는 함수를 구현하였다.

그리고 이 함수는 Iterative 방식, 즉 반복문을 통해 검색을 하는 방식으로 구현해 보았다.

함수 내에서 while문이 한번씩 돌 때 마다, 즉 비교를 한번씩 할 때마다 searchCnt를 1씩 증가시켜주고,

메인함수에서 넘겨받은 포인터 변수로 array의 head값과 tail값을 연산에 맞춰 변형 시켜가면서 연산을 해 주었다.

이렇게 구현한 함수를 이용하여 실제로 3930이라는 수를 검색해 보고 검색에 걸리는 시간을 측정해 보았다.

총 13번 비교과정을 통해 2 microsec가 소요되는 것을 확인할 수 있었다.

다음으로는 Recursive한 방법을 이용한 함수를 통해서 검색을 해보고 소요된 시간을 측정해 보도록 하겠다.

Binary Search 를 구현해 보겠다.

먼저 Binary Search란 

위의 그림처럼 배열의 중간값을 기준으로

찾고자 하는 값이 중간값보다 크면 기준의 오른쪽 배열을 선택, 찾고자 하는 값이 중간값보다 작으면 기준의 왼쪽 배열을 

선택해가며 원하는 숫자를 찾아내는 방법이다.

Binary Search에 대한 포스팅은

1. 사이즈가 10,000인 배열을 생성하고 배열에 겹치지 않는 랜덤한 숫자를 저장한 뒤 파일에 저장한다.

2. Binary Search를 Iterative한 방식으로 구현해 본다.

3. Binary Search를 Recursive한 방식으로 구현해 본 뒤 Iterative한 방식과 비교해 본다.

총 3개의 글로 나누어 포스팅 해 보겠다.

먼저 중복이 없이 오름차순으로 정렬된 10000개의 정수를 생성하여 data.txt 파일에 저장하였다.

처음에 랜덤하게 생성된 값을 기준으로 매번 이전값과 비교하여 이전값보다 클 경우에만 저장되는 방식으로 구현을 하려고

하였으나 이럴경우 처음 생성되는 기준값이 커질 수도 있고, 이전 값과 다음값의 차이가 엄청나게 클 수도 있는 문제점이 있었다.

따라서 간단하게 제일 첫번째 값은 무조건 1로 저장하고 이후 값부터는 이전값보다 최소 1에서 최대 3까지의 범위 내에서

플러스 되는 방식으로 10,000개의 정수를 생성해 보았다.

정수가 모두 생성된 뒤 data.txt 파일을 열어보면 10,000개의 정수가 오름차순으로 제대로 생성되어 있는 모습을 확인할 수 

있었다.

Insertion Sorting에 이어 이번에는 Selection Sorting의 시간을 측정해 보았다.

이번에도 마찬가지로 1,000,000개의 랜덤한 숫자를 생성한 뒤 Selection Sorting을 이용하여 정렬하고 시간을 측정해 보았다.

측정된 시간은 1772.119초, 약 29분 53초가 소요되었다.

역시 정렬되기 전 숫자들은 before.txt 파일에, 정렬된 후의 숫자들은 after.txt에 저장하고 제대로 정렬이 되었는지 또한 확인해 보았다.

제대로 정렬된 모습을 볼 수 있었다.

같은 1,000,000개의 숫자를 정렬 할 때 Insertion Sorting과 비교해 본다면 정렬해야 할 숫자의 양이 많아질 때는 

Selection Sorting이 비교적 느린 속도를 보여주었다.

그래프에서 보는 것 처럼 일정 범위내에서는 비슷한 속도를 보이지만 연산량이 많아질수록 Selection Sorting의 속도가

더 오래 걸리는 모습을 확인할 수 있었다.

소스코드