StackOverflowError

M

Moinsn

Mitglied
Ich hab da ein kleinen Problem in einen Rekursiven Backtracking Algorithmus.
In der Methode getCord(Klasse opportunities) wird eine ArrayList an die Methode SetStone(Klasse Main) zurückgegeben in der der Fehler zu stecken scheint. Da die ArrayList wiederum eine ArrayList beinhaltet die wiederum n intArray beinhaltet blick ich langsam nicht mehr durch. SetStone läuft Rekursiv und gibt nach ca 2500 Durchläufen einen StackOverflowError.

Methode SetStone ais der Klasse main:
Java: 
public void setStone() {
	

		tempOpp = List.get(count);

		ArrayList<int[]> opps;
		
		
		for(int i=0; i<9; i++)
			for(int j=0; j<9; j++)
				playingField[i][j] = tempOpp.playingField[i][j];
				
		System.out.println("Anz. Moeglichkeiten = "+tempOpp.allOpps.size());
		
		
		
		if(tempOpp.getAnz() == 1){ 
			System.out.println("\nENDE... mit " +count +" Zügen!");
			return;
		}
		
		
		opps = tempOpp.getCord();
		
		if(opps == null){
			System.out.println("\n\n\nback_________________________");
			goBack();
			mainCount++;
		}
		else{
			mainCount++;
			System.out.println("Anz. Durchläufe: "+mainCount);
			System.out.println("Anz. Sprünge: "+List.size());
			
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(0))[0] +" ; " +((int[])opps.get(0))[1]);
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(1))[0] +" ; " +((int[])opps.get(1))[1]);
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(2))[0] +" ; " +((int[])opps.get(2))[1]+"\n");
			
			playingField[((int[])opps.get(0))[0]][((int[])opps.get(0))[1]] = '#';
			playingField[((int[])opps.get(1))[0]][((int[])opps.get(1))[1]] = '#';
			playingField[((int[])opps.get(2))[0]][((int[])opps.get(2))[1]] = 'O';
			

			newLevel();			
		}

Methode getCord in der Klasse opportunities
Java: 
public ArrayList getCord() {
		printField();
		
		ArrayList<ArrayList> tempallOpps = null;
		if(allOpps.isEmpty() || allOpps.size()<= 0) {
			System.out.print("getCord() says-> allOpps are Empty, i call goBack()");
			return null;
		}
		else {
			tempallOpps = new ArrayList<ArrayList>(allOpps.get(allOpps.size()-1)); 

			System.out.println("getCord sys -> return ok");
			allOpps.remove(allOpps.size()-1);
		}
		
		return tempallOpps;
	}

Methode oppAnalyse in der Klasse opportunities (Belegung der Werte die an die main zurückgegeben werden sollen)
Java: 
public void oppAnalyse() {
		for(int i=0; i<9;i++) {
			for(int j=0; j<9;j++) {
				
				
				
				if(i>2 && playingField[i][j] == 'O') {
					if(playingField[i-2][j] == '#' && playingField[i-1][j] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i-1,j});
						opps.add(new int[]{i-2,j});
						allOpps.add(opps);
						System.out.println("opp add1 "+i+j +";"+(i-1)+j+";"+(i-2)+j);
					}
				}
				
				if(j>2 && playingField[i][j] == 'O')
					if(playingField[i][j-2] == '#' && playingField[i][j-1] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i,j-1});
						opps.add(new int[]{i,j-2});
						allOpps.add(opps);
						System.out.println("opp add2 "+i+j +";"+i+(j-1)+";"+i+(j-2));
				}
				
				if(i<7 && playingField[i][j] == 'O')
					if(playingField[i+2][j] == '#' && playingField[i+1][j] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i+1,j});
						opps.add(new int[]{i+2,j});		
						allOpps.add(opps);
						System.out.println("opp add3 "+i+j +";"+(i+1)+j+";"+(i+2)+j);
				}
				
				if(j<7 && playingField[i][j] == 'O')
					if(playingField[i][j+2] == '#' && playingField[i][j+1] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i,j+1});
						opps.add(new int[]{i,j+2});				
						allOpps.add(opps);
						System.out.println("opp add4 "+i+j +";"+i+(j+1)+";"+i+(j+2));
				}

			}
		}
	}

DANKE

