Python 优化算法

时间：12-14来源：作者：点击数：

1.1 优化算法时间复杂度

一个良好的算法能够对性能起到关键作用，因此性能改进的首要点是对算法的改进。在算法的时间复杂度排序上依次是：

O(1) -> O(lg n) -> O(n lg n) -> O(n^2) -> O(n^3) -> O(n^k) -> O(k^n) -> O(n!)

因此如果能够在时间复杂度上对算法进行一定的改进，对性能的提高不言而喻。不同的场景有不同的优化方式，总得来说，一般有分治，分支界限，贪心，动态规划等思想。

下面的内容将集中讨论数据结构的选择。

1.1.1 字典 (dictionary) 与列表 (list)

Python 字典中使用了 hash table，因此查找操作的复杂度为 O(1)，而 list 实际是个数组，在 list 中，查找需要遍历整个 list，其复杂度为 O(n)，因此对成员的查找访问等操作字典要比 list 更快。

清单 1. 代码 dict.py

from time import time  
t = time()  
list = ['a','b','is','python','jason','hello','hill','with','phone','test',  
'dfdf','apple','pddf','ind','basic','none','baecr','var','bana','dd','wrd']  
#list = dict.fromkeys(list,True)  
print list  
filter = []  
for i in range (1000000):  
    for find in ['is','hat','new','list','old','.']:  
        if find not in list:  
            filter.append(find)  
print "total run time:"  
print time()-t

上述代码运行大概需要 16.09seconds。如果去掉行 #list = dict.fromkeys(list,True) 的注释，将 list 转换为字典之后再运行，时间大约为 8.375 seconds，效率大概提高了一半。因此在需要多数据成员进行频繁的查找或者访问的时候，使用 dict 而不是 list 是一个较好的选择。

1.1.2 集合 (set) 与列表 (list)

set 的 union， intersection，difference 操作要比 list 的迭代要快。因此如果涉及到求 list 交集，并集或者差的问题可以转换为 set 来操作。

清单 2. 求 list 的交集：

1.  from time import time  
2.  t = time()  
3.  lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]  
4.  listb=[2,4,6,9,23]  
5.  intersection=[]  
6.  for i in range (1000000):  
7.      for a in lista:  
8.          for b in listb:  
9.              if a == b:  
10.                 intersection.append(a)  
11.    
12. print "total run time:"  
13. print time()-t

上述程序的运行时间大概为：

total run time: 
38.4070000648

清单 3. 使用 set 求交集

1.  from time import time  
2.  t = time()  
3.  lista=[1,2,3,4,5,6,7,8,9,13,34,53,42,44]  
4.  listb=[2,4,6,9,23]  
5.  intersection=[]  
6.  for i in range (1000000):  
7.      list(set(lista)&set(listb))  
8.  print "total run time:"  
9.  print time()-t

改为 set 后程序的运行时间缩减为 8.75，提高了 4 倍多，运行时间大大缩短。读者可以自行使用表 1 其他的操作进行测试。

表 1. set 常见用法

语法	操作	说明
set(list1) \| set(list2)	union	包含 list1 和 list2 所有数据的新集合
set(list1) & set(list2)	intersection	包含 list1 和 list2 中共同元素的新集合
set(list1) - set(list2)	difference	在 list1 中出现但不在 list2 中出现的元素的集合

1.2 充分利用 Lazy if-evaluation 的特性

python 中条件表达式是 lazy evaluation 的，也就是说如果存在条件表达式 if x and y，在 x 为 false 的情况下 y 表达式的值将不再计算。因此可以利用该特性在一定程度上提高程序效率。

清单 6. 利用 Lazy if-evaluation 的特性

1.  from time import time  
2.  t = time()  
3.  abbreviations = ['cf.', 'e.g.', 'ex.', 'etc.', 'fig.', 'i.e.', 'Mr.', 'vs.']  
4.  for i in range (1000000):  
5.      for w in ('Mr.', 'Hat', 'is', 'chasing', 'the', 'black', 'cat', '.'):  
6.          if w in abbreviations:  
7.          #if w[-1] == '.' and w in abbreviations:  
8.              pass  
9.  print "total run time:"  
10. print time()-t

