Heap-Speicher der JVM wird gesprengt

Danke für den Tipp mit den Boolean-array,wird meine implementierung sehr erschweren ,aber wenn dadurchd er Fehler behoben werden kann isses akzeptabel

Der Tip mit dem Boolean array hängt vor allem mit zwei Gründen zusammen.
  1. Da du Wahrheitswerte errechnest ist Boolean mit seinen Belegungen "true" und "false" eigentlich der "richtige" Datentyp
  2. Ein Boolean Array verbraucht nur einen Byte pro Eintrag, mit Strings verbrauchst du schon 4Byte alleine für die Referrenz plus zusätzlich noch einmal einige Bytes für die Strings selbst. Du fährst hier also deutlich Speicherintensiver
  3. Zusätzlich kommt noch, das Stringverleiche mehr Rechenzeit verbrauchen. Du bist also mit Booleans schneller unterwegs

Es kann natürlich dennoch sein, dass es für dich sinnvoller ist, trotzdem Strings zu verwenden.
 
Also ich habe jetzt mein Programm mit nem 2dim boolean-Array erneut programmiert .
jetzt kann ich statt 2^18 , 2^19 übergeben (yeah xD ) aber 2^20 geht immer noch nicht.

Dein Programm (von Johannes7146) errechnet mir 20mb (dim1 =20, speicherbelgegung = 1 //wegen boolean)

und mein Programm gibt mir aber wieder die Fehlermeldung

Code:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at WerteT.TruthTable.<init>(TruthTable.java:19)
        at WerteT.Main.main(Main.java:19)

und eigentlich will ich 2^25 über geben und da errechnet mir dein Programm 839 mb
hmmmm.....
 
Bei 25 Werten kommst du unter 800 MB nicht raus.
Du solltest überlegen ob du für die Problemlösung wirklich die komplette Tabelle aufbauen musst.
Je nach dem was du herausfinden willst, brauchst du möglicherweise gar nicht die Wahrheitstabelle, sondern kannst das Problem mit einem SAT Solver lösen (Wikipedia Artikel).

In jedem Fall bin ich jetzt neugierig geworden.
Kannst du den kompletten Quellcode posten, damit ich ihn mal bei mir ausführen kann?

MfG

Andibert
 
So ich hab mal in den Quellcode geguckt, den du mir per PN geschickt hast.
Hier schreib ich nur, das was für alle interessant ist, Dinge die sich direkt auf deinen Quellcode beziehen schreibe ich per PN.

Uhrsache für den Crash ist, wie bereits von vieler Seite angenommen, die schiere Größe des Arrays.
Durch Heraufsetzen der Speichergrenzen wie Johannes7146 es erklärt hat, wird es möglich größere Arrays (Dimension 24) zu erstellen. Für jede weitere Dimension musst du den zur Verfügung gestellten Speicher verdoppeln. Jedoch hat sich schon bei der Dimension 25 mein Betriebssystem geweigert genügend freien Speicher zur Verfügung zu stellen. Als ich versucht hab ihn dazu zu zwingen, in dem ich die initiale Größe der VM auf einen Gigabyte festgelegt habe, fing mein OS wie wild an Daten auf die Festplatte auszulagern, und viele Programme reagierten so gut wie gar nicht mehr. Nach fünf Minuten habe ich Eclipse dann abgeschossen, um wieder Kontrolle über mein OS zu erlangen.

Wie ich das sehe, ist die Größe 25 absichtlich so gewählt, um Abgaben zu verhindern, die mit einer Großen Wahrheitstabelle arbeiten.
Des weiteren hast du auch keine Kontrolle darüber welche Rechner dein Programm später ausführen. Ein Ändern der VM Größe auf große Werte, ist also nicht ganz trivial. Du solltest dich also nach einer Möglichkeit umschauen, wie du das Problem ohne große Tabelle lösen kannst.

Wenn die Tabelle Verwendest hast du immer einen exponentiellen Aufwand. Zusätzlich musst du danach auf dieser Riesen Tabelle Algorithmen für NP-Vollständige Probleme (Wikipedia Link) anwenden. Wenn du da die Dimension nur noch ein wenig erhöhst, landest du bei Berechnungszeiten die die Menschheitsgeschichte Übertreffen.

Alles Weitere dann per PN

MfG

Andibert

P.S. Guter Beitrag Johannes, das gibt n Daumen
 
Zuletzt bearbeitet:
P.S. Guter Beitrag Johannes, das gibt n Daumen

Man tut was man kann ^^
Danke :-)

