目录
0. 普通斐波那契
import time
start = time.time()
def fib0(n: int) -> int:
if n < 2:
return n
return fib0(n-1) + fib0(n-2)
print("fib0(40) = ", fib0(40))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
fib0(40) = 102334155
程序运行时间为: 29.292827367782593 Seconds
1. 结果缓存
每次计算任务完成后就把结果保存起来,这样在下次需要时即可直接检索出结果,而不需要一而再再而三地重复计算
from typing import Dict
import time
start = time.time()
memo: Dict[int, int] = {0: 0, 1: 1}
def fib1(n: int) -> int:
if n not in memo:
memo[n] = fib1(n-1) + fib1(n-2)
return memo[n]
print("fib1(120) = ", fib1(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
fib1(120) = 5358359254990966640871840
程序运行时间为: 0.005672931671142578 Seconds
fib1(120) = 5358359254990966640871840
程序运行时间为: 0.00408172607421875 Seconds
fib1(120) = 5358359254990966640871840
程序运行时间为: 0.004380702972412109 Seconds
2. 自动化结果缓存
- 每次用新的参数执行fib()时,该装饰器就会把返回值缓存起来。以后再用相同的参数调用fib()时,都会从缓存中读取该参数对应的fib()之前的返回值并返回
- @lru_cache的maxsize属性表示对所装饰的函数最多应该缓存多少次最近的调用结果,如果将其设置为None就表示没有限制
Cache replacement policies
from functools import lru_cache
import time
start = time.time()
@lru_cache(maxsize=None)
def fib2(n: int) -> int:
if n < 2:
return n
return fib2(n-1) + fib2(n-2)
print("fib2(120) = ", fib2(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
fib2(120) = 5358359254990966640871840
程序运行时间为: 6.771087646484375e-05 Seconds
fib2(120) = 5358359254990966640871840
程序运行时间为: 7.05718994140625e-05 Seconds
fib2(120) = 5358359254990966640871840
程序运行时间为: 7.677078247070312e-05 Seconds
3. 迭代
import time
start = time.time()
def fib3(n: int) -> int:
if n == 0: return 0
last: int = 0
next: int = 1
for _ in range(1, n):
last, next = next, last+next
return next
print("fib3(120) = ", fib3(120))
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
fib3(120) = 5358359254990966640871840
程序运行时间为: 1.5020370483398438e-05 Seconds
fib3(120) = 5358359254990966640871840
程序运行时间为: 1.33514404296875e-05 Seconds
fib3(120) = 5358359254990966640871840
程序运行时间为: 1.430511474609375e-05 Seconds
4. 生成器
目前为止,已完成的这些函数都只能输出斐波那契序列中的单个值。如果要将到某个值之前的整个序列输出,又该怎么做呢?用yield语句很容易就能把fib5()转换为Python生成器。在对生成器进行迭代时,每轮迭代都会用yield语句从斐波那契序列中吐出一个值
from typing import Generator
import time
start = time.time()
def fib4(n: int) -> Generator[int, None, None]:
yield 0
if n > 0: yield 1
last: int = 0
next: int = 1
for _ in range(1, n):
last, next = next, last+next
yield next
res = [_ for _ in fib4(120)]
print("fib4(120) = ", res[120])
end = time.time()
print('程序运行时间为: %s Seconds' % (end-start))
标签:120,数列,程序运行,5358359254990966640871840,Seconds,斐波,int,time,那契 From: https://www.cnblogs.com/Knight02/p/fib.htmlfib4(120) = 5358359254990966640871840
程序运行时间为: 0.004061222076416016 Seconds
fib4(120) = 5358359254990966640871840
程序运行时间为: 0.004450798034667969 Seconds
fib4(120) = 5358359254990966640871840
程序运行时间为: 0.004158735275268555 Seconds