EDIT - exception vergessen:

Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io_OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at opportunities.printField(opportunities.java:31)
at opportunities.getCord(opportunities.java:70)
at main.setStone(main.java:88)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.newLevel(main.java:62)
at main.setStone(main.java:109)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.newLevel(main.java:62)
at main.setStone(main.java:109)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.newLevel(main.java:62)
at main.setStone(main.java:109)
at main.newLevel(main.java:62)
at main.setStone(main.java:109)
at main.newLevel(main.java:62)
at main.setStone(main.java:109)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.newLevel(main.java:62)
.
. -viele viele weitere-
.
at main.goBack(main.java:52)
at main.setStone(main.java:92)
at main.goBack(main.java:52)
 
V

Volvagia

Top Contributor
Beim Betreten einer Methode wird die letzte Methode und Zeilennummer auf einem Stack abgelegt. Jeder Thread enthält so einen. Wird die Methode verlassen, nimmt er das Letzte Element vom Stack und fährt dort fort.
Entweder die Methode muss so lange laufen, das die max. Größe des Stacks überschritten wird, in dem Fall könntest du mit einen Parameter mit mehr Speicher starten. Vielleicht ist ein umdesignen dann aber doch besser.
...oder der Methode fehlt oder sie enthält eine fehlerhafte Abbruchbedingung, wodurch du quasi eine Endlosschleife gebaut hast, und einfach der Stack überläuft.
 
M

Moinsn

Mitglied
Die Abbruchbedingung haut schon hin.
Es sind halt nur ein paar Millionen Rekursive Aufrufe.
Wie genau kann ich denn mit mehr Speicher starten???
Der kann mir gern meine 8GB füllen.
Mfg
 
A

anonym

Gast
Hast du mal per Hand ausgerechnet, wieviele ineinandergeschachtelte Aufrufe es sind? Zuviele sollten das nicht werden. Probier es mal mit einem Testcase, in dem es maximal x Aufrufe mit kleinem x werden. Divergiert das auch, passt die Abbruchbedingen vermutlich doch nicht. Im Stacktrace der Fehlermeldung siehst du, wieviele rekursive Aufrufe es waren.

Dein Fehler sagt: in goBack() wird setStone() aufgerufen. goBack() sehen ich im Listing garnicht, deshalb kann ich es hier gerade nicht sagen, aber viele rekursive Dinge gehen auch als Schleife. Hier mal ein Beispiel:

Berechnen der Fakultät n!

rekursiv:
[Java]
public int fac(int n){
if(n==0){
return 1;
}
return n*fac(n-1);
}
[/Java]

Nun, wo liegt iterativ das Problem? Naja, wir müssen lösen, dass zur Berechnung dess aktuellen Werts der Vorherige verwendet wird. Zum Beispiel so:

[Java]
public int fac(int n){
int z =1;

for(;n>0;n--){
z=z*n;
}

return z;
}
[/Java]

Und wie kommst du dahin? Naja, zuerst baust du deine Methode so um, dass die letzte Anweisung, die vor dem return berechnet wird, der rekursive Aufruf ist. Für die Fakultät zum Beispiel:

[Java]
public int fac(int n){
return helper(n, 1);
}

public int helper(int n, int z){
if(n==0){
return z;
}
return helper(n-1, n*z);
}
[/Java]

Der Trick ist, das Zwischenergebnis in der Variable z mitzunehmen. Und jetzt musst du nurnoch den helper eleminieren und stattdessen eine Schleife benutzen.

Einige funktionale Sprachen haben Compiler bzw. VMs, die die Struktur mit fac und helper automatisch so umsetzen würden, dass kein Stack Overflow auftritt. Sie entfernen den Aufrufrahmen der äußeren Methode vom Stack und ersetzen ihn durch den der Inneren, wenn der letzte Befehl vor dem return ein Methodenaufruf ist (der neue Aufrufrahmen für die neue Methode bekommt dabei den Rücksprungpointer aus dem alten Rahmen).

Java macht das allerdings soweit ich weiß nicht.
 
M

Moinsn

Mitglied
Es ist im eigentlichen Sinne keine Rekursion sollte aber trotzdem funktionieren. Der Algorithmus soll alle Möglichkeiten in Peg Solitär einen Stein zu setzen durchlaufen und den weg mit den wenigsten Sprüngen finden. Hier von mir beschrieben.
Peg Solitär
Ich häng da seit Tagen dran, und so langsam übersteigt das meine Fähigkeiten. Wäre Cool wenn ihr mein Unfall noch funktionstüchtig bekommt.
DANKESCHÖN

Hier nun das gesamte Programm .... (2 Klassen)
Java: 
import java.util.ArrayList;

	

public class main extends StackOverflowError{
	
	int mainCount;
	opportunities tempOpp; 
	 
	opportunities tempCountOpp;
	ArrayList<opportunities> List = new ArrayList<opportunities>();
	char[][] playingField = new char[9][9];
	int count=0;
	
