1

几天前我写了这个，它似乎工作正常，但速度很慢。生成斐波那契数列中的第 100 万个数字需要 25 秒。有没有办法让这更有效？

def main():
    num1 = 0
    num2 = 1
    var = 0
    num = int(raw_input("What fibonacci number do you want to know? "))
    while 1:
        num3 = num1
        num1 = num1 + num2
        num2 = num3
        var+=1
        if var>=num:
            print num3
            return main()
        else:
            None

main()

请注意，我是python初学者，所以我不会理解高级概念

4

5 回答 5

4

我发现使用卢卡斯数字可以让我得到最快的结果：

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
    else:
        return (L, F)

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        L, F = powLF(n // 2)
        return L * F

像矩阵指数一样，它具有 O(NlogN) 复杂度，但它的常数成本较低，因此“在点上”击败它：

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)
0.40711593627929688
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)
0.20211100578308105

是的，速度是原来的两倍。

我不能将上述实现归功于我与之比较的矩阵指数算法；两者都列在literateprograms.org上。

计算第 1,000,000 个斐波那契数需要：

>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.09112384080886841

不到十分之一秒。

于 2012-09-09T11:52:44.720 回答
2

不是严格的答案，但新程序员的一个非常普遍的习惯是违反关注点分离。

更好的是：

def fibonacci(n):
    ...

def main():
    num = int(raw_input("What fibonacci number do you want to know? "))
    print fibonacci(num)

这使斐波那契不会被用户界面代码弄乱。

于 2012-09-09T13:16:04.230 回答
1

如果你想快速计算斐波那契数，你应该使用封闭表达式或矩阵求幂。如果您希望能够生成任意大的数字，请使用矩阵求幂。

一个示例实现：

>>> def matrix_mul(A, B):
...     return ([A[0][0] * B[0][0] + A[0][1] * B[1][0],
...              A[0][0] * B[0][1] + A[0][1] * B[1][1]],
...             [A[1][0] * B[0][0] + A[1][1] * B[1][0],
...              A[1][0] * B[0][1] + A[1][1] * B[1][1]])
... 
>>> def matrix_exp(A, e):
...     if not e:
...             return [[1,0],[0,1]]
...     elif e % 2:
...             return matrix_mul(A, matrix_exp(A, e-1))
...     else:
...             sq= matrix_exp(A, e//2)
...             return matrix_mul(sq, sq)
... 
>>> def fibo(n):
...     M = [[1,1],[1,0]]
...     return matrix_exp(M, n)[0][0]
>>> fibo(1)
1
>>> fibo(2)
2
>>> fibo(3)
3
>>> fibo(4)
5
>>> fibo(5)
8
>>> fibo(115)
781774079430987230203437L
>>> fibo(123456)
#instantaneus output of a HUGE number

还有这个不可读的版本要快得多：

>>> 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]
... 
>>> timeit.timeit('fib(1000000)', 'from __main__ import fib', number=100)/100
0.0012753009796142578     # 1 millisecond for the millionth fibonacci number :O

这是 literateprograms.org 的最后一个（链接在另一个答案中）。

于 2012-09-09T12:03:38.463 回答
1

您可以使用在整数运算中完成的矩阵指数，或者使用以幂函数的速度完成的封闭形式表达式。（注意使用封闭形式表达式的数字错误）。O(logn)

于 2012-09-09T11:49:44.813 回答
0

这是非常有效的：

import numpy as np

M = np.matrix([[1, 1], [1, 0]])

def fib(n):
  if n < 2:
    return 1
  MProd = M.copy()
  for _ in xrange(n-2):
    MProd *= M
  return MProd[0,0] + MProd[0,1]
于 2015-10-27T18:15:26.683 回答