Unerwarteter OutOfMemoryError

[Avantarius]

Hallo Leute,

Habe ein höchst mysteriöses Problem. Habe eine Klasse in der ein Algorithmus implementiert wird. Darin unter Anderem:

int Vertices;
int[][] Matrix;
int[] VertGrd;
...
Matrix = new int[Vertices][Vertices];		
VertGrd = new int[Vertices];
ArrayList<Integer> Solution = new ArrayList<Integer>();
int best = 0;
...

Vertices, Matrix und VertGrd wurden nur einmal mit Werten initialisiert, dann nicht mehr geändert; solang hats noch funktioniert. Nach dem Einfügen von

...
for (int i = 0; i < Vertices; i++)
if (Matrix[i][curidx] != 0) VertGrd[i]--;
...

hab ich dann einen "Exception in thread "main" java.lang.OutOfMemoryError: Java heap space" bekommen. Offenbar steigt durch den hinzugefügten Code der Speicherbedarf konstant an bis es zum Fehler kommt. Laut Fehlermeldung passiert der Fehler jedoch hier:

Solution.add(best);

Bin echt ratlos und wäre für jede Hilfe dankbar!

 

[musiKk]

Klassen groß, Variablen hingegen klein schreiben. Das sind weit verbreitete Konventionen und wenn man sich nicht daran hält, dann kann das ziemlich Verwirrung stiften.

Davon abgesehen: Mit diesen Code-Bruchstücken wird es schwierig, Dir zu helfen. Wo wird das add() ausgeführt; wie oft passiert das; mit welchen Größenordnungen haben wir zu tun (z. B. die Variable Vertices). Ohne Kontext kann man da nichts beurteilen.
Bis jetzt lautet meine wahrscheinlich wenig hilfreiche Diagnose einfach nur: Die Liste Solution wird zu groß.

 

[Avantarius]

Hab mal den Code etwas entrümpelt, ganzer Code wie folgt:

package ads1ss09.pa2;

import java.util.Set;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.LinkedList;

public class GroupFinder {
	
	int vertices;
	int edges;
	int[][] matrix;
	int[] vertGrd;
	
	public GroupFinder(int numNodes, Set<Edge> edges) {
		vertices = numNodes;
		matrix = new int[vertices][vertices];		
		vertGrd = new int[vertices];
		Iterator<Edge> it = edges.iterator();
		Edge tmp;
		while (it.hasNext()) {
			this.edges++;
			tmp = it.next();
			matrix[tmp.node1][tmp.node2] = tmp.weight;
			matrix[tmp.node2][tmp.node1] = tmp.weight;
			vertGrd[tmp.node1]++;
			vertGrd[tmp.node2]++;
		}
	}
	
	public ArrayList<Integer> findGroup1() {
		ArrayList<Integer> solution = new ArrayList<Integer>();
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		int i = 0;
		int c;
		int best = 0;
		int bestgrd = 0;
		Iterator<Integer> it;
		
		for (i = 0; i < vertices; i++)
			list.add(i);
		
		while (!list.isEmpty()) {
			bestgrd = 0;
			it = list.iterator();
			while (it.hasNext()) {
				c = it.next();
				if (bestgrd < vertGrd[c]) {
					bestgrd = vertGrd[c];
					best = c;
				}
			}
			solution.add(best);
			it = list.iterator();
			while (it.hasNext()) {
				c = it.next();
				if (matrix[best][c] == 0) { 
					it.remove();
					for (i = 0; i < vertices; i++)
						if (matrix[i][c] != 0) vertGrd[i]--;
				}
			}
		}
		return solution;
	}
}

Laut Fehlermeldung liegt es an Zeile 54, was meiner Meinung nach überhaupt keinen Sinn macht, da alles perfekt funtioniert wenn ich die Zeilen 60 und 61 weglasse (welche ja mit solution nichts zu tun haben).

Zu den Größenordnungen: vertices kann von 100 bis maximal circa 5000 sein.

Am Speicher mangelt es auf jeden Fall nicht da Java, bevor die Fehlermeldung kommt, über 700 MB RAM belegt, soviel können die Datenstrukturen in diesem Programm gar nicht brauchen.

 

[musiKk]

Hm, ich kann das leider nicht nachstellen. Ich habe mal numNodes mit 5.000 angegeben, dann fliege ich aber in Zeile 17 raus. Auch wenn ich die numNodes mal auf 2.500 runtersetze und 100.000 Edges in dem Set übergebe (wobei das bei mir einfach nur eine Klasse mit drei int-Variablen ist), scheitert es an Zeile 17.
In solchen Fällen bleibt Dir - sofern eine speicherschonendere Umstrukturierung nicht möglich ist - nichts übrig, als den Speicher der JVM zu erhöhen.

Vom bloßen Draufschauen kann ich aber auch nicht sehen, warum die Zeilen 60, 61 einen Einfluss haben. Ich vermute aber, dass sich dadurch semantisch derart etwas ändert, dass die Zeile 59 seltener aufgerufen wird, die gibt ja wieder Ressourcen frei. Aber das sind genau die richtigen Aufgaben für Profiler (wozu ich Dir jedoch keinen Support geben kann, da ich damit zu wenig Erfahrung habe).

 

[Avantarius]

Offenbar bin ich in eine Endlosschleife geraten (Zeile 43). Wenn ich jetzt nach Zeile 57

if (c == best) it.remove(); else

einfüge, funktionierts.

Warum es zu der Enlosschleife kommt weiß ich nicht da eigentlich in jedem Durchlauf mindestens einmal die Zeile 59 aufgerufen werden sollte (matrix ist ja die Adjazenzmatrix eines schlichten Graphen und da gilt auf jeden Fall matrix[best][best] == 0).

Was das überhaupt mit den Zeilen 60+61 zu tun hat weiß ich auch nicht, da matrix außer im Konstruktor ja nie geändert wird.

Auf jeden Fall funkts jetzt wieder. Ich danke dir auf jeden Fall für deine Hilfe und hoffe ich hab dich nicht zu sehr ins Grübeln gebracht!