알고리즘 문제풀이 시간 단축을 위한 팁 (2)

photo by Christopher Gower on Unplash

 

1편에 이어서 몇 가지 더 써 보고자 한다.

 

Cache를 고려하자

이 내용은 너무 기본적인 내용이라 넣을까 말까 고민을 했는데, 의외로 모르는 사람들이 많은듯해서 한 번 더 상기하고자 작성한다.

 

기본적으로 컴퓨터는 하나의 값을 읽어올 때 딱 그 변수를 읽어오는 것이 아니라. 주변에 있는 값을 포함해서 한 블록을 통째로 준비시킨다. 왜냐하면 통상적으로 주변에 있는 값들을 연속적으로 읽을 확률이 높기 때문이다.

 

따라서 연속해서 사용할 값은 쓴다면 연속한 위치에 있는 게 좋다.

// 1000x1000 array 요소의 총 합을 반환 해주는 함수
void badSum(int a[1000][1000])
{
	int sum = 0;
	for(int x = 0 ;x < 1000 ; x++)
		for(int y = 0 ; y < 1000; y++)
			sum += a[y][x];	// 매번 cache miss가 발생할 확률이 높다.
	return sum;
}

void goodSum(int a[1000][1000])
{
	int sum = 0;
	for(int y = 0 ;y < 1000 ; y++)
		for(int x = 0 ; x < 1000; x++)
			sum += a[y][x];	// 근접한 메모리순으로 접근함으로써 위 badSum 함수보다 빠르다.
	return sum;
}

 

낮은 N에서는 N^2이 NlogN보다 빠를 수도 있다.

낮은 시간 복잡도를 가졌지만 내부에 구현량이 많다면 낮은 N^2이 NlogN보다 더 빠를 수도 있다.

 

N이 16일 때 아래와 같다.(log는 밑을 2로 한다.)

N^2 = 256 / NlogN = 64 

그런데 만약 NlogN의 각 스테이지에서 연산량이 5배 이상 많다면?

N^2 > NlogN * 5로  N^2 알고리즘이 더 빨라진다.

 

아래 예를 보자.

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

void makeNums(int* arr, int N){
	for (int i = 0; i < N; i++)
		arr[i] = rand();
}

void SelectionSort(int* arr, int left, int right)
{
	for (int i = left; i <= right; i++)
	{
		int min = arr[i];
		int minIndex = i;
		for (int j = i + 1; j <= right; j++)
		{
			if (arr[j] < min)
			{
				min = arr[j];
				minIndex = j;
			}
		}
		int buf = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = buf;
	}
}

int buf[1000];
void MergeSort(int* arr, int left, int right)
{
	if (left >= right)	return;

	int bp = left, lp = left;
	int mid = left + (right - left) / 2;
	int rp = mid + 1;

	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	while (lp <= mid && rp <= right)
	{
		if (arr[lp] < arr[rp])	buf[bp++] = arr[lp++];
		else					buf[bp++] = arr[rp++];
	}
	while (lp <= mid)	buf[bp++] = arr[lp++];
	while (rp <= right)	buf[bp++] = arr[rp++];

	for (bp = left; bp <= right; bp++)
		arr[bp] = buf[bp];

}

int main()
{
	int arr[1000];
	int elapseSelect, elapseMerge;
	clock_t start;
	clock_t end = clock();
	for (int i = 1; i < 100; i++)
	{	
		// i개의 인티저를 Selection sort(N^2) * 10000번 반복
		start = clock();
		for (int j = 0; j < 10000; j++)
		{
			makeNums(arr, i);
			SelectionSort(arr, 0, i - 1);
		}
		end = clock();
		elapseSelect = end - start;

		// i개의 인티저를 Merge sort(NlogN) * 10000번 반복
		start = clock();
		for (int j = 0; j < 10000; j++)
		{
			makeNums(arr, i);
			MergeSort(arr, 0, i - 1);
		}
		end = clock();
		elapseMerge = end - start;

		printf("For %d nums : selection %d ms / merge %d ms elapsed\n", i, elapseSelect, elapseMerge);
	}
    return 0;
}

 

