1

以下代码模拟查找最近的对，但是当我生成大于 250 的随机对时，它会引发堆栈溢出错误。但是 250 双和任何偶数以下似乎都可以正常工作。有任何想法吗？

该错误发生在 if 语句下的 ComparePoints 的递归调用中。

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);
        }
    }
}
4

2 回答 2

1

听起来您超出了为程序分配的堆栈内存量。您可以使用 -Xss 选项更改堆栈大小。例如java -Xss 8M，将堆栈大小更改为 8MB 并运行您的程序。

于 2016-03-29T03:26:03.087 回答
0

Java 内部有调用堆栈，它将方法调用存储为堆栈帧。它以 LIFO 方式处理这些方法调用（帧）。当创建新线程（在您的情况下为主线程）时，会为该线程分配固定数量的堆栈和堆内存。因此，每当调用堆栈耗尽时，我们都会收到 stackoverflow 错误。在你的情况下，递归调用的数量已经超过了调用堆栈的大小，所以你得到了错误。

于 2016-03-29T03:57:14.057 回答