복잡도(Big O) 줄이기 | 성능개선하는 방법들(mallloc()의 단점, std::move(), Sanity check, 배열복사, 증감연산자, call-by-value) | 좋은 코드란 무엇일까

 

좋은 코드란?

• 성능, 안전함, 에러찾기쉬운, 관리쉬운, 중복x
• 시간복잡도와 공간복잡도 고려하기.

 

 

 

Big O 예시)

O( 2*(n+1) ) becomes O(n)

O( n^3+n^2+1 ) becomes O(n^3)

영향 적게 주는건(차수가 낮은 항) 그냥 제외하면 됨.

 

Big O 계산 예시)

아래와 같이 함수 호출을 하는 코드가 있다고 가정

int f(int n)
{
	if (n <= 1)
    {
    	return 1;
    }
    return f(n-1) + f(n-1);
}

f(n)-> f(n-1) +f(n-1)

-> f(n-2) + f(n-2) + f(n-2) + f(n-2)

-> f(n-3) + f(n-3)+ f(n-3)+ f(n-3)+ f(n-3)+ f(n-3)+ f(n-3)+ f(n-3)

-> . . .

1, 2, 4, 8, ... 2^n 

-> 2^(n+1)-1 

->O(2^n) 이 된다.

 

성능 개선 방법들

1. call-by-value

local stack에 들어감. C에서는 이 함수를 호출한 녀석에게 복사를 시켜서 속도가 느려질 수 있음.

 

2. strcpy vs strncpy

strcpy는 null이 있을때까지 복사동작을 하는데, 만약 null이 없다면 오류를 일으킬수있다.

따라서 따로 개수를 지정해서, 지정된 개수 내에서 null자가 있을때까지 동작을 하도록하여 오류를 피하는 strncpy를 사용. +)strncat

 

3. 배열 복사할 때- memset, memcpy 사용

배열 복사에서, for문을 돌려 복사하는것보다

memset, memcpy를 사용하는것이 속도를 훨씬 줄일 수 있다.

 

예시)

-memset( array, size, 0)  //메모리블록을 0으로 채울 때

-memcpy(array1, array2, size)  //한 배열을 다른 배열로 복사

 

4. malloc()

malloc은 운영체제에 요구 -> 할당된 메모리의 첫주소값이 return.

mem=malloc

if (mem){

   . . . error가 발생할 때의 코드

}

 

           -> malloc이 return 되는 데에 오랜시간이 걸릴 수도 있음.

너무 많이 사용 시 시간 복잡도가 매우 안 좋아지겠다.

 

5. for-loop에서 증감연산자

우리가 흔히 쓰는 for-loop 에서도

for (int i=0; i<SIZE; i++)
{
	...
}

위보다

 

for (int i=0; i<SIZE; ++i)
{
	...
}

로 쓰는것을 추천함.

Debug모드에서 후위연산자의 경우 임시객체를 만들어 리턴함. 따라서 전위연산보다 느리다.

그러나 release 모드에서는 컴파일러가 더 효율적인 코드로 최적화를 해주기때문에 성능이 동일함

 

6. std::move()

vector<int> ar = { 1,2,3,4 ...} ;


	for (vector<int>::iterator it = ar.begin(); it != ar.end(); ++it)
	{
		//1.sum = sum + *it;
		//2.sum += *it;
		//3.sum = std::move(sum) + *it;
		
	}

 

std::move()는 STL에서 제공하는 함수다. 어떤것을 move시켜주는 함수가 아니다.

sum이 금방 변경되는 녀석이라는걸 컴파일러에 알려주는 함수이다.

위의 1,2,3방법 중에 3번째 방법이 가장 최적의 성능이다.

 

7. Sanity check

첫번째방법)

정상적으로 돌아가는지, 입력값이 맞는지 체크하는걸 함수 첫부분에 넣도록함.

const bool DEBUG = true;
if (DEBUG) if (잘못된동작) return ;

 

만약, 동작 상 배열 a와 b의 메모리공간이 같아야한다면? 두 메모리공간이 같지 않다면 유망하지않으며, 아래 코드들을 실행할 필요가 없어진다면?

const bool DEBUG=ture;
if (DEBUG) if (a.size() != b.size() ) return;

위와 같이 써줄 수 있다.

 

 

두번째 방법)

#define NDEBUG  //이녀석이 먼저 선언되어야함
#include <assert.h> //C에서는 assert.h를, C++에서는 cassert 
assert() //true인 조건을 ()안에 넣기. 안에 있는 조건이 틀리면 중지됨

예) 사람 키를 0~500cm까지를 유망하다고 보고, assert( 0 < height && height < 500) 으로 쓸 수 있음.

시스템이 assert를 지원한다면 두번째 방법을 쓰고, 지원 안 한다면 첫번째 방법을 쓰면 됨.