记忆化问题 - 我的备忘录字典比 lru_cache 表现得更好。为什么？

Question

我一直在玩记忆，lru_cache...我有一个简短的问题，为什么我的记忆代码运行比 lru_cache 好。

我的代码：

memo = {}
def fib(n): 
    if n == 0:
        return 0
    elif n < 2: 
        return 1
    else:
        if n not in memo:
            memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
print(fib(900))

lru_cache代码：

from functools import lru_cache


@lru_cache(maxsize=1000)
def fib(n):
    if n == 0:
        return 0
    elif n < 2:
        return 1
    else:
       return fib(n -1) + fib(n -2)
    
    
print(fib(499))

第二次我试图找到第 500 个 fib 数，我得到以下错误 lru_cache:

lk/Documents/VSCode/testing_zone/fibonacci_examples/fib_with_lru_cache.py
Traceback (most recent call last):
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 14, in <module>
    print(fib(500))
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1) + fib(n -2)
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1) + fib(n -2)
  File "c:\Users\lk\Documents\VSCode\testing_zone\fibonacci_examples\fib_with_lru_cache.py", line 11, in fib
    return fib(n -1) + fib(n -2)
  [Previous line repeated 496 more times]
RecursionError: maximum recursion depth exceeded

然而，在我运行陷入同样的错误之前，我可以在我的简单字典记忆中达到 900

lk/Documents/VSCode/testing_zone/fibonacci_examples/fib_with_memo.py
54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800

我的理解是 dict 和 lru_cache 的操作方式相同，它们引用 dict 或 lru_cache 以在调用 fib(n) 之前查看 n 是否在其中函数。

我的问题是为什么他们的表现不一样？我是否错误配置了代码，或者是否有额外的 optimizations/code 我需要与 lru_cache 一起使用？

lru_cache 必须工作，因为 fib(400) 几乎立即返回，如果装饰器不存在，则不会发生。

Answer 1

您的确切问题是 @lru_cache 引入了第二个函数调用。它确实在函数 fib.

周围放置了一个包装器

当您认为自己在调用 fib 时，实际上是在调用包装程序。它查看该值是否在其缓存中。如果是，则为 returns 的值；如果不是，它调用保存的 fib 原始定义，将返回值放入其缓存中，然后 returns 该值。

所以当你调用fib(500)时，你的函数调用深度是1000。你的记忆程序已经将它的缓存内联到函数体中，所以调用深度只有500。因此最大递归的错误。

您可以使用sys.getrecursionlimit()找出当前的递归限制。您可以使用 sys.setrecursionlimit().

修改限制

记忆化问题 - 我的备忘录字典比 lru_cache 表现得更好。为什么？

memoization question - My memo dict performs better than lru_cache. Why?

python

python-3.x

memoization