克服堆溢出问题

Question

我试着从Project Euler中解决问题。我知道我的方法在逻辑上是可行的(它几乎可以立即返回小规模问题的答案)。然而，它的伸缩性非常可怕。我已经尝试更改.ini文件，但无济于事。

下面是我的代码：

public class Number28 {

    static int SIZE = 101; //this should be an odd number, i accidentally posted 100
    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        long spiral[][]= new long[size][size];
        if(size == 1){
            spiral[0][0] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= new long[size - 2][size - 2];
            subspiral = spiral(size - 2);
            for(int r = 0; r < size - 2; r++){
                for(int c = 0; c < size - 2; c++){
                    spiral[r + 1][c + 1] = subspiral[r][c];
                }
            }
            long counter = subspiral[0][size - 3];
            for(int r = 1; r < size ; r++){
                counter++;
                spiral[r][size - 1] = counter;
            }
            for(int c = size - 2; c >= 0; c--){
                counter++;
                spiral[size - 1][c] = counter;
            }
            for(int r = size - 2 ; r >= 0 ; r--){
                counter++;
                spiral[r][0] = counter;
            }
            for(int c = 1; c < size ; c++){
                counter++;
                spiral[0][c] = counter;
            }

            return spiral;
        }
    }
}

以下是编辑后的代码，像宝石一样工作：

public class Number28 {
    static int SIZE = 1001;
    static long spiral[][]= new long[SIZE][SIZE];

    /**
     * @param args
     */
    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        long spiral[][]= spiral(SIZE);
        long sum = 0;
        for(int i = 0; i < SIZE; i++)
        {
            sum += spiral[i][i];
            sum += spiral[i][SIZE - 1 - i];
        }
        System.out.println(sum - 1);
        double time = System.currentTimeMillis() - start;
        System.out.println(time);

    }
    public static long[][] spiral(int size){
        if(size == 1){
            spiral[SIZE / 2][SIZE / 2] = 1;
            return spiral;
        }
        else{
            long subspiral[][]= spiral(size - 2);
            int edge = (SIZE - size) / 2;
            long counter = subspiral[edge + 1][edge + size - 2];

              for(int r = 1; r < size ; r++){
                  counter++;
                  spiral[edge + r][edge + size - 1] = counter;
          }
          for(int c = size - 2; c >= 0; c--){
                  counter++;
                  spiral[edge + size - 1][edge + c] = counter;
          }
          for(int r = size - 2 ; r >= 0 ; r--){
                  counter++;
                  spiral[edge + r][edge] = counter;
          }
          for(int c = 1; c < size ; c++){
                  counter++;
                  spiral[edge][edge + c] = counter;
          }
            return spiral;
        }
    }
}

Answer 1

不熟悉Euler问题，但可怕的似乎是您不断地分配和重新分配基本上是一次性中间螺旋的东西，因为您递归地向下调用到基本情况。

重新调整，这样你就可以提前分配你的全部螺旋。然后调用您的递归函数，通过引用传递完整的螺旋作为参数，以及一个"level“参数，该参数将随每次递归调用而变化。例如，初始调用是100x100螺旋和级别100；下一个(递归)调用是参考相同的螺旋和级别98。函数内的所有操作都将在一个且仅分配的螺旋上完成。

简而言之:只分配一次数据结构，即使您递归地操作该数据结构。

Answer 2

作为Project Euler的一般建议，如果您的解决方案没有规模，几乎可以肯定有更好的方法来解决它。如果你在之前的问题上使用了相同类型的解决方案，你可以查看其他用户关于之前问题的帖子，以获得以不同方式解决问题的想法。

Answer 3

我看到的第一个问题是在运行SIZE = 100的程序时出现NegativeArraySizeException。我猜这与每个递归调用如何将大小减少2有关。

我相信史蒂文关于钱的评论是对的。您正在分配数组的大小，它们进行递归调用。这会导致(SIZE - 1)数量的数组被分配，消耗掉所有的内存。删除这一行应该可以防止任何内存在必要时被分配。