Overheading Heap Overflow Probleme

Question

Ich habe versucht, Probleme von Project Euler zu lösen. Ich weiß, dass meine Methode logisch funktionieren würde (sie gibt fast sofort Antworten auf das kleine Problem zurück). Es skaliert jedoch schrecklich. Ich habe bereits versucht, die INI-Datei zu ändern, aber ohne Erfolg.

Hier ist mein 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; 
     } 
    } 
} 

Hier ist der bearbeitete Code, wie ein Edelstein gearbeitet:

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

Nicht vertraut mit den Euler-Problemen, aber der Horror scheint Ihre fortwährende Zuweisung und Neuzuteilung von im Grunde wegwerfbaren Zwischenspiralen zu sein, wie Sie rekursiv zum Basisfall aufrufen.

Umstrukturieren, so dass Sie Ihre volle Spirale nach vorne zuweisen. Rufen Sie dann Ihre rekursive Funktion auf und übergeben Sie Ihre vollständige Spirale als Parameter als Referenz, zusammen mit einem Parameter "level", der sich mit jedem rekursiven Aufruf ändert. Zum Beispiel ist der anfängliche Anruf mit 100 × 100-Spirale und Stufe 100; Der nächste (rekursive) Aufruf erfolgt mit der gleichen Spirale, durch Referenz und mit der Ebene 98. Operationen innerhalb der Funktion werden alle auf der einzig zugewiesenen Spirale ausgeführt.

Kurz gesagt: ordnen Sie Ihre Datenstruktur einmal zu, auch wenn Sie diese Datenstruktur rekursiv bearbeiten.

Answer 2

Als allgemeines Stück Projekt Euler Beratung, wenn Ihre Lösung skaliert nicht, gibt es fast sicher ein besserer Weg, es zu lösen. Wenn Sie dieselbe Art von Lösung für ein früheres Problem verwendet haben, können Sie die Beiträge von anderen Benutzern der vorherigen Frage durchgehen, um Ideen zur Lösung des Problems auf verschiedene Arten zu erhalten.

Answer 3

Das erste Problem, das ich sah, wie ein Negative war, wenn Ihr Programm mit SIZE = 100. läuft Ich denke, das etwas mit, wie jeder rekursiven Aufruf der Größe von 2.

Ich glaube, abnimmt, dass Steven Kommentar zu tun hat, ist direkt auf das Geld. Sie ordnen die Größe des Arrays zu und führen einen rekursiven Aufruf durch. Dies bewirkt, dass (SIZE - 1) die Anzahl der Arrays zugewiesen wird, wodurch Ihr gesamter Speicher verbraucht wird. Das Entfernen dieser einen Zeile sollte verhindern, dass Speicher zugewiesen wird, bis sie benötigt wird. Hier

Answer 4

ist eine vereinfachte Lösung, die nicht eine Matrix speichert:

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

} 

Erläuterung:

von 1 starten Sie 4 Summen sehen:

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

1 4 mal zugegeben wird, deshalb kann der Standardwert für sum ist -3.

Lassen Sie uns diese Beträge sammeln:

• 4 + 24 + 76 + 160 + 276 + ... (aus diesem Grund first4 und r ist 20 = 24 - 4)

Sie können beobachten, dass sich r um 32 pro Schritt erhöht (24 - 4 = 32 + 76 - 24 = 32 + 32 + 160 - 76 = ...) und die tatsächliche Anzahl (first) sich um r erhöht.