在未进行优化之前程序的运行时间大概为 8.84，如果使用注释行代替第一个 if，运行的时间大概为 6.17

1.3 合理使用 copy 与 deepcopy

对于dict和list等数据结构的对象，直接赋值使用的是引用的方式。而有些情况下需要复制整个对象，这时可以使用copy包里的copy和deepcopy，这两个函数的不同之处在于后者是递归复制的。效率也不一样：（以下程序在ipython中运行）

import copy
a = range(100000)
%timeit -n 10 copy.copy(a) # 运行10次 copy.copy(a)
%timeit -n 10 copy.deepcopy(a)
10 loops, best of 3: 1.55 ms per loop
10 loops, best of 3: 151 ms per loop

timeit 后面的 -n 表示运行的次数，后两行对应的是两个 timeit 的输出，下同。由此可见后者慢一个数量级。

1.4 合理使用生成器（generator）和 yield

一个普遍被忽略的内存优化是生成器的使用。生成器让我们创建一个函数一次只返回一条记录，而不是一次返回所有的记录，如果你正在使用 python2.x，这就是你为啥使用 xrange 替代 range 或者使用 ifilter 替代 filter 的原因。一个很好地例子就是创建一个很大的列表并将它们拼合在一起。

1.  import timeit  
2.  import random  
3.    
4.  def generate(num):  
5.      while num:  
6.          yield random.randrange(10)  
7.          num -= 1  
8.    
9.  def create_list(num):  
10.     numbers = []  
11.     while num:  
12.         numbers.append(random.randrange(10))  
13.         num -= 1  
14.     return numbers  
15.           
16. print(timeit.timeit("sum(generate(999))", setup="from __main__ import generate", number=1000))  
17. print(timeit.timeit("sum(create_list(999))", setup="from __main__ import create_list", number=1000))

输出：

1.00842191191
0.933518458666

列表解析要比在循环中重新构建一个新的 list 更为高效，因此我们可以利用这一特性来提高运行的效率。

1.  from time import time  
2.  t = time()  
3.  list = ['a','b','is','python','jason','hello','hill','with','phone','test',  
4.  'dfdf','apple','pddf','ind','basic','none','baecr','var','bana','dd','wrd']  
5.  total=[]  
6.  for i in range(1000000):  
7.      for w in list:  
8.          total.append(w)  
9.  print "total run time:"  
10. print time()-t

使用列表解析：

1.  for i in range(1000000):  
2.       a = [w for w in list]

上述代码直接运行大概需要 17s，而改为使用列表解析后，运行时间缩短为 9.29s。将近提高了一半。生成器表达式则是在 2.4 中引入的新内容，语法和列表解析类似，但是在大数据量处理时，生成器表达式的优势较为明显，它并不创建一个列表，只是返回一个生成器，因此效率较高。在上述例子上中代码 a = [w for w in list] 修改为 a = (w for w in list)，运行时间进一步减少，缩短约为 2.98s。

1.5 优化循环

对循环的优化所遵循的原则是尽量减少循环过程中的计算量，有多重循环的尽量将内层的计算提到上一层。下面通过实例来对比循环优化后所带来的性能的提高。程序清单 4 中，如果不进行循环优化，其大概的运行时间约为 132.375。

清单 4. 为进行循环优化前

1.  from time import time  
2.  t = time()  
3.  lista = [1,2,3,4,5,6,7,8,9,10]  
4.  listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]  
5.  for i in range (1000000):  
6.      for a in range(len(lista)):  
7.          for b in range(len(listb)):  
8.              x=lista[a]+listb[b]  
9.  print "total run time:"  
10. print time()-t

现在进行如下优化，将长度计算提到循环外，range 用 xrange 代替，同时将第三层的计算 lista[a] 提到循环的第二层。