	public static void main(String[] args) {
		
		main myMain = new main();
		
		myMain.createField();
		
		myMain.newLevel();
	}
	
	
	public void createField() { 		
			
		for(int v=0; v<playingField.length; v++)
			for(int h=0; h<playingField.length; h++)
				playingField[v][h] = 'O';
			
		for(int v=0; v<playingField.length; v++) {
			for(int h=0; h<playingField.length; h++) {
				if(v<playingField.length/3 && ( h<playingField.length/3 || h>=6) || v>=6 && ( h<playingField.length/3 || h>=6 ) || v==0 || v==playingField.length-1 || h==0)
					playingField[v][h] = 'x';
			}
		}
		playingField[3][8] = 'x';
		playingField[5][8] = 'x';
		playingField[4][8] = 'x';
		
		playingField[4][4]= '#';
	}
	
	
	public void goBack() {
		count = List.size()-2;
		int temp = List.size()-1;
		try{
		List.remove(temp);

		
		setStone();
		}catch(StackOverflowError t)
		{
			 System.out.println("StackOverflowError bei goBack");
			 goBack();
		}
	}
	
	
	public void newLevel() {
		System.out.println("\n\n\nnew__________________________");
		
		List.add(new opportunities(playingField));
		count = List.size()-1;
	
		
			setStone();	
	}
	
	
	public void setStone() {
	

		tempOpp = List.get(count);

		ArrayList<int[]> opps;
		
		
		for(int i=0; i<9; i++)
			for(int j=0; j<9; j++)
				playingField[i][j] = tempOpp.playingField[i][j];
				
		System.out.println("Anz. Moeglichkeiten = "+tempOpp.allOpps.size());
		
		
		
		if(tempOpp.getAnz() == 1){ 
			System.out.println("\nENDE... mit " +count +" Zügen!");
			return;
		}
		
		
		
		opps = null;
		try{
		opps = tempOpp.getCord();
		}catch(StackOverflowError t) {
			System.out.println("StackOverflowError bei ifElse Steinsetzen");
			setStone();
		}
		
		
		if(opps == null){
			System.out.println("\n\n\nback_________________________");
			goBack();
			mainCount++;
		}
		else{
			mainCount++;
			System.out.println("Anz. Durchläufe: "+mainCount);
			System.out.println("Anz. Sprünge: "+List.size());
			
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(0))[0] +" ; " +((int[])opps.get(0))[1]);
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(1))[0] +" ; " +((int[])opps.get(1))[1]);
			System.out.println("setStone say-> I get cords: "+((int[])opps.get(2))[0] +" ; " +((int[])opps.get(2))[1]+"\n");
			
			playingField[((int[])opps.get(0))[0]][((int[])opps.get(0))[1]] = '#';
			playingField[((int[])opps.get(1))[0]][((int[])opps.get(1))[1]] = '#';
			playingField[((int[])opps.get(2))[0]][((int[])opps.get(2))[1]] = 'O';
			

			newLevel();			
		}
		
		
		
	}
}

Java: 
import java.util.ArrayList;



public class opportunities {

	
	public char[][] playingField = new char[9][9];
	public ArrayList<ArrayList<int[]>> allOpps = new ArrayList<ArrayList<int[]>>();
	
	
	
	
	public opportunities(char[][] playingField) {
		
		for(int i=0; i<9; i++)
			for(int j=0; j<9; j++)
				this.playingField[i][j] = playingField[i][j];
		try{
			oppAnalyse();
		}catch(StackOverflowError t) {
			System.out.println("StackOverflowError bei oppAnalyse");
			oppAnalyse();
		}
	}
	
	
	public void printField(){
		int i=0;
		int j=0;
		
		System.out.print(" ");
		
		for(int z=0; z<9; z++)
			System.out.print(z);
	
		System.out.println("");	
		
		for(i=0; i<playingField.length; i++){			
			System.out.print(i);
			for(j=0; j<playingField.length; j++){	
				System.out.print(playingField[i][j]);
			}
			System.out.println("");			
		}
		
		
	}
	

	
	