Zurück zum Thema:
1. Vorschlag.
Wie wäre es wenn du die Tabelle nach und nach generieren lässt und dann in einer Datenbank abspeicherst.
So wird später nicht der Ram benötigt sondern die Festplatte (diese sollte genügen Platz bieten).
Bleibt noch offen wie lange es dann dauert einen Wert aus dieser Tabelle herauszufiltern.

2. Vorschlag.
Das Array aufteilen. Ein 2 Dimensionales Array kannst du dir ja wie eine Tabelle vorstellen.
Einfach jede Zeile einzelnt ablegen.

Wenn du ein Array mit
dim1 = 20
dim2 = 1048576
anlegen möchtest,...

dann leg doch einfach 20 mal ein array mit
dim1 = 1
dim2 = 1048576
an.

Wenn du das erste erstellt hast, kannst du es serialiesieren (Java Objekt auf der Festplatte speichern).
Danach kannst du das nächste erstellen, da der Speicher der für das erste genutzt wurde wieder frei ist.

Beim Zugriff musst du dann schauen welche Datei du wieder laden musst.
 
Zuletzt bearbeitet:
Ich habe noch zwei Tipps für dich:

1. Verwende nicht den Typ boolean, sondern ein BitSet, dann verbraucht nämlich jeder Wahrheitswert nur 1 Bit.
2. Überprüfe mal, ob du nicht einen besseren Algorithmus verwenden kannst. Das Beste ist wohl, wenn du mir die ursprüngliche Problemstellung und/oder deinen Quellcode zusendest.
 
Hier mal ein Beipsiel zu Vorschalg 2.
Das Anlegen der Dateien musst du wsl nur einmalig machen.
Also erst einmal ausführen,
dann den Teil auskommentieren wo das Array Zeilenweise abgelegt wird.
Und dann nochmals starten.

Java:
package de.tutorials.johannes7146;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

public class MemTest {

	/**
	 * Speicherpfad andem die serialisierten Dateien liegen.
	 */
	private String speicherPfad = "D:" + File.separator + "ser";

	public static void main(String[] args) {
		MemTest memTest = new MemTest();

		// Festplatte wieder leeren
		// memTest.clean();

		System.out.println("ENDE");
		System.exit(0);
	}

	public MemTest() {
		int dim1 = 25;
		int dim2 = calculateExpLinear(dim1);
		System.out.println("Dim1: " + dim1);
		System.out.println("Dim2: " + dim2);

		// 1 Byte pro Referenz
		int speicherBelegung = 1;

		double memory = ((double) dim1 * (double) dim2 * (double) speicherBelegung);

		System.out.println("genutzer Speicher: " + memory + " byte");
		System.out.println("genutzer Speicher: " + memory / 1000 + " KiloByte");
		System.out.println("genutzer Speicher: " + memory / 1000 / 1000
				+ " MegaByte");
		System.out.println("genutzer Speicher: " + memory / 1000 / 1000 / 1000
				+ " GigaByte");

		// Array komplett anlegen
		// boolean[][] test = new boolean[dim1][dim2];

		// Array Zeilenweise anlegen und auf Festplatte ablegen
		for (int i = 0; i < dim1; i++) {
			boolean[][] tmp = new boolean[1][dim2];
			zeileSpeichern(i + 1, tmp);
			tmp = null;
			System.gc();
		}
		
		System.out.println(wertLesen(22, 123456));
		wertSchreiben(22, 123456, true);
		System.out.println(wertLesen(22, 123456));

	}

	/**
	 * Berechnet die Größe der 2. Dimension
	 * 
	 * @param length1
	 * @return
	 */
	public static int calculateExpLinear(int length1) {
		int amount = 1;
		for (int i = 0; i < length1; i++) {
			amount *= 2;
		}
		return amount;
	}