清单 5. 循环优化后

1.  from time import time  
2.  t = time()  
3.  lista = [1,2,3,4,5,6,7,8,9,10]  
4.  listb =[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01]  
5.  len1=len(lista)  
6.  len2=len(listb)  
7.  for i in xrange (1000000):  
8.      for a in xrange(len1):  
9.          temp=lista[a]  
10.         for b in xrange(len2):  
11.             x=temp+listb[b]  
12. print "total run time:"  
13. print time()-t

上述优化后的程序其运行时间缩短为 102.171999931。在清单 4 中 lista[a] 被计算的次数为 10000001010，而在优化后的代码中被计算的次数为 1000000*10，计算次数大幅度缩短，因此性能有所提升

1.6 字符串的优化

python 中的字符串对象是不可改变的，因此对任何字符串的操作如拼接，修改等都将产生一个新的字符串对象，而不是基于原字符串，因此这种持续的 copy 会在一定程度上影响 python 的性能。对字符串的优化也是改善性能的一个重要的方面，特别是在处理文本较多的情况下。字符串的优化主要集中在以下几个方面：

1、在字符串连接的使用尽量使用 join() 而不是 +：在代码清单 7 中使用 + 进行字符串连接大概需要 0.125 s，而使用 join 缩短为 0.016s。因此在字符的操作上 join 比 + 要快，因此要尽量使用 join 而不是 +。

清单 7. 使用 join 而不是 + 连接字符串

1.  from time import time  
2.  t = time()  
3.  s = ""  
4.  list = ['a','b','b','d','e','f','g','h','i','j','k','l','m','n']  
5.  for i in range (10000):  
6.   for substr in list:  
7.       s+= substr  
8.  print "total run time:"  
9.  print time()-t

同时要避免：

1.  s = ""  
2.  for x in list:   
3.      s += func(x)

而是要使用：

1.  slist = [func(elt) for elt in somelist]  
2.  s = "".join(slist)

2、当对字符串可以使用正则表达式或者内置函数来处理的时候，选择内置函数。如 str.isalpha()，str.isdigit()，str.startswith((‘x’, ‘yz’))，str.endswith((‘x’, ‘yz’))

3、对字符进行格式化比直接串联读取要快，因此要使用

1.  out = "%s%s%s%s" % (head, prologue, query, tail)

而避免

out = "" + head + prologue + query + tail + ""

1.7 其它优化技巧

1.7.1 不借助中间变量交换两个变量的值

In [3]: %%timeit -n 10000
 a,b=1,2
 ....: c=a;a=b;b=c;
 ....:
10000 loops, best of 3: 172 ns per loop
 
In [4]: %%timeit -n 10000
a,b=1,2
a,b=b,a
 ....:
10000 loops, best of 3: 86 ns per loop

使用 a,b=b,a 而不是 c=a;a=b;b=c; 来交换 a,b 的值，可以快1倍以上。

1.7.2 使用if is

a = range(10000)
%timeit -n 100 [i for i in a if i == True]
%timeit -n 100 [i for i in a if i is True]
100 loops, best of 3: 531 μs per loop
100 loops, best of 3: 362 μs per loop

使用 if is True 比 if == True 将近快一倍。

1.7.3 使用级联比较x < y < z

x, y, z = 1,2,3
%timeit -n 1000000 if x < y < z:pass
%timeit -n 1000000 if x < y and y < z:pass
1000000 loops, best of 3: 101 ns per loop
1000000 loops, best of 3: 121 ns per loop

x < y < z 效率略高，而且可读性更好。

1.7.4 while 1 比 while True 更快

def while_1():
 n = 100000
 while 1:
 n -= 1
 if n <= 0: break
def while_true():
 n = 100000
 while True:
 n -= 1
 if n <= 0: break
 
