Résolution des problèmes de débordement de tas

Question

J'ai tenté de résoudre des problèmes avec Project Euler. Je sais que ma méthode fonctionnerait logiquement (elle renvoie presque instantanément les réponses au problème à petite échelle). Cependant, il évolue horriblement. J'ai déjà essayé de changer le fichier .ini, mais en vain.

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

Voici le code modifié, a fonctionné comme un bijou:

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

Vous n'êtes pas familier avec les problèmes d'Euler, mais l'horreur semble être votre allocation continuelle et ré-allocation de ce qui sont essentiellement des spirales intermédiaires jetables, comme vous appelez récursivement au cas de base.

Restructurez-vous de façon à ce que votre spirale soit entièrement à l'avant. Appelez ensuite votre fonction récursive, en passant votre spirale complète en paramètre par référence, avec un paramètre "level", qui changera avec chaque appel récursif. Par exemple, l'appel initial est avec la spirale 100x100 et le niveau 100; l'appel suivant (récursif) est avec la même spirale, par référence, et le niveau 98. Les opérations à l'intérieur de la fonction seront toutes effectuées sur la spirale à un et à seulement.

En résumé: allouez une fois votre structure de données, même si vous opérez récursivement dans cette structure de données.

Answer 2

En tant que pièce générale du conseil du projet Euler, si votre solution n'échelle pas, il y a presque certainement une meilleure façon de le résoudre. Si vous avez déjà utilisé le même type de solution sur un problème antérieur, vous pouvez parcourir les messages d'autres utilisateurs sur la question précédente pour trouver des idées permettant de résoudre le problème de différentes manières.

Answer 3

Le premier problème que j'ai vu était un NegativeArraySizeException lors de l'exécution de votre programme avec la taille = 100. Je suppose que cela a quelque chose à voir avec la façon dont chaque appel récursif diminue la taille par 2.

Je crois que le commentaire de Steven est juste sur l'argent. Vous allouez la taille du tableau, en faisant un appel récursif. Cela provoque (SIZE - 1) nombre de tableaux à allouer, manger toute votre mémoire. Suppression de cette ligne devrait empêcher toute mémoire d'être allouée jusqu'à ce que nécessaire.

Answer 4

est ici une solution simplifiée qui ne stocke pas une matrice:

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

} 

Explication:

A partir de 1 vous pouvez voir 4 sommes:

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

1 on ajoute 4 fois, ceci est la raison pour laquelle la valeur par défaut de sum est -3.

Rassemblons ces sommes:

• 4 + 24 + 76 + 160 + 276 + ... (ce qui est la raison pour laquelle first est 4 et r est 20 = 24 - 4)

Vous pouvez observer que r augmente de 32 par pas (24 - 4 = 32 + 76 - 24 = 32 + 32 + 160 - 76 = ...) et le nombre réel (first) augmente de r.