从 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 <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 也可以使用缓存方法来优化递归计算,但那就太麻烦了。

最后说点注意的:

  1. 程序代码可能有点乱,一会而函数名是 fibonacci,一会儿又是 f,反正都是一个意思就行了
  2. 这里只谈递归计算,关于转换成迭代计算什么的就不说了
  3. 速度优化什么的最无聊了,现在你应该知道我有多无聊了吧