Leetcode 引入了一个内存递归模板来计算斐波那契数
def fib(self, N):
"""
:type N: int
:rtype: int
"""
cache = {}
def recur_fib(N):
if N in cache:
return cache[N]
if N < 2:
result = N
else:
result = recur_fib(N-1) + recur_fib(N-2)
# put result in cache for later reference.
cache[N] = result
return result
return recur_fib(N)
使用模板解决509.Fibonacci Number - LeetCode
记忆化解决方案
class Solution:
def __init__(self):
self.cache = {}
def fib(self, N: int) -> int:
#memoization solution
if N < 0 or N == None: return None
if N in self.cache: return self.cache[N]
if N < 2:
self.cache[N] = N
return N
else:
res = self.fib(N-1) + self.fib(N-2)
self.cache[N] = res
return res
获得相对较好的分数:
教程提到
按照指导方针编写
cache
装饰器。@recur_cache
def fib(N):
#basic solution
if N < 0 or N == None : return None
if N < 2: return N
else:
return fib(N-1) + fib(N-2)
cache = {}
def recur_cache(func):
def wrapper(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
return wrapper
不幸的是,很难将
cache
放入装饰器中。如果将缓存重命名为
memo
,则应完成大量手动工作,并且解决方案与非装饰器 none 相比没有竞争力。怎么可能解决问题?
最佳答案
确保 fib
定义在 recur_cache
之后,并将 cache
的定义放在 recur_cache
中:
def recur_cache(func):
cache = {}
def wrapper(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
return wrapper
@recur_cache
def fib(N):
#basic solution
if N < 0 or N == None : return None
if N < 2: return N
else:
return fib(N-1) + fib(N-2)
为了使其适用于任何签名的函数(不仅仅是具有单个位置参数的函数),我们可以捕获调用的 *args 和 **kwargs 并将它们作为键存储在缓存中:
def recur_cache(func):
cache = {}
def wrapper(*args, **kwargs):
key = (args, frozenset(kwargs.items())) # dicts aren't hashable
if key not in cache:
cache[key] = func(*args, **kwargs)
return cache[key]
return wrapper
关于python - 生成斐波那契数时使用装饰器应用内存,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/55726137/