Overcoming heap overflow issues

Question

After taking a single Computer Science course last semester, I've been attempting to improve my coding abilities by trying to solve problems from Project Euler. I know my method would work logically(it returns answers to the small scale problem almost instantly). However, it scales horribly. If anyone could help me develop a better approach, or help me fix my memory issue, it'd be greatly appreciated. I already attempted changing the .ini file, but to no avail.

Here's my code:

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

}

Here's the edited code, worked like a gem. Thanks everyone!:

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

As a general piece of Project Euler advice, if your solution doesn't scale, there's almost certainly a better way to solve it. If you've used the same type of solution on an earlier problem you can go through the posts from other users on the earlier question to get ideas for solving the problem in different ways.

Answer 2

Not familiar with the Euler problems, but the horror appears to be your continual allocation and re-allocation of what are basically throwaway intermediate spirals, as you call down recursively to the base case.

Restructure so that you allocate your full spiral up front. Then call your recursive function, passing your full spiral in as a parameter by reference, along with a "level" parameter, which will change with each recursive call. E.g., initial call is with 100x100 spiral and level 100; next (recursive) call is with same spiral, by reference, and level 98. Operations within the function will all be done on the one-and-only-allocated spiral.

In a nutshell: allocate your data structure once, even if you operate on that data structure recursively.

Answer 3

The first problem I saw was a NegativeArraySizeException when running your program with SIZE = 100. I guess this has something to do with how each recursive call is decreasing the size by 2.

I believe that Steven's comment is right on the money. You are allocating the size of the array, them making a recursive call. This causes (SIZE - 1) number of arrays to be allocating, eating up all of your memory. Removing that one line should prevent any memory from being allocated until necessary.