빠른 피보나치 항 구하기
피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다.
def fib(n):
if n < 3:
return (0, 1)[n]
return fib(n-1) + fib(n-2)
하지만 이 함수는 지극히 비효율적이라
%time fib(35)
Wall time: 7.05 s
Out[7]: 9227465
이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다.
# 메모이제이션을 위한 데코레이터 함수
def memoize(f):
cache = {}
def inner(arg):
if arg in cache:
return arg
return cache.setdefault(arg, f(arg))
return inner
# 메모이제이션을 적용한 피보나치 항 구하기
@memoize
def fib_cached(n):
if n < 2:
return (0, 1)[n]
return fib(n-2) + fib(n-1)
# 그 결과는
%time fib_cached(300)
Wall time: 1 ms
Out[6]: 44552
상당히 준수하다. 하지만 이 방법은 치명적인 약점이 있는데, 그만큼 많은 메모리 공간을 캐시로 쓴다는 점과, 재귀에 기반하기 때문에 처음부터 너무 큰 값을 계산하는 경우 재귀 깊이의 한계에 빠지게 된다. (n = 30,000 일 때를 처음부터 계산할 수 없음)
dp 기법을 이용하는 방법도 있다. 이 역시 메모리를 부가적으로 쓰긴하지만, 캐싱보다도 더 빠르며, 재귀 한계에 대한 위험이 없다.
def fib_dp(n):
ns = [1, 1] + [0] * (n - 1)
for i in range(2, n+1):
ns[i] = ns[i-2] + ns[i-1]
return ns[n]
# 1000 loops, best of 3: 279 µs per loop
피보나치 수열은 단순히 앞의 두 값을 더한 값이 그 다음항이 되기 때문에 dp 대신 값을 바꿔나가는 방법으로 다음과 같이 구현해도 된다. 이는 추가적인 메모리를 더 쓰지 않는다.
def fib_f(n):
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
%timeit fib_f(1000)
10000 loops, best of 3: 108 µs per loop
되려 메모이제이션을 쓰는 것보다 빠르다.
하지만 이보다도 더 빠른 방법이 있으니, 그것은 빠른 피보나치 변환을 쓰는 것이다.
def multiply(x, y):
a, b = x
c, d = y
return (a*c + b*d, a*d + b*c + b*d)
def power(x, n):
if n is 0:
return (1, 0)
if n % 2 == 0:
return power(multiply(x, x), n // 2)
return multiply(power(multiply(x, x), n // 2), x)
def fib_fast(n):
return power((1, 1), n)[0]
백만번째 항을 계산하는데, 빠른 피보나치 변환을 계산한 결과는 1.5초 가량이며, 앞에서부터 계산한 결과는 14초가 넘어간다. 거의 10배의 결과인데, 이는 큰 값에서는 빠른 피보나치 변환 알고리즘이 강력함을 발휘한다고 볼 수 있다. 하지만 어느정도 규모 이하의 값에서는 앞에서부터 계산하는 방식이 좀 더 간편하고 빠르게 써먹을 수 있을 것 같다.