	public char[][] getPlayingField() {
		return this.playingField;
	}
	
	
	public int getAnz() {
		int anz = 0;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				if(playingField[i][j] == 'O')
					anz++;
			}
		}
		return anz;
	}
	
	
	public ArrayList<int[]> getCord() {
		printField();
		
		ArrayList<int[]> tempOpp = null;
		
		if(allOpps.isEmpty() || allOpps.size()<= 0) {
			System.out.print("getCord() says-> allOpps are Empty, i call goBack()");
			return null;
		}
		else {
			tempOpp = new ArrayList<int[]>(allOpps.get(allOpps.size()-1)); 

			System.out.println("getCord sys -> return ok");
			allOpps.remove(allOpps.size()-1);
		}
		
		return tempOpp;
	}
	
	

	public void oppAnalyse() {
		for(int i=0; i<9;i++) {
			for(int j=0; j<9;j++) {
				
				ArrayList<int[]> opps;
				
				if(i>2 && playingField[i][j] == 'O') {
					if(playingField[i-2][j] == '#' && playingField[i-1][j] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i-1,j});
						opps.add(new int[]{i-2,j});
						allOpps.add(opps);
						System.out.println("opp add1 "+i+j +";"+(i-1)+j+";"+(i-2)+j);
					}
				}
				
				if(j>2 && playingField[i][j] == 'O')
					if(playingField[i][j-2] == '#' && playingField[i][j-1] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i,j-1});
						opps.add(new int[]{i,j-2});
						allOpps.add(opps);
						System.out.println("opp add2 "+i+j +";"+i+(j-1)+";"+i+(j-2));
				}
				
				if(i<7 && playingField[i][j] == 'O')
					if(playingField[i+2][j] == '#' && playingField[i+1][j] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i+1,j});
						opps.add(new int[]{i+2,j});		
						allOpps.add(opps);
						System.out.println("opp add3 "+i+j +";"+(i+1)+j+";"+(i+2)+j);
				}
				
				if(j<7 && playingField[i][j] == 'O')
					if(playingField[i][j+2] == '#' && playingField[i][j+1] == 'O') {
						opps = new ArrayList<int[]>();
						opps.add(new int[]{i,j});
						opps.add(new int[]{i,j+1});
						opps.add(new int[]{i,j+2});				
						allOpps.add(opps);
						System.out.println("opp add4 "+i+j +";"+i+(j+1)+";"+i+(j+2));
				}

			}
		}
	}
}
 
Zuletzt bearbeitet:
M

maki

Gast
Den Stack kann man mit Xss erhöhen, aber Achtung, unter Windows gibt es einen bug, der Xss Parameter wird nur für einen neu gestarteten Thread gesetzt.
 
M

Moinsn

Mitglied
Das einstellen des XSS Parameter auf -Xss1024m scheint es gebracht zu haben.
Er kommt nun mit 31 Zügen zum Ziel.
 
Zuletzt bearbeitet:
M

Moinsn

Mitglied
Ich hab jetzt dass den Minimum xss wert ausgelotet. Wenn ich es auf 9m Stelle läufts noch.
Nun müsste ich noch alle nicht durch Backtracing rückgängig gemachten Schritte notieren und könnte somit überprüfen ob es wenigstens richtig funktioniert.
Leider hab ich noch keine Idee wo und wie ich das am schlausten bewerkstellige. Hat vllt. jmd. einen Vorschlag?

Evtl. hat ja auch noch jmd. ne Idee wie ich die xss Größe auf 2m runter bekomme.

Vielen Dank
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Zeppi Rekursion StackOverflowError Allgemeine Java-Themen 4
S Stackoverflowerror Allgemeine Java-Themen 2
javaerd Binomialkoeffizient ausrechnen, Exception in thread "main" java.lang.StackOverflowError Allgemeine Java-Themen 6
Androbin Interpreter-Fehler Probleme mit Rekursion - StackOverflowError Allgemeine Java-Themen 8
G StackoverflowError beim laden einer FXMML Datei Allgemeine Java-Themen 1
G maven 3.1.1 StackOverflowError Allgemeine Java-Themen 3
A Binäre Suche im Array mit StackOverflowError Allgemeine Java-Themen 3
H StackOverflowError erst ab 87 Array Elementen Allgemeine Java-Themen 4
E Interpreter-Fehler StackOverflowError Allgemeine Java-Themen 3
E StackOverflowError Allgemeine Java-Themen 8
F Stackoverflowerror beheben Allgemeine Java-Themen 5
Schandro StackOverflowError bei Rekursion verhindern Allgemeine Java-Themen 14
U Kompilieren einer großen Datei if-else = StackOverflowError Allgemeine Java-Themen 4
J java.lang.StackOverflowError Debugging? Allgemeine Java-Themen 51
S StackOverflowError - Brett vor'm Kopf Allgemeine Java-Themen 6
T Profifrage: java.lang.StackOverflowError bei BigInteger Allgemeine Java-Themen 27
G StackOverflowError Allgemeine Java-Themen 6
F Warum StackOverFlowError? Allgemeine Java-Themen 6

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben