[데이터 구조] 4차시 프로그램 성능 분석

0. 프로그램의 성능 평가

1) 프로그램의 일반적인 평가 항목들

• 프로그램이 처음에 정한 문제의 sepcifications을 만족하는가?
• 프로그램의 documentation이 충분한가?
• 프로그램이 readable한가?
• 프로그램이 correct하게 옳은 답을 내는가?
• 문제의 논리적 단위를 생성할 때, 함수를 효율적으로 사용했는가?
• 프로그램의 수행 시간이 늦지 않은가?
• 프로그램이 storage(memory, disk)를 효과적으로 사용하는가?

 

 

2) 프로그램의 성능을 측정하는 방법들

(1) Time & Space 측정법(15% 정도)

: Program 성능을 측정하기 위해, Machine(HW)과 독립적인 다음 2가지 SW적 요소를 분석하는 방법

• Time 요소(효율성, efficiency, 속도 지향)
• Space 사용 정도(메모리 공간 점유도, economy, 경제성 지향)

 

(2) Step Count 법(5% 정도)

: Program(code)의 Step 수를 하나하나 세는 방법

 

(3) 점근식 표기법(Asymptotic Notation) (거의 대부분, 100% 사용)

: 품질 및 성능 측정, 품질 보증서

 

 

 

 

1. 모듈1: Time & Space 측정법

1) Program(P)의 Time & Space Complexity

(1) Space & Time을 사용하여 측정하는 이유

• 프로그램 P가 사용하는 1️⃣메모리 공간(Space)과 프로그램의 2️⃣수행 시간(Time)을 측정해서 정량적(수치)으로 보여주는 방법
• 프로그램 P의 정량적 성능을 표현하기 위해 2가지 metric인 1️⃣Space complexity와 2️⃣Time complexity를 사용한다.

 

(2) 용어 정의 - S(P) & T(P)

• Space complexity: 프로그램 P의 수행 완료에 필요한 memory 용량
  S(P): Space Degree of the Program
  
  
• Time complexity: 프로그램 P의 수행 완료에 필요한 CPU 사용 시간
  T(P): Time Efficiency of the Program

 

2) Space Complexity - S(P)

(1) 고정공간(fixed)과 변이공간(variable)의 합으로 계산됨

• 고정 공간(c): program의 input/output size에 무관한 space(c로 표현함)
  1️⃣ Instruction space(실제 프로그램 자체 코드 저장공간)
  2️⃣ Space for simple variables(프로그램 내에서 선언된 변수들의 크기를 잰다)
  3️⃣ Fixed size structured variable들의 크기(크기를 미리 알 수 있는 struct 등)
  4️⃣ Constants들의 크기
  
  
• 변이 공간: program이 input/output size에 종속된 space(Sp(I)로 표현). 이 프로그램이 Instance가 됐을 때 space!
  * 인스턴스화 = 프로세스가 됨
  - 문제 해결 과정(프로그램의 수행 과정 = Run time)에서 instance I에 의하여 결정되는
  1️⃣Structured variables의 space와 2️⃣Recursion에 의해 사용된 space의 합으로 구성
  - A function of some characteristics of the instance I

loop는 한 번당 n

 

 

3) Time Complexity - T(P)

(1) T(P) 계산법

 

 

(2) Run time(execution time) 추정 방법

• 정확한 계산의 단점: 시스템 clock 수로 계산 가능하지만, machine dependent하여 큰 의미가 없다.
• 실용적인 대안: program이 수행하는 operation의 수로 추정하며, machine independent하게 추정하면 된다.
  (-> 다음 모듈에서 배울, Program Step을 이용하자!)

return은 안 들어감! 변수 초기화 및 선언 부분에서 사용된 변수가 변수 로딩으로 카운트 된다.

 

참고

 

 

[ 모듈 정리 ] Time & Space 측정법

 

 

 

 

2. 모듈2: Step Count법

1) Program Step을 세는 방법

- 정의: Syntactically 혹은 semantically 의미 있는 program의 segment(code 자체)이다. 이것은 running time이 instance characteristics와 무관한 특징을 가진다.

- 선언은 관심 없음. assignment만!

 

- 프로그램 Step Count법 예제 #1: count

float sum(float list [], int n)
{
    int count = 0; // for counting steps, count 변수 선언
    
    //시작
    float tempsum = 0;
    count++;
    
    int i; // declaration은 무시
    for(i = 0; i < n; i++){
        count++; // for 반복문 때문. 반복문 실행될 때마다 count ++;
        
        tempsum += list[i];
        count++;
    }
    count++; // for 반복문 빠져나올 때 조건 검사했으므로 마지막 execution of for. count.
    count++; // return으로 함수 끝나기 전에 미리 count
    
    return tempsum;
}

 

 

- 프로그램 Step Count법 예제 #2: Recursive summing

