java - 并行QuickSort中的Stackoverflow异常，输入变化很小

Question

我已经使用Java ForkJoin库实现了并发的快速排序算法。我正在使用大量随机生成的Integers测试解决方案。

当随机生成的Integers的方差很大时，这一切都很好。 random.nextInt()。但是只要方差减小，即。 random.nextInt() % 10，我得到了这样的异常跟踪：

java.lang.StackOverflowError
    at java.util.concurrent.ForkJoinTask.setExceptionalCompletion(ForkJoinTask.java:489) ...

Test.java

public static void main(String[] args) {
    final int SIZE = 160_000;
    Random rand = new Random();
    Integer[] data = new Integer[SIZE];

    for(int i = 0; i < data.length; i++) {
        data[i] = rand.nextInt() % 10; // works for "rand.nextInt()", breaks with "% 10"
    }

    long t0 = System.currentTimeMillis();
    QSort.sort(data);
    long t1 = System.currentTimeMillis();

    System.out.println("Sorted: " + QSort.isSorted(data));
    System.out.println("Time elapsed: " + (t1-t0) + " ms");
}

QSort.java

public class QSort {

    private static class QSortJob<T extends Comparable<T>> extends RecursiveAction {

        private final T[] arr;

        private final int left;

        private final int right;

        private QSortJob(T[] arr, int left, int right) {
            this.arr = Objects.requireNonNull(arr);
            this.left = left;
            this.right = right;
        }

        @Override
        protected void compute() {
            if (left < right) {
                int pivotIndex = left + (right - left) / 2;

                pivotIndex = partition(pivotIndex);

                invokeAll(new QSortJob<>(arr, left, pivotIndex-1),
                        new QSortJob<>(arr, pivotIndex+1, right));
            }
        }


        private int partition(int pivotIndex) {
            T pivotValue = arr[pivotIndex];

            swap(pivotIndex, right);

            int storeIndex = left;
            for (int i=left; i<right; i++) {
                if (arr[i].compareTo(pivotValue) < 0) {
                    swap(i, storeIndex);
                    storeIndex++;
                }
            }

            swap(storeIndex, right);

            return storeIndex;
        }

        private void swap(int i, int j) {
            T tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }       
    }

    public static <T extends Comparable<T>> void sort(T[] arr) {
        ForkJoinPool pool = new ForkJoinPool();
        pool.invoke(new QSortJob<>(arr, 0, arr.length-1));
        pool.shutdown();
    }

为什么会在很小的输入方差上发生这种情况，如何解决它？

Answer 1

这与当太多值被重复时快速排序算法如何划分（子）数组有关。总而言之，您越来越接近快速排序的最坏运行时行为，这导致堆栈深度与要排序的数组大小成正比，而不是该大小的对数。

分析
为了说明这一点，让我们看一个例子。

让我们通过选择除以2时的随机生成值的余数来简化示例。这使我们仅关注两个不同的值。

在执行快速排序以帮助我们调查时，我们将打印以下信息：depth，这是递归在堆栈中的深度（为简单起见，我们将忽略fork-join框架进行的其他调用，这不会影响分析），branch，这是我们在分区子数组的左侧还是右侧进行操作，以及此子数组的length：

private static class QSortJob<T extends Comparable<T>> extends RecursiveAction {
    private final T[] arr;
    private final int left;
    private final int right;
    private final int depth;
    private final String branch;

    private QSortJob(T[] arr, int left, int right, int depth, String branch) {
        this.arr = Objects.requireNonNull(arr);
        this.left = left;
        this.right = right;
        this.depth = depth;
        this.branch = branch;
    }

