Получил stackoverflowerror при использовании быстрой сортировки, могу ли я увеличить стек и кучу? - PullRequest
Новая
       37

Получил stackoverflowerror при использовании быстрой сортировки, могу ли я увеличить стек и кучу?

2 голосов
/ 20 мая 2011

Могу ли я увеличить стек и кучу в Java? Я использую BlueJ.

========

EDIT:

Вот код: 

// ***** Quick-Sort Method *****

public static void quickSort(int[] data, int first, int n)
{
    int p, n1, n2;
    if(n > 1)
    {
        p = partition(data, first, n);
        n1 = p - first;
        n2 = n - n1 - 1;
        quickSort(data, first, n1);
        quickSort(data, p+1, n2);
    }
}

// ***** PRIVATE HELPER FUNCTIONS *****

public static void quickSort(int[] data)
{
    quickSort(data, 0, data.length);
}

private static int partition(int[] A, int first, int n )
{
    int right = first + n - 1;
    int ls = first;
    int pivot = A[first];
    for(int i = first+1; i <= right; i++)
    {
        if(A[i] <= pivot)
        // Move items smaller than pivot only, to location that would be at left of pivot
        {
            ls++;
            swap(A, i, ls);
        }
    }
    swap(A, first, ls);
    return ls;
}

private static void swap(int[] data, int pos1, int pos2)
{
    int temp = data[pos1];
    data[pos1] = data[pos2];
    data[pos2] = temp;
}

Ответы [ 5 ]

6 голосов
/ 20 мая 2011

Попытка увеличить размер стека из-за переполнения - это все равно, что покупать больше мусорных баков, когда ваша корзина заполнена, а не вывозить ее на свалку.

Скорее всего, вы идете в бесконечную рекурсию.Не могли бы вы опубликовать свой код?

2 голосов
/ 20 мая 2011

Можно использовать следующие параметры JVM:

  • -Xms начальный размер кучи Java
  • -Xmx максимальный размер кучи Java
  • -Xss Setразмер стека потоков

Если вы хотите установить эти параметры по умолчанию в BlueJ, вам нужно сделать следующее:

  • Найти bluej.defs файл
  • Найдите bluej.vm.args свойство (строку) в этом файле
  • Добавьте параметр, который вы хотите в этой строке, например bluej.vm.args = -Xmx512m, чтобы установить размер кучи максимум 512 МБ.

Надеюсь, это поможет.

1 голос
/ 20 мая 2011

Ошибка переполнения стека обычно возникает из-за неправильного рекурсивного вызова.Вы уверены, что не делаете ничего плохого, например, указываете правильные пути выхода (или условия завершения) для своего потока рекурсии?

0 голосов
/ 20 мая 2011

Простейшая реализация Quicksort в худшем случае уязвима для использования памяти O (N). можно изменить его для использования O (log N) в худшем случае, только вернувшись в меньший подмассив и превратив оставшуюся рекурсию в цикл while: 

//the following code probably contains of-by-one errors

quicksort(xs, begin, end):
    while(not empty list){
        mid = partition(xs, begin, end)
        if( mid-begin < end-mid){
            quicksort(xs, begin, mid)
            end = mid
        }else{
            quicksort(xs, mid, end)
            begin = mid
        }
0 голосов
/ 20 мая 2011

мне кажется, что это раздел, который прослушивается 

private static int partition(int[] A, int first, int n )
{
    int right = first + n-1;
    int ls = first;
    int pivot = A[right];//use right most for pivot
    for(int i = first;i<right;i++)
    {
        if(A[i]<pivot){
           swap(A,i,ls);
           ls++;//inc after swap
        }

    }
    swap(A,right,ls);
    return ls;
}

Я получил этот код из Википедии

...