python 中的记忆斐波那契算法

Question

我有这种记忆技术来减少获取斐波那契数列的调用次数：

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
        return memo[n]


def fib1(n):
    memo = {0:1, 1:1}
    return fastFib(n, memo)


numCalls = 0
n = 6
res = fib1(n)
print 'fib of', n,'=', res, 'numCalls = ', numCalls

但我被困在这里：memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo) 和这里 memo = {0:1, 1:1}。每次我想得到一个号码的谎言时，它如何准确地减少呼叫次数？

Answer 1

你应该 return memo[n] 总是，不仅仅是在不安全的查找（fastFib() 的最后一行）：

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    #this should be outside of the if clause:
    return memo[n] #<<<<<< THIS

这样减少了调用次数，因为对于 n 的每个值，您实际上最多计算和递归一次，将递归调用次数限制为 O(n)（上限2n 次调用），而不是一遍又一遍地重新计算相同的值，有效地进行指数级递归调用。

fib(5) 的一个小例子，其中每一行都是一个递归调用：

天真的方法：

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) = 
3 + f(1) + f(0) + f(3) = 
3 + 1 + f(0) + f(3) = 
5 + f(3) = 
5 + f(2) + f(1)  =
5 + f(1) + f(0) + f(1) =
5 + 1 + f(0) + f(1) =
5 + 2 + f(1) =
8

现在，如果你使用 memoization，你不需要重新计算很多东西（比如 f(2)，计算了 3 次）你会得到：

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =  {f(2) is already known}
3 + 2 + f(3) = {f(3) is already known}
5 + 3  = 
8

如你所见，第二个比第一个短，数字越大(n)，这个差异就越大。

Answer 2

可以使用 functools 库在 Python 3.2+

中完成

import functools

@functools.lru_cache(maxsize=None) #128 by default
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Answer 3

以下方法使用最小缓存大小（2 个条目）同时还提供 O(n) 渐近：

from itertools import islice
def fibs():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def fib(n):
    return next(islice(fibs(), n-1, None))

此实现来自斐波那契的经典核心递归定义（Haskell 的 https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation）。

有关更直接的（核心递归）翻译，请参阅 https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce。

Answer 4

可以在单个 class 或如下函数中完成

class Solution:
    def __init__(self):
        # initialize memo
        self.memo = {}


    def fib(self, n: int) -> int:
        # base case
        if n < 2:
            return n

        # check if fib(n) is already in memo - f(n) was calculated before
        if n in self.memo:
            return self.memo[n]
        else:
            f = self.fib(n - 1) + self.fib(n - 2)

        # store the value of fib(n) when calculated 
        self.memo[n] = f 
   
        return f

Answer 5

不使用额外库或使用全局变量的另一种解决方案：

def fib(n, memo):
    try:
        if memo[n]:
            # return memoized value
            return memo[n]
    except IndexError:
        pass

    if n == 1 or n == 2:
        # memoizing base cases
        result = 1
        memo.insert(0, 0)
        memo.insert(1, result)
        memo.insert(2, result)

    else:
        result = fib(n-1, memo) + fib(n-2, memo)
        memo.insert(n, result)

    return result

print(fib(8, []))

python 中的记忆斐波那契算法

Memoization fibonacci algorithm in python

python

algorithm

memoization