    @Override
    protected void compute() {
        if (left < right) {
            int pivotIndex = left + (right - left) / 2;
            System.out.println(String.format("Branch=%s, depth=%d, length(subarray)=%d", branch, depth, right - left + 1));

            pivotIndex = partition(pivotIndex);
            invokeAll(new QSortJob<>(arr, left, pivotIndex-1, depth + 1, "Left"),
                    new QSortJob<>(arr, pivotIndex+1, right, depth + 1, "Right"));
        }
    }

第一次呼叫将如下所示：

pool.invoke(new QSortJob<>(arr, 0, arr.length-1, 0, "Root"));

让我们使用以下方法生成值的分布：

for(int i = 0; i < data.length; i++) {
    data[i] = Math.abs(rand.nextInt()) % 2;
}

我运行的程序大小为100,000，这足以重现堆栈溢出。让我们看一下第一个调用的日志：

Branch=Root, depth=0, length(subarray)=100000
Branch=Right, depth=1, length(subarray)=99999
Branch=Right, depth=2, length(subarray)=99998
Branch=Right, depth=3, length(subarray)=99997
Branch=Left, depth=4, length(subarray)=49882
Branch=Right, depth=4, length(subarray)=50114
Branch=Right, depth=5, length(subarray)=49881
Branch=Right, depth=5, length(subarray)=50113
Branch=Right, depth=6, length(subarray)=49880
Branch=Right, depth=6, length(subarray)=50112
Branch=Right, depth=7, length(subarray)=49879
Branch=Right, depth=7, length(subarray)=50111
Branch=Right, depth=8, length(subarray)=49878

当我们第二次调用QSortJob#compute时发生了什么？我们有一个子数组，它是原始数组的长度减去一。根据对算法的理解，可以得出结论，分区方法找到了数据透视图的值0，因为数组中的所有值均为>= 0，因此没有一个“移动”到左侧。因此，枢轴将停留在其初始位置（即索引0），并且右数组的大小将变为初始大小减一。
然后，该算法在只有一个元素的左分支上调用自身，并立即返回，并且不会为其打印任何日志。
与（1）相同的推理适用于第四和第五次调用（第3行和第4行）。
在选择1作为枢轴之后生成第五行。在0和1出现“合理”均匀分布的假设下，我们的0和1大致一样多，这解释了左右子数组49882和99997 - 49882 = 50115的大小。 ，分别用唯一值0或1填充。
这是了解堆栈溢出的关键所在。我们可以重现在（1）中应用于当前左右子数组的推理，由于它们是由唯一值构成的，因此将导致分区效率低下，因为枢轴值始终位于子数组的最左索引处进行排序。当我们深入堆栈时，我们可以在日志中观察到这种模式，因为“右”子数组的大小始终减小1：50114、50113、50112、50111 ...和49881、49880、49879、49878 ...值得注意的是，我们永远不会为左分支打印日志，因为它只会由一个元素组成-就像（2）中那样。
我们可以通过归纳得出结论，从现在开始，我们将不得不进行大致100,000 / 2 = 50,000的递归调用，从而过度填充堆栈。


可以将这种分析转换为以下情况：当除以10时，我们将剩下的随机生成的值取整。这使我们获得了值{-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}的集合，输入数组的大小为160,000，并且在统一下分布式假设，这使我们在数组中出现每个160000 / 19 ~= 8421这些值。让我们重述一下我们先前采用的理由：在递归过程中的某个时候，我们将这些值中的每一个都隔离在大小为〜8421的数组中，从那里，该算法将调用自身8421次，再次使堆栈溢出。

结论
正如我们所看到的，由于其分区方案，快速排序算法对要排序的数组的内容很敏感。因此，它是“易受攻击的”，因此无法为每个输入提供保证的，一致的运行时复杂性。

一个典型的例子来说明这是一个已经排序的数组，或者，如我们所选择的，一个填充有唯一值的数组：

Arrays.fill(data, 0);

进一步分析和评论
这当然不是致命的：您的算法可以适应检测这些“边缘”情况以切换到另一种策略，并避免进行深度，低效的递归调用。如果您愿意，我可以进一步描述我的意思。