m, n = 1000000, 1000000
%timeit -n 100 while_1()
%timeit -n 100 while_true()
100 loops, best of 3: 3.69 ms per loop
100 loops, best of 3: 5.61 ms per loop
while 1 比 while true快很多，原因是在python2.x中，True是一个全局变量，而非关键字。
1.7.5          使用**而不是pow
1
2
3
4
%timeit -n 10000 c = pow(2,20)
%timeit -n 10000 c = 2**20
10000 loops, best of 3: 284 ns per loop
10000 loops, best of 3: 16.9 ns per loop

** 就是快10倍以上！

1.7.6 使用局部变量

使用局部变量，避免 global 关键字。python 访问局部变量会比全局变量要快得多，因此可以利用这一特性提升性能

1.7.7 使用 build in 函数

build in 函数通常较快，add(a,b) 要优于 a+b

1.8 使用 `cProfile`, `cStringIO` 和 `cPickle` 等用c实现相同功能（分别对应 `profile`, `StringIO`, `pickle`）的包

import cPickle
import pickle
a = range(10000)
%timeit -n 100 x = cPickle.dumps(a)
%timeit -n 100 x = pickle.dumps(a)
100 loops, best of 3: 1.58 ms per loop
100 loops, best of 3: 17 ms per loop

由 c 实现的包，速度快10倍以上！

1.9 使用最佳的反序列化方式

下面比较了 eval, cPickle, json 方式三种对相应字符串反序列化的效率：

import json
import cPickle
a = range(10000)
s1 = str(a)
s2 = cPickle.dumps(a)
s3 = json.dumps(a)
%timeit -n 100 x = eval(s1)
%timeit -n 100 x = cPickle.loads(s2)
%timeit -n 100 x = json.loads(s3)
100 loops, best of 3: 16.8 ms per loop
100 loops, best of 3: 2.02 ms per loop
100 loops, best of 3: 798 μs per loop

可见 json 比 cPickle 快近3倍，比 eval 快20多倍。

1.10 使用 C 扩展 Extension

目前主要有 CPython（python 最常见的实现的方式）原生 API, ctypes,Cython，cffi 三种方式，它们的作用是使得Python程序可以调用由C编译成的动态链接库，其特点分别是：

CPython 原生 API: 通过引入 Python.h 头文件，对应的C程序中可以直接使用Python的数据结构。实现过程相对繁琐，但是有比较大的适用范围。

ctypes: 通常用于封装（wrap）C程序，让纯 Python 程序调用动态链接库（Windows 中的 dll 或 Unix 中的 so 文件）中的函数。如果想要在python中使用已经有C类库，使用ctypes是很好的选择，有一些基准测试下，python2+ctypes 是性能最好的方式。

Cython: Cython 是 CPython 的超集，用于简化编写C扩展的过程。Cython 的优点是语法简洁，可以很好地兼容 numpy 等包含大量C扩展的库。Cython 的使得场景一般是针对项目中某个算法或过程的优化。在某些测试中，可以有几百倍的性能提升。

cffi: cffi 的就是 ctypes 在 pypy（详见下文）中的实现，同进也兼容 CPython。cffi 提供了在 python 使用 C 类库的方式，可以直接在 python 代码中编写C代码，同时支持链接到已有的C类库。

使用这些优化方式一般是针对已有项目性能瓶颈模块的优化，可以在少量改动原有项目的情况下大幅度地提高整个程序的运行效率。

1.11 并行编程

因为 GIL 的存在，Python 很难充分利用多核 CPU 的优势。但是，可以通过内置的模块multiprocessing 实现下面几种并行模式：

多进程：对于 CPU 密集型的程序，可以使用 multiprocessing 的 Process、Pool 等封装好的类，通过多进程的方式实现并行计算。但是因为进程中的通信成本比较大，对于进程之间需要大量数据交互的程序效率未必有大的提高。
多线程：对于 IO 密集型的程序，multiprocessing.dummy 模块使用 multiprocessing 的接口封装threading，使得多线程编程也变得非常轻松(比如可以使用Pool的map接口，简洁高效)。
分布式：multiprocessing 中的 Managers 类提供了可以在不同进程之共享数据的方式，可以在此基础上开发出分布式的程序。

