파이썬 함수 실행 속도를 1000배 빠르게 해주는 모듈/functools, cache 데코레이터,재귀함수, 피보나치 수열

---

목차

1. 주제 소개

2. 예제 함수 소개

3. cache 데코레이터 소개

---

 

1. 주제 소개

 

앞서 이 블로그에 파이썬의 연산 속도를 빠르게 만들어 주는 NUMBA 라이브러리를  소개한 적이 있다.

 

파이썬(Python) 속도를 100배, 1000배 빠르게 해주는 라이브러리(numba)

파이썬(Python) 속도를 100배, 1000배 빠르게 해주는 라이브러리(numba)

 

이번에 소개하려는 내용도 파이썬 함수의 실행 속도를 빠르게 해주는 방법인데, 위에 소개한 내용과는 작동 원리와 용도가 다른 것이다.

 

함수의 형태 중에는 재귀함수라는 것이 있다. 함수를 호출하면 그 함수가 또 다른 함수를 호출하는 형태의 함수를 재귀함수라고 한다.

 

재귀함수의 예제로 흔하게 다뤄지는 것이 피보나치 수열이다. 피보나치 수열은 n번째 수가 n-1번째 수와 n-2번째 수의 합과 같은 수열을 말한다.

 

https://ko.m.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

이를 파이썬 함수로 다음과 같이 구현할 수 있다. 맨 마지막 줄의 return 구문을 보면 fib 함수가 다시 호출되고 있다. 

 

def fib(n):

    if n < 2:
        return n

    return fib(n-1) + fib(n-2)

 

이와 같은 함수를 재귀함수라고 하는데, n이 커질수록 함수가 반복적으로 호출되는 횟수가 많아져서 실행 속도가 굉장히 느려진다.

 

이러한 경우에 함수의 실행 속도를 획기적으로 줄여줄 수 있는 파이썬의 내장 모듈인 functools를 소개한다.

 

반응형

 

2. 예제 함수 소개

 

functools의 사용법을 보기 전에 먼저 예제의 함수가 어떻게 작동하는지를 더 자세히 살펴 보기 위해서 코드 몇 줄을 추가하고, 피보나치 수열의 7번째 수를 구해 보자.

 

def fib(n):

    if n < 2:
        return n

    print("calculating", n, "...") # 함수가 호출될 때마다 문자열을 출력

    return fib(n-1) + fib(n-2)

if __name__ == "__main__":

    print(fib(7)) # 피보나치 수열의 7번째 수열을 출력

 

위의 코드를 실행해 보면 아래와 같은 결과가 출력된다.

 

calculating 7 ...
calculating 6 ...
calculating 5 ...
calculating 4 ...
calculating 3 ...
calculating 2 ...
calculating 2 ...
calculating 3 ...
calculating 2 ...
calculating 4 ...
calculating 3 ...
calculating 2 ...
calculating 2 ...
calculating 5 ...
calculating 4 ...
calculating 3 ...
calculating 2 ...
calculating 2 ...
calculating 3 ...
calculating 2 ...
13

 

맨 아랫줄에 피보나치 수인 13이 출력되었고, 그 위로 함수가 호출될 때마다 출력된 문자열이 보인다.

 

자세히 살펴 보면, n이 7과 6일 때는 함수가 1번씩만 호출이 되었지만, 5일 때는 2번, 4일 때는 3번 호출되는 등 같은 함수가 여러 차례 호출된 것을 볼 수 있다.

 

이런 특징 때문에 n이 커질수록 함수의 실행 속도가 굉장히 느려지게 된다.

 

실험 삼아 50번째 피보나치 수를 구해 보기로 하고, 실행 속도를 측정해보려 했는데, 스크립트를 실행하고 한참이 지나도 결과가 출력이 안 되어 결국 중단하고 말았다. 

 

$ time python fib.py

^CTraceback (most recent call last):

......

KeyboardInterrupt

python fib.py  938.77s user 0.04s system 99% cpu 15:42.43 total

 

출력 결과의 맨 마지막 줄 끝을 보면 총 실행 시간이 출력되었는데, 15분 42초간 연산을 했는데도 50번째 피보나치 수를 구하지 못하였다.

 

반응형

 

3. cache 데코레이터 소개

 

이제 예제의 스크립트에 cache 데코레이터를 추가해 보자. cache 데코레이터의 역할은 같은 함수를 여러 번 호출하지 않고, 캐시에 저장해 뒀다가 불러올 수 있게 해 주는 것이다.

 

https://docs.python.org/ko/3/library/functools.html

functools — 고차 함수와 콜러블 객체에 대한 연산 — Python 3.10.4 문서

 

사용법은 간단하다. 관련 모듈을 불러오고, 함수 위에다 표시만 해주면 된다.

 

from functools import cache  # cache를 불러옴

@cache # 함수 위에 데코레이터 추가
def fib(n):

    if n < 2:
        return n

    print("calculating", n, "...")

    return fib(n-1) + fib(n-2)

if __name__ == "__main__":

    print(fib(7))

 

수정한 스크립트를 실행한 결과는 다음과 같다. 앞서 본 것과 달리 함수가 총 6번만 호출되었고, 7번째 피보나치 수도 정상적으로 출력되었다.

 

calculating 7 ...
calculating 6 ...
calculating 5 ...
calculating 4 ...
calculating 3 ...
calculating 2 ...
13

 

 

이제 cache 데코레이터를 적용했을 때와 적용하지 않았을 때의 실행 속도 차이를 비교해 보자.

 

40번째 피보나치 수를 데코레이터 없이 구해보니 1분 18초가 걸렸다.

 

$ time python fib.py

102334155

python fib.py  77.25s user 0.06s system 98% cpu 1:18.71 total

 

데코레이터를 추가하니 0.04초가 걸린다.

 

$ time python fib.py

102334155

python fib.py  0.02s user 0.02s system 86% cpu 0.044 total

 

속도의 차이가 조금 더 와닿도록 영상으로도 비교해 보자. n을 32로 줄이고 두 개의 서로 다른 스크립트로 저장한 뒤에 번갈아서 2번씩 실행해 봤다.

 

 

fib_cache.py 실행 결과가 fib.py 실행 결과 출력 후에 곧바로 이어서 출력되어 마치 둘이 동시에 실행된 것처럼 보이지만 사실은 순차적으로 실행되는 것이다.

 

코드 2줄을 추가했을 뿐인데 상당한 차이가 느껴진다.