Warum erhalte ich einen Stapelüberlauffehler?

Question

Der folgende Code simuliert das Finden des nächsten Paares, aber wenn ich eine zufällige Anzahl von Paaren größer als 250 erzeuge, wird ein Stapelüberlauffehler ausgelöst. Aber 250 Paare und jede Menge darunter scheint gut zu funktionieren. Irgendwelche Ideen?

Der Fehler tritt bei dem rekursiven Aufruf von ComparePoints unter der if-Anweisung auf.

public class Divide { 

    Point2D closest1; 
    Point2D closest2; 
    double Distance = Double.MAX_VALUE; 

    public Divide(Point2D[] RandArray){ 
     SortArray s = new SortArray(); 
     RandArray = s.SortPointsX(RandArray); 
     SplitAndConquer(RandArray); 
    } 

    private double ComparePoints(Point2D a, Point2D b, Point2D[] s, 
       int CurrentPoint, int NextPoint){ 
      if(s[CurrentPoint] != null && s[NextPoint] != null){ 
       if (Distance > a.distance(b) && 
         (a.getX() != b.getX() || a.getY() != b.getY())){ 
        Distance = a.distance(b); 
        closest1 = new Point2D.Double(a.getX(), a.getY()); 
        closest2 = new Point2D.Double(b.getX(), b.getY()); 
       } 
       if (NextPoint == (s.length - 1)){ 
        NextPoint = s.length - ((s.length - 1) - CurrentPoint); 
        CurrentPoint++; 
       } 
       if (CurrentPoint != (s.length - 1)){ 
        if (NextPoint != (s.length - 1)){ 
        NextPoint++; 
        ComparePoints(s[CurrentPoint], s[NextPoint], 
          s, CurrentPoint, NextPoint); 
        } 
       } 
       if (CurrentPoint == (s.length - 1)){ 
        CurrentPoint = 0; 
        NextPoint = 0; 
       } 
      } 
     return Distance; 
    } 

    private void SplitAndConquer(Point2D[] RandArray){ 
     double median = RandArray[RandArray.length/2].getX(); 
     int countS1 = 0; 
     int countS2 = 0; 
     boolean exact = false; 
     int CurrentPoint = 0; 
     int NextPoint = 0; 
     Point2D[] s1 = new Point2D[RandArray.length/2]; 
     Point2D[] s2 = new Point2D[RandArray.length/2]; 

     for (int i = 0; i < RandArray.length; i++){ 

      if (RandArray[i].getX() < median){ 
       s1[countS1] = RandArray[i]; 
       countS1++; 
      } 
      else if (RandArray[i].getX() > median){ 
       s2[countS2] = RandArray[i]; 
       countS2++; 
      } 
      else if (RandArray[i].getX() == median && exact == false){ 
       s2[countS2] = RandArray[i]; 
       exact = true; 
       countS2++; 
      } 
      else if (RandArray[i].getX() == median && exact == true) { 
       s1[countS1] = RandArray[i]; 
       exact = false; 
       countS2++; 
      } 
     } 

     if (s1[0] != null && s1[1] != null){ 
      Distance = ComparePoints(s1[0], s1[1], s1, 
        CurrentPoint, NextPoint); 
      Distance = ComparePoints(s2[0], s2[0], s2, 
        CurrentPoint, NextPoint); 
      }else{ 
       System.out.println 
       ("One of the subsets does not contain enough points!"); 
      } 
     CheckMid(RandArray, Distance, median, CurrentPoint, NextPoint); 
     PrintClosest(); 
     } 

    private void PrintClosest() { 
     System.out.println("The closest pair found using Divide " 
       + "And Conquer is at (" 
       + closest1.getX() + " " + closest1.getY() + "), and (" 
       + closest2.getX() + " " + closest2.getY() + ")"); 
     System.out.println("The distance between the pairs is: " + Distance); 

    } 

    private void CheckMid(Point2D[] randArray, double d, double m, 
      int current, int next) { 
     int MidCount = 0; 
     Point2D[] MidArray = new Point2D[randArray.length]; 
     for(int i = 0; i < randArray.length; i++){ 
      if(randArray[i].getX() > (m - d) && 
        randArray[i].getX() < (m + d)){ 
       MidArray[MidCount] = randArray[i]; 
       MidCount++; 
      } 
     } 
     if (MidArray[0] != null && MidArray[1] != null){ 
     ComparePoints(MidArray[0], MidArray[1], MidArray, 
       current, next); 
     } 
    } 
} 

Answer 1

Klingt, als würden Sie die Menge an Stapelspeicher überschreiten, die Ihrem Programm zugewiesen ist. Sie können die Stapelgröße mit der Option -Xss ändern. ZB java -Xss 8M, um die Stapelgröße auf 8 MB zu ändern und das Programm auszuführen.

Answer 2

Intern verfügt Java über einen Aufruf-Stack, der die Methodenaufrufe als Stack-Frames speichert. Und es verarbeitet diese Methodenaufrufe (Frames) auf LIFO-Weise. Wenn ein neuer Thread erstellt wird (in Ihrem Fall ein Hauptthread), wird diesem Thread eine feste Menge an Stack- und Heap-Speicher zugewiesen. Also immer wenn der Call-Stack erschöpft ist, erhalten wir einen Stackoverflow-Fehler. In Ihrem Fall hat die Anzahl der rekursiven Aufrufe die Größe des Aufruf-Stacks überschritten und Sie erhalten den Fehler.