输入方差小的并行快速排序中的 Stackoverflow 异常

Question

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

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

java.lang.WhosebugError
    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

当我们使用 % 10 时，会生成很多重复值，这就是问题所在。

当子数组中的所有值都相等时，进一步的调用将停止，并且通过减少不必要的调用，jun 运行 3000000 个元素没有任何问题

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

            int[] pivotArr = partition(pivotIndex);
            pivotIndex=pivotArr[0];
            int pivotFlag=0;
            pivotFlag=pivotArr[1];
            if(pivotFlag!=1)
            invokeAll(new QSortJob<>(arr, left, pivotIndex-1),
                    new QSortJob<>(arr, pivotIndex+1, right));
        }
    }


    private int[] partition(int pivotIndex) {
        T pivotValue = arr[pivotIndex];
        int uniqVal=0,uniqFlag=0;
        int pivotArr[];
        swap(pivotIndex, right);

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

        swap(storeIndex, right);
        if(uniqVal == (right-left)) {
            uniqFlag=1;
            System.out.println("Yes, it is equal--"+uniqVal);
            }
        pivotArr=new int[]{storeIndex,uniqFlag};
        return pivotArr;
    }

Answer 2

这与当重复值过多时快速排序算法如何划分（子）数组有关。长话短说，你越来越接近快速排序最糟糕的运行时行为，这导致堆栈深度与要排序的数组大小成正比，而不是这个大小的对数。

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

让我们通过选择运行dom 生成的值除以 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 的第二次调用时发生了什么？我们有一个子数组，它是原始数组的长度减一。根据我们对您的算法的理解，我们可以由此得出结论，分区方法找到了 pivot 的值 0，因为我们数组中的所有值都是 >= 0，因此 none 的它们在枢轴的左边 "moved"，因此枢轴停留在它的初始位置，即索引 0，右边数组的大小变为初始大小减一。
然后算法在左边b运行ch上调用自己，它只有一个元素，并且立即returns，并且没有为它打印日志。
与 (1) 相同的推理适用于第四次和第五次调用（第 3 行和第 4 行）。
第五行是在选择1作为支点后生成的。在 0 和 1 均匀分布出现 "reasonably" 的假设下，我们有大致与 1 一样多的 0，这解释了 [=26] 的大小=]和99997 - 49882 = 50115分别为左右子数组，分别填充一个唯一值0或1。
这里是理解栈溢出的关键所在。我们可以在当前的左子数组和右子数组上重现 (1) 中应用的推理，因为它们由唯一值组成，将导致分区效率低下，因为主元值将始终位于子数组的最左边索引进行排序。随着堆栈的深入，我们可以在日志中观察到这种模式，因为 "right" 子数组的大小总是减少 1：50114、50113、50112、50111...和 49881、49880、49879 , 49878... 值得注意的是，我们从不打印左侧 b运行ch 的日志，因为它只会由一个元素组成 - 就像 (2).
我们可以通过归纳得出结论，从这一点开始，我们将不得不进行大约 100,000 / 2 = 50,000 次递归调用，从而过度填充堆栈。

此分析可用于运行将运行dom 生成的值除以 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 次，再次溢出堆栈。

结论
正如我们刚刚看到的，快速排序算法由于其分区方案，对待排序数组的内容很敏感。因此，"vulnerable" 它无法为每个输入提供保证运行一致的运行时复杂度。

一个典型的例子来说明这是一个已经排序的数组，或者，正如我们可以选择的那样，一个填充了唯一值的数组：

Arrays.fill(data, 0);

进一步分析和评论
这当然不是致命的：你的算法可以适应检测这些 "edge" 情况以切换到另一种策略并避免深度、低效的递归 calls.I 如果你愿意的话可以进一步描述我的意思.

输入方差小的并行快速排序中的 Stackoverflow 异常

Stackoverflow exception in parallel QuickSort with small variance of input

java

concurrency

quicksort

fork-join