Project Euler #2 Python 3.5 延迟帮助

Question

我是编码新手，正在尝试做项目欧拉练习来提高我的编码知识。关于 Project Euler #2，我遇到过几种解决方案。

但是，我想知道为什么我的代码的计算时间比我找到的解决方案要长得多。

如果有人能指导我了解两者之间的区别，我将不胜感激。

我的代码：

def fib(n):
if n==0:
    return 0
elif n == 1:
    return 1
else:
    f=fib(n-1)+fib(n-2)
    return f

i=0
store=[]
while fib(i)<=4000000:
    i += 1
    if fib(i)%2 == 0:
        store.append(fib(i))

print('The total is: '+str(sum(store)))

我找到的在线解决方案：

a = 1
b = 2
s = 0
while b <= 4000000:
if not b % 2:
    s += b
a, b = b, a + b
print(s)

Answer 1

要计算fib(10)，用你的实现：

fib(10) = fib(9) + fib(8)

其中fib(9)是递归计算的：

fib(9) = fib(8) + fib(7)

看到问题了吗？ fib(8)的结果要计算两次！进一步扩展表达式（例如，得到fib(8)的结果），当数字很大时，冗余计算是巨大的。

递归本身不是问题，但您必须存储较小的斐波那契数的结果，而不是不断地计算相同的表达式。一种可能的解决方案是使用字典来存储中间结果。

Answer 2

您正在对函数使用递归调用，而另一个解决方案使用普通迭代循环。

进行函数调用必然会产生一些调用和返回的开销。对于更大数量的 n，您将有很多这样的函数调用。

一遍又一遍地附加到列表并对其求和可能也比通过累加器执行此操作慢。

Answer 3

你的解决方案每次进入你的 while 循环时都会调用一个递归函数（有 2 次递归）。然后在循环中再次运行相同的功能。另一个解决方案只添加数字然后进行排列。我猜你并不真的需要斐波那契数列，但如果你坚持使用它，运行只用一次并保存结果，而不是重新运行ing 它。另外，您存储所有结果并在最后求和。这也（不仅）消耗了一点时间，也许您不需要存储中间结果。

Answer 4

正如其他几个答案所指出的，递归导致您的 fib() 函数被调用得非常频繁，实际上是 111 561 532 次。通过添加计数器很容易看出这一点：

count = 0

def fib(n):
    global count
    count += 1

    if n==0:

# the rest of your program

print(count)

有两种方法可以解决这个问题；将您的程序重写为迭代而不是递归（就像您发布的其他解决方案一样），或者缓存来自 fib().

的中间结果

看，你调用 fib(8)，它又必须调用 fib(7) 和 fib(6)，等等。仅仅计算 fib(8) 需要 67 次调用 fib()!

但稍后，当您调用 fib(9) 时，也调用 fib(8)，它必须重新完成所有工作（另外 67 次调用fib())。这很快就会失控。如果fib()能记住它已经计算过fib(8)并记住结果就更好了。这称为缓存或记忆。

幸运的是，Python 的标准库有一个专门用于此目的的装饰器，functools.lru_cache:

from functools import lru_cache

@lru_cache()
def fib(n):
    if n==0:

...

在我的计算机上，您的程序执行从 27 秒内的 111 561 532 次 fib() 调用变为 0.028 秒内的 35 次调用。

Project Euler #2 Python 3.5 延迟帮助

Project Euler #2 Python 3.5 Help on Latency

python

fibonacci

python-3.x