최적화

김현송·2023년 4월 25일

코드 최적화

Memoization과 재귀함수

일반적으로 피보나치 함수를 구현할 때 재귀형태의 함수로 구현을 많이 합니다.

예1)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

하지만 DP를 이용한 메모이제이션을 이용하면 시간을 단축시킬 수 있습니다.

예2)

def fibonacci(n):
    fib_values = [0, 1]
    
    for i in range(2, n+1):
        fib_values.append(fib_values[i-1] + fib_values[i-2])
    
    return fib_values[n]

위 코드의 경우는 특히 파이썬의 특성상 배열의 크기를 동적으로 늘려주기 때문에 더욱 유용하다고 할 수 있습니다.

함수 호출 및 재귀 깊이를 고려하고, 참조 가능한 범위의 값일 경우 + 동적 계획법을 이용한 프로그래밍이 가능한 경우에 최적화를 할 수 있습니다.

메모리 최적화

해를 구하는 함수에서 메모리를 최소로 사용하기 위해서는 다음과 같은 방법으로 최적화를 진행합니다.

def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev1 = 0
    prev2 = 1
    for i in range(2, n+1):
        current = prev1 + prev2
        prev1 = prev2
        prev2 = current
    return current

Python 메모리 관리자는 객체별 할당자를 통해 OS의 메모리 관리자와 상호 작용하여 힙에 공간이 있는지 없는지 판단 후에 객체를 생성합니다. 원시 메모리는 힙에 생성되게 됩니다.
힙에 생성된 원시 객체는 지역변수를 통해 참조가 가능합니다.

하지만 함수 객체를 생성할 때 차지하는 메모리 영역은 "블록" 이라는 메모리 청크를 관리하며 스택 메모리에 해당 함수 객체를 생성하기 때문에 원시객체를 갱신하는 것과 달리 스택 메모리 안에서 함수가 실행되고 종료되기 전까지의 메모리를 차지하고 있습니다.

따라서 메모리 성능에서 차이를 가져오게 됩니다.

python에서 메모리 측정은 메모리 할당 추적(tracemalloc) 라이브러리를 통해 확인 가능합니다.

적합한 라이브러리 사용

라이브러리를 적절하게 사용한다면 4배 이상의 실행 속도 차이를 가져올 수 있습니다.
math.dist라는 메서드 내부에는 zip이라는 내장함수를 사용하는데 이 내장함수가 병렬처리에 효과적인 함수입니다. (각 객체의 iterator 반환을 통해 병렬 처리를 합니다.)

가시적인 지표 활용

프로파일 (profile)은 프로그램의 여러 부분이 얼마나 자주 그리고 얼마나 오랫동안 실행되었는지를 기술하는 통계 집합입니다

https://docs.python.org/ko/3/library/profile.html?highlight=cprofile#module-cProfile

실행 횟수

memory_profiler을 활용하면 line by line으로 해당 코드가 몇번 실행되었는지 + 메모리 사용량을 확인 할 수 있습니다.

import timeit

code_to_test = """
def find_even_numbers(numbers):
    return [number for number in numbers if number % 2 == 0]

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_numbers = find_even_numbers(numbers)
"""

execution_time = timeit.timeit(code_to_test, number=1000)
print(f"Execution time: {execution_time:.4f} seconds")

~~1000003번은 변수가 생성되고 할당하는 것까지 포함하는 것으로 생각됩니다.~~

실행 시간

timeit을 통해 해당 코드의 실행 시간도 알 수 있습니다.

import timeit

code_to_test = """
def find_even_numbers(numbers):
    return [number for number in numbers if number % 2 == 0]

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_numbers = find_even_numbers(numbers)
"""

execution_time = timeit.timeit(code_to_test, number=1000)
print(f"Execution time: {execution_time:.4f} seconds")