python - 快速排序没有变得更快

Question

我最近了解到人们如何努力使快速排序更快。从随机选择一个枢轴元素到切换到较小数组的插入排序，甚至使用 3 向分区处理等键。我很好奇随机生成的数据是如何工作的，并想分析一些 python 代码。我附上下面的脚本。问题是脚本最终会花费相同的时间!当我使用 %prun 时，看起来快速排序被调用的次数也非常相似。所以，我们所做的所有改进只有在我们的数据遇到最坏情况(非常多的方向错误？)时才有用。

def hoare_partition(a, lo, hi):

    if lo >= hi or (lo + 1) == len(a) - 1:
        return None
    pivot = a[lo]
    left = lo + 1
    right = hi


    while left <= right and right < len(a):
        while left < len(a) and a[left] < pivot:
            left += 1
        while a[right] > pivot:
            right -= 1
        if left <= right and right < len(a):
            a[left], a[right] = a[right], a[left]
            left += 1
            right -= 1
    a[lo], a[right] = a[right], a[lo]
    return right

def hoare_quicksort(a, lo, hi):
    ''' this is a vanilla implementation of quick sort. this will call the partition method that uses first element as pivot '''

    if lo < hi:
        p = hoare_partition(a, lo, hi)
        if p:
            #print 'calling for ', lo, p - 1
            hoare_quicksort(a, lo, p - 1)  

            #print 'calling for ', p + 1, hi
            hoare_quicksort(a, p + 1, hi)

这是我们选择第一个元素本身作为枢轴的 Vanilla 实现。然后，我改为选择中点。

所以，一行被改变了

mid = lo + (hi - lo)//2

a[lo], a[mid] = a[mid], a[lo]
pivot = a[lo]

然后我也做随机枢轴选择，像这样:

pos = random.randint(lo, hi + 1)


a[lo], a[pos] = a[pos], a[lo]
pivot = a[lo]

现在，我用

称呼他们

%prun hoare_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun mid_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)
%prun random_quicksort([random.randint(0, 10000) for i in xrange(1000)], 0, 999)

所有这些花费的时间几乎相同(5.22、5.27、5.61 毫秒)。当我使用 %prun 调用它们并查看快速排序被调用的次数时，我再次得到非常相似的数字。那么，怎么了？

Answer 1

你的基准被打破了。

1. 您正在对 random.randint 的 1000 次迭代进行基准测试，而不是您的排序。
2. 每个排序只运行一次，因此您要对操作系统中的线程和进程切换延迟进行基准测试。

尝试预先创建源数组并运行每个排序千次，甚至数百万次。