從 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):
if n < 2:
return n
else:
return f(n-2) + f(n-1)
print f(40)
同樣,先看看運行的速度如何,結果:
python tcache.py 0.02s user 0.01s system 77% cpu 0.036 total
這個的確非常驚艷,速度加快了將近3000倍,比 C 的都快40多倍,當然,這個相當于作弊了,哈哈,先看一下計算量如何,依然 python -m cProfile tcache.py 一下,這個沒有讓我久等,瞬間出結果:
202 function calls (84 primitive calls) in 0.001 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
41/1 0.000 0.000 0.000 0.000 tcache.py:18(f)
1 0.000 0.000 0.000 0.000 tcache.py:4()
1 0.000 0.000 0.000 0.000 tcache.py:7(cache)
79/1 0.000 0.000 0.000 0.000 tcache.py:9(_cache)
1 0.000 0.000 0.000 0.000 #省略無關
對 f 的調用現在是41了,這個和前面的331160281一比,不快才怪。
以上扯了那么多,究竟是為什么,我只是想說,對算法的優化是提高速度最快的方法,當然 C 也可以使用緩存方法來優化遞歸計算,但那就太麻煩了。
最后說點注意的:
程序代碼可能有點亂,一會而函數名是 fibonacci,一會兒又是 f,反正都是一個意思就行了
這里只談遞歸計算,關于轉換成迭代計算什么的就不說了
速度優化什么的最無聊了,現在你應該知道我有多無聊了吧
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态