斐波那契数列的高效计算 [英] Efficient calculation of Fibonacci series
问题描述
我工作的一个项目欧拉的问题：一个关于偶数Fibonacci数的总和。
I'm working on a Project Euler problem: the one about the sum of the even Fibonacci numbers.
我的code：
def Fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]
的问题的解决方案可以容易地通过印刷和（list2中）找到。然而，它采取了很多时间来拿出list2中我猜。有没有什么办法，使这个更快？或者是好的，即使这样......
The problem's solution can be easily found by printing sum(list2). However, it is taking a lot of time to come up with the list2 I'm guessing. Is there any way to make this faster? Or is it okay even this way...
（问题：通过考虑其值不超过4亿元，找到连值项的和斐波那契序列条款）
(the problem: By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.)
推荐答案
是的。原始递归解决方案所花费的时间的很多的。这样做的原因是，对于计算出的每一个号码，它需要计算所有previous号码不止一次。看看下面的图片。
Yes. The primitive recursive solution takes a lot of time. The reason for this is that for each number calculated, it needs to calculate all the previous numbers more than once. Take a look at the following image.
它重新presents计算斐波那契（5）与你的函数。正如你所看到的，它计算的值斐波那契（2）三次，和值斐波那契（1）五次。这只是变得越来越坏了更高的要计算的数量。
It represents calculating Fibonacci(5) with your function. As you can see, it computes the value of Fibonacci(2) three times, and the value of Fibonacci(1) five times. That just gets worse and worse the higher the number you want to compute.
是什么使得它的甚至的要命的是，就在你列表计算每个Fibonacci数，你不使用你的加快计算知识previous号码 - 你计算从头开始。每个号码
What makes it even worse is that with each fibonacci number you calculate in your list, you don't use the previous numbers you have knowledge of to speed up the computation – you compute each number "from scratch."
有几个选项，使这个速度快：
There are a few options to make this faster:
最简单的方法是只创建斐波那契数的清单给你想要的号码。如果你这样做，你从下往上建立或可以这么说，你可以重复使用previous数字创造下一个。如果你有斐波那契数字列表 [0，1，1，2，3] ，您可以使用最后两个数字在该列表中创建一个号码。
The easiest way is to just create a list of fibonacci numbers up to the number you want. If you do that, you build "from the bottom up" or so to speak, and you can reuse previous numbers to create the next one. If you have a list of the fibonacci numbers [0, 1, 1, 2, 3], you can use the last two numbers in that list to create the next number.
此方法将是这个样子：
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs
...
然后你可以通过执行获得第20斐波那契数
Then you can get the first 20 fibonacci numbers by doing
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
或者你可以通过执行得到的前40个列表中的第17 Fibonacci数
Or you can get the 17th fibonacci number from a list of the first 40 by doing
>>> fib_to(40)[17]
1597
2。记忆化（相对先进的技术）
另一种选择，使其更快的存在，但它是一个更复杂一点为好。由于您的问题是，你重新计算你已经计算出的值，你也可以选择，以节省您已经计算在字典中的值，并尝试从您重新计算之前得到他们。这就是所谓的记忆化的。它可能看起来是这样的：
2. Memoization (relatively advanced technique)
Another alternative to make it faster exists, but it is a little more complicated as well. Since your problem is that you re-compute values you have already computed, you can instead choose to save the values you have already computed in a dict, and try to get them from that before you recompute them. This is called memoization. It may look something like this:
>>> def fib(n, computed = {0: 0, 1: 1}):
... if n not in computed:
... computed[n] = fib(n-1, computed) + fib(n-2, computed)
... return computed[n]
这可以计算大的斐波那契数在微风：
This allows you to compute big fibonacci numbers in a breeze:
>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
这其实是这样一个共同的技术，Python 3中包括一个装饰来为你做这个。我present给你，自动记忆化！
This is in fact such a common technique that Python 3 includes a decorator to do this for you. I present to you, automatic memoization!
import functools
@functools.lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
这的确pretty的同样的事情为previous功能，但所有的计算东西的 lru_cache处理装饰。
This does pretty much the same thing as the previous function, but with all the computed stuff handled by the lru_cache decorator.
第三种方法，所建议的米奇，是仅计算时没有在列表中保存中间值。你可以想象这样
A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing
>>> def fib(n):
... a, b = 0, 1
... for _ in range(n):
... a, b = b, a+b
... return a
我不建议这最后的两个方法，如果你的目标是要建立Fibonacci数的列表的。 fib_to（100）将是很多的比更快[FIB（N）为N的范围内（101） ] ，因为后者，你仍然可以计算从无到有列表中每个数字的问题。
I don't recommend these last two methods if your goal is to create a list of fibonacci numbers. fib_to(100) is going to be a lot faster than [fib(n) for n in range(101)] because with the latter, you still get the problem of computing each number in the list from scratch.
这篇关于斐波那契数列的高效计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
