Python中的递归、记忆和可变缺省参数

Question

“BASE”表示不只是使用LRU_Cache。所有这些都是“足够快的”--我不是在寻找最快的算法--但是时间让我吃惊，所以我希望我能学到一些关于Python是如何“工作”的东西。

def fibonacci(n):
    a, b = 0, 1
    if n in (a, b): return n
    for _ in range(n - 1):
        a, b = b, a + b
    return b

def fibonacci(n, memo={0:0, 1:1}):
    if len(memo) <= n:
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return memo[n]

def fib_seq():
    a, b = 0, 1
    yield a
    yield b
    while True:
        a, b = b, a + b
        yield b

def fibonacci(n):
    return next(x for (i, x) in enumerate(fib_seq()) if i == n)

loop: about 140 μs
memo: about 430 ns
genr: about 250 μs

现在很清楚了，我（和前面的许多人一样）只是偶然发现了Python的可变缺省参数。这种行为解释了执行速度的实际和明显的提高。

Answer 1

你所看到的是记忆的全部意义。第一次调用该函数时，memo缓存为空，并且必须递归。但下一次使用相同或更低的参数调用它时，答案已经在缓存中，因此它立即返回。如果您执行了数千个呼叫，那么您将第一个呼叫的时间摊销到所有其他呼叫中。这就是什么使memoization如此有用的优化，您只需支付成本第一次。

如果您想看看当缓存是新鲜的并且您必须执行所有递归时需要多长时间，那么您可以在基准调用中将初始缓存作为显式参数传递：

fibonacci(100, {0:0, 1:1})