[DS] Ch1. Performance Analysis

Performance Analysis

• 성능 분석 : running time(계산 시간, 실행 속도) / primary and secondary storage(RAM, 하드디스크에서 어느 만큼의 용량을 사용하는가)

• 성능 분석 방법 - machine-independent(기계 독립적; 기계 자체의 성능 차이가 프로그램 성능에 영향을 주어서는 안 됨)
  1) Time complexity(시간 복잡도) : 프로그램 시작에서 끝까지 소요되는 시간
  2) Space complexity(공간 복잡도) : 프로그램 시작에서 끝까지 필요로 하는 메모리 양

Which has better performance? (1)

1. Iterative function for summing a list of numbers

float sum(float list[], int n)  // n은 instance characteristic
{
	float tempsum = 0;
    int i;
    for (i = 0; i < n; i++)  // list[0]~list[n-1] 합계를 구하는 for문
    	tempsum += list[i];
    return tempsum;
}

반복문 사용 O (ex: for, while, do-while)

2. Recursive function for summing a list of numbers

float rsum(float list[], int n)  // n은 instance characteristic
{
	// if (n) == if(n!=0)
	if (n) return rsum(list,n-1) + list[n-1];  // n이 0이면 False, 0이 아니면 True
    return 0;
}

반복문 사용 X, 재귀함수 (function 내에서 다시 그 function을 호출)

Q. Which has a better performance?

A. 계산 시간 측면에서 Iterative function이 더 효율적. Recursive function은 function call에 시간 소요.

[Memory Stack In Recursive Function]
Function call이 될 때마다 call frame이 생성됨.
call frame => parameters, return address, local variable, register(caller/callee) 저장
Function call이 끝나고 원래 주소로 되돌아가면 call frame이 없어짐.
Recursion이 일어나서 function call이 일어날 때마다 frame이 하나씩 생성되고, 제일 마지막에 생성된 것부터 차례대로 frame이 삭제됨. (Last In First Out)
메모리 내 frame을 쌓을 수 있는 공간이 초과되면 stack overflow 발생

Which has better performance? (2)

• Fibonacci 수열
  F(0)=0, F(1)=1, F(i)=F(i-1)+F(i-2) for i>1 (i는 instance characterisitic)

1. Iterative version : F(0)~F(n-1) 저장 가능한 size n인 배열 생성
2. Recursive version : 특정 조건(i>1)을 만족하면 return F(i-1)+F(i-2), i=0 또는 1이 되면 recursion 끝

• 1부터 n까지 정수 합 계산

1. Iterative version

int sum(int n)
{
	int sum = 0;
    for (int i = 1; i <= n; i++)
    	sum += i;
    return sum;
}

2. Recursive version

int F(int i)
{
	if (i == 1) 
    	return 1;
    else 
    	return F(i-1)+i;
}

Recursive equation :
F(1) = 1
F(i) = F(i-1) + i --- (i>1)
.
3. Constant time function => 가장 간단한 algorithm

int F(int i)
{
	return i * (i+1) / 2
}

Some Uses of Performance Analysis

• 알고리즘의 실용성 판단
• 매우 큰 instance에 대한 실행 시간 예측
• 복잡도가 다른 두 알고리즘 간 비교
  ex) O(n) and O(n^2)

Program Complexity

• Performance Analysis(성능 분석) : 프로그램이 되기 전, 알고리즘 구성 단계에서 미리 예측
• Performance measurement(성능 측정) : 프로그램 구현 끝난 후, 직접 실행해서 측정 (귀납적 테스팅)
  "time.h" library를 통해 계산 시간 측정 가능

Space Complexity

• Fixed part : 고정된 메모리 공간이 항상 필요한 부분
  Instruction space (명령문)
  space for simple variables (변수)
  fixed-size structured variables (struct 변수들)
  constants (상수)

• Variable part : instance characteristic에 의해 가변적으로 메모리 공간이 필요한 부분
  ex) recursive call에서 n값에 따라 stack에 생성된 call frame의 개수 달라짐

  S(P) = c + Sp(n)
  S(P) : 프로그램 P에 필요한 메모리 공간
  c : 상수(고정된 메모리 공간)
  n : instnace characteristics(ex: I/O size, number) => 이로 인해 계산 속도 결정됨

#define K 100
int main() {	
    int a, b, c;
    struct {
    	int x;
        int y;
    } point;
    c = a + b;
    for (int i = 0; i <= b; i++) 
    	a += i;
    scanf_s("%d",c);
    int *L = (int*)malloc(size of (int)*n);

Fixed part : 명령문/변수 저장 공간 ex) K, a, b, c, struct, c = a+b, for, scanf_s, malloc
Variable part : ex) malloc 저장 공간(n 값에 따라 가변적)

float abc(float a, float b, float c)
{
	return a+b+b*c+(a+b+c)/(a+b)+4.00;
}

S(n) = 0 (가변적인 부분 X)

float sum(float list[], int n) // list[] : 배열을 가리키는 pointer, n : 배열의 size
{
	float tempsum = 0;
    int i;
    for (i = 0; i < n; i++)
    	tempsum += list[i];
    return tempsum;
}

S(n) = 0 (가변적인 부분 X)

float rsum(float list[], int n)  // list[] : pointer(4byte), int n(4byte)
{
	if (n) return rsum(list,n-1) + list[n-1];  // return 주소(4byte)
    return 0;
}

call 한 번 당 12 byte
call = > n ~ 0 (n+1번)
if n is MAX_SIZE,
S(MAX_SIZE) = 12 * (MAX_SIZE + 1)