heap space, LinkedList umspeichern

[Lirave]

Hallo, dies sind meine ersten Versuche mit Java.
Ich arbeite mit dem Tool eclipse.
Und habe mir dort eine Klasse Guillotine mit main() Funktion erstellt, und eine Klasse Funktionen, die einige Funktionen enthält.
Und eine weitere Klasse Stein, welches ein Bauteil repräsentiert.

Guillotine.java

import java.io.*;
import java.util.LinkedList;
public class Guillotine {

	/**
	 * @param args
	 */
	  public static void main(String[] args) {
		  	int drehen = 0;
		  	int anzahl = 0;
	        //Eingabe
	        BufferedReader ar = new BufferedReader(new InputStreamReader(System.in));
	        
	        try{
	            System.out.println("Anzahl der Steine eingeben: ");
	            anzahl = Integer.parseInt(ar.readLine());
	            
	        }catch(IOException ioe){
	            ioe.printStackTrace();
	        }catch(NumberFormatException nfe){
	            nfe.printStackTrace();
	        }
	        
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        
	        try{
	            System.out.println("Soll das drehen um 90° möglich sein? [0/1]: ");
	            drehen = Integer.parseInt(br.readLine());
	            
	        }catch(IOException ioe){
	            ioe.printStackTrace();
	        }catch(NumberFormatException nfe){
	            nfe.printStackTrace();
	        }
	        //
	        
	        // Steine werden erstellt und in Liste gespeichert, und eventuell gedreht hinzugefügt
	        LinkedList<Stein> Steine = new LinkedList<Stein>();
	        for(int i=1; i<=anzahl; i++){
	        	
	        	int[] num = Funktionen.erstelle(i,anzahl);
	        	int random1= (int)(Math.ceil(10*Math.random()));
	        	int random2= (int)(Math.ceil(10*Math.random()));
	        	Steine.addLast(new Stein(random1,random2,num,"n"+String.valueOf(i)));
	        	if (random1 != random2 && drehen == 1) {
	        		Steine.addLast(new Stein(random2,random1,num,"d"+String.valueOf(i)));
	        	}
	        	
	        }
	        
	        //LinkedList<LinkedList<Stein>> Teile= new LinkedList<LinkedList<Stein>>();

	        
	        
	        
	        //
	        
	        LinkedList<Stein> Teile_alt = Steine;						//alle bisherigen Teile	
	        LinkedList<Stein> Teile_neu = Steine;						//alle im letzten Schritt hinzugekommenne Teile
	        LinkedList<Stein> Teile_neu_neu = new LinkedList<Stein>();	//alle in diesem Schritt hinzukommenden Teile
	        Stein Teil_neu;
	        Stein Teil_alt;
	        Stein Teil_neu_neu;
	        
	        // kombinert alle neuen Teile mit den bisher erzeugten Teilen
	        for(int z=1; z < anzahl ;z++){
	        	
		        for(int i=0; i<Teile_neu.size(); i++){
		        	Teil_neu = Teile_neu.get(i);
		        	for(int j=0; j<Teile_alt.size(); j++){
		        		Teil_alt = Teile_alt.get(j);
		        		
		        		if (Funktionen.disjunkt(Teil_alt.getNummer(),Teil_neu.getNummer())){	//wenn beide Teile disjunkte Steine enthält, dann verbinde sie
		        			Teil_neu_neu = Funktionen.verbindehorizontal(Teil_alt,Teil_neu);
			        		Teile_neu_neu.addLast(Teil_neu_neu);
			        		Teil_neu_neu = Funktionen.verbindevertikal(Teil_alt,Teil_neu);
			        		Teile_neu_neu.addLast(Teil_neu_neu);
		        		}
		        	}   		        	
		        }
		        Teile_alt = Funktionen.listenverbinden( Teile_alt ,Teile_neu_neu);
		        Teile_neu = Funktionen.listenersetzen(Teile_neu, Teile_neu_neu);
                        Teile_neu_neu.clear();

	        }

	        //Ausgabe von Teile_neu_neu
	        System.out.println(Teile_alt.size());
	        for(int i=0; i<Teile_alt.size(); i++){
	        	System.out.println("Stein"+(i+1)+" ("+Teile_alt.get(i).getId()+") : "+ Teile_alt.get(i).getNummer());
	        }
	        //			
	  }      
}

