java - 当数组变得太大时 Stackoverflow

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 5 年前。

Improve this question

我正在尝试使用采用 float 的测试类来实现快速排序的版本。当我尝试生成大小为 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

StackOverflowError 通常是由错误的递归调用引起的。您的 QuickSort 类有一个递归函数，当您传入长度为 10^8 的数组时，该函数会在超出堆栈大小时不断调用自身。

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

根据您的上次更新，似乎 partition() 方法递归地调用自身，超出了 Java 堆空间的限制。

在此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 )。