以前有人见过这种改进吗？

Question

处理先前快速排序中的重复元素

我找到了一种在quicksort中更有效地处理重复元素的方法,并且想知道是否有人之前已经看过这个.

这种方法大大减少了检查重复元素所涉及的开销,这有助于在有和没有重复元素的情况下提高性能.通常,重复的元素以几种不同的方式处理,我将首先列举.

首先,有荷兰国旗方法对数组进行排序[ < pivot | == pivot | unsorted | > pivot].

其次,有一种方法是在排序过程中将相等的元素放在最左边,然后将它们移动到排序中心[ == pivot | < pivot | unsorted | > pivot],然后在排序后将==元素移动到中心.

第三,Bentley-McIlroy分区将==元素放在两边,以便排序[ == pivot | < pivot | unsorted | > pivot | == pivot],然后==元素移动到中间.

最后两种方法是为了减少开销.

我的方法

现在,让我解释一下我的方法如何通过减少比较次数来改进快速排序.我一起使用两个quicksort函数而不是一个.

我将调用的第一个函数q1,它将数组排序为[ < pivot | unsorted | >= pivot].

我将调用的第二个函数q2,它将数组排序为[ <= pivot | unsorted | > pivot].

现在让我们一起看看它们的用法,以便改进重复元素的处理.

首先,我们调用q1整个数组.它选择了一个我们将进一步引用的枢轴,pivot1然后进行排序pivot1.因此,我们的数组按此顺序排序[ < pivot1 | >= pivot1 ].

然后,对于[ < pivot1]分区,我们q1再次发送它,那部分是相当正常的,所以让我们先对另一个分区进行排序.

对于[ >= pivot1]分区,我们将其发送给q2.q2选择一个数据透视表,我们将从pivot2该子数组中引用它并将其分类[ <= pivot2 | > pivot2].

如果我们现在看整个数组,我们的排序看起来像[ < pivot1 | >= pivot1 and <= pivot2 | > pivot2].这看起来非常像双枢轴快速排序.

现在,让我们回到q2([ <= pivot2 | > pivot2])里面的子阵列.

对于[ > pivot2]分区,我们只是将其发送回q1不是很有趣.

对于[ <= pivot2]分区,我们首先检查是否pivot1 == pivot2.如果它们相等,则此分区已经排序,因为它们都是相同的元素!如果枢轴不相等,那么我们只是q2再次发送这个分区,它选择一个枢轴(进一步pivot3),排序,如果pivot3 == pivot1,那么它就不必排序[ <= pivot 3]等等.

希望你现在明白了.使用这种技术的改进是处理相同的元素而不必检查每个元素是否也等于枢轴.换句话说,它使用较少的比较.

我还没有尝试过另一种可能的改进,即检查分区qs2的大小[ <= pivot2]是否相当大(或者[> pivot2]分区非常小),与其整个子阵列的大小相比,然后再做一个更标准的改进在这种情况下检查重复的元素(上面列出的方法之一).

源代码

这里有两个非常简单qs1和qs2功能.他们使用Sedgewick会聚指针排序方法.它们显然可以非常优化(例如,他们选择非常差的枢轴),但这只是为了表明这个想法.我自己的实现更长,更快,更难读,所以让我们从这开始:

