파이썬을 배울 때 선생님께서 피보나치 수열의 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!