数组变得太大时的 Stackoverflow

Question

我正在尝试实现一个带浮点数测试类的快速排序版本。当我尝试生成大小为 10⁸ 的数组时，运行我的测试类出现堆栈溢出。

我尝试使用大小为 10⁷ 的数组，效果很好

在我的测试类中，我生成了两个完全相同的数组，一个用我的算法排序，一个用 javas 排序 Arrays.sort()。

这是我的测试类的样子。

package Quicksort;

import org.junit.Before;
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;

public class QuickSortTest {

private static float[] quickSort, javaSort;
private final static int SIZE = (int) 1e7;

@Before
public void init(){
    System.gc();
    quickSort = new float[SIZE];
    javaSort = new float[SIZE];
    for(int i = 0; i < SIZE; i++){
        int temp = (int) (Math.random() * 1000) + 1;
        quickSort[i] = temp;
    }

    javaSort = quickSort;
}

@Test
public void testQuickSort(){
    QuickSort.sort(quickSort);
    Arrays.sort(javaSort, 0, SIZE);
    assertArrayEquals(quickSort, javaSort, .0f);
}

}

快速排序实施：

private static void quickSort(float[] table, int first, int last){
        if(first < last){
            int pivotIndex = partition(table, first, last);
            quickSort(table, first, pivotIndex - 1);
            quickSort(table, pivotIndex + 1, last);
        }
    }

public static int partition(float[] table, int first, int last){
        sort3(table, first, last);
        swap(table, first, (first + last) / 2);
        float pivot = table[first];
        int up = first;
        int down = last;
        do{
            while((up < last) && table[up] <= pivot){
                up++;
            }
            while(table[down] > pivot){
                down--;
            }
            if(up < down){
                swap(table, up, down);
            }
        }while(up < down);
        swap(table, first, down);
        return down;
    }

Answer 1

A WhosebugError 通常是由错误的递归调用引起的。你的 QuickSort class 有一个递归函数，当你传入一个长度为 10^8 的数组时，它会不断调用自己超出堆栈大小。

解决此问题的一种方法是将您的实现切换为迭代方法而不是递归方法。

根据您的上次更新，似乎 partition() 方法递归调用自身超出了 Java 堆 space.

的限制

在此 post 中，您可以找到一个迭代 partition() 实现。它稍微复杂一些，但能够处理数组的大小。

import java.util.Arrays;
import java.util.Random;

// Java program for implementation of QuickSort
class QuickSort
{
    public static void main(String[] args) {
        QuickSort sort=new QuickSort();
        int[] randomArray = createRandomArray((int) Math.pow(2, 20));

        sort.qSort(randomArray);
        //System.out.println(Arrays.toString(randomArray));
    }

    private void qSort(int[] arr) {
        this.qSort(arr, 0, arr.length-1);
    }

    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<=high-1; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    void qSort(int arr[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            qSort(arr, low, pi-1);
            qSort(arr, pi+1, high);
        }
    }


    private static int[] createRandomArray(int size){
        Random randNumGenerator = new Random();
        int[] arr = new int[size];
        for (int i=0; i<arr.length; i++)
        {
            arr[i] = (randNumGenerator.nextInt(100)+1);
        }
        return arr;
    }
}

看来您想牢记以下内容；

最大堆大小（changeable at JVM initiation），
最大堆栈大小 (changeable at JVM initiation) 和
Java (mostly 2^31, some new JVMs limits it to 2^31-5) 中的最大数组大小。

数组变得太大时的 Stackoverflow

Stackoverflow when arrays get too big

java

stack-overflow

quicksort