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

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

소개

파이썬을 배울 때 선생님께서 피보나치 수열의 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 < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

아니면 CACHE를 직접 작성할 수도 있습니다.

def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n < 2:
        return 1
    else:
        ls = [1, 1]
        for i in range(2, n):
            next_value = ls[-1] + ls[-2]
            ls.append(next_value)
            cache[i] = next_value
        cache[n-1] = ls[-1]
        return ls[-1]

위 내용은 피보나치 수열을 계산하기 위해 프로그램을 어디까지 최적화할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!