Cython 是用 Python 的语法写C语言，原理其实就是解释器将 python 语言翻译成C语言然后再用编译器（比如 gcc 或者 vc++ ）编译成可被 python 调用的动态链接库。是用 Cython 的好处自然就是快。最近想到一个问题，斐波那契数列可以用两种方法实现，一种是用迭代方法，即根据定义当前值等于前两个值的和。另一种是使用数列知识中的求通式法直接算出。哪种更快？

想象中我们认为肯定是使用求通式法更为快捷方便，算的速度也应该更快，可另一方面觉得，及时求出通式，其实计算机也得不停用乘法进行“循环”，其时间消耗应该仍然很大。为了多尺度比较，我想出四种方法进行计算，分别是：

  1. 使用 Cython 定义迭代器，Python 调用51次（第一次为初始化）
  2. 直接使用 Python 循环50次
  3. 直接用 Python 根据公式计算n=51时的结果
  4. 直接使用 Cython 循环50次

先看结果

1
2
3
4
5
6
7
8
9
10
11
12
cython_generator
time used: 0.000038 s
20365011074
python_loop
time used: 0.000014 s
20365011074
python_math
time used: 0.000059 s
20365011074.0
cython_loop
time used: 0.000003 s
20365011074

很容易接受最后种方法速度最快，毕竟它几乎全是C的实现。而如果仅仅是循环的话，那么Python本身的实现也是够快的（仅比Cython慢了3、4倍）。而如果使用Python的高级功能-迭代器，速度就明显下降了，而使用math以后，速度更慢，证明了我的观点，使用通式计算数列本身也是挺耗时的。不过后来又做了个改变才发现我的想法不完全对，当我增加两个测试：python实现999次循环以及计算n=1000时候的情况，发现
1
2
3
4
5
6
python_loop_999
time used: 0.000269 s
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
python_math_999
time used: 0.000009 s
4.34665576869e+208

很明显说明python的数学实现是被优化的，而如果用迭代，只能老老实实的加，其性能也明显下降（不过保证了精度）

由于Cython中只支持64位的long long，所以连100次都无法迭代，没有参与后续的计算。

下面附实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#fab.pyx
def fab(int max): 
    cdef int n = 0 
    cdef long long a = 0
    cdef long long b = 1
    while n < max: 
        yield b 
        a, b = b, a + b 
        n = n + 1 

f = fab(1000)

def fab_50():
    cdef int n = 0
    cdef long long a = 0 
    cdef long long b = 1
    while n < 50:
        a, b = b, a + b
        n += 1
    return b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#test.py
import fab
import time
import math
f = fab.f

def print_time(fnc):
    def new_fnc(*arg,**kwarg):
       starttime = time.time()
       r = fnc(*arg,**kwarg)
       endtime = time.time()
       print "time used: %f s" %(endtime - starttime)
       return r
    return new_fnc

@print_time
def calc_by_cython():
    f = fab.f
    for i in range(51):
        x=f.next()
    return x

@print_time
def calc_by_cython_50():
    return fab.fab_50()

@print_time
def calc_by_python(x):
    a = 0; b = 1
    for i in range(x):
        a,b = b, a+b
    return b
@print_time
def calc_by_math(x):
    sqrt_5 = math.sqrt(5)
    n = x+1
    return 1/sqrt_5 * (((1+sqrt_5)/2)**n - ((1-sqrt_5)/2)**n)
@print_time
def calc_sqrt():
    return math.sqrt(5)
print 'cython_generator'
print calc_by_cython()
print 'python_loop'
print calc_by_python(50)
print 'python_math'
print calc_by_math(50)
print 'cython_loop'
print calc_by_cython_50()

print 'python_loop_999'
print calc_by_python(999)
print 'python_math_999'
print calc_by_math(999)