1개부터 100개까지의 숫자를 각각 만 번씩 Selection Sort(N^2), Merge Sort(NlogN)으로 정렬한 뒤 시간을 비교한 것이다. 결과는 다음과 같다.

 

/*
...
For 48 nums : selection 60 ms / merge 59 ms elapsed
For 49 nums : selection 60 ms / merge 60 ms elapsed
For 50 nums : selection 63 ms / merge 65 ms elapsed
For 51 nums : selection 68 ms / merge 66 ms elapsed
For 52 nums : selection 70 ms / merge 66 ms elapsed
For 53 nums : selection 72 ms / merge 72 ms elapsed
...
*/

1~50개의 숫자를 정렬할 때는 Selection sort가 더 빠르다.

카라 추바 곱셈(N^log3) 같은 알고리즘은 한 스테이지당 연산량이 매우 많은데 이런 알고리즘의 경우에는 N이 200~1000 이하일 때는 일반 곱셈(N^2)이 더 빠르다고 한다.

N의 개수가 일정하지 않은 이유는 서버의 사양에 따라 다르기 때문에 테스를 통해 어떤 N이 최적인지 알아보아야 한다.

 

그럼 위와 같은 교훈을 얻었으니 새로운 소팅을 짜 보자. Selection Sort와 Merge Sort를 혼합하는 것이다.(NewMergeSort라고 명명하겠다)

void NewMergeSort(int* arr, int left, int right)
{
	if (left + 50 >= right) // 변경된 if문
	{
		SelectionSort(arr, left,right); // 추가된 부분
		return;
	}

	int bp = left, lp = left;
	int mid = left + (right - left) / 2;
	int rp = mid + 1;

	NewMergeSort(arr, left, mid);
	NewMergeSort(arr, mid + 1, right);
	while (lp <= mid && rp <= right)
	{
		if (arr[lp] < arr[rp])	buf[bp++] = arr[lp++];
		else					buf[bp++] = arr[rp++];
	}
	while (lp <= mid)	buf[bp++] = arr[lp++];
	while (rp <= right)	buf[bp++] = arr[rp++];

	for (bp = left; bp <= right; bp++)
		arr[bp] = buf[bp];

}

Sorting 알고리즘과 같이 간단한 곳에서는 굳이 혼합할 필요는 없다. 다만 복잡한 알고리즘에서는 혼합하는 것을 고려해 보는 것도 좋다.

 

값 복사 최소화

값을 복사하면 복사할수록 시간은 더 많이 걸린다는 것은 자명한 사실이다. 따라서 값을 복사할 필요가 없다면 굳이 할 필요가 없다. 참조자나 포인터를 활용하면 값 복사를 위한 오버헤드를 줄일 수 있다.

특히 이 방법은 재귀 함수에서 빛을 발한다.

// 벡터 v에 대한 값 복사가 depth번 이루어진다.
int sumVectorRecursive(vector<int> v, int depth)
{
	if(depth >= v.size()) return 0;
    return v[depth] + sumVectorRecursive(v, depth + 1);
}


// 참조자(&)를 이용하여 값 복사를 방지
// const 키워드를 이용하여 값 오염 방지
int sumVectorRecursive(const vector<int>& v, int depth)
{
	if(depth >= v.size()) return 0;
    return v[depth] + sumVectorRecursive(v, depth + 1);
}

위 함수를 아래와 같이 개선하면 depth * v.size() 만큼의 값 복사가 일어나는 것을 방지 할 수 있다.

 

 

2편은 여기까지. 생각해보고 더 쓸 거리가 있으면 3편에 이어서.

나름 오래걸려서 썼는데, 쓰고보니 엄청 짧고 세가지 밖에 없다.