Python 斐波那契数列的高效计算
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18172257/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficient calculation of Fibonacci series
提问by user65165
I'm working on a Project Eulerproblem: the one about the sum of the even Fibonacci numbers.
我正在研究一个Project Euler问题：关于偶数斐波那契数之和的问题。
My 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]
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...
通过打印 sum(list2) 可以很容易地找到问题的解决方案。但是，我猜想列出 list2 需要花费很多时间。有什么办法可以让它更快吗？或者这样也可以吗...
(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.)
（问题：通过考虑 Fibonacci 数列中值不超过 400 万的项，找到偶数值项的总和。）
采纳答案by kqr
Yes. The primitive recursive solution takes a lotof 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.
是的。原始递归解决方案需要很多时间。这样做的原因是，对于计算的每个数字，它需要多次计算所有先前的数字。看看下面的图片。
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(5)用你的函数计算。如您所见，它计算了Fibonacci(2)三倍的值和Fibonacci(1)五倍的值。你想要计算的数字越大，情况就会变得越来越糟。
What makes it evenworse 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."
是什么使得它甚至更糟的是，就在你列表计算每个Fibonacci数，你不使用你的知识，以前的数字来加速计算-你计算每个号码“从头开始”。
There are a few options to make this faster:
有几个选项可以加快速度：
1. Create a list "from the bottom up"
1.创建一个“自下而上”的列表
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.
最简单的方法是创建一个斐波那契数字列表，直到您想要的数字为止。如果你这样做，你可以“自下而上”构建，可以重复使用以前的数字来创建下一个。如果您有一个斐波那契数字列表[0, 1, 1, 2, 3]，您可以使用该列表中的最后两个数字来创建下一个数字。
This approach would look something like this:
这种方法看起来像这样：
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs
...
Then you can get the first 20 fibonacci numbers by doing
然后你可以通过做得到前 20 个斐波那契数
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Or you can get the 17th fibonacci number from a list of the first 40 by doing
或者您可以通过执行以下操作从前 40 个列表中获取第 17 个斐波那契数
>>> fib_to(40)[17]
1597
2. Memoization (relatively advanced technique)
2.记忆化（比较先进的技术）
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:
存在另一种使其更快的替代方法，但它也有点复杂。由于您的问题是重新计算已经计算过的值，因此您可以选择将已经计算过的值保存在 dict 中，并在重新计算之前尝试从中获取它们。这称为记忆。它可能看起来像这样：
>>> 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
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!
这实际上是一种常见的技术，Python 3 包含一个装饰器来为您执行此操作。我呈现给你，自动记忆！
import functools
@functools.lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
This does pretty much the same thing as the previous function, but with all the computedstuff handled by the lru_cachedecorator.
这与前面的函数做的事情几乎一样，但是所有的computed东西都由lru_cache装饰器处理。
3. Just count up (a na?ve iterative solution)
3. 向上计数（一个天真的迭代解决方案）
A third method, as suggested by Mitch, is to just count up without saving the intermediary values in a list. You could imagine doing
Mitch 建议的第三种方法是直接计数而不将中间值保存在列表中。你可以想象做
>>> def fib(n):
... a, b = 0, 1
... for _ in range(n):
... a, b = b, a+b
... return a
I don't recommend these last two methods if your goal is to create a listof fibonacci numbers. fib_to(100)is going to be a lotfaster 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.
如果您的目标是创建斐波那契数列，我不推荐最后两种方法。fib_to(100)将是一个很大的速度比[fib(n) for n in range(101)]，因为后者，你仍然可以计算从无到有列表中每个数字的问题。
回答by ChrisProsser
Any problems like this will take a long time to run if there are a lot of levels of recursion. The recursive definition is good for coding the problem in a way that can be easily understood, but if you need it to run faster an iterative solution such as the answer in this threadwill be much quicker.
如果有很多级别的递归，任何像这样的问题都需要很长时间才能运行。递归定义有利于以易于理解的方式对问题进行编码，但如果您需要它运行得更快，则迭代解决方案（例如此线程中的答案）会更快。
回答by Paulo Bu
Recursively calculating Fibonacci will be most inefficient than doing iteratively. My recommendation is:
递归计算斐波那契将比迭代计算效率最低。我的建议是：
Take the time to create a Fibonacciclass as an iterator, and do the calculations independently for each element in the index, maybe with some @memoizedecorator(and also here) to cache all previous calculations.
花时间创建一个Fibonacci类作为迭代器，并为索引中的每个元素独立进行计算，也许使用一些@memoize装饰器（也在这里）来缓存所有先前的计算。
Hope this helps!
希望这可以帮助！
回答by Lukasz
kqr's solution nr 2 is my definite favourite.
However in this specific case we are loosing all our calculations between consequent calls within the list comprehension:
kqr的解决方案 nr 2 是我最喜欢的。
但是，在这种特定情况下，我们会丢失列表推导式中后续调用之间的所有计算：
list2 = [i for i in list1 if fib(i) % 2 == 0]
, so I decided to go one step further and memoize it between loop steps as follows:
，所以我决定更进一步，在循环步骤之间记住它，如下所示：
def cache_fib(ff):
comp = {0: 0, 1: 1}
def fib_cached(n, computed=comp):
return ff(n, computed)
return fib_cached
@cache_fib
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]
回答by Manoj Nawathale
int count=0;
void fibbo(int,int);
void main()
{
fibbo(0,1);
getch();
}
void fibbo(int a,int b)
{
count++;
printf(" %d ",a);
if(count<=10)
fibbo(b,a+b);
else
return;
}
回答by Piotr Dabkowski
This is a very fast algorithm and it can find n-th Fibonacci number much faster than simple iterative approach presented in other answers, it is quite advanced though:
这是一个非常快的算法，它可以比其他答案中提出的简单迭代方法更快地找到第 n 个斐波那契数，但它非常先进：
def fib(n):
v1, v2, v3 = 1, 1, 0 # initialise a matrix [[1,1],[1,0]]
for rec in bin(n)[3:]: # perform fast exponentiation of the matrix (quickly raise it to the nth power)
calc = v2*v2
v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
if rec=='1': v1, v2, v3 = v1+v2, v1, v2
return v2
You can read some more about involved math here.
您可以在此处阅读更多有关涉及数学的内容。
回答by Nicholas Hamilton
Solution in R, benchmark calculates 1 to 1000th Fibonacci number series in 1.9 seconds. Would be much faster in C++ or Fortran, in fact, since writing the initial post, I wrote an equivalent function in C++ which completed in an impressive 0.0033 seconds, even python completed in 0.3 seconds.
R 中的解决方案，基准测试在 1.9 秒内计算第 1 到 1000 个斐波那契数列。实际上，在 C++ 或 Fortran 中会快得多，事实上，自从写第一篇文章以来，我在 C++ 中编写了一个等效的函数，它在 0.0033 秒内完成，甚至 python 在 0.3 秒内完成。
#Calculate Fibonnaci Sequence
fib <- function(n){
if(n <= 2)
return(as.integer(as.logical(n)))
k = as.integer(n/2)
a = fib(k + 1)
b = fib(k)
if(n %% 2 == 1)
return(a*a + b*b)
return(b*(2*a - b))
}
#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
res = sapply(0:abs(nmax),fib)
if(doPrint)
print(paste(res,collapse=","))
return(res)
}
#Benchmark
system.time(doFib(1000))
#user system elapsed
# 1.874 0.007 1.892
回答by Stefan Gruenwald
One fast way is to calculate the fib(n/2) number recursively:
一种快速的方法是递归计算 fib(n/2) 数：
fibs = {0: 0, 1: 1}
def fib(n):
if n in fibs: return fibs[n]
if n % 2 == 0:
fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
return fibs[n]
else:
fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
return fibs[n]
from time import time
s=time()
print fib(1000000)
print time()-s
回答by rohansumant
Haskell 1 liner :-
Haskell 1 班轮：-
fibs = 0 : (f 1 1) where f a b = a : f b (a+b)
This code is extremely efficient and calculates Fibonacci numbers up to (10^1000) in less than a second !
This code will also be useful for this problemin Project Euler.
这段代码非常高效，可以10^1000在不到一秒的时间内计算出高达 ( ) 的斐波那契数列！此代码也将用于解决Project Euler 中的此问题。
回答by greybeard
To find the sum of the first neven-valued fibonacci numbers directly, put 3n + 2in your favourite method to efficiently compute a single fibonacci number, decrement by one and divide by two (fib((3*n+2) - 1)/2)). How did math dummies survive before OEIS?
要直接找到第一个n偶数值斐波那契数的总和，请输入3n + 2您最喜欢的方法来有效地计算单个斐波那契数，减一并除以二 ( fib((3*n+2) - 1)/2))。在OEIS之前，数学傻瓜是如何生存的？
