※ 나동빈 저자의 '이것이 취업을 위한 코딩 테스트다 with 파이썬 '를 참고하여 정리한 글입니다.
사실 직접 시간 복잡도와 공간 복잡도를 실제로 측정하는 것은 처음 글에서 때에 따라 유용하게 쓰이지만 대부분은 빅오 표기법(Big-O Notation)을 사용하여 다루지 않겠다고 하였지만 잠깐 소개하고 넘어 가겠다.
실제로 측정하는 방법은 주로 검증을 위해 쓰이는데 우리가 처음 알고리즘을 공부한다면 너무 빅오 표기법에만 의존하지 말고 정말 내가 계산한 빅오 표기법의 성능과 일치 하는지 검증을 위해 테스트 해 보면 좋다.
아마 이 과정을 통해서 더 알고리즘 성능 측정을 능숙하게 할 수 있게 될 것이며, 자신의 필요에 따라 구현하고 측정하는 개발자의 능력 또한 성장할 수 있을 것이다.
보통 어떤 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때 측정하며, 내가 짠 알고리즘 코드와 기본 라이브러리 알고리즘 함수의 성능 차이도 비교 해볼 수 있다.
추가로 코드로 인한 성능 측정은 컴퓨터 CPU, 메모리(RAM) 등의 H/W적 성능에 의해 결과가 다르게 나오지만 비교 대상 알고리즘을 동일한 시스템에서 측정한다면 알고리즘 성능 차이 비교에서는 문제가 없다.
자신이 설계한 알고리즘의 성능을 확인하기 위해서, 코드를 사용하여 시간을 측정 해 보는 습관을 기르면 좋을 것이다.
시간 속도 측정
파이썬에서는 다음과 같이 라이브러리 함수를 이용하면 쉽게 측정이 가능하다.
import time
start_time = time.time() # 측정 시작
# 알고리즘 코드
# ~~~
# ~~~
end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력
C언어는 다음과 같이 라이브러리 함수를 사용하면 측정이 가능하다.
#include <stdio.h>
#include <time.h>
int main() {
clock_t start, end;
double cpu_time_used;
// 측정 시작
start = clock();
// 실행할 알고리즘 코드
// ~~~
// 측정 종료
end = clock();
// 걸린 시간 계산 (초 단위로 변환)
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
// 수행 시간 출력
printf("time: %f seconds\n", cpu_time_used);
return 0;
}
- clock() 함수: 프로그램이 시작된 이후에 경과된 시간을 클록 틱(clock ticks) 단위로 반환해.
- CLOCKS_PER_SEC: 1초 동안의 클록 틱 수. clock()에서 반환된 값을 초 단위로 변환하기 위해 사용해.
- start = clock(): 시작 시간 측정.
- end = clock(): 종료 시간 측정.
- (end - start) / CLOCKS_PER_SEC: 실제 경과 시간을 초 단위로 변환.
C++은 C언어처럼 <ctime> 라이브러리를 사용할 수 있지만, C++11부터는 <chrono> 라이브러리가 추가되어 더 정밀하게 시간을 측정할 수 있게 되었다.
#include <iostream>
#include <ctime> // C++에서 C언어의 time.h 대신 사용하는 헤더
int main() {
// 측정 시작
clock_t start, end;
start = clock();
// 실행할 알고리즘 코드
// ~~~
// 측정 종료
end = clock();
// 걸린 시간 계산 (초 단위로 변환)
double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
// 수행 시간 출력
std::cout << "Time: " << cpu_time_used << " seconds" << std::endl;
return 0;
}
- clock_t start, end: 클록 틱을 저장할 변수를 선언.
- start = clock(): 프로그램의 실행 시작 시점의 시간을 클록 틱 단위로 저장.
- end = clock(): 프로그램 실행 후 종료 시점의 시간을 클록 틱 단위로 저장.
- CLOCKS_PER_SEC: 초당 클록 틱 수를 나타내는 상수. 이를 이용해 클록 틱을 초 단위로 변환.
- (end - start) / CLOCKS_PER_SEC: 경과 시간을 초 단위로 계산.
#include <iostream>
#include <chrono> // 시간 측정 라이브러리
int main() {
// 측정 시작
auto start = std::chrono::high_resolution_clock::now();
// 실행할 알고리즘 코드
// ~~~
// 측정 종료
auto end = std::chrono::high_resolution_clock::now();
// 걸린 시간 계산 (초 단위로 변환)
std::chrono::duration<double> elapsed = end - start;
// 수행 시간 출력
std::cout << "Time: " << elapsed.count() << " seconds" << std::endl;
return 0;
}
- auto start = std::chrono::high_resolution_clock::now(): 현재 시간을 고해상도 클럭으로 측정 (시작 시간).
- auto end = std::chrono::high_resolution_clock::now(): 현재 시간을 측정 (종료 시간).
- std::chrono::duration<double>: 두 시간 간의 차이를 초 단위로 저장.
- elapsed.count(): 초 단위로 경과 시간을 출력.
메모리 사용량 측정
직접적으로 메모리 사용량을 측정하려면 외부 도구나 라이브러리를 활용할 수 있다.
C/C++에서 유닉스 기반 시스템(리눅스, macOS)에서 getrusage() 함수를 사용해 메모리 사용량을 측정할 수 있다.
이 함수는 프로그램이 사용한 메모리와 CPU 시간을 반환해.
#include <iostream>
#include <sys/resource.h>
int main() {
struct rusage usage;
// 실행할 알고리즘 코드
// ~~~
// 메모리 사용량 측정
getrusage(RUSAGE_SELF, &usage);
// 최대 메모리 사용량 출력 (KB 단위)
std::cout << "Max memory usage: " << usage.ru_maxrss << " KB" << std::endl;
return 0;
}- ru_maxrss: 프로그램이 실행되는 동안 사용한 최대 메모리를 KB 단위로 반환.
C/C++에서 Windows에서는 GetProcessMemoryInfo() 함수를 사용해, 프로세스의 메모리 사용량을 측정할 수 있다.
#include <windows.h>
#include <psapi.h>
#include <iostream>
int main() {
PROCESS_MEMORY_COUNTERS pmc;
// 실행할 알고리즘 코드
// ~~~
// 현재 프로세스 메모리 사용량 측정
if (GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc))) {
std::cout << "Working Set Size: " << pmc.WorkingSetSize / 1024 << " KB" << std::endl;
}
return 0;
}- pmc.WorkingSetSize: 프로세스의 현재 메모리 사용량을 KB 단위로 반환.
파이썬에서는 psutil이나 tracemalloc 라이브러리를 사용해, 메모리 사용량을 측정할 수 있다.
import psutil
import os
# 실행할 알고리즘 코드
# ~~~
# 메모리 사용량 측정
process = psutil.Process(os.getpid())
mem_info = process.memory_info()
# 현재 메모리 사용량 출력 (바이트 단위)
print(f"Memory usage: {mem_info.rss / 1024 ** 2} MB")- rss: 실제로 프로그램이 사용한 실제 메모리(resident set size).
파이썬에서는 메모리 할당을 추적하는 tracemalloc을 사용해, 메모리 사용량을 추적할 수 있다.
import tracemalloc
# 메모리 추적 시작
tracemalloc.start()
# 실행할 알고리즘 코드
# ~~~
# 메모리 사용량 측정
current, peak = tracemalloc.get_traced_memory()
# 현재와 최대 메모리 사용량 출력
print(f"Current memory usage: {current / 1024 ** 2} MB")
print(f"Peak memory usage: {peak / 1024 ** 2} MB")
# 메모리 추적 종료
tracemalloc.stop()
대부분 라이브러리 함수들을 사용하여 측정하는 정도만 되어도 좋다.
이미 검증된 측정 도구들이기 때문이다.
