Numpy 用timeit进行性能分析

Python标准库中的timeit是一个用来测量代码段执行时间的模块。我们将使用不同大小的NumPy数组，测量其调用sort函数时所要耗费的时间。经典的快速排序和归并排序算法的平均执行时间是O(nlogn)，因此我们将尝试对测量结果进行拟合，看其是否具有类似的时间复杂度。

具体步骤

我们需要若干用来排序的数组。

1. 创建用来排序的数组。

创建若干不同大小的数组，其中的数组元素都是随机整数。

times = numpy.array([])

for size in sizes:
    integers = numpy.random.random_integers
    (1, 10 ** 6, size)

2. 测量执行时间。

为了测量时长，需要创建一个定时器，并为其提供一个需要执行的函数和相关的引入语句。然后执行100次排序操作，得到总的排序时间。

def measure():
    timer = timeit.Timer('dosort()',
    'from __main__ import dosort')

    return timer.timeit(10 ** 2)        

3. 构建测量时间数组。

通过逐一添加测量值的方式，构建测量时间数组。

times = numpy.append(times, measure())

4. 比照nlogn模型拟合数据。

比照nlogn这个理论模型，对测量时间数据进行拟合。因为我们选择的数组大小是2的整数次幂，通过改变幂指数来改变大小，所以相关的计算过程并不复杂。

fit = numpy.polyfit(sizes * powersOf2, times, 1)

本攻略的完整代码如下。

import numpy
import timeit
import matplotlib.pyplot

# 本程序用来测量NumPy中sort函数的性能
# 并绘制出数组大小与执行时间的对应关系图。
integers = []

def dosort():
    integers.sort()

def measure():
    timer = timeit.Timer('dosort()', 
    'from __main__ import dosort')

return timer.timeit(10 ** 2)

powersOf2 = numpy.arange(0, 19)
sizes = 2 ** powersOf2

times = numpy.array([])

for size in sizes:
    integers = numpy.random.random_integers(1, 10 ** 6, size)
    times = numpy.append(times, measure())

fit = numpy.polyfit(sizes * powersOf2, times, 1)
print fit
matplotlib.pyplot.title("Sort array sizes vs execution times")
matplotlib.pyplot.xlabel("Size")
matplotlib.pyplot.ylabel("(s)")
matplotlib.pyplot.semilogx(sizes, times, 'ro')
matplotlib.pyplot.semilogx(sizes, 
numpy.polyval(fit, sizes * powersOf2))
matplotlib.pyplot.show()

最终得到的数组大小和执行时间的对应关系图如下：

攻略小结

我们测量了NumPy中sort函数的平均执行时间。本攻略中用到了如下函数。