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/

10-12 14:27
查看更多