Java - ForkJoin/MergeSort Stackoverflow

Question

我正在使用 ForkJoin 框架来实现合并排序/插入排序排序解决方案。但是我遇到了 stackoverflow 错误，并且似乎无法追踪问题发生的位置。该解决方案旨在对 1 - 10,000000 范围内的随机值进行排序。对于 0 - 100 的范围，我使用插入排序，对于更大的范围，我使用合并排序。

主要方法:

class Assignment3 {
  public static void main(String[] args) {              
    long startTime1 = System.currentTimeMillis();
    int S = 10000000;
    int d[] = new int[S];

    for(int j=0;j<d.length;j++) {
        d[j] = (int)(Math.random()*10000);
    }

    ForkJoinPool fjpool = new ForkJoinPool();
    // Array, lb, ub
    fjpool.invoke(new Ass3Q2(d,0,d.length));

    long endTime1 = System.currentTimeMillis();
    long runningTime1 = endTime1 - startTime1;
    System.out.println(runningTime1+" millisecs ("+(runningTime1/1000.0)+")");

    boolean sorted = true;
    for(int i=0;i<d.length-1;i++) {
        if(d[i] > d[i+1]) {
            sorted = false;
        }
    }
    System.out.println("Sorted List: "+sorted);
   }
 }

排序解决方案:

class Ass3Q2 extends RecursiveAction{

/* RecursiveAction becasue we dont want to return a value */

private int[] f;
private int lb;
private int ub;
private static final int BLOCKSIZE = 100;

public Ass3Q2(int a[], int l, int u) {
    f = a;lb = l;ub = u;
}

protected void compute() {
    // Check if bounds are within block size
    if(ub-lb <= BLOCKSIZE) {
        // Do Insertion sort
        System.out.println("UB/LB: "+(ub-lb));
        insertionSort(f, lb, ub);
    } else {
        // MergeSort
        int m = lb + (ub-lb)/2;
        System.out.println("Mid: "+m);
        Ass3Q2 left = new Ass3Q2(f, lb, m);
        Ass3Q2 right = new Ass3Q2(f, m+1, ub);
        invokeAll(left,right);
        left.join();right.join();
        mergeSort(f, lb, ub);
    }
}

 static void mergeSort(int a[], int l, int u) {
    if(l+1 < u) {
        int mid = (l+u)/2;
        mergeSort(a,l,u);
        mergeSort(a,mid,u);
        merge(a,l,mid,u);
    }
}

 static void merge(int f[], int p, int q, int r){
        //p<=q<=r
        int i = p; int j = q;
        //use temp array to store merged sub-sequence
        int temp[] = new int[r-p]; int t = 0;
        while(i < q && j < r){
            if(f[i] <= f[j]){
                temp[t]=f[i];i++;t++;
            }
            else{
                temp[t] = f[j]; j++; t++;
            }
        }
        //tag on remaining sequence
        while(i < q){ temp[t]=f[i];i++;t++;}
        while(j < r){ temp[t] = f[j]; j++; t++;}
        //copy temp back to f
        i = p; t = 0;
        while(t < temp.length){ f[i] = temp[t]; i++; t++;}
  }


 static void insertionSort(int f[], int lb, int ub) {
    for(int i = lb; i< ub; i++) {
        int j = i;
        int k = f[i];
        while((j>0)&&(f[j-1] > k)) {
            f[j] = f[j-1];
            j--;
        }
        f[j] = k;
    }
}


}

堆栈跟踪:

Exception in thread "main" java.lang.StackOverflowError
at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
at sun.reflect.NativeConstructorAccessorImpl.newInstance(Unknown Source)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source)
at java.lang.reflect.Constructor.newInstance(Unknown Source)
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source)
at java.util.concurrent.ForkJoinTask.reportResult(Unknown Source)
at java.util.concurrent.ForkJoinTask.join(Unknown Source)
at java.util.concurrent.ForkJoinPool.invoke(Unknown Source)
at Assignment3.main(Assignment3.java:71)
Caused by: java.lang.StackOverflowError
at Ass3Q2.mergeSort(Assignment3.java:150)
at Ass3Q2.mergeSort(Assignment3.java:150)
at Ass3Q2.mergeSort(Assignment3.java:150)
at Ass3Q2.mergeSort(Assignment3.java:150)
at Ass3Q2.mergeSort(Assignment3.java:150)
at Ass3Q2.mergeSort(Assignment3.java:150)

Answer 1

mergeSort 使用相同的参数调用自身:mergeSort(a,l,u);(如果我们输入 if)，那就是stackoverflow错误的原因。

static void mergeSort(int a[], int l, int u) {
    if(l+1 < u) {
        int mid = (l+u)/2;
        mergeSort(a,l,u); // this call is most likely unwanted
        mergeSort(a,mid,u);
        merge(a,l,mid,u);
    }
}