python 快速实现 斐波那波数列 空间换时间lru_cach

斐波那波数列

python中经常实现的方法是通过递归进行调用：

递归调用的原理是每次都会重新计算a(x-1)和a(x-2)的值，但是我们使用缓存就可以将这个值进行缓存起来，在进行下次调用的时候会自动进行加载。
这也就是以空间换时间的概念。

def a(x):
    if x == 0 or x == 1:
        return x
    return a(x - 1) + a(x - 2)
time1 = time.time()
b = a(30)
print(b)
time2 = time.time()
print(time2 - time1)

结果为：

102334155
44.24778628349304

我们发现py是十分慢的

使用缓存

import time
from functools import lru_cache
@lru_cache()
def a(x):
    if x == 0 or x == 1:
        return x
    return a(x - 1) + a(x - 2)
time1 = time.time()
b = a(40)
print(b)
time2 = time.time()
print(time2 - time1)

结果为:

102334155
0.0  # 太快忽略为0

手动实现缓存

这里能够比较直观的看出来缓存的原理

import time
def cach(func):
    cach1 = {}
    def get_chce(x):
        if x not in cach1:
            cach1[x] = func(x)
        return cach1[x]
    return get_chce
@cach
def a(x):
    if x == 0 or x == 1:
        return x
    return a(x - 1) + a(x - 2)
time1 = time.time()
b = a(30)
print(b)
time2 = time.time()
print(time2 - time1)

结果还是如此优秀：

102334155
0.0