Fibonacci using Memoization

Legacy Fibonacci

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

def Main():
    number = int(input("Enter integer: "))
    print(fibo(number))

if __name__=='__main__':
    Main()

Fibonacci using Memoization

__fibo_cache = {}
def fibo(n):
    if n in __fibo_cache:
        return __fibo_cache[n]
    else:
        __fibo_cache[n] = n if n < 2 else fibo(n-2) + fibo(n-1)
        return __fibo_cache[n]

def Main():
    number = int(input("Enter integer: "))
    print(fibo(number))

if __name__=='__main__':
    Main()

위 소스를 기준으로 fibo(5) 을 구한다고 가정하면 아래와 같은 순서로 memoization 을 수행한다.

1. call fibo(5) -> 5 is not in __fibo_cache -> fibo(3) + fibo(4)
2. call fibo(3) -> 3 is not in __fibo_cache -> fibo(1) + fibo(2)
3. call fibo(1) -> 1 is not in __fibo_cache -> __fibo_cache[1] = 1 memo
4. call fibo(2) -> 2 is not in __fibo_cache -> __fibo_cache[2] = 2 memo
5. __fibo_cache[3] = 1 + 2 = 3 memo
6. call fibo(4) -> 4 is not in __fibo_cache -> fibo(2) + fibo(3)
7. 2,3 is in __fibo_cache -> __fibo_cache[4] = 2 + 3 = 5 memo
8. __fibo_cache[5] = 3 + 5 = 8 memo

중복해서 계산이 필요한 부분은 memo를 해두고 그것을 찾아볾으로써 불필요한 연산을 줄여줄 수 있다.

Fibonacci using memoization and decorator

Python의 Decorator를 이용하면 아래와 같이 좀 더 그럴싸하게 구현할 수 있다.

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function

@memoize
def fibo(n):
    return n if n < 2 else fibo(n-2) + fibo(n-1)

def Main():
    number = int(input("Enter integer: "))
    print(fibo(number))

if __name__=='__main__':
    Main()

소스코드 출처: http://ujihisa.blogspot.com/2010/11/memoized-recursive-fibonacci-in-python.html