如果我们创建一个类似返回斐波那契数列的递归函数,并使用lru_cache
..真正的总督是什么max size
范围?
很明显,我们在计算每一项时只需要最后两项..但是设置maxsize
to 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
元素?也许这会有帮助。
你是对的,仅缓存 2 个值就足以进行斐波那契计算.
您的功能无法正常工作,因为递归调用未按正确顺序设置。在你的函数中添加一些打印语句,你就会理解它的行为。
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)
and fib(2)
. But fib(3)
needed fib(2)
and then fib(1)
,所以最后 2 个调用是fib(3)
and fib(1
)所以你需要再次重新计算fib(2)
.
所以你应该切换fib(n - 1)
and 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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)