Fibonacci系列的有效计算

Question

我正在研究一个Project Euler问题:关于偶数Fibonacci数的总和问题.

我的代码:

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]

通过打印sum(list2)可以很容易地找到问题的解决方案.但是,我猜测它需要花费大量时间来提出list2.有没有办法让这更快？或者这样就可以了......

(问题:通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和.)

Answer 1

是.原始递归解决方案需要花费大量时间.这样做的原因是,对于计算的每个数字,它需要多次计算所有先前的数字.看看下面的图片.

它代表Fibonacci(5)用你的功能计算.如您所见,它计算Fibonacci(2)三次的值,并计算五次的值Fibonacci(1).只是越来越差,你想要计算的数字越高.

是什么使得它甚至更糟的是,就在你列表计算每个Fibonacci数,你不使用你的加快计算知识以前的号码-你计算每个号码"从头开始".

有几个选项可以加快速度:

1."自下而上"创建一个列表

最简单的方法是创建一个斐波纳契数列表,最多可达到您想要的数字.如果你这样做,你可以"自下而上"构建或者说,你可以重复使用以前的数字来创建下一个数字.如果您有斐波那契数字列表,则[0, 1, 1, 2, 3]可以使用该列表中的最后两个数字来创建下一个数字.

这种方法看起来像这样:

>>> def fib_to(n):
...     fibs = [0, 1]
...     for i in range(2, n+1):
...         fibs.append(fibs[-1] + fibs[-2])
...     return fibs
...

然后你就可以得到前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]

或者你可以从前40个列表中得到第17个斐波纳契数

>>> fib_to(40)[17]
1597

2.记忆(相对先进的技术)

另一种使其更快的替代方案存在,但它也有点复杂.由于您的问题是您重新计算已经计算的值,因此您可以选择将已经计算的值保存在dict中,并在重新计算之前尝试从中获取它们.这称为memoization.它可能看起来像这样:

>>> 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]

这使您可以轻松计算大的斐波那契数字:

>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675

事实上,这是一种常见的技术,Python 3包含一个装饰器来为您完成此操作.我给你,自动记忆!

import functools

@functools.lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

这与前一个函数几乎完全相同,但所有computed东西都由lru_cache装饰器处理.

3.算上(一个天真的迭代解决方案)

Mitch建议的第三种方法是在不保存列表中的中间值的情况下进行计数.你可以想象做

>>> def fib(n):
...     a, b = 0, 1
...     for _ in range(n):
...         a, b = b, a+b
...     return a

如果您的目标是创建斐波纳契数列表,我不建议使用最后两种方法.fib_to(100)将是一个很大的速度比[fib(n) for n in range(101)],因为后者,你仍然可以计算从无到有列表中每个数字的问题.

Answer 2

这是一个非常快速的算法,它可以比其他答案中提供的简单迭代方法更快地找到第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

你可以在这里阅读更多有关数学的内容.

Answer 3

Python没有优化尾递归,因此这里介绍的大多数解决方案都会失败,Error: maximum recursion depth exceeded in comparison如果n太大(并且大,我的意思是1000).

递归限制可以增加,但它会使Python在操作系统中的堆栈溢出时崩溃.

请注意fib_memo/ fib_local和fib_lru/ 之间的性能差异fib_local_exc:LRU缓存要慢得多,甚至没有完成,因为它已经为n = ~500产生运行时错误:

import functools
from time import clock
#import sys
#sys.setrecursionlimit()

@functools.lru_cache(None)
def fib_lru(n):
    if n < 2:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

def fib_memo(n, computed = {0: 0, 1: 1}):
    if n not in computed:
        computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
    return computed[n]

def fib_local(n):
    computed = {0: 0, 1: 1}
    def fib_inner(n):
        if n not in computed:
            computed[n] = fib_inner(n-1) + fib_inner(n-2)
        return computed[n]
    return fib_inner(n)

def fib_local_exc(n):
    computed = {0: 0, 1: 1}
    def fib_inner_x(n):
        try:
            computed[n]
        except KeyError:
            computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
        return computed[n]

    return fib_inner_x(n)

def fib_iter(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def benchmark(n, *args):
    print("-" * 80)
    for func in args:
        print(func.__name__)
        start = clock()
        try:
            ret = func(n)
            #print("Result:", ret)
        except RuntimeError as e:
            print("Error:", e)
        print("Time:", "{:.8f}".format(clock() - start))
        print()

benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)

结果:

fib_iter
Time: 0.00008168

fib_memo
Time: 0.00048622

fib_local
Time: 0.00044645

fib_local_exc
Time: 0.00146036

fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552

迭代解决方案是迄今为止最快的,即使n=100k(0.162秒)也不会破坏堆栈.它确实没有返回中间斐波纳契数.

如果你想计算n偶数Fibonacci数,你可以调整迭代方法,如下所示:

