来自CPython合并排序的意外性能曲线

Question

我在Python中实现了一个简单的合并排序算法.算法和测试代码如下:

import time
import random
import matplotlib.pyplot as plt
import math
from collections import deque

def sort(unsorted):
    if len(unsorted) <= 1:
        return unsorted
    to_merge = deque(deque([elem]) for elem in unsorted)
    while len(to_merge) > 1:
        left = to_merge.popleft()
        right = to_merge.popleft()
        to_merge.append(merge(left, right))
    return to_merge.pop()

def merge(left, right):
    result = deque()
    while left or right:
        if left and right:
            elem = left.popleft() if left[0] > right[0] else right.popleft()
        elif not left and right:
            elem = right.popleft()
        elif not right and left:
            elem = left.popleft()
        result.append(elem)
    return result

LOOP_COUNT = 100
START_N = 1
END_N = 1000

def test(fun, test_data):
    start = time.clock()
    for _ in xrange(LOOP_COUNT):
        fun(test_data)
    return  time.clock() - start

def run_test():
    timings, elem_nums = [], []
    test_data = random.sample(xrange(100000), END_N)
    for i in xrange(START_N, END_N):
        loop_test_data = test_data[:i]
        elapsed = test(sort, loop_test_data)
        timings.append(elapsed)
        elem_nums.append(len(loop_test_data))
        print "%f s --- %d elems" % (elapsed, len(loop_test_data))
    plt.plot(elem_nums, timings)
    plt.show()

run_test()

尽管我可以看到一切正常,但我应该得到一个漂亮的N*logN曲线.但图片略有不同:

http://s8.postimage.org/o8ysrafat/deque_long_run_2.png

我试图调查这个问题的事情:

1. PyPy.曲线没问题.
2. 使用gc模块禁用GC.错误的猜测.调试输出显示它甚至在测试结束之前都没有运行.
3. 使用meliae进行内存分析 - 没什么特别的或可疑的.`我有另一个实现(使用相同的合并函数的递归实现),它的行为方式类似.我创建的测试周期越多 - 曲线中的"跳跃"越多.

那么如何解释这种行为并 - 有希望 - 解决？

UPD:将列表更改为collections.deque

UPD2:添加了完整的测试代码

UPD3:我在Ubuntu 11.04操作系统上使用Python 2.7.1,使用四核2Hz笔记本电脑.我试图扭转大部分其他过程:尖峰的数量下降,但其中至少有一个仍在那里.

Answer 1

您只是在机器上获得其他进程的影响.

对输入大小1运行排序功能100次,并记录在此上花费的总时间.然后为输入大小2运行100次,并记录花费的总时间.您继续这样做,直到达到输入大小1000.

假设您的操作系统(或您自己)偶尔开始做一些CPU密集型操作.让我们说这个"尖峰"只要你运行你的排序功能5000次就会持续.这意味着5000/100 = 50个连续输入大小的执行时间看起来很慢.过了一会儿,另一个尖峰发生了,另一个输入尺寸范围看起来很慢.这正是您在图表中看到的.

我可以想到一种避免这个问题的方法.对每个输入大小运行一次排序功能:1,2,3,...,1000.重复此过程100次,使用相同的1000个输入(重要的是,请参见最后的说明).现在将每个输入大小花在的最小时间作为图表的最终数据点.

这样,你的尖峰应该只影响每个输入大小,只有100次运行中的几次; 而且由于你采取的是最低限度,它们可能对最终图表没有任何影响.

如果你的尖峰真的很长很频繁,你当然可能想要增加超过当前每个输入大小100的重复次数.

看着你的尖峰,我注意到在尖峰期间执行速度正好减慢了3次.我猜这个操作系统会在高负载期间为你的python进程提供一个插槽.无论我的猜测是否正确,我推荐的方法都应该解决问题.

编辑:

我意识到我没有在我提出的问题解决方案中澄清一点.

对于给定的输入大小,您应该在100次运行中的每次运行中使用相同的输入吗？或者应该使用100种不同的(随机)输入？

由于我建议花费最少的执行时间,因此输入应该相同(否则您将得到不正确的输出,因为您将测量最佳情况算法复杂度而不是平均复杂度!).

但是当你采用相同的输入时,你会在图表中产生一些噪音,因为有些输入比其他输入快.

因此,更好的解决方案是解决系统负载问题,而不会产生每个输入大小只有一个输入的问题(这显然是伪代码):

seed = 'choose whatever you like'
repeats = 4
inputs_per_size = 25
runtimes = defaultdict(lambda : float('inf'))
for r in range(repeats):
  random.seed(seed)
  for i in range(inputs_per_size):
    for n in range(1000):
      input = generate_random_input(size = n)
      execution_time = get_execution_time(input)
      if runtimes[(n, i)] > execution_time:
        runtimes[(n,i)] = execution_time
for n in range(1000):
  runtimes[n] = sum(runtimes[(n,i)] for i in range(inputs_per_size))/inputs_per_size

现在你可以使用runtimes [n]来构建你的情节.

当然,根据您的系统是否超吵,你可能会改变(repeats, inputs_per_size)从(4,25)地说,(10,10)或甚(25,4).

Answer 2

我可以使用您的代码重现尖峰:

您应该选择一个合适的计时功能(time.time()vs. time.clock()- from timeit import default_timer),测试中的重复次数(每次测试需要多长时间),以及从中选择最短时间的测试次数.它可以为您提供更好的精度和更少的外部影响.阅读timeit.Timer.repeat()文档中的说明:

从结果向量计算平均值和标准偏差并报告这些是很诱人的.但是,这不是很有用.在典型情况下,最低值给出了机器运行给定代码段的速度的下限; 结果向量中较高的值通常不是由Python的速度变化引起的,而是由于其他过程干扰您的计时准确性.因此结果的min()可能是您应该感兴趣的唯一数字. 之后,您应该查看整个向量并应用常识而不是统计.

timeit 模块可以为您选择合适的参数:

$ python -mtimeit -s 'from m import testdata, sort; a = testdata[:500]' 'sort(a)'

这是timeit基于性能的曲线:

该图显示sort()行为与O(n*log(n))以下内容一致:

|------------------------------+-------------------|
| Fitting polynom              | Function          |
|------------------------------+-------------------|
| 1.00  log2(N)   +  1.25e-015 | N                 |
| 2.00  log2(N)   +  5.31e-018 | N*N               |
| 1.19  log2(N)   +      1.116 | N*log2(N)         |
| 1.37  log2(N)   +      2.232 | N*log2(N)*log2(N) |

为了生成我用过的数字make-figures.py:

$ python make-figures.py --nsublists 1 --maxn=0x100000 -s vkazanov.msort -s vkazanov.msort_builtin 

哪里:

# adapt sorting functions for make-figures.py
def msort(lists):
    assert len(lists) == 1
    return sort(lists[0]) # `sort()` from the question

def msort_builtin(lists):
    assert len(lists) == 1
    return sorted(lists[0]) # builtin

此处描述了输入列表(注意:输入已排序,因此内置sorted()函数显示预期的O(N)性能).