	/**
	 * Holt sich die entsprechende Zeile von der Festplatte und gibt den
	 * gewünschten Wert zurück
	 * 
	 * @param posDim1
	 * @param posDim2
	 * @return
	 */
	public boolean wertLesen(int posDim1, int posDim2) {
		boolean[][] tmp = zeileLaden(posDim1 + 1);
		return tmp[0][posDim2];
	}

	/**
	 * Holt sich die entprechende Zeile von der Festplatte, änder Sie und speichert sie wieder ab.
	 * @param posDim1
	 * @param posDim2
	 * @param value
	 */
	public void wertSchreiben(int posDim1, int posDim2, boolean value) {
		boolean[][] tmp = zeileLaden(posDim1 + 1);
		tmp[0][posDim2] = value;
		zeileSpeichern(posDim1 + 1, tmp);
	}

	/**
	 * Speichert eine Zeile des Arrays auf der Festplatte ab
	 * 
	 * @param zeile
	 *            die Zeilennummer
	 * @param data
	 *            Das Array, welches die Zeile repäsentiert
	 */
	public void zeileSpeichern(int zeile, boolean[][] data) {
		try {
			long start = System.currentTimeMillis();
			ObjectOutputStream oos = new ObjectOutputStream(
					new FileOutputStream(speicherPfad + File.separator + zeile
							+ ".ser"));
			oos.writeObject(data);
			oos.flush();
			oos.close();
			long ende = System.currentTimeMillis();
			System.out.println("Zeile " + zeile + " in " + (ende - start)
					+ " ms gespeichert.");
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	/**
	 * Läde eine Zeile von der Festplatte
	 * 
	 * @param zeile
	 *            Die Nummer der gewünschten Zeile
	 * @return
	 */
	public boolean[][] zeileLaden(int zeile) {
		long start = System.currentTimeMillis();
		boolean[][] result = null;

		try {
			ObjectInputStream ois = new ObjectInputStream(new FileInputStream(
					speicherPfad + File.separator + zeile + ".ser"));
			result = (boolean[][]) ois.readObject();
			ois.close();
			long ende = System.currentTimeMillis();
			System.out.println("Zeile " + zeile + " in " + (ende - start)
					+ " ms geladen.");

		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
		}

		return result;
	}

	/**
	 * Löscht alle Dateien die im Speicherpfad liegen
	 */
	public void clean() {
		File f = new File(speicherPfad);
		for (File element : f.listFiles()) {
			element.delete();
		}
	}

}
 
Zuletzt bearbeitet:
Ich hab mit dieser Methode gerade für dim1 = 27 angegeben und 3,6BG auf meine Festplatte ausgelagert.
Das scheint soweit zu funktionieren.

Dim1 = 25;
Eine Zeile Schreiben ca. 640 ms
Eine Zeile lesen ca. 328ms
--> Einen wert im Array ändern dauert also 1 Sekunde. Nur lesen 328ms. (gilt für meinen Rechner und dim1 = 25).

Dim1 = 27;
Eine Zeile Schreiben ca. 2,5 Sekunden.
Eine Zeile lesen ca. 2,5 sekunden.
--> Einen wert im Array ändern dauert also 5 Sekunden. Nur lesen 2,5 Sekunden. (gilt für meinen Rechner und dim1 = 27).
 
Zuletzt bearbeitet:
Hallo,

wie sieht denn nun konkret das Problem aus, das mit der Wahrheitstabelle gelöst werden soll? Korn-flake und Andibert haben sich ja anscheinend schon hinter verschlossenen Türen ausgetauscht, was dem Rest der Welt leider nicht viel bringt…

Grüße,
Matthias
 
So wie ich das verstanden habe möchte er mit einem 2 dimensionalem Array Arbeiten, welches so groß ist, das es nicht im Speicher gehalten werden kann.

Mit dem Beipsiel von mir klappt es bis dim1 = 27.
Bei dim1 = 28 reicht der Speicher nichtmal um eine Zeile im Ram zu halten. (Zumindest nicht ohne die VM-Start-argugmente anzupassen)
 
Zuletzt bearbeitet:
Zurück