def fib_even_iter(n):
    a, b = 0, 1
    c = 1
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            c += 1
    return a

或者,如果您对途中的每个偶数感兴趣,请使用生成器:

def fib_even_gen(n):
    a, b = 0, 1
    c = 1
    yield a
    while c < n:
        a, b = b, a + b
        if a % 2 == 0:
            yield a
            c += 1
    return a

for i, f in enumerate(fib_even_gen(100), 1):
    print("{:3d}.  {:d}".format(i, f))

结果:

  1.  0
  2.  2
  3.  8
  4.  34
  5.  144
  6.  610
  7.  2584
  8.  10946
  9.  46368
 10.  196418
 11.  832040
 12.  3524578
 13.  14930352
 14.  63245986
 15.  267914296
 16.  1134903170
 17.  4807526976
 18.  20365011074
 19.  86267571272
 20.  365435296162
 21.  1548008755920
 22.  6557470319842
 23.  27777890035288
 24.  117669030460994
 25.  498454011879264
 26.  2111485077978050
 27.  8944394323791464
 28.  37889062373143906
 29.  160500643816367088
 30.  679891637638612258
 31.  2880067194370816120
 32.  12200160415121876738
 33.  51680708854858323072
 34.  218922995834555169026
 35.  927372692193078999176
 36.  3928413764606871165730
 37.  16641027750620563662096
 38.  70492524767089125814114
 39.  298611126818977066918552
 40.  1264937032042997393488322
 41.  5358359254990966640871840
 42.  22698374052006863956975682
 43.  96151855463018422468774568
 44.  407305795904080553832073954
 45.  1725375039079340637797070384
 46.  7308805952221443105020355490
 47.  30960598847965113057878492344
 48.  131151201344081895336534324866
 49.  555565404224292694404015791808
 50.  2353412818241252672952597492098
 51.  9969216677189303386214405760200
 52.  42230279526998466217810220532898
 53.  178890334785183168257455287891792
 54.  757791618667731139247631372100066
 55.  3210056809456107725247980776292056
 56.  13598018856492162040239554477268290
 57.  57602132235424755886206198685365216
 58.  244006547798191185585064349218729154
 59.  1033628323428189498226463595560281832
 60.  4378519841510949178490918731459856482
 61.  18547707689471986212190138521399707760
 62.  78569350599398894027251472817058687522
 63.  332825110087067562321196029789634457848
 64.  1409869790947669143312035591975596518914
 65.  5972304273877744135569338397692020533504
 66.  25299086886458645685589389182743678652930
 67.  107168651819712326877926895128666735145224
 68.  453973694165307953197296969697410619233826
 69.  1923063428480944139667114773918309212080528
 70.  8146227408089084511865756065370647467555938
 71.  34507973060837282187130139035400899082304280
 72.  146178119651438213260386312206974243796773058
 73.  619220451666590135228675387863297874269396512
 74.  2623059926317798754175087863660165740874359106
 75.  11111460156937785151929026842503960837766832936
 76.  47068900554068939361891195233676009091941690850
 77.  199387062373213542599493807777207997205533596336
 78.  844617150046923109759866426342507997914076076194
 79.  3577855662560905981638959513147239988861837901112
 80.  15156039800290547036315704478931467953361427680642
 81.  64202014863723094126901777428873111802307548623680
 82.  271964099255182923543922814194423915162591622175362
 83.  1152058411884454788302593034206568772452674037325128
 84.  4880197746793002076754294951020699004973287771475874
 85.  20672849399056463095319772838289364792345825123228624
 86.  87571595343018854458033386304178158174356588264390370
 87.  370959230771131880927453318055001997489772178180790104
 88.  1571408518427546378167846658524186148133445300987550786
 89.  6656593304481317393598839952151746590023553382130993248
 90.  28197781736352815952563206467131172508227658829511523778
 91.  119447720249892581203851665820676436622934188700177088360
 92.  505988662735923140767969869749836918999964413630219877218
 93.  2143402371193585144275731144820024112622791843221056597232
 94.  9079598147510263717870894449029933369491131786514446266146
 95.  38461794961234640015759308940939757590587318989278841661816
 96.  162926777992448823780908130212788963731840407743629812913410
 97.  690168906931029935139391829792095612517948949963798093315456
 98.  2923602405716568564338475449381171413803636207598822186175234
 99.  12384578529797304192493293627316781267732493780359086838016392
100.  52461916524905785334311649958648296484733611329035169538240802

Time: 0.00698620

这是在约7毫秒内的前100个甚至斐波那契数字,包括打印到终端的开销(在Windows上容易低估).

Answer 4

基于这样一个事实fib(n) = fib(n-1)+fib(n-2),直截了当的解决方案是

def fib(n):
    if (n <=1):
        return(1)
    else:
        return(fib(n-1)+fib(n-2))

