[如果我们正在创建一个类似递归函数的函数,该函数将返回斐波那契数列,并使用lru_cache
.. max size
参数的真正调节器是什么?
[很明显,在计算每一项时,我们只需要最后两项。但是将maxsize
设置为2
并运行第一个1000
计算将花费很多时间。
我尝试使用仅包含两个元素的缓存字典:
fib_cache = {0: 1, 1: 1}
def fib(n):
if n == 1:
val = 1
elif n == 2:
val = 1
elif n > 2:
val = fib_cache[0] + fib_cache[1]
fib_cache[0] = fib_cache[1]
fib_cache[1] = val
return val
然后,我使用lru_cache
运行类似的功能:
from functools import lru_cache
@lru_cache(maxsize=3)
def fib1(n):
if n == 1:
val = 1
elif n == 2:
val = 1
elif n > 2:
val = fib1(n - 1) + fib1(n - 2)
return val
我称每个计算的前1000次,结果在性能上是相同的。但是,我不确定如何指定maxsize
参数。我刚刚发现,对于此特定功能,需要2个年龄,而3个可以正常工作。我的猜测是它将存储结果fib1(n)
以及用于计算结果的最后两个项目fib1(n - 1) and fib1(n - 2)
,但是为什么不立即替换最旧的结果呢?在计算之前fib1(n)
是否在高速缓存中发生?有没有办法查看lru_cache
元素?也许这会有所帮助。
向功能添加一些打印内容,您将了解其行为。
from functools import lru_cache
@lru_cache(maxsize=2)
def fib(n):
print(f'calling fib({n})')
if n == 1:
val = 1
elif n == 2:
val = 1
elif n > 2:
val = fib(n - 1) + fib(n - 2)
print(f'fib({n}) is being computed')
return val
fib(5)
# calling fib(5)
# calling fib(4)
# calling fib(3)
# calling fib(2)
# fib(2) is being computed
# calling fib(1)
# fib(1) is being computed
# fib(3) is being computed
# calling fib(2)
# fib(2) is being computed
# fib(4) is being computed
# calling fib(3)
# calling fib(1)
# fib(1) is being computed
# fib(3) is being computed
# fib(5) is being computed
所以这里发生的是当您从fib(4)
计算时,它需要fib(3)
和fib(2)
。但是fib(3)
需要fib(2)
然后 fib(1)
,所以最后2个调用是fib(3)
和fib(1
),因此您需要再次重新计算fib(2)
。
因此您应该切换fib(n - 1)
和fib(n - 2)
以使其起作用:
@lru_cache(maxsize=2)
def fib(n):
if n == 1:
val = 1
elif n == 2:
val = 1
elif n > 2:
val = fib(n - 2) + fib(n - 1)
return val