如何确定lru_cache 所需的maxsize？

Question

如果我们正在创建一个类似于 return 斐波那契数列的递归函数，并使用 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 个值就足以进行斐波那契计算。

您的函数无法正常工作，因为递归调用的设置顺序不正确。在您的函数中添加一些打印语句，您将了解它的行为。

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

如何确定lru_cache 所需的maxsize？

How to determine the required maxsize of lru_cache?

python

caching

memoization