Stein.java

public class Stein {
    private int hoehe;
    private int breite;
    private int[] nummer;
    private String id;

    public Stein(int h, int b, int[] n,String c) {
        this.hoehe = h;
        this.breite = b;
        this.nummer = n;
        this.id = c;
        
    }

    public void setHoehe(int h) {
        this.hoehe = h;
    }

    public void setBreite(int b) {
        this.breite = b;
    }

    public void setNumber(int[] n) {
        this.nummer = n;
    }
    
    public void setId(String c) {
        this.id = c;
    }

    public int getHoehe() {
        return hoehe;
    }

    public int getBreite() {
        return breite;
    }

    public int[] getNummer() {
        return nummer;
    }
    
    public String getId() {
        return id;
    }
    
    public void disp() {
    	System.out.print("Höhe: "+this.hoehe+" Breite: "+this.breite+" Steine: ");
    	for(int i=0;i<this.nummer.length;i++){
    		System.out.print(this.nummer[i]+" ");
    	}
    	System.out.println();
    	
    }

}

und zu guterletzt noch Funktionen.java

import java.util.LinkedList;
public class Funktionen {

    public static Stein verbindehorizontal(Stein s1, Stein s2) {
        return new Stein(Math.max(s1.getHoehe(), s2.getHoehe()),s1.getBreite() + s2.getBreite(), add(s1.getNummer(), s2.getNummer()),"("+s1.getId()+"h"+s2.getId()+")");
    }
    
    public static Stein verbindevertikal(Stein s1, Stein s2) {
        return new Stein(s1.getHoehe() + s2.getHoehe(),Math.max(s1.getBreite(), s2.getBreite()), add(s1.getNummer(), s2.getNummer()),"("+s1.getId()+"v"+s2.getId()+")");
    }
    
    public static LinkedList<Stein> listenverbinden( LinkedList<Stein> Liste1 ,LinkedList<Stein> Liste2) {
    	for(int i = 0; i<Liste2.size(); i++ ) {
    		Liste1.addLast(Liste2.get(i));
    	}
        return Liste1;
    }
    
    public static LinkedList<Stein> listenersetzen( LinkedList<Stein> Liste1, LinkedList<Stein> Liste2) {
    	Liste1.clear();
    	for(int i = 0; i<Liste2.size(); i++ ) {
    		Liste1.addLast(Liste2.get(i));
    	}
        return Liste1;
    }
    
    
    
    public static int[] erstelle(int i , int anzahl){
    	int[] nummer = new int[anzahl];
    	for(int j = 0; j< anzahl; j++){
    		if (i == (j+1)){
    			nummer[j] =1;
    		}else{
    			nummer[j] =0;    		
    		}
    	}
    	return nummer;
    }
    
    public static boolean disjunkt(int[] teile1, int[] teile2){
    	for (int i = 0; i < teile1.length; i++){
    		if (teile1[i] == 1 && teile2[i]==1){
    			return false;
    		}
    	}
    	return true;
    }
    
    
    
    public static int[] add(int[] i, int[] j){
    	int[] nummer = new int[i.length];
    	for (int k = 0; k< i.length; k++){
    		nummer[k] = i[k] + j[k];
    	}
    	return nummer;
    }
}

In der Guillotine.java werden zuerst 2 Werte eingelesen, die Anzahl der zu erstellenden Steine, und ob man sie um 90° drehen können soll.