float rsum(float list [], int n)
{
    count ++; // 아래 줄의 if 때문에 count++;
    
    if (n) {
        count++; // 아래의 return rsum 때문에 count++;
        return rsum(list, n-1) + list[n-1];
    }
    
    count++; // 아래의 return 때문에 count++;
    return 0;
}

 

 

- 프로그램 Step Count법 예제#3

void add(int a[][MAX_SIZE],
         int b[][MAX_SIZE],
         int c[][MAX_SIZE],
         int rows, int cols)
{
    int i, j, count // 선언은 무시
    
    for(i=0; i < rows; i++){
        count++; // 반복문 들어올 때마다
        for(j=0; j < cols; j++){
            count++; // 반복문 들어올 때마다
            
            c[i][j] = a[i][j] + n[i][j];
            count++; // 위의 코드 때문에
        }
        count++; // 반복문 나올때
    }
    count++; // 반복문 나올 때
}

* for 반복문에서 step count는 for 반복문 들어가자마자와 나오자마자 센다.

 

 

[ 모듈 정리 ] 프로그램 Step Count법과 그 문제점

• Program의 step을 count하는 목적은
  1️⃣ 서로 다른 두 program들의 time complexity를 상대적으로 분석하고 비교
  2️⃣ Instance(n)의 characteristic들(움직임, 루프 등)이 변할 때, run time의 증가치 분석
  
  
• 문제점
  

  

  
  1️⃣ (1)과 (2)가 분명히 연산양이 다름에도, 동등하게 1 step으로 count된다는 것은 불공정하다.
  2️⃣ 프로그램이 큰 경우, 정확한 step count는 일반적으로 어렵다.
  3️⃣ 모든 문장에 count++ 문장을 넣는 것은 쉽지 않다.
  
  ✅ 해결방안: program의 time과 space complexity를 잘 나타내는 개념이 필요하다.

 

 

3. 모듈3: 점근식 표기법(Asymptotic Notation) - 분석적 방법

1) Asymptotic Notation 개요

(1) 정의: Upper bound complexity, Big-O, "빅오"라고 읽음

- 해설

g(n)은 f(n)을 포함할 정도로 크게 설정한 후, f(n)은 g(n)보다 작다고 말한다.

f(n)은 항상 g(n)보다 작으므로, f(n)이 자신을 소개할 때,

"난 g(n)보다 작다. g(n)은 나의 Upper Bound다."라고 말할 수 있다.

 

(2) 예시

• 3n + 2 <= O(4n)
• 10n^2 + 4n + 2 <= O(10n^4)

 

2) Upper Bound Complexity(O)

(1) f(n) = O(g(n))

- "g(n)이 f(n)의 Upper Bound다"라고 읽는다.

- 의미: 이것은 "f(n) 함수의 결과치가 g(n) 함수의 것보다 클 수 없다" -> f(n)이 아무리 클지라도, g(n)보다는 작다.

 

(2) g(n) 설정법: f(n)보다는 크지만, 가능한 f(n)에 근접한 작은 값으로 잡아야, f(n)을 잘 설명할 수 있게 된다.

-> g(n) 설정 시, f(n)에 가깝게 설정할수록, f(n)이 더 잘 설명된다.

 

(3) Big-O 예시

 

 

3) Lower Bound Complexity(Ω) - 트리 검색엔진의 기반

(1) f(n) = Ω(g(n))

- "g(n)이 f(n)의 Lower Bound다"라고 읽는다.

- 의미: 이것은 "f(n) 함수의 결과치가 g(n) 함수의 것보다 작을 수 없다." -> f(n)이 아무리 작아도, g(n)보다는 크다.

 

(2) Big-Omega(Ω) 설정법

: f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a,b가 존재하고(주어지고)
모든 n>=b에 대해 f(n)>=a·g(n)이면, f(n) = Ω(g(n))

 

(3) Big-Ω 예시

 

 

4) Both Bound Complexity( θ ) 

(1) f(n) = θ(g(n))

- 의미: g(n)이 f(n)보다 작기도 하고 크기도 한 것이다.(f(n)에서 가장 큰 부분?... 인가?...)

 

(2) Big-Theta(θ) 설정법

: f, g가 양의 정수를 갖는 함수일 때, 세 양의 상수 a,b,c가 존재하고(주어지고),

모든 n >= c에 대해, a·g(n) <= f(n) <= b·g(n)이면, f(n) = θ(g(n))

 

(3) Big-Theta(θ) 예

 

 

 

5) 점근적 표기법 예제

 

6) 점근적 표기법의 상대적 성능 비교 분석

- 최악의 경우를 해당 프로그램의 성능으로 판단함

 

- 모듈1에서 배운 Time Complexity라는 용어는, 이제 Big-O로 표현되는 점근적 복잡도가 더 많이 사용되면서 Time Complexity라 하면 Big-O 표현이 대표됨. 현재는 점근적 복잡도가 P의 성능을 나타내는 Time complexity의 대명사로 사용됨.

 

- 우선순위

 

 

 

 

[ 모듈 정리 ]