[toc]

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))

fib4(120) = 5358359254990966640871840
程序运行时间为: 0.004061222076416016 Seconds
fib4(120) = 5358359254990966640871840
程序运行时间为: 0.004450798034667969 Seconds
fib4(120) = 5358359254990966640871840
程序运行时间为: 0.004158735275268555 Seconds