Danach werden entsprechend viele Steine erstellt, und zu beginn in den beiden LinkedLists Teile_alt und Teile_neu gespeichert.
Nun werden alle Teile miteinander kombiniert und die neu entstandenen Teile werden in einer weiteren LinkedList Teile_neu_neu gespeichert.

Soweit so gut.
Nun möchte ich für die weiteren Durchgänge die LinkedListen neu "anordnen".
Und zwar soll im nächsten Schritt in der Liste Teile_alt drin stehen alle werte aus Teile_alt und die aus Teile_neu_neu.
Teile_neu_neu soll jetzt umkopiert werden, so dass diese Werte nun in der Liste Teile_neu zufinden sind (alle Teile aus Teile_neu sind gelöscht). Und am Schluss soll noch Teile_neu_neu geleert werden.

Ich dachte auch, dass ich dies so oben in dem Script getan habe, doch leider klappt es nicht ganz.
Denn entweder ich bekomme eine exeption, wegen zuwenig Speicher, oder es wird alles gelöscht.

Hoffe ihr versteht, was mein Problem ist und könnt mir schnell helfen.

Mit freundlichen Grüßen
Robert

 

[MQue]

Hab mal drüber geschaut und mir sind ein paar Sachen aufgefallen,

1. deine for- Schleifen fangen immer mit 1 an
for(int z=1; z < anzahl ;z++){ // Indizes von Arrays und Listen beginne aber bei 0 -> array[0] oder list.get(0).

2. Wenn du die Inhalte einer Liste kopieren willst, musst du den Inhalt (sprich die Objekte der Liste) kopieren (deep copy -> also mit new die Objekte neu erzeugen und dann die Werte in das Objekt setzen wie beim original) und dann diese kopierten Objekte in der neuen Liste speichern.

LinkedList<Stein> Teile_alt = steine; // das erzeugt nur eine Referenz Teile_alt auf die steine- Liste. Du hast aber auf keinen Fall eine neue Liste.

3. referenzVariablen fangen in Java klein an und es wird CamelCasing verwendet, teileAlt statt Teile_alt

Hoffe es hilft,

 

[Lirave]

Danke für deine schnelle Antwort,
das die Listen bei index 0 anfangen ist mir klar gewesen, die äußere Schleife ist nur eine Zählschleife.

Aber wenn ich das richtig verstanden habe muss ich jedes Element aus der einen Liste neu erstellen und dann hinzufügen, danach kann ich dann die alte Liste löschen.

Werde das sofort probieren.

Ich habe mal von einer Klasse clone gelesen, ist das das sogenannte deep copy ?

Gruß
Robert

 

[Lirave]

sorry, ist mir noch eingefallen habe nichts gefunden um meinen Beitrag zu editieren(denke dies ist nicht möglich als Gast)

wenn ich nun in der Funktionen.java eine Funktion schreibe und dort die Liste übergebe die später sozusagen einen anderen Namen haben soll.(Also alle Teile von Steine in Teile_alt speichern)

Teile_alt = Funktionen.ersetzen(Steine);

Funktionen.java

    public static LinkedList<Stein> ersetzen( LinkedList<Stein> Liste1) {
        LinkedList<Stein> Liste_copy = new LinkedList<Stein>();
        for(int i = 0; i<Liste1.size(); i++ ) {
            Liste_copy.addLast(new Stein(Liste1.get(i).getHoehe,....));        // Plus weitere Attribute von Stein
        }
        Liste1.clear();
        return Liste_copy;
    }

Mit dieser Variante habe ich jetzt erreicht, dass alle Listen Einträge von Steine jetzt in Teile_alt zu finden sind. (Hoffe ich)

Aber wie sieht es mit den anderen Listen aus, also Steine und Liste1, und Liste_copy.
Mir wäre es am liebsten, wenn nur noch etwas in Liste_alt zu finden wäre, eventuell noch in Steine, damit ich es später in der main methode löschen kann. (wegen dem Speicherbedarf)

Oder sehe ich das richtig, dass jetzt Liste_alt nur auf Objecte von Liste_copy zeigt, aber wenn ich die Funktion erneut mit andern Listen aufrufe die Werte in Liste_alt auch geändert werden ?

 

[MQue]

shallow copy (macht das von dir angesprochene clone standardmäßig auch so):

List<Person> listPersonen1 = new ArrayList<Person>();
List<Person> listPersonen2 = new ArrayList<Person>();

Person person1 = new Person();
person1.setName("Hannes");

listPersonen1.add(person1);
listPersonen2 = listPersonen1;  // die Refenenz listPersonen2 zeigt auf listPersonen1, es gibt aber nur 
eine Person ("Hannes"), wenn du person1 in listPersonen1 löscht, gibt es kein Person mehr,
weder in listPersonen1 noch in listPersonen2

deep copy:

List<Person> listPersonen1 = new ArrayList<Person>();
List<Person> listPersonen2 = new ArrayList<Person>();

Person person1 = new Person();
person1.setName("Hannes");
listPersonen1.add(person1);

Person person1Copy = new Person();
person1Copy.setName(listPersonen1.get(0).getName());
listPersonen2.add(person1Copy);

am besten, du machst dir einen Copy- Construktur wie man ihn von C++ oder C# her kennt, dann klappt am einfachsten.

 

[Lirave]

ich habe noch eine Frage,

wenn ich folgendes mache:

LinkedList<Stein> test = new LinkedList<Stein>();

dann habe ich schon speicherplatz für eine LinkedList reserviert, es ist aber noch leer, oder ?
Und mit test greife ich dann auf den Speicher zu.

Wenn das richtig ist, was passiert, wenn ich folgendes mache.

LinkedList<Stein> test = new LinkedList<Stein>();

LinkedList<Stein> test = new LinkedList<Stein>();

Dann würde nach meinem jetzigen Verständnis 2 mal speicher reserviert werden. aber test kann nun nur noch auf den 2. speicher zugreifen, der erste würde dann zu Datenmüll.

Sehe ich das richtig?

Oder macht das einen unterschied ob ich vorher was in test speichere oder nicht, also

LinkedList<Stein> test = new LinkedList<Stein>();
test.setHoehe(1);
LinkedList<Stein> test = new LinkedList<Stein>();
test.setHoehe(2);

Dann würde doch irgendwo "Stein" rumliegen mit Hoehe 1 auf den nichtmehr zugegriffen werden kann.

Gruß Robert

 

[Lirave]

Habe nochmal rumgebastelt am Programm, und denke ich habe auch nicht zu viel Speicher verbraucht, trotzdem kommt er bei 158 Steinen und drehen gleich 1 mit folgender Fehlermeldung.

"Anzahl der Steine eingeben:
158
Soll das drehen um 90° möglich sein? [0/1]:
1
1Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Funktionen.add(Funktionen.java:77)
at Funktionen.verbindehorizontal(Funktionen.java:5)
at Guillotine.main(Guillotine.java:116)"

Kann es sein, das ein int[] durch seine länge auf 157 einträge begrenzt ist ?
Oder wo liegt eurer Meinung nach der Fehler.

Ich habe mein gesammtes Programm was in eclipse erstellt wurde mal gepackt, und hoffe es hat jemand die Zeit mal da drüber zu schauen.

Hier ist der Link wo ihr das zip Archiv mit den Daten runterladen könnt. (Hoffe es ist hier erlaubt)
kostenlos Dateien hochladen bei File Upload X

Mfg Robert


Achja habe das Programm mit einem Kommando gestartet, das angeblich mehr Speicherplatz freigibt für java ( -Xms800m -Xmx800m)

 

[SlaterB]

> Kann es sein, das ein int[] durch seine länge auf 157 einträge begrenzt ist ?

wie schließt du von einem Speicherfehler darauf?
die Exception kommt, weil du zuviel Speicher brauchst, ein int[] für sich kann 2 Mill. ints fassen, was 8 GB entspricht,
also in heutigen Zeiten kaum je erreicht wird

dein Programm downloaden und analysieren ist etwas viel verlangt,
kannst du es nicht selber einigermaßen durchschauen? fange mit 5 Steinen an oder 2x 5 Steine,
wieviele neue werden daraus erzeugt, 25? + paar mal kopieren vielleicht insgesamt 100 Stein-Objekte?
dann baue im Stein-Konstruktor ein Log ein, oder zähle auch nur eine statische Variable hoch und gib die am Ende aus,
wenn die bei 10.000 statt 100 steht, dann läuft was schief,

so klingt da ja in etwa wenn bei 158 ein OutOfMemoryError kommt,
kann natürlich auch sein, dass die Steine damit weniger zu tun haben, sondern die Listen schuld sind..

 

[Lirave]

Hallo, ich bin darauf gekommen, da eclipse mir zu der Fehlermeldung genau diese Zeile ausgibt, in der ich so ein int[] deklariere.

Wie man so eine Zähl variable in die Klasse einbaut habe ich nicht hin bekommen.

Ich habe den Code aber nochmal gekürzt.

	        LinkedList<Stein> Steine = new LinkedList<Stein>();
	        for(int i=1; i<=anzahl; i++){
	        	
	        	int[] num = Funktionen.erstelle(i,anzahl);
	        	int random1= (int)(Math.ceil(10*Math.random()));
	        	int random2= (int)(Math.ceil(10*Math.random()));
	        	Steine.addLast(new Stein(random1,random2,num,"n"+String.valueOf(i)));
	        	if (random1 != random2 && drehen == 1) {
	        		Steine.addLast(new Stein(random2,random1,num,"d"+String.valueOf(i)));
	        		
	        	}
	        }

Dies habe ich mit 7000 Steinen probiert,und es kommt zu einem heap space error.
Er zeigt wieder folgende Zeile an:

    public static int[] erstelle(int i , int anzahl){
    	int[] nummer = new int[anzahl];                    // um genau zu sein diese Zeile wird als Fehlerquelle erkannt
    	for(int j = 0; j< anzahl; j++){
    		if (i == (j+1)){
    			nummer[j] =1;
    		}else{
    			nummer[j] =0;    		
    		}
    	}
    	return nummer;
    }

 

[SlaterB]

die Stelle zeigt nur den Tropfen, der das Fass zum Überlaufen bringt, obwohl für sich wahrscheinlich gar nicht so groß
(zur Sicherheit aber besser 'anzahl' per System.out.println vorher ausgeben,
damit loggst du auch, wie oft die Methode erstelle() aufgerufen wird,
wenn tausende derartiger Ausgaben kommen, sollte das auffallen)

zum Zählen noch ein Beispiel:

public class Test {
    public static void main(String[] args)   {
        for (int i = 0; i < 10; i++)   {
            for (int j = 0; j < 10; j++)   {
                for (int k = 0; k < 10; k++)      {
                    new Stein();
                }
            }
        }
        System.out.println("Anzahl Steine: " + Stein.count);
    }
}
class Stein {
    static int count;

    public Stein()  {
        count++;
    }
}

Ausgabe: 1000

 

[Lirave]

Ich habe eine Verständnis frage.

Ich habe Objecte vom Typ Stein.
Dann habe ich Listen in denen ich Objecte vom Typ Stein anordne.

Dann habe ich eine neue Klasse von Objecten (die heißen Teile) und zwar bestehen die aus jeweils einem int[] und einer LinkedList<Stein>.
Diese Teile ordne ich wiederum in einer LinkedList<Teile> an.
Dadurch wollte ich erreichen, dass ich eine Art 2d Liste habe.


Wenn ich nun einen Stein erstelle, mittels new.
Und dann eine neue Liste mittels new erstelle und in diese dann den Stein mittels add einreihe.
Was passiert da genau. Wird dann der Stein nur verlinkt und in der Liste gespeichert. Oder habe ich dann Speicher belegt mit dem Object Stein und zusätzlich noch Speicher in der Liste, wo der Stein drin steht.

Und was passiert dann wenn ich Liste.clear() ausführe. Wird dann auch der Speicher von Stein freigegeben, oder existiert der weiter ?


Mfg Robert

 

[SlaterB]

ein Objekt wie Stein mit paar int- und sonstigen Variablen wird sicherlich 50-100 Byte groß sein,
diese werden immer dann belegt wenn irgendwo new Stein() steht,

Variablen/ Referenzen zeigen auf diese Objekte und belegen 4 Byte Speicher, egal wie groß das verlinkte Objekt ist,
eine Liste von 100 Plätzen ist normalerweise um die 400 Byte groß, Steine werden nicht kopiert,
sondern nur auf dasselbe Objekt im Speicher gezeigt

ob das Leeren der Liste direkt Speicher spart hängt von der Implementierung ab,
bei einer LinkedList ist jeder Platz ein kleines Stück Speicher (und deutlich mehr als 4 Byte) der beim Leeren eingespart wird,
eine ArrayList behält dagegen normalerweise ihre 100 Plätze, um sie später nicht neu reservieren zu müssen,
wenn die Liste wieder voller wird,

ob ein Stein-Objekt im Speicher entfernt wird, hängt davon ab, ob von irgendwo im Programm noch darauf verwiesen wird,
wenn es zwei Listen gab, mag das leeren der einen wenig Auswirkung haben, sind aber beide geleert oder
selber nicht mehr erreichbar, so werden die Steine freigegeben,

ich werde nun vielleicht doch bald das Programm anschauen, irgendwo muss der Speicher ja sein

 

[Lirave]

Ich bin es nochmal, habe mir gerade überlegt wenn ich 1000 Steine erstelle, das klappt ja ganz gut.
Aber später im Programm will ich auch Steine wieder löschen, wie mache ich das ?

Hatte gedacht ich mache eine Procedur clear(Stein) und würde dort alle einträge auf 0 setzten, aber dann ist er ja nicht gelöscht, wie bekomme ich den Speicherplatz wieder frei von einem Object das ich nicht mehr haben will ?


Gruß Robert

 

[eRaaaa]

------->

ob ein Stein-Objekt im Speicher entfernt wird, hängt davon ab, ob von irgendwo im Programm noch darauf verwiesen wird,
wenn es zwei Listen gab, mag das leeren der einen wenig Auswirkung haben, sind aber beide geleert oder
selber nicht mehr erreichbar, so werden die Steine freigegeben,

<------

Und zwar durch die Garbage_Collection

 

[Lirave]

so habe mich nun registriert, die Möglichkeit Beiträge zu editieren wollte ich nach dem letzten Post nutzen.


Den hatte ich erstellt, ohne den vorherigen zu lesen, kA wie das passiert ist.
Wenn das automatisch passiert weiß ich nicht woran es liegt, werde erstmal weiter machen, vlt geht das dann später wenn ich mehrere Kombinationen wieder entferne.

Hoffe ich kann heute Abend eine aktuellere Version rein stellen.

 

[Lirave]

gut denke ich habe das heap space Problem behoben, danke für eure Hinweise.

Nun habe ich ein anderes Problem, es dauert einfach so lange bis das Programm durchgelaufen ist.

Habe es mit 10 Steinen und drehen=1 gestartet.
Dauert aber etwas über 4min bis es durchgelaufen ist, und es eine minimale Anordnung ausspuckt.

Gibt es da ein paar Tricks wie man es schneller machen kann ?

Habe es mal wieder hochgeladen, falls jemand Zeit hat.
KLICK