不同的业务场景可以选择其中的一种或几种的组合实现程序性能的优化。

1.12 终级大杀器：PyPy

PyPy 是用 RPython（CPython 的子集）实现的 Python，根据官网的基准测试数据，它比 CPython 实现的 Python 要快6倍以上。快的原因是使用了 Just-in-Time(JIT) 编译器，即动态编译器，与静态编译器(如 gcc,javac 等)不同，它是利用程序运行的过程的数据进行优化。由于历史原因，目前 pypy 中还保留着 GIL，不过正在进行的STM项目试图将PyPy变成没有GIL的Python。

如果python程序中含有C扩展(非cffi的方式)，JIT的优化效果会大打折扣，甚至比CPython慢（比Numpy）。所以在 PyPy 中最好用纯 Python 或使用cffi扩展。

随着 STM，Numpy等项目的完善，相信 PyPy 将会替代 CPython。

1.13 Ctypes 的介绍

对于关键性的性能代码 python 本身也提供给我们一个 API 来调用C方法，主要通过 ctypes来实现，你可以不写任何C代码来利用 ctypes。默认情况下 python 提供了预编译的标准c库，我们再回到生成器的例子，看看使用 ctypes 实现花费多少时间。

1.  import timeit  
2.  from ctypes import cdll  
3.    
4.  def generate_c(num):  
5.      #Load standard C library  
6.      #libc = cdll.LoadLibrary("libc.so.6") #Linux  
7.      libc = cdll.msvcrt #Windows  
8.      while num:  
9.          yield libc.rand() % 10  
10.         num -= 1  
11.   
12. print(timeit.timeit("sum(generate_c(999))", setup="from __main__ import generate_c", number=1000))

输出：

0.404974439902

仅仅换成了c的随机函数，运行时间减了大半！但是还能做得更好！

1.14 Cython 的介绍

Cython 是 python 的一个超集，允许我们调用C函数以及声明变量来提高性能。尝试使用之前我们需要先安装 Cython。

sudo pip install cython

Cython 本质上是另一个不再开发的类似类库Pyrex的分支，它将我们的类 Python 代码编译成C库，我们可以在一个 python 文件中调用。对于你的python文件使用 .pyx 后缀替代 .py 后缀，让我们看一下使用 Cython 如何来运行我们的生成器代码。

1.  #cython_generator.pyx  
2.  import random  
3.    
4.  def generate(num):  
5.      while num:  
6.          yield random.randrange(10)  
7.          num -= 1

我们需要创建个 setup.py 以便我们能获取到 Cython 来编译我们的函数。

1.  from distutils.core import setup  
2.  from distutils.extension import Extension  
3.  from Cython.Distutils import build_ext  
4.    
5.  setup(  
6.      cmdclass = {'build_ext': build_ext},  
7.      ext_modules = [Extension("generator", ["cython_generator.pyx"])]  
8.  )

编译使用：

python setup.py build_ext--inplace

你应该可以看到两个文件 cython_generator.c 文件和 generator.so 文件，我们使用下面方法测试我们的程序：

1.  import timeit  
2.  print(timeit.timeit("sum(generator.generate(999))", setup="import generator", number=1000))  
3.  >>> 0.835658073425

还不赖，让我们看看是否还有可以改进的地方。我们可以先声明 num 为整形，接着我们可以导入标准的C库来负责我们的随机函数。

1.  #cython_generator.pyx  
2.  cdef extern from "stdlib.h":  
3.      int c_libc_rand "rand"()  
4.    
5.  def generate(int num):  
6.      while num:  
7.          yield c_libc_rand() % 10  
8.          num -= 1

如果我们再次编译运行我们会看到这一串惊人的数字。

>>> 0.033586025238

仅仅的几个改变带来了不赖的结果。然而，有时这个改变很乏味，因此让我们来看看如何使用规则的 python 来实现吧。

1.15 PyPy 的介绍

