时间戳

首页 > 解决方案 > 生成斐波那契数时使用装饰器应用记忆

python - 生成斐波那契数时使用装饰器应用记忆

问题描述

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 数 - LeetCode

  1. 斐波那契数 2

斐波那契数列，通常表示F(n)形成一个序列，称为斐波那契数列，使得每个数都是前两个数的和，从0和开始1。那是，

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

给定N，计算F(N)。

示例 1：

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

笔记：

0≤≤30 N。

记忆化解决方案

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

获得相对较好的分数：

运行时间：36 毫秒，比 80.05% 的 Python3 在线提交的斐波那契数要快。

内存使用：13.1 MB，少于 Python3 在线提交斐波那契数的 5.02%。

教程提到了

作为一个练习，您可以尝试使记忆更通用和非侵入性，即在不更改原始功能的情况下应用记忆。（提示：可以参考一种称为装饰器的设计模式）。

按照指南编写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，则需要完成大量手动工作，并且解决方案比非装饰器无竞争力。

怎么可能解决问题？

标签： pythondecorator

解决方案

确保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

推荐阅读