Преодоление проблем переполнения кучи

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

Как общий совет Project Euler, если ваше решение не масштабируется, почти наверняка есть лучший способ его решить. Если вы использовали такой же тип решения для более ранней проблемы, вы можете просмотреть сообщения других пользователей по предыдущему вопросу, чтобы получить идеи для решения проблемы различными способами.

Answer 2

Не знаком с проблемами Эйлера, но ужас, кажется, заключается в том, что вы постоянно распределяете и перераспределяете то, что по сути являются одноразовыми промежуточными спиралями, когда вы рекурсивно вызываете базовый случай.

Перестройтесь так, чтобы вы распределили всю свою спираль впереди. Затем вызовите рекурсивную функцию, передав полную спираль в качестве параметра по ссылке вместе с параметром «level», который будет меняться при каждом рекурсивном вызове. Например, начальный звонок со спиралью 100x100 и уровнем 100; следующий (рекурсивный) вызов с той же спиралью, по ссылке и на уровне 98. Все операции внутри функции будут выполняться по единственной, выделенной спирали.

В двух словах: выделите структуру данных один раз, даже если вы рекурсивно оперируете этой структурой данных.

Answer 3

Вот упрощенное решение, которое не хранит матрицу:

public class P28 {

    private final static int N = 1001;

    public static void main(String[] args) {

        int limit = (N + 1) / 2;
        int sum = -3;
        int first = 4;
        int r = 20;
        for (int i = 1; i <= limit; i++) {
            sum += first;
            first += r;
            r += 32;
        }
        System.out.println(sum);
    }

}

Пояснение:

Начиная с 1 вы можете увидеть 4 суммы:

• 1 + 3 + 13 + 31 + 57 + ...
• 1 + 5 + 17 + 37 + 65 + ...
• 1 + 7 + 21 + 43 + 73 + ...
• 1 + 9 + 25 + 49 + 81 + ...

1 добавляется 4 раза, поэтому значение по умолчанию для sum равно -3.

Давайте соберем эти суммы:

• 4 + 24 + 76 + 160 + 276 + ... (вот почему first равно 4, а r равно 20 = 24 - 4)

Вы можете заметить, что r увеличивается на 32 за шаг (24 - 4 = 32 + 76 - 24 = 32 + 32 + 160 - 76 = ...), и фактическое число (first) увеличивается r.

Answer 4

Первой проблемой, с которой я столкнулся, была NegativeArraySizeException при запуске вашей программы с SIZE = 100. Я думаю, это как-то связано с тем, как каждый рекурсивный вызов уменьшает размер на 2.

Я считаю, что комментарий Стивена прав на деньги. Вы выделяете размер массива, а вы делаете рекурсивный вызов. Это приводит к (SIZE - 1) количеству массивов, которые будут выделяться, пожирая всю вашу память. Удаление этой строки должно предотвратить выделение памяти до тех пор, пока она не понадобится.