memoization问题-我的memo dict比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

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

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

lru_cache必须正常工作，因为fib(400)几乎是立即返回的，如果没有装饰器，就不会发生这种情况。

Answer 1

您的确切问题是@lru_cache引入了第二个函数调用。从字面上看，它在函数fib周围放置了一个包装器。

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

所以当你调用fib(500)时，你的函数调用深度是1000。您的memoization程序已将其缓存内联到函数体中，因此调用深度仅为500。因此，关于最大递归的错误。

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