Переполнение стека, когда массивы становятся слишком большими

Я пытаюсь реализовать версию быстрой сортировки с тестовыми классами, которая принимает 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;
    }
Источник

1 ответ

Решение

StackruError обычно вызывается плохим рекурсивным вызовом. Ваш QuickSort Класс имеет рекурсивные функции, которые продолжают вызывать себя за пределами размера стека, когда вы передаете массив длиной 10^8.

Чтобы решить эту проблему, нужно переключить реализацию на итеративный, а не рекурсивный.

на основании вашего последнего обновления, кажется, partition() Метод вызывает себя рекурсивно за пределами пространства кучи Java.

В этом посте вы можете найти итеративный 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;
    }
}

Кажется, вы хотите запомнить следующее;

Источник
Другие вопросы по тегам