python - 在生成斐波那契数列时使用装饰器应用内存

Question

Leetcode引入了一个memoization递归模板来计算斐波那契数

For the sake of comparison, we provide the implementation of Fibonacci number solution with memoization below.

As an exercise, you could try to make memoization more general and non-intrusive, i.e. applying memoization without changing the original function. (Hint: one can refer to a design pattern called decorator).

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

509. Fibonacci Number2

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0and 1. That is,

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

Given N, calculate F(N).

Example 1:

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

Example 2:

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

Example 3:

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

Note:

0 ≤ N ≤ 30.

内存解决方案

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

获得相对较好的分数:

Runtime: 36 ms, faster than 80.05% of Python3 online submissions forFibonacci Number.

Memory Usage: 13.1 MB, less than 5.02% of Python3 online submissions for Fibonacci Number.

教程中提到

As an exercise, you could try to make memoization more general and non-intrusive, i.e. applying memoization without changing the original function. (Hint: one can refer to a design pattern called decorator).

按照指南编写一个缓存装饰器。

@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，需要做很多手工工作，而且这个解决方案比非装饰器没有竞争力。

如何解决问题？

Answer 1

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