Cython与Python基准测试对比

Question

我正在尝试使用冒泡排序算法来测试Cython与纯Python的性能差异，这是我的结果，它表明纯Python比Cython运行速度更快，那么我的结果是否正确？或者我的代码有问题？

脚本试图创建一个随机列表，然后分别使用Cython和纯Python实现的冒泡排序算法对其进行排序。

benchmark.py

import cybubble
import pybubble
from timeit import default_timer as timer
from decimal import *
import random
getcontext().prec = 8

if __name__ == '__main__':
    random_list = [random.randrange(0,10) for i in range(9999)] #generate a random list
    cy_start = timer()   #start timer
    cybubble.bubble_sort(random_list)   #execute cython bubble sort
    cy_end = timer()     #stop timer

    py_start = timer()   #start timer
    pybubble.bubble_sort(random_list)   #execute pure python bubble sort
    py_end = timer()     #stop time

    print "Python execution time:"
    python = (Decimal(py_end) - Decimal(py_start))
    print (python)

    print "Cython execution time:"
    cython = (Decimal(cy_end) - Decimal(cy_start))
    print (cython)

cybubble.pyx

cpdef bubble_sort(collection):
    cdef int length
    cdef int i
    cdef int j
    length = len(collection)
    for i in range(length-1):
        swapped = False
        for j in range(length-1-i):
            if collection[j] > collection[j+1]:
                swapped = True
                collection[j], collection[j+1] = collection[j+1], collection[j]
        if not swapped:
            break  # Stop iteration if the collection is sorted.
    return collection

pybubble.py

def bubble_sort(collection):
    length = len(collection)
    for i in range(length-1):
        swapped = False
        for j in range(length-1-i):
            if collection[j] > collection[j+1]:
                swapped = True
                collection[j], collection[j+1] = collection[j+1], collection[j]
        if not swapped:
            break  # Stop iteration if the collection is sorted.
    return collection

setup.py

# several files with ext .pyx, that i will call by their name
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules=[
    Extension("cybubble",       ["cybubble.pyx"]),
]

setup(
  name = 'MyProject',
  cmdclass = {'build_ext': build_ext},
  ext_modules = ext_modules,
)

编译Cython模块的命令：

python setup.py build_ext --inplace

结果：

Python execution time:
0.0014050007
Cython execution time:
1.5976260

结果表明，在这个例子中纯Python比Cython更快，而且Cython并不总是比纯Python更快。

我希望在这个脚本中Cython能够比纯Python表现得更好。

这就是我在benchmark.py中解决问题的方法。

import cybubble
import pybubble
from timeit import default_timer as timer
from decimal import *
import random
import copy
getcontext().prec = 8

if __name__ == '__main__':
    random_list = [random.randrange(0,10) for i in range(9999)]
    random_list2 = copy.copy(random_list)
    random_list3 = copy.copy(random_list)


    cy_start = timer()
    cybubble.bubble_sort(random_list2)
    cy_end = timer()

    py_start = timer()
    pybubble.bubble_sort(random_list3)
    py_end = timer()


    print "Python execution time:"
    python = (Decimal(py_end) - Decimal(py_start))
    print (python)

    print "Cython execution time:"
    cython = (Decimal(cy_end) - Decimal(cy_start))
    print (cython)

结果：

Python execution time:
8.9958801
Cython execution time:
1.6466939

- Rasool Ziafaty

---

时间差异相差几个数量级，这让我想到可能还有其他问题。建议您尝试找出Cython代码中哪些部分需要较长时间（例如在代码中加入计时器）。 - Blokje5

谢谢@Blokje5，但是我的Cython代码与我的Python代码完全相同，唯一的区别是cdef变量，如果我删除它们，Cython执行时间将为4.23674。您有更好的基准测试计时建议吗？ - Rasool Ziafaty

Answer 1

这是因为你对列表进行了原地排序--在列表是随机的情况下，你使用Cython先对列表进行排序，然后在列表已经排序的情况下使用Python对列表进行排序。由于冒泡排序在列表已经排序时的最佳时间复杂度为O(n)，因此当列表已经排序时调用Python版本的速度要比调用Cython版本快得多，而Cython版本在列表随机的情况下需要平均时间复杂度为O(n ^ 2)。

如果您想要正确地对这两个实现进行基准测试，应该对列表进行复制并进行排序。

- blhsing