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

Question

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

当随机生成的Integers的方差较大时，即random.nextInt()，这一切都可以正常工作。但每当方差减小时，即random.nextInt() % 10，我都会得到如下异常跟踪：

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

测试。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 ran对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

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

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

让我们通过选择剩余的随机生成值除以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;
}

我运行了一个大小为100000的程序——这足以让我重现堆栈溢出。让我们看看第一次通话的记录：

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

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

这种分析可以转化为这样一种情况：我们将随机生成的值的剩余部分除以10。这就为输入数组留下了一组大小为160,000的值{-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，在均匀分布的假设下，这就给我们留下了数组中每个值的160000 / 19 ~= 8421次出现。让我们重现我们之前采用的推理：在递归过程中的某个时刻，我们将这些值中的每一个分离成大小为8421的数组，从那里开始，算法将调用自己8421次，再次溢出堆栈

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

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

Arrays.fill(data, 0);

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