Python中的递归，记忆和可变默认参数 [英] Recursion, memoization and mutable default arguments in Python

问题描述

基本"的含义不只是使用lru_cache.所有这些都是足够快"的-我并不是在寻找最快的算法-但是时间让我感到惊讶，所以我希望我可以学习一些关于Python工作"的方式.

"Base" meaning without just using lru_cache. All of these are "fast enough" -- I'm not looking for the fastest algorithm -- but the timings surprised me so I was hoping I could learn something about how Python "works".

简单循环(/尾递归):

Simple loop (/tail recursion):

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)

我希望第一个简单易行，它将是最快的.不是.尽管有递归和许多函数调用，但第二个是迄今为止最快的.第三个很酷，并使用现代"功能，但速度较慢，令人失望.(我很想在某些方面将生成器视为记忆的替代方法-因为他们记住了它们的状态-并且由于它们是用C实现的，所以我希望它们会更快.)

I expected the first, being dead simple, to be the fastest. It's not. The second is by far the fastest, despite the recursion and lots of function calls. The third is cool, and uses "modern" features, but is even slower, which is disappointing. (I was tempted to think of generators as in some ways an alternative to memoization -- since they remember their state -- and since they're implemented in C I was hoping they'd be faster.)

典型结果:

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

因此，任何人都可以特别说明为什么记忆比简单循环快一个数量级吗?

So can anyone explain, in particular, why memoization is an order of magnitude faster than a simple loop?

现在知道我(像我之前的许多人一样)只是偶然发现了Python的可变默认参数.此行为说明了执行速度的实际和表面上的收益.

Clear now that I have (like many before me) simply stumbled upon Python's mutable default arguments. This behavior explains the real and the apparent gains in execution speeds.

推荐答案

您所看到的是整个记忆的重点.第一次调用该函数时， memo 缓存为空，因此必须递归.但是，下次使用相同或较低的参数调用它时，答案已经在缓存中，因此它会立即返回.如果您执行了数千个通话，那么您将摊销第一个通话的时间，超过所有其他通话的时间.这就是使备忘录成为有用的优化的原因，您只需第一次支付费用.

What you're seeing is the whole point of memoization. The first time you call the function, the memo cache is empty and it has to recurse. But the next time you call it with the same or a lower parameter, the answer is already in the cache, so it returns immediately. if you perform thousands of calls, you're amortizing that first call's time over all the other calls. That's what makes memoization such a useful optimization, you only pay the cost the first time.

如果要查看刷新缓存需要多长时间，并且必须执行所有递归操作，则可以将初始缓存作为基准调用中的显式参数传递:

If you want to see how long it takes when the cache is fresh and you have to do all the recursions, you can pass the initial cache as an explicit argument in the benchmark call:

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

这篇关于Python中的递归，记忆和可变默认参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！