fibonacci數列python_從 Python 計算 Fibonacci 數列說起-變量-匯編語言學習筆記

fibonacci數列python_從 Python 計算 Fibonacci 數列說起

2023-12-06 阅读 28 评论 0

摘要：從 Python 計算 Fibonacci 數列說起09 Oct, 2012編程語言之爭，爭到最后大都就是在爭論速度了，速度當然很重要，畢竟現實的物理設備和人類的想象力之間差距還是蠻大的，然而比較矛盾的是，越接近人類思維的語言就和計算機硬件隔的越遠，

從 Python 計算 Fibonacci 數列說起

09 Oct, 2012

編程語言之爭，爭到最后大都就是在爭論速度了，速度當然很重要，畢竟現實的物理設備和人類的想象力之間差距還是蠻大的，然而比較矛盾的是，越接近人類思維的語言就和計算機硬件隔的越遠，速度也必然會受到影響，不過我才不去談各種語言運行速度呢，這該多無聊啊。

下面只是通過一個使用 Python 計算 Fibonacci 數列的例子來亂談一下，不是什么速度優化秘笈。談到 Fibonacci 數列，這個可是講遞歸的時候必然有的例子，那么就用遞歸計算的方法來說明。

def fibonacci(n):

if n < 2:

return n

else:

return fibonacci(n-2) + fibonacci(n-1)

print fibonacci(40)

現在我們關心的是速度，為了簡單，直接使用 time 命令，運行 time python t.py (t.py 即上面那段代碼所在的文件)，等待良久，終于出結果：

python t.py 63.56s user 0.08s system 99% cpu 1:03.80 total

好吧，63.56s，看不出啥道理，使用 C 語言來作為標準，作為以后的參照。

#include

int fibonacci(n) {

if (n < 2) {

return n;

}

return fibonacci(n - 2) + fibonacci(n - 1);

}

int main() {

printf("%d\n", fibonacci(40));

return 0;

}

使用 gcc -O3 優化編譯，運行結果：

./a.out 0.85s user 0.00s system 99% cpu 0.859 total

嗯，快了將近75倍，大約兩個數量級，看來動態語言和靜態語言之間的速度差別那還是真的很大，于是開始考慮怎么加快 Python 計算的速度了，直接使用 C 擴展，但一大堆的 API 接口和規范貌似很麻煩，用 python 圖的就是一個心情舒爽，身心健康什么的，又去寫 C 那多不爽。幸好有 Cython 這貨，看一下例子，依樣寫了一個：

# fib.pyx

cdef int f(int n):

if n < 2:

return n

else:

return f(n-2) + f(n-1)

def fibonacci(n):

return f(n)

通過編譯后，會生成一個 fib.so 的動態鏈接庫，于是在 Python 中只需要 import 就行了：

from fib import fibonacci

print fibonacci(40)

同樣運行結果是：

python t.py 1.96s user 0.01s system 99% cpu 1.984 total

好家伙，速度提高了將近60倍，和純 C 的差距也縮小多了，這個速度和 Java、Go 的就在同一水平了，看來使用 C 擴展就是不同反響啊。不過貌似一開始優化的時候就走錯路了，動態語言固然加上 C 擴展可以威力大增，但這樣的優化實在應該作為最后的選擇，而最重要的一點就是對計算算法的分析(注意這里只考慮使用遞歸計算，也只是優化遞歸計算，不要想為什么不把它轉換成迭代計算)，使用遞歸計算 Fibonacci 數列，會產生很多重復的計算，這個重復的數量是極其驚人的，時間增長相對于 n 是指數增長的，底數為 1.6180，于是計算的慢也就太正常了。使用 python -m cProfile t.py 來分析一下，看計算量如何：

331160283 function calls (3 primitive calls) in 619.178 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)

331160281/1 619.178 0.000 619.178 619.178 t.py:19(f)

1 0.000 0.000 619.178 619.178 t.py:4()

1 0.000 0.000 0.000 0.000 ...(省略無關)

使用這個分析會減慢運行速度，等了將近十分鐘，終于出結果了，那個 t.py: 19(f) 就是 fibonacci 函數，調用了331160281次，不慢才怪。對付重復計算的一個方法就是，緩存計算過的值，這樣就可以大大加快計算速度了，對于 Python 來說，要緩存函數計算的結果簡直太容易了，使用裝飾器可以方便的達到目的，于是寫出優化遞歸計算的代碼：

def cache(function):

caches = {}

def _cache(*args, **kw):

key = 'f' + str(args[0])

if key in caches:

return caches[key]

result = function(*args, **kw)

caches[key] = result

return caches[key]

return _cache

@cache

def f(n):