Быстрый алгоритм, вызывающий переполнение стека

Question

SOLVED: опубликовано в конце этого комментария.

Я продолжаю получать эту ошибку, и я не могу найти объяснения, почему это происходит.

Exception in thread "main" java.lang.StackOverflowError 
at java.util.Random.nextDouble(Random.java:444) 
at java.lang.Math.random(Math.java:716) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:50) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 

Я как сумасшедший прибегая к помощи и, кажется, никто не имел такую ​​же проблему, или я к глупы, чтобы искать правильные вещи (совершенно возможно).

В любом случае, я создаю случайные числа, чтобы найти номер сводки для общего quickSort, и пару часов назад он работал несколько раз, но теперь я получаю эту ошибку каждый раз.

Пожалуйста, я так расстроен ... Хе-хе! Что я делаю неправильно? Как это может вызвать переполнение?

вот мой код ...

package assignment6quickSort; 

import java.util.ArrayList; 
import java.util.List; 
import java.util.Comparator; 


public class M6 { 

    static M6Comparator<Integer> comp = new M6Comparator<Integer>(); 
    static Integer[] array = new Integer[20]; 
    static ArrayList qsSorted = new ArrayList(); 

    public static void main (String[] args) {  

     for (int i = 0; i < array.length; i++) { 
      array[i] = (int)(50 * Math.random()); 
     } 

     for (int i: array) { 
      System.out.print(i + ", "); 
     } 

     quickSort(array, comp); 
     System.out.println("\n"); 

     for (Object i: qsSorted) { 
      System.out.print(i + ", "); 
     } 

    } 

    static <T> void quickSort(T[] a, Comparator<? super T> comp) { 

     ArrayList<T> temp = new ArrayList<T>(); 
     for (int i = 0; i < a.length; i++) { 
      temp.add(a[i]); 
     } 

     qsSorted = qsAlgorithm(temp, comp); 
    } 

    static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) { 

     ArrayList<T> L = new ArrayList<T>(); 
     ArrayList<T> G = new ArrayList<T>(); 

     if (a.size() <= 1) 
      return a; 
     int pivot = (int)Math.random() * a.size(); 
     T pivotValue = a.get(pivot); 
     for (int i = 0; i < a.size(); i++) { 
      if (comp.compare(a.get(i), pivotValue) == -1 || comp.compare(a.get(i), pivotValue) == 0) { 
       L.add(a.get(i)); 
      } else { 
       G.add(a.get(i)); 
      } 
     } 

     L = qsAlgorithm(L, comp); 
     G = qsAlgorithm(G, comp); 
     L.addAll(G); 

     return L; 

    } 

} 

Кроме того, здесь мой компаратор:

package assignment6quickSort; 

import java.util.Comparator; 

public class M6Comparator<E> implements Comparator<E> { 

    public int compare(E original, E other) { 

     return((Comparable<E>)original).compareTo(other); 
    } 

} 

### РЕШЕНИЕ ###

По-видимому, классическое рекурсивное переполнение ошибка. Спасибо за помощь @pst и @Marcin! Вот пересмотр qsAlgorithm() метод:

static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) { 

     ArrayList<T> L = new ArrayList<T>(); 
     ArrayList<T> P = new ArrayList<T>(); 
     ArrayList<T> G = new ArrayList<T>(); 

     if (a.size() <= 1) 
      return a; 
     int pivot = (int)Math.random() * a.size(); 
     T pivotValue = a.get(pivot); 
     for (int i = 0; i < a.size(); i++) { 
      int v = comp.compare(a.get(i), pivotValue); 
      if (v == -1) { 
       L.add(a.get(i)); 
      } else if (v == 0) { 
       P.add(a.get(i)); 
      } else { 
       G.add(a.get(i)); 
      } 
     } 

     return concatenate(qsAlgorithm(L, comp), P, qsAlgorithm(G, comp)); 

    } 

    static <T> ArrayList<T> concatenate(ArrayList<T> a, ArrayList<T> p, ArrayList<T> b) { 

     a.addAll(p); 
     a.addAll(b); 

     return a; 

    } 

Answer 1

Вы вводите рекурсивный вызов слишком много раз, пока ваш стек не переполнится.Проблема заключается в том, что вы достигнете точки в вашем главном сравнивать цикл, в котором вы всегда добавить все элементы в массив темпа «L», и ни к «G», так что ваш рекурсивный вызов:

L = qsAlgorithm(L, comp); 

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

ArrayList<T> a 

так что вы никогда не выйти из рекурсии в строке 49:

if (a.size() <= 1) 
    return a; 

решения было бы сделать дополнительный выход, когда ваш массив температуры имеет последний 2 EQUA l элементов.

Редактировать: Быстрое и грязное исправление ... это отнюдь не эффективный код. Я использовал еще одну коллекцию «E» для «четных» значений и добавлю их в результирующий список в конце.

static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) { 

    ArrayList<T> L = new ArrayList<T>(); 
    ArrayList<T> E = new ArrayList<T>(); 
    ArrayList<T> G = new ArrayList<T>(); 

    if (a.size() <= 1) 
     return a; 
    int pivot = (int)Math.random() * a.size(); 
    T pivotValue = a.get(pivot); 
    for (int i = 0; i < a.size(); i++) { 
     int v = comp.compare(a.get(i), pivotValue); 
     if (v == -1) { 
      L.add(a.get(i)); 
     } else if (v == 0) { 
      E.add(a.get(i)); 
     } else { 
      G.add(a.get(i)); 
     } 
    } 

    L = qsAlgorithm(L, comp); 
    G = qsAlgorithm(G, comp); 
    L.addAll(E); 
    L.addAll(G); 

    return L; 

} 

Answer 2

Это, вероятно, не nextDouble функция, которая действительно переполняется стек, просто так получилось, что вы вызываете его на каждом шаге рекурсии и поэтому, скорее всего, - функция, достигающая предела. Реальная проблема заключается в том, что вы слишком сильно пересматриваете (ошибочный базовый случай, когда вы, возможно, перестаете рекурсировать).

Похоже, a.size является вашим variant. Убедитесь, что a действительно уменьшается с каждые шаг вашей рекурсии.

Answer 3

Рэнд не вызывает рекурсию, которая вызывает переполнение стека, но являетсяthe straw that broke the camel's back.

В предыдущем 2-тонный сена кипы :

at assignment6quickSort.M6.qsAlgorithm(M6.java:50) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 
at assignment6quickSort.M6.qsAlgorithm(M6.java:60) 
.. 

---

Проблема в заданный код является то, что ось входит в рекурсивном суб-проблемы. Представьте себе случай ввода [x,x], где оба значения рекурсивно выбраны в последовательности L как x <= x. R всегда будет терминальным (0 элементов), но L никогда не будет терминальным (2 элемента).

См. Quicksort on Wikipedia и обратите внимание на псевдокод concatenate(quicksort('less'), 'pivot', quicksort('greater')). То есть, опорный элемент не включен в подзадачи.