빠른 피보나치 항 구하기

피보나치 수열은 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배의 결과인데, 이는 큰 값에서는 빠른 피보나치 변환 알고리즘이 강력함을 발휘한다고 볼 수 있다. 하지만 어느정도 규모 이하의 값에서는 앞에서부터 계산하는 방식이 좀 더 간편하고 빠르게 써먹을 수 있을 것 같다.