如何确定lru_cache所需的最大尺寸？

Question

如果我们创建一个递归函数，比如返回斐波纳契序列的递归函数，并使用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元素吗？也许这会有帮助。

Answer 1

您是对的，仅缓存2个值就足以满足Fibonacci计算的需要。

您的函数不能正常工作，因为递归调用没有按照良好的顺序设置。将一些打印语句添加到您的函数中，您将了解它的行为。

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)，所以最后两个调用是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