LRU缓存的最大大小如何确定？

Question

如果我们正在创建递归函数（比如返回斐波那契数列），并使用`lru_cache`，那么控制`maxsize`参数的真正因素是什么？

很明显，当计算每个项时，我们只需要最后两个项。但将`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)和fib1(n-2)）一起存储，但为什么结果不会立即替换最旧的项呢？fib1(n)是否在计算之前就已经放在缓存内存中？ 有没有办法查看lru_cache元素？也许这会有所帮助。

- Aziz

---

顺便提一下，有一种更快的分治算法可以用于斐波那契数列。https://www.nayuki.io/page/fast-fibonacci-algorithms - Nikos M.

回答你的问题，缓存大小和缓存失效通常更多地是一门艺术而非精确科学。通常没有已知的确切限制，试错法可以发现每种情况的最佳参数。 - Nikos M.

@Nikos M. 谢谢，这是一个很酷的方法，但它只适用于斐波那契数列。我希望能找到一种更通用的方法来指定所需的缓存内存... 比如说你有一个更复杂的函数，每次运行返回一个值列表而不是单个值... 正如你所说，试错可能是一个好方法... 谢谢。 - Aziz

顺便提一下：由于递归，您已经使用了O(n)的堆栈空间，因此仅针对斐波那契问题，在这里限制LRU缓存的大小没有太大意义... - Zack Light

Answer 1

你是对的，Fibonacci计算仅需要缓存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

- mbh86