ArrayList kopieren

[Aerics]

Abend zusammen.

Und zwar möchte ich gerne innerhalb einer Schleife meine ArrayList kopieren.
Leider bekomme ich recht schnell ein Speicherüberlauf. Aus diesem Grund denke ich, dass
ich etwas falsch mache.

Deklaration auserhalb der Schleife:

ArrayList<Integer> tmpNodes = new ArrayList<Integer>();
ArrayList<Integer> Nodes = new ArrayList<Integer>();

Kopieren/Clonen der ArrayList innerhalb der Schleife:

tmpNodes = (ArrayList<Integer>) Nodes.clone();            
Nodes.clear();

 

[maki]

Vairablen schreibt man klein.

Ansonsten ist der Fehler nicht in dem von dir gezeigten Code, da fehlt was.

 

[SlaterB]

innerhalb welcher Schleife/ wieso in einer Schleife?

 

[Aerics]

Habe leider den Code mit der Schleife nicht hier zu Hause.
Ich ging mal davon aus, dass es an dem Clone liegt.
Eben ein Versuch mit einer millionen Einträge gestartet und lief problemlos.

Dann muss ich Morgen nochmal Debuggen und melde mich dann noch einmal.

 

[MFM]

Was spricht denn gegen die in java.lang.System hinterlegte Methode static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) ?

in Deinem Fall also

System.arraycopy(nodes,0,tmpNodes,0,nodes.length);

Musst Du das wirklich in einer Schleife machen?

 

[Aerics]

So in etwas müsste es gewesen sein:

GetCount int(int startid) {
	ArrayList<Integer> tmpnodes = new ArrayList<Integer>();
	ArrayList<Integer> nodes = new ArrayList<Integer>();
	int iCount = 0;	
	
	while(startid not in node) {
		iCount++;
		tmpnodes = (ArrayList<Integer>) nodes.clone();           
		nodes.clear();
	
		for(tmpnode.size) {
			nodes.add(HolNeVerbindung(tmpnode.get(i)));
		}
	}	

	return iCount;
}

Ich hole mir immer für x Nodes dessen Verbindung und speicher diese. Nun hole ich für die neuen Nodes wiederum dessen Verbindungen bis eben die ID mit der startid übereinstimmt.
Würde ich nich über eine tmpvariable gehen hätte ich nicht imemr die letzten Verbindungen drin wo ich die neuen suche, sondern eben immer alle. Dementsprechend würde ich immer wieder für eine unwichtige Menge erneut suchen.

 

[SlaterB]

das clone() ist unnötig, baue daraus

GetCount int(int startid) {
	
	ArrayList<Integer> nodes = new ArrayList<Integer>();
	int iCount = 0;	
	
	while(startid not in node) {
		iCount++;
		ArrayList<Integer> tmpnodes = nodes;
		nodes = new ArrayList<Integer>();
	
		for(tmpnode.size) {
			nodes.add(HolNeVerbindung(tmpnode.get(i)));
		}
	}	

	return iCount;
}

allerdings ist sehr stark anzunehmen, dass clone() hier nicht das Problem ist,
sondern die Methode selber mit potentiell exponentiellen Wachstum, Endlosschleifengefahr usw.,

gut möglich, dass die Exception dann beim clone() auftrat, aber das ist nur das Bauernopfer,
wenn die Wanne voll ist, kann jeder an sich noch so kleine Tropfen den Überlauf bewirken

----

Beispiel:

ein Node-Netz
A -- B -- C




am Anfang ist B in der Liste,
im zweiten Schritt dessen Nachbarn, also A und C,
danach die Nachbarn von A (B) und C (B), also zwei B,
danach A, C, A, C
danach 4 B
danach A, C, A, C, A, C, A, C
usw.
bald sind es unendlich viele

 

[Aerics]

Schon mal vielen Dank!
Ich werde Morgen nochmal an der Arbeit schauen wo das Problem auftritt und poste dann noch einmal.

Schönen Abend noch.

 

[Aerics]

Hier wie versprochen die Methode.
Diese scheint nun zu funktionieren, doch mich würde eure Meinung interessieren, da ja die Heransgehensweise über die Templiste in Frage gestellt wurde.

    private static int GetJumpCount(int fromSolarSystemID, int toSolarSystemID) {
        if(fromSolarSystemID == toSolarSystemID)
            return 0;
        
        ArrayList<Integer> Nodes = new ArrayList<Integer>();
        int iCount = 1;
        
            for (Integer i : MapSolarSystemJumps.get(fromSolarSystemID)) {
                Nodes.add(i);
        }
        
        Collections.sort(Nodes);        
        
        while(Collections.binarySearch(Nodes,toSolarSystemID) <= 0){            
            ArrayList<Integer> tmpNodes = Nodes;
            Nodes = new ArrayList<Integer>(); 
            
            for (int i = 0; i < tmpNodes.size(); i++) {
                for (Integer y : MapSolarSystemJumps.get(tmpNodes.get(i))) {
                    if(Collections.binarySearch(Nodes,y) <= 0) {
                        Nodes.add(y);
                        Collections.sort(Nodes);
                    }
                }
            }
            
            iCount++;
        }

        return iCount;
    }

 

[SlaterB]

ich glaube, mehr als solch verrückte Vermutungen wie meine vorherigen kann man dazu nicht aufstellen,
denn niemand weiß, was genau in dem Programm passiert,

vielleicht läuft auch alles super, aber dann bleibt die vorherige OutOfMemoryException ungeklärt,
am clone() kann es nicht liegen

 

[Aerics]

Ich denke, dass das Problem mit dem Memory dadurch auftrat, dass ich 2 IDs wählte, wovon es eine nicht in der DB und somit keine Verbindung gab.

Das Programm macht bis jetzt noch gar nix groß.

Hier stehen all meine ca. 5 tausend Nodes mit dessen Verbindungen drin.

private static Map<Integer, HashSet<Integer>> MapSolarSystemJumps = new HashMap<Integer,HashSet<Integer>>();

Anschließend rufe ich meine Methode mit 2 IDs auf und renne so lange durch diese Map, bis sich beide treffen.

Ob man das noch optimieren kann weis ich nicht.
Hab schon überlegt, ob es nicht schneller sein müsste, von Start- sowie Endnode anzufangen und sich in der Mitte zu treffen. Denn wenn ich von einem Punkt aus gehe wird es theoretisch ja mit jedem tieferen Schritt x mal so viele Möglichkeiten geben bis ich am Ende angekommen bin. Vielleicht liege ich aber auch falsch

/edit
Also ich bin jetzt auf den A* Algo gestoßen.
Leider verstehe ich diese nicht richtig und finde keine Implementation in Java. Bin mir auch nicht ganz so sicher, ob dieser für mein Fall wirklich gut ist.
Dies hier ist eine PHP-Lösung die für mein Problem bereits genutzt wurde und recht performant sein soll.
http://web.archive.org/web/20070316001615/http://www.asenski.com/archives/7
Leider hab ich noch nicht den Aha-Effekt was das Dinge da macht