0. Performance analysis
1) 프로그램을 판단하는 기준
1> 프로그램이 원래의 명세와 부합하는가?
2> 정확하게 작동하는가?
3> 프로그램을 어떻게 사용하고 어떻게 수행하는지에 관한 문서화가 프로그램 내에 되어져 있는가?
4> 논리적 단위를 생성하기 위해 프로그램이 함수를 효과적으로 사용하는가?
5> 프로그램 코드는 읽기 쉬운가?
이 기준들은 중요 요소이지만, 대형 시스템을 개발할 때 이 기준들을 달성시키는 법을 설명하기란 매우 어렵다. 이러한 기준들은 프로그래밍 스타일과 밀접한 관련이 있고 이에 대한 경험과 훈련이 필요하다.
또한 좀 더 구체적인 기준으로 프로그램을 분석할 수 있도록 상기의 항목에 다음 두 가지 기준을 추가한다.
<performance evaluation>
6> 프로그램이 메인 메모리와 보조기억장치를 효율적으로 사용하는가?
7> 작업에 대한 프로그램의 실행 시간은 허용할 만한가?
2) 성능 평가
1> performance analysis
- 컴퓨터와 상관없이 시공간의 추산에 초점을 두는 분야
- 복잡도 이론(complexity theory)과 관련이 있다.
2> performance measurement
- 컴퓨터에 의존적인 실행 시간을 얻어내는 것
- 이 실행 시간은 비효율적인 코드 세그먼트를 분별하는 데 활용
3) Complexity
1> 공간 복잡도(space complexity): 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양
2> 시간 복잡도(time complexity): 프로그램을 실행시켜 완료하는 데 필요한 컴퓨터 시간의 양
1. Space Complexity (공간 복잡도)
1) requirements
1> fixed space requirements
- 프로그램의 입출력의 횟수나 크기에 관계없이 요구하는 공간
- 명령어 공간(코드 저장을 위한 공간), 단순 변수, 고정 크기의 구조화 변수(struct와 같은), 그리고 상수들을 위한 공간
2> variable space requirements
- (해결하려는 문제의 특정 인스턴스 I에 의존하는 크기를 가진) 구조화 변수들을 위해 필요로 하는 공간들로 구성
- 인스턴스 I에 작업하는 프로그램 P의 가변 공간 요구는 Sp(I)로 표기한다.
- Sp(I)는 인스턴스 I의 특성(characteristic) 함수들에 의해 정해진다.
(ex> 입출력의 횟수, 크기, 값)
- S(P) = c + Sp(I) (S(P) = 전체 공간 requirement) (c = fixed space requirement)
- 프로그램의 space complexity를 분석할 때에는 보통 variable space requirement만 고려한다.
2) Example 1 (simple arithmetic function)
float abc(float a, float b, float C)
{
return a+b+b*c+(a+b-c)/(a+b)+4.00;
}1> 문제: 3개의 단순 변수를 입력으로 받아 하나의 단순 값을 출력으로 반환하는 함수 abc가 있다.
2> 해결: 이 함수는 오직 고정 공간 요구만을 가지고 있으므로 Sabc(I) = 0 이다.
3) example 2 (adding a list of number iteratively)
float sum(float list[], int n)
{
float tempsum = 0;
int i;
for( i = 0; i < n; i++) tempsum += list[i];
return tempsum;
}1> 문제: 리스트에 있는 수를 모두 더한다. 비록 출력은 단순 값이지만 입력은 배열을 포함한다. 그러므로 가변 공간 요구는 배열이 함수로 어떻게 전달되는지에 달려 있다.
2> 해결 1: <passed by value> Pascal 같은 유형의 프로그래밍 언어들은 값 호출(call by value) 방식으로 배열을 전달할 수 있다. 이는 함수가 수행되기 전에 배열 전체가 임시 저장소에 복사된다는 것을 의미한다. 이러한 유형의 언어에서 프로그램을 위한 가변 공간 요구는 n이 배열의 크기 일 때, Ssum(I) = Ssum(n) = n 이 된다. C 언어는 값 호출 방식으로 모든 매개변수를 전달한다.
3> 해결 2: <passed by reference> C언어에서는 함수에 배열을 매개변수로 전달할 때 배열의 첫 번째 요소의 주소를 전달한다. 또, C언어에서는 배열을 복사하지 않으므로, Ssum(n) = 0 이다.
(공간이 아닌 주소 복사는 공간 요구에 카운트하지 않는다.)
4) example 3 (adding a list of numbers recursively)
float rsum(float list[], int n)
{
if (n) return rsum(list, n-1) + list[n-1];
return 0;
}1> 문제: 이번 함수도 리스트에 있는 수를 합산하기 위한 프로그램인데, 순환적으로 작성되었다. 이는 컴파일러가 매개변수, 지역변수, 그리고 순환 호출을 할 때마다 복귀 주소를 저장해야 한다는 것을 의미한다.
2> 해결:
- 하나의 순환 호출을 위해 요구되는 공간 = 2개의 매개변수(list[], n) + 복귀 주소 (지역 변수는 없다.)
- int와 pointer는 각각 4byte가 필요하다.
- 매개변수 (array pointer) : list[] (4byte)
- 매개변수 (int) : n (4byte)
- 복귀주소 : (4byte)
??
- 결론: S_rsum(n) = 12*n
2. Time Complexity (시간 복잡도)
1) 소요시간 (프로그램 p에 의해 소요되는 시간 T_p)
T_p = compile time + execution(running) time
1> compile time
- 인스턴스 특성에 의존하지 않아서 fixed requirement와 유사하다.
- 일단 정확히 수행된다는 것이 검증되면, 그 프로그램을 다시 컴파일하지 않고도 여러 번 수행할 수 있다.
- 결론: execution time(실행 시간)만 고려하면 된다.
(space complexity에서 fixed는 고려하지 않고 variable만 고려하던 맥락과 유사하다.)
...
2> execution time
- 측정법 1: 시스템 클럭(system clock)을 이용해서 시간을 재는 것
- 측정법 2: 프로그램이 수행하는 연산의 횟수를 계산
2) program step
1> 정의: 실행 시간이 인스턴스 특성과 (구문적으로 또는 의미적으로) 독립성을 갖는 프로그램 단위이다
3) Example 1 (Iterative summing of a list of numbers)
<Program 1.13>
float sum(float list[], int n)
{
float tempsum = 0; count++; /* 지정문을 위한 선언 */
int i;
for ( i = 0; i < n; i++) {
count++; /* for 루프를 위한 연산 */
tempsum += list[i]; count++; /* 지정문을 위한 연산 */
}
count++; /* for 문의 마지막 실행 */
count++; /* 반환을 위한 명령문 */
return tempsum;
}1> 문제: 합계 함수에 대한 단계 수를 구하고자 한다.
2> hint: 위의 코드는 count를 어디에 삽입해야 되는지를 보여준다. 여기서 우리가 걱정해야 되는 것은 실행 명령문이지 함수의 헤더나 변수 선언이 아니다.
3> 해결
4> Simplified version of Program
<Program 1.14>
float sum(float list[], int n)
{
float tempsum = 0;
int i;
for ( i = 0; i < n; i++)
count += 2;
count += 3;
return 0;
}
5> 단순화된 해결:
우리의 주요 관심사는 프로그램의 최종 횟수를 결정하는 것이기 때문에 프로그램 1.13에서 대부분의 프로그램 명령문을 제거해서 간단하게 프로그램 1.14와 같이 만들수 있는데, count에 대한 값은 동일하다. 이러한 단순화 과정은 총계(count)를 계산 하기 쉽게 한다. 프로그램 1.14를 보면, count의 초기 값이 0인 경우 최종 값이 2n + 3이 됨을 알 수 있다. 그래서 sum을 호출할 때마다 총 2n + 3 단계가 수행된다.
4) Example 2 (Recursive summing of a list of numbers)
<Program 1.15>
float rsum(float list[], int n)
{
count++;
if (n) {
count++;
return rsum(list, n-1) + list[n-1];
}
count++;
return list[0];
}1> 문제: 합산 함수의 순환 버전에 대한 단계 수를 알아본다.
2> 해결
3> 반복 함수와의 비교
- 앞선 프로그램 1.13과 비교해보면 순환 함수는 반복 함수보다 실제로 단계 수가 더 작다.
- 그러나 이 단계 수는 우리에게 얼마나 많은 단계가 수행되는지를 말해줄 뿐, 각 단계가 얼마나 많은 시간을 소요하는지 말해주는 게 아니다.
- 통상적으로 순환 함수가 작은 단계 수를 가지더라도 반복 함수보다 실행 속도는 더 느리다.
(상식적으로 함수자체를 호출해서 다시 실행하는 것이 함수 내에서의 반복보다 오래 걸린다.)
5) Example 3 (Matrix addition)
<program 1.17>
void add(int a[][MAX_SIZE, int b[][MAX_SIZE], int c[][MAX_SIZE], int rows, int cols)
{
int i, j;
for ( i = 0; i < rows; i++) {
count++; /* i for 루프를 위한 명령문 */
for( j = 0; j < cols j++) {
count++; /* j for 루프를 위한 명령문 */
c[i][j] = a[i][j] + b[i][j];
count++; /* 지정문을 위한 명령문 */
}
count++; /* for 루프에 대한 마지막 j */
}
count++; /* for 루프에 대한 마지막 i */
}2> Simplified version of Program
<Program 1.18>
void add(int a[][MAX_SIZE], int b[][MAX_SIZE], int c[][MAX_SIZE], int rows, int cols)
{
int i, j;
for( i = 0; i < rows; i++) {
for( j = 0; j < cols; j++) {
count += 2;
}
count += 2;
}
count++;
}
6) Summary
1> 프로그램의 시간 복잡도는 그 프로그램의 기능을 수행하기 위해 프로그램이 취한 단계 수로 표현된다.
2> 단계 수는 그 자체가 인스턴스 특성을 갖는 함수이다.
3> 그래서 한 프로그램의 단계 수를 결정하기 전에 그 문제에 대한 어떤 특성이 사용될지를 정확하게 알 필요가 있다.
4> 대다수 프로그램의 시간 복잡도는 입력의 수나 출력의 수, 아니면 쉽게 명세되는 다른 특성에만 의존하지 않는다.
5> 단계 수를 유일하게 결정할 때 발생할 수 있는 매개변수 선택의 부적절함을 세 가지 경우 - 최상, 최악, 평균의 경우 -단계 수를 모두 정의함으로써 해결할 수 있다.
'자료구조' 카테고리의 다른 글
| 1-6강 - Performance measurement (시간 측정) (0) | 2020.03.31 |
|---|---|
| 1-5강 - Performance analysis (2) 점근 표기법 (0) | 2020.03.31 |
| 1-4강 - Data abstraction (0) | 2020.03.30 |
| 1-3강 - Algorithm specification (2) 재귀 알고리즘 (0) | 2020.03.30 |
| 1-3강 - Algorithm specification (1) 선택 정렬, 이진 탐색 (0) | 2020.03.30 |
