Home >Backend Development >Python Tutorial >How Far You Can Optimize a Program to Compute the Fibonacci Sequence?
When I was learning Python, our teacher gave us a homework -- calculate the Nth number of Fibonacci Sequence.
I think it's very easy, so I write this code:
def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n - 1) + fib(n - 2)
Later, I know this kind of solution cost too much time.
I change the solution to iteration.
def fib(n): ls = [1,1] for i in range(2,n): ls.append(ls[i-1]+ls[i-2]) return ls[n-1]
I use matplotlib draw the time it cost:
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()
Result Here:
The time it cost is very short.
But I write fib(300000), cost 5.719049899998936 seconds. It's too long.
When I grow up, I learn CACHE, so I change the solution to use dict to store the result.
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)
Or we can write the CACHE by ourself.
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]
The above is the detailed content of How Far You Can Optimize a Program to Compute the Fibonacci Sequence?. For more information, please follow other related articles on the PHP Chinese website!