// qs sorts into [ < p | >= p ]
void qs1(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[right], temp;
    long i = left - 1, j = right;
    // do the sort
    for(;;){
        while(a[++i] < pivot);
        while(a[--j] >= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[i];
    a[i] = a[right];
    a[right] = temp;

    // send the [ < p ] partition to qs1
    if(left < i - 1)
        qs1(a, left, i - 1);
    // send the [ >= p] partition to qs2
    if( right > i + 1)
        qs2(a, i + 1, right);
}

void qs2(int a[], long left, long right){
    // Pick a pivot and set up some indicies
    int pivot = a[left], temp;
    long i = left, j = right + 1;
    // do the sort
    for(;;){
        while(a[--j] > pivot);
        while(a[++i] <= pivot) if(i == j) break;
        if(i >= j) break;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    // Put the pivot in the correct spot
    temp = a[j];
    a[j] = a[left];
    a[left] = temp;

    // Send the [ > p ] partition to qs1
    if( right > j + 1)
        qs1(a, j + 1, right);
    // Here is where we check the pivots.
    // a[left-1] is the other pivot we need to compare with.
    // This handles the repeated elements.
    if(pivot != a[left-1])
            // since the pivots don't match, we pass [ <= p ] on to qs2
        if(left < j - 1)
            qs2(a, left, j - 1);
}

我知道这是一个相当简单的想法,但是当我添加标准的快速排序改进时,它在运行时得到了相当大的改进(3个枢轴选择的中位数和小数组的插入排序).如果您要使用此代码进行测试,则只能在随机数据上进行测试,因为选择较差的轴(或改进了轴选择).要使用此类,您可以调用:

qs1(array,0,indexofendofarray);

一些基准

如果你想知道它有多快,这里有一些初学者的数据.这使用我的优化版本,而不是上面给出的版本.然而,上面给出的那个仍然比双枢轴快速时间更接近std::sort时间.

在具有2,000,000个元素的高度随机数据上,我得到了这些时间(从排序几个连续数据集):

std::sort - 1.609 seconds  
dual-pivot quicksort - 1.25 seconds  
qs1/qs2 - 1.172 seconds

std::sortC++标准库排序在哪里,双枢轴快速排序是几个月前由Vladimir Yaroslavskiy发布的,并且qs1/qs2是我的快速实施.

随机数据少得多.拥有2,000,000个元素并生成rand() % 1000(这意味着每个元素大约有2000个副本)的时间是:

std::sort - 0.468 seconds  
dual-pivot quicksort - 0.438 seconds  
qs1/qs2 - 0.407 seconds

在某些情况下,双枢轴快速排序胜出,我确实意识到双枢轴快速排序可以进行更多优化,但同样可以安全地说明我的快速排序.

谁看过这个吗？

我知道这是一个很长的问题/解释,但你们之前有没有看到过这种改进？如果是这样,为什么不使用它？

Answer 1

Vladimir Yaroslavskiy | 9月11日12:35 使用新的Dual-Pivot Quicksort替换java.util.Arrays中的Quicksort

访问http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Answer 2

要回答你的问题,我以前没有见过这种方法.我不打算对你的代码进行分析并做其他艰苦的工作,但也许以下是正式展示你的算法的下一步/考虑因素.在现实世界中,实现排序算法以具有:

良好的可扩展性/复杂性和低开销

扩展和开销很明显,易于衡量.在分析排序时,除了时间衡量比较和交换的数量.大文件的性能也取决于磁盘搜索时间.例如,合并排序适用于带磁盘的大型文件.(另请参阅快速排序与合并排序)

广泛的输入和良好的性能

有很多数据需要排序.众所周知,应用程序以模式生成数据,因此在某些模式下使排序具有抵御性能差的重要性非常重要.您的算法针对重复数字进行优化.如果所有数字都重复但只有一次(即seq 1000> file; seq 1000 >> file; shuf file)怎么办？如果数字已经排序怎么办？向后排序？1,2,3,1,2,3,1,2,3,1,2,3的模式怎么样？1,2,3,4,5,6,7,6,5,4,3,2,1？7,6,5,4,3,2,1,2,3,4,5,6,7？在其中一种常见情况下表现不佳是一个交易破坏者!在与已发布的通用算法进行比较之前,准备好此分析是明智的.

病理表现低风险

在所有输入的排列中,有一个比其他输入更糟糕.表现比平均水平差多少？有多少排列会提供类似的不良表现？

祝你下一步好运!

Answer 3

这是一个很大的改进，我确信如果您期望有很多相等的对象，它已经被专门实现了。这种墙周有很多。

如果我理解你写的所有内容都是正确的，那么它不被普遍“了解”的原因是它确实提高了基本的 O(n2) 性能。这意味着，对象数量增加一倍，时间增加四倍。除非所有对象都是平等的，否则你的改进不会改变这一点。