从 Python 计算 Fibonacci 数列说起
编程语言之争，争到最后大都就是在争论速度了，速度当然很重要，毕竟现实的物理设备和人类的想象力之间差距还是蛮大的，然而比较矛盾的是，越接近人类思维的语言就和计算机硬件隔的越远，速度也必然会受到影响，不过我才不去谈各种语言运行速度呢，这该多无聊啊。
下面只是通过一个使用 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 <stdio.h>
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(<module>)
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(<module>)
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，反正都是一个意思就行了 - 这里只谈递归计算，关于转换成迭代计算什么的就不说了
- 速度优化什么的最无聊了，现在你应该知道我有多无聊了吧