然而,这里的问题是一些值被多次计算,因此效率非常低.原因可以在这个草图中看到:

本质上,每次递归调用fib函数都必须计算所有以前的斐波纳契数以供自己使用.因此,计算得最多的值将是fib(1),因为它必须出现在@kqr的答案所示的树的所有叶节点中.该算法的复杂性是树的节点数,即$ O(2 ^ n)$.

现在更好的方法是跟踪两个数字,即当前值和前一个值,因此每次调用都不必计算所有先前的值.这是草图中的第二个算法,可以如下实现

def fib(n):
   if (n==0):
       return(0,1)
   elif (n==1):
       return(1,1)
   else:
       a,b = fib(n-1)
       return(b,a+b)

这种算法的复杂性是线性$ O(n)$,一些例子也是如此

>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)

Answer 5

我意识到这个问题是 8 年前提出的，并且已经得到了彻底的回答\xe2\x80\xa6 很抱歉将其弹回顶部。但总有更多的话要说。我在搜索改进我自己的算法时发现了这个，我想分享一下。

\n

我想提出我自己的看法，因为我发现这个问题并没有真正被提及。我认为我的算法在迄今为止的贡献者中是独一无二的。我利用众所周知的斐波那契数方程（维基百科）来缩小指数。其他一两个人简要介绍了基本版本，但我更进一步。

\n

这是一个递归算法，但我能够在 0.15 秒内计算出 Fib（200 万），在 2 秒内计算出 Fib（1000 万），在 75 秒内计算出 Fib（1 亿）。一切都没有错误。我要说的是，它不是计算连续斐波那契数列的最快的；这最适合挑选出非常大的个体。

\n

到目前为止提到的大多数算法 - 无论它们有多快 - 都很难在不存在递归深度问题的情况下达到 Fib(100) 以上。一些贡献者回避了我的算法的部分内容，尽管他们有一些我的算法没有的缺点。并不是说我的矿是最好的或者什么的，但我认为它相当快并且可以计算出非常大的小纤维。我认为值得加入讨论。

\n

最重要的是，我不使用任何内存。没有任何类型的列表、字典或数组。没有缓存或记忆。甚至没有一个持久保存的常量。没有导入特殊包。只是基本的、简单的、带有基本整数类型的Python。我还扩展了该函数来计算负小纤维，对运行时间的影响可以忽略不计。

\n

我应该警告\xe2\x80\xa6 我是一名数学家，而不是程序员。我毫不怀疑这可以进一步改进。我不知道大O是什么。

\n

def fib(n):\n      if n<0: return int(pow(-1, (n&1)+1))*fib(-n)\n      if n == 0: return 0\n      if n==1 or n==2: return 1\n      if n==3: return 2\n      \n      # n is multiple of 3\n      if n%3 == 0:\n            third = n//3\n            fibthird = fib(third)\n            return 5*pow(fibthird,3) + 3*pow(-1, third)*fibthird\n            \n      # even n\n      if n&1==0:\n            return pow(fib((n>>1) + 1),2) - pow(fib((n>>1) - 1), 2)\n\n      # for odd n\n      return ( pow(fib((n>>1)+1),2) + pow(fib(n>>1),2) )\n

\n

运行代码，告诉我你的想法。我很想听听社区的意见。就我个人而言，我对它印象深刻，并且已经运行了一段时间。但以我有限的（编程）知识找不到改进它的方法。尝试添加列表、记忆、缓存等，要么无法改进任何东西，要么使运行时间变得更糟。在极少数情况下，我发现一些可以改善运行时间的东西，对运行时间的好处可以忽略不计，而对内存的成本却很大，而且我认为这是不公平的交易。

\n\n

主要测试

\n

为了增加乐趣，我在下面添加了与斐波那契数相关的基本概率 is_prime 测试：

\n

def is_prime_fib(n):\n      # Fibonacci Probabilistic is_prime test. Compositeness deterministic.\n      if n==1: return False\n      if n==5: return True\n      if n%5 in [1,4] and fib(n-1) % n == 0: return True\n      if n%5 in [2,3] and fib(n+1) % n == 0: return True\n      return False\n

\n

我将其包含在内只是为了好玩，尽管它是偏离主题的。这是一个众所周知的使用斐波那契数的素性测试，但不幸的是它没有被使用，因为大多数斐波那契计算算法很慢，导致递归错误，或者以其他方式产生不准确，从而使测试不可靠，我们自然而然地求助于其他算法。我认为游戏可以稍微改变一下。

\n

就其本身而言，斐波那契素性测试是概率性的。n=1 和 n=5 的情况是无法产生正确结果的奇怪情况，但它们太明显了，无需担心。除此之外，False 在复合性方面是确定性的，True 在素数方面是概率性的。通过此测试为正确的组合是斐波那契伪素数。与其他概率测试相结合，我们可以实现紧急决定论。

\n