“基础”意味着不使用 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)
我预计第一个非常简单,是最快的。它不是。第二个是迄今为止最快的,尽管有递归和大量函数调用。第三个很酷,使用了“现代”功能,但速度更慢,令人失望。 (我很想在某些方面将生成器视为内存的替代方案——因为它们会记住它们的状态——而且由于它们是用 C 语言实现的,我希望它们会更快。)
典型结果:
loop: about 140 μs
memo: about 430 ns
genr: about 250 μs
那么谁能特别解释一下为什么内存比简单循环快一个数量级?
编辑:
现在很清楚,我(像我之前的许多人一样)只是偶然发现了 Python 的可变默认参数。这种行为解释了执行速度的实际和明显的提高。
最佳答案
您看到的是内存的全部意义。第一次调用该函数时,memo
缓存为空,必须递归。但是下次你用相同或更小的参数调用它时,答案已经在缓存中,所以它会立即返回。如果您执行了数千次调用,那么您就是在将第一个调用的时间分摊到所有其他调用上。这就是使记忆化成为如此有用的优化的原因,您只需支付第一次费用。
如果您想查看缓存刷新时需要多长时间并且您必须执行所有递归,您可以在基准调用中将初始缓存作为显式参数传递:
fibonacci(100, {0:0, 1:1})
关于python - Python 中的递归、内存和可变默认参数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55068876/