PyPy 是一个 Python2.7.3 的即时编译器（JIT），通俗地说这意味着让你的代码运行的更快。Quora在生产环境中使用了 PyPy。PyPy 在它们的下载页面有一些安装说明，但是如果你使用的Ubuntu系统，你可以通过 apt-get 来安装。它的运行方式是立即可用的，因此没有疯狂的 bash 或者运行脚本，只需下载然后运行即可。让我们看看我们原始的生成器代码在 PyPy 下的性能如何。

1.  import timeit  
2.  import random  
3.    
4.  def generate(num):  
5.      while num:  
6.          yield random.randrange(10)  
7.          num -= 1  
8.    
9.  def create_list(num):  
10.     numbers = []  
11.     while num:  
12.         numbers.append(random.randrange(10))  
13.         num -= 1  
14.     return numbers  
15.           
16. print(timeit.timeit("sum(generate(999))", setup="from __main__ import generate", number=1000))  
17. >>> 0.115154981613 #PyPy 1.9  
18. >>> 0.118431091309 #PyPy 2.0b1  
19. print(timeit.timeit("sum(create_list(999))", setup="from __main__ import create_list", number=1000))  
20. >>> 0.140175104141 #PyPy 1.9  
21. >>> 0.140514850616 #PyPy 2.0b1

1.16 进一步测试

为什么还要进一步研究？PyPy 是冠军！并不全对。虽然大多数程序可以运行在PyPy上，但是还是有一些库没有被完全支持。而且，为你的项目写C的扩展相比换一个编译器更加容易。让我们更加深入一些，看看ctypes如何让我们使用C来写库。我们来测试一下归并排序和计算斐波那契数列的速度。下面是我们要用到的C代码（functions.c）：

1.  /* functions.c */  
2.  #include "stdio.h"  
3.  #include "stdlib.h"  
4.  #include "string.h"  
5.    
6.  /* http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C */  
7.  inline  
8.  void merge(int *left, int l_len, int *right, int r_len, int *out)  
9.  {  
10.     int i, j, k;  
11.     for (i = j = k = 0; i < l_len && j < r_len; )  
12.         out[k++] = left[i] < right[j] ? left[i++] : right[j++];  
13.    
14.     while (i < l_len) out[k++] = left[i++];  
15.     while (j < r_len) out[k++] = right[j++];  
16. }  
17.    
18. /* inner recursion of merge sort */  
19. void recur(int *buf, int *tmp, int len)  
20. {  
21.     int l = len / 2;  
22.     if (len <= 1) return;  
23.    
24.     /* note that buf and tmp are swapped */  
25.     recur(tmp, buf, l);  
26.     recur(tmp + l, buf + l, len - l);  
27.    
28.     merge(tmp, l, tmp + l, len - l, buf);  
29. }  
30.    
31. /* preparation work before recursion */  
32. void merge_sort(int *buf, int len)  
33. {  
34.     /* call alloc, copy and free only once */  
35.     int *tmp = malloc(sizeof(int) * len);  
36.     memcpy(tmp, buf, sizeof(int) * len);  
37.    
38.     recur(buf, tmp, len);  
39.    
40.     free(tmp);  
41. }  
42.   
43. int fibRec(int n){  
44.     if(n < 2)  
45.         return n;  
46.     else  
47.         return fibRec(n-1) + fibRec(n-2);  
48. }

在 Linux 平台，我们可以用下面的方法把它编译成一个共享库：

gcc -Wall-fPIC-c functions.c
gcc -shared-o libfunctions.so functions.o

使用 ctypes，通过加载 libfunctions.so 这个共享库，就像我们前边对标准C库所作的那样，就可以使用这个库了。这里我们将要比较 Python 实现和C实现。现在我们开始计算斐波那契数列：

1.  #functions.py  
2.  from ctypes import *  
3.  import time  
4.    
5.  libfunctions = cdll.LoadLibrary("./libfunctions.so")  
6.    
7.  def fibRec(n):  
8.      if n < 2:  
9.          return n  
10.     else:  
11.         return fibRec(n-1) + fibRec(n-2)  
12.   
13. start = time.time()   
14. fibRec(32)  
15. finish = time.time()  
16. print("Python: " + str(finish - start))  
17.   
18. #C Fibonacci  
19. start = time.time()   
20. x = libfunctions.fibRec(32)  
21. finish = time.time()  
22. print("C: " + str(finish - start))  
[plain] view plaincopy在CODE上查看代码片派生到我的代码片
1.  Python: 1.18783187866 #Python 2.7  
2.  Python: 1.272292137145996 #Python 3.2  
3.  Python: 0.563600063324 #PyPy 1.9  
4.  Python: 0.567229032516 #PyPy 2.0b1  
5.  C: 0.043830871582 #Python 2.7 + ctypes  
6.  C: 0.04574108123779297 #Python 3.2 + ctypes  
7.  C: 0.0481240749359 #PyPy 1.9 + ctypes  
8.  C: 0.046403169632 #PyPy 2.0b1 + ctypes

正如我们预料的那样，C 比 Python 和 PyPy 更快。我们也可以用同样的方式比较归并排序。

我们还没有深挖Cypes库，所以这些例子并没有反映python强大的一面，Cypes库只有少量的标准类型限制，比如int型，char数组，float型，字节（bytes）等等。默认情况下，没有整形数组，然而通过与c_int相乘（ctype为int类型）我们可以间接获得这样的数组。这也是代码第7行所要呈现的。我们创建了一个c_int数组，有关我们数字的数组并分解打包到 c_int 数组中

主要的是c语言不能这样做，而且你也不想。我们用指针来修改函数体。为了通过我们的 c_numbers 的数列，我们必须通过引用传递 merge_sort 功能。运行 merge_sort 后，我们利用 c_numbers 数组进行排序，我已经把下面的代码加到我的 functions.py 文件中了。

1.  #Python Merge Sort  
2.  from random import shuffle, sample  
3.    
4.  #Generate 9999 random numbers between 0 and 100000  
5.  numbers = sample(range(100000), 9999)  
6.  shuffle(numbers)  
7.  c_numbers = (c_int * len(numbers))(*numbers)  
8.    
9.  from heapq import merge  
10.    
11. def merge_sort(m):  
12.     if len(m) <= 1:  
13.         return m  
14.    
15.     middle = len(m) // 2  
16.     left = m[:middle]  
17.     right = m[middle:]  
18.    
19.     left = merge_sort(left)  
20.     right = merge_sort(right)  
21.     return list(merge(left, right))  
22.   
23. start = time.time()  
24. numbers = merge_sort(numbers)  
25. finish = time.time()  
26. print("Python: " + str(finish - start))  
27.   
28. #C Merge Sort  
29. start = time.time()  
30. libfunctions.merge_sort(byref(c_numbers), len(numbers))  
31. finish = time.time()  
32. print("C: " + str(finish - start))  
[plain] view plaincopy在CODE上查看代码片派生到我的代码片
1.  Python: 0.190635919571 #Python 2.7  
2.  Python: 0.11785483360290527 #Python 3.2  
3.  Python: 0.266992092133 #PyPy 1.9  
4.  Python: 0.265724897385 #PyPy 2.0b1  
5.  C: 0.00201296806335 #Python 2.7 + ctypes  
6.  C: 0.0019741058349609375 #Python 3.2 + ctypes  
7.  C: 0.0029308795929 #PyPy 1.9 + ctypes  
8.  C: 0.00287103652954 #PyPy 2.0b1 + ctypes

这儿通过表格和图标来比较不同的结果。

	Merge Sort	Fibonacci
Python 2.7	0.191	1.187
Python 2.7 + ctypes	0.002	0.044
Python 3.2	0.118	1.272
Python 3.2 + ctypes	0.002	0.046
PyPy 1.9	0.267	0.564
PyPy 2.0b1	0.266	0.567
PyPy 2.0b1 + ctypes	0.003	0.046