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

10 分の 1 秒弱です。

于 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

整数演算で実行される行列指数を使用するか、累乗関数の速度で実行される閉形式式を使用できます。(閉じた形式の式を使用する際の数値エラーに注意してください)。O(logn)

于 2012-09-09T11:49:44.813 に答える
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 に答える