[21일차] 임베디드 자료구조 및 알고리즘 (유클리드, 소수판별 알고리즘)

이번 주 부터 자료구조 및 알고리즘에 대해 배운다. 오늘 배운 내용은 크게 3가지 이다.

     1) 알고리즘 유형 설명

     2) 유클리드 알고리즘 보드에 올려보기

     3) 소수를 구하는 알고리즘 보드에 올려보기

---

1. 알고리즘 :

명령을 효율적으로 처리하는 순서

 

2. 자료구조 :

Data를 효율적으로 저장하는 방식

 

○ 알고리즘

• 알고리즘의 성능 평가
  1) 수행 시간 (속도)
  2) 필요한 기억장치의 양 (메모리)
  - 대개는 수행 시간이 더 중요하게 평가된다.
• 알고리즘의 유형 : 입력되는 자료(Data)의 수 N에 대하여 수행 시간을 함수 관계로 표현
  

수행 시간	설명
1	입력자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
logN	N이 증가함에 따라 실행시간이 조금씩 늘어남 (ex. 성능이 좋은 검색 알고리즘은 대부분 logN의 수행시간을 가짐
N	입력자료의 수에 따라 선형적으로 실행 시간이 걸리는 경우
NlogN	문제를 쪼개어 독립적으로 해결하여 다시 하나로 모으는 경우 (ex. 성능이 좋은 정렬 알고리즘의 실행시간은 NlogN에 비례)
N^2	이중 루프내에서 입력자료를 처리하는 경우
N^3	삼중 루프내에서 입력자료를 처리하는 경우
2^N	입력 자료의 수에 따라 실행시간이 급격히 늘어남.

 

• O표기법 (빅오 표기법)
  - 알고리즘의 성능을 표현할 객관적인 기준
  - 최악의 경우를 가정하여 표현한다.
  
• 그 외 빅오메가 표기법, 세타 표기법 등이 있다.
• 시간소요량(속도)와 공간 소요량(메모리)는 일반적을 ㅗ반비례하기 때문에 실행시간의 단축과 공간 절약의 중요도를 따져 양자 중의 선택이 필요하다.

---

○ 실습1 : 에라토스테네스의 체 (sieve)

• 주어진 N보다 작은 소수를 모두 구하는 알고리즘.
• 2가지 방식의 알고리즘을 작성하여 두 알고리즘의 시간 소요량을 비교하였다.

출처 : 위키피디아

 

• 첫 번째 방식 - 불필요한 연산을 한다.

   // MAX까지의 소수 판별하기
   int iptr[MAX]={0, };
   ...
   for (i = 2; i < MAX; i++)
    {
		if (iptr[i] == 1)
			continue;
		for(j = i+1 ;j<=MAX ;j++)
			if((j%i)==0)   iptr[j] = 1;	// sieved out  by { 2,3,4,...... }
    }

 

• 두 번째 방식 - 앞에 gif 에 나오는 방식과 더 유사하다. 어떤 수의 배수이면 소수가 아닌 걸로 판단함.

   // MAX까지의 소수 판별하기
   int iptr[MAX]={0, };
   ...
   for (i = 2; i < MAX; i++)
    {
		if (iptr[i] == 1)
			continue;
        j=i;
		while ((j += i) <= MAX)	// (2),4,6,8,.... , (3),(6),9,... , (5),...
			iptr[j] = 1;	// sieved out
    }

 

 

• main 문과 PRIME3(연산 함수) 의 코드
  1) PRIME3.c

PRIME3.c

- 함수 인자 r 에 따라 실행되는 알고리즘이 다르다.

/*                                                           */
/*  PRIME3.C   :    Erastothenes's sieve                     */
/*                                                           */
#include "my_lib.h"

#define MAX  150

void Prime_Main3(int r)
{
    int i, j;
    int iptr[MAX+1]={0, };
	
    for (i = 2; i < MAX; i++)
    {
        if (iptr[i] == 1)
            continue;
        j = i;
	if(r==1){
			for(j = i+1 ;j<=MAX ;j++)
				if((j%i)==0)   iptr[j] = 1;	// sieved out  by { 2,3,4,...... }
		}
	else{
			while ((j += i) <= MAX)	// (2),4,6,8,.... , (3),(6),9,... , (5),...
				iptr[j] = 1;	// sieved out
		}
    }
    for (i = 2; i <= MAX; i++)
    {
        if (iptr[i] == 0)
            Uart_Printf("\t%6d", i);
    }
}

2) main 문

main

#include "my_lib.h"
#include "option.h"
#include "2450addr.h"

#define	  msg	" Performance Testing for what ? \n"

void Main(void)
{
	int laps;

	Uart_Init(115200);	/*	Uart init	*/

	//Uart_Send_String( msg );	/*banner*/

	//start_timer0();	   	/* timer start	*/

	/* code something to measure here	*/

	//laps = GetElapsedTime();  	/* get time lap */
	//stop_timer0();		/* timer stop	*/
	//Uart_Printf("clock spend go 0x30for testing %d \n", laps);

/**/
	/* code something to measure here	*/
	start_timer0();	 
	Prime_Main3(1);
	laps = GetElapsedTime(); 
	stop_timer0();		/* timer stop	*/
	Uart_Printf("\nclock spend for testing %d \n", laps);
	
	start_timer0();	 
	Prime_Main3(2);
	laps = GetElapsedTime(); 
	stop_timer0();		/* timer stop	*/
	Uart_Printf("\nclock spend for testing %d \n", laps);

/**/

}

• Make 하기.
  1) Makefile 에서 PRIME3.c와 .o 를 추가해준 뒤, make 해준다.

 

• 결과
  - 2~150까지의 소수를 모두 확인할 수 있다.
  - 소수 확인 작업이 더 길었던 첫 번째 방법의 시간이 4875ns로 더 오래 걸린 것을 확인할 수 있다.

---

○ 실습2 : 유클리드 알고리즘

• 임의의 정수의 최대 공약수를 구할 수 있는 알고리즘이다. 이를 코드로 구현하고 각각의 구현 알고리즘에 따라 걸리는 시간을 비교하였다.
• main문과 EUCLID_MAIN 문의 코드

1) EUCLID_MAIN.c

EUCLID_MAIN.c

• u와 v의 차를 이용하는 minus 함수
• 나머지 연산(%)을 이용하는 modulus 함수
• modulus를 재귀적으로 구현한 recursion함수

이 세가지 함수를 이용하여 유클리드 알고리즘을 구현하였다.

#define	LOOP	10000
int gcd_minus(int u, int v);
int gcd_modulus(int u, int v);
int gcd_recursion(int u, int v);

void EUCLID_MAIN(void)
{
	int u, v, gcd;
	int i;

	Uart_Printf("\n EUCLID2 : Get GCD with time checking\n");
	Uart_Printf("				Input 0 to end program\n");
//
		Uart_Printf("\n\nInput two positive integer -> 280, 30 ");
		u=280;
		v=30;
		//if(u<0 || v<0) continue;
		//if(u==0 || v==0) break;
		
	start_timer0();	   	/* timer start	*/
	for(i=0; i<LOOP; i++)	gcd = gcd_minus(u, v);
	Uart_Printf("\n Minus methods : GCD of %d and %d is %d."
				"in %d ns in CORE0", u, v, gcd, GetElapsedTime());
	stop_timer0();
	
	start_timer0();	   	/* timer start	*/
	for(i=0; i<LOOP; i++)	gcd = gcd_modulus(u, v);
	Uart_Printf("\n Modulus methods : GCD of %d and %d is %d."
				"in %d ns in CORE0", u, v, gcd, GetElapsedTime());
	stop_timer0();

	start_timer0();	   	/* timer start	*/
	for(i=0; i<LOOP; i++)	gcd = gcd_recursion(u, v);
	Uart_Printf("\n Recursion methods : GCD of %d and %d is %d."
				"in %d ns in CORE0", u, v, gcd, GetElapsedTime());
	stop_timer0();
//
	
}
int gcd_minus(int u, int v){
	int t;
	while(u){
		if(u<v){
			t=u; u=v; v=t;
		}
		u=u-v;
	}
	return v;
}
int gcd_modulus(int u, int v){
	int t;
	while(v){
		t=u%v;
		u=v;
		v=t;
	}return u;
}
int gcd_recursion(int u, int v){
	if(v==0)
		return u;
	else
		return	gcd_recursion(v, u%v);
}

 

2) main.c

#include "my_lib.h"
#include "option.h"
#include "2450addr.h"

#define	  msg	" Performance Testing for what ? \n"

void Main(void)
{
	int laps;

	Uart_Init(115200);	/*	Uart init	*/

	Uart_Send_String( msg );	/*banner*/

	start_timer0();	   	/* timer start	*/

	/* code something to measure here	*/
	EUCLID_MAIN();
	laps = GetElapsedTime();  	/* get time lap */
	stop_timer0();		/* timer stop	*/
	Uart_Printf("clock spend go 0x30for testing %d \n", laps);
}

• 결과 (makefile 에 EUCLID_MAIN.c와 .o를 추가해줬다.)
  - 각각의 함수가 걸린 시간을 알 수 있다.
•