피보나치 수열을 계산하기 위해 프로그램을 어디까지 최적화할 수 있습니까?

소개

파이썬을 배울 때 선생님께서 피보나치 수열의 N번째 수를 계산하라는 숙제를 내주셨어요.

아주 쉬운 것 같아서 다음 코드를 작성합니다.

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1)   fib(n - 2)

나중에 이런 종류의 솔루션에는 시간이 너무 많이 걸린다는 것을 알게 되었습니다.

프로그램 최적화

해법을 반복으로 변경합니다.

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

나는 matplotlib를 사용하여 비용이 드는 시간을 그립니다.

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

결과는 다음과 같습니다.

비용이 드는 시간이 매우 짧습니다.

하지만 저는 fib(300000)을 썼고 비용은 5.719049899998936초였습니다. 너무 깁니다.

어른이 되면 CACHE를 배워 결과를 저장하기 위해 dict를 사용하도록 솔루션을 변경합니다.

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n 



또는 직접 CACHE를 작성할 수도 있습니다.


def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n