D
Doubleslash
Gast
Hallo,
in unserem Programmierpraktikum im Studiengang Wirtschaftsinformatik war neulich die Aufgabe gestellt worden, eine rekursive Methode zu schreiben, die ein gegebenes Feld von Zeichen (in welcher Form auch immer) permutiert, also alle Möglichkeiten der Anordnungen seiner Elemente ausgibt. Ich habe das versucht wie folgt (beachtet, dass von uns verlangt wurde, dass auf Java 1.4 Stufe zu machen, daher keine Verwendung generischer Typen):
Wie ich schon im Kommentar geschrieben habe, geht das ab 9 Elementen in der Liste nimmer ohne den RAM der JVM zu vergrößern. Das kanns doch aber nich sein. Ich habe an den 3 Stellen im Code mit dem entsprechenden Kommentar schon die Objekte die nur temporär benötigt werden auf "null" gesetzt, damit sie der Garbage Collector rauswirft. Trotzdem tritt ab 9 Elementen in der zu permutierenden Liste ohne RAM-Erweiterung "heap space"-Fehler auf - der JVM geht der Speicher aus. Ich verstehe das nicht. Löscht der GC die Objekte nicht oder liegt es daran, dass eine LinkedList (oder generell eine List) nicht so viele Elementen handhaben kann?
Ich weiß, man hätte das sicher auf mit einem einzigen Array lösen können, aber ich möchte für den Erfahrungswert wissen, wo hier das Perfomance-Problem liegt. Einer von euch ne Idee?
in unserem Programmierpraktikum im Studiengang Wirtschaftsinformatik war neulich die Aufgabe gestellt worden, eine rekursive Methode zu schreiben, die ein gegebenes Feld von Zeichen (in welcher Form auch immer) permutiert, also alle Möglichkeiten der Anordnungen seiner Elemente ausgibt. Ich habe das versucht wie folgt (beachtet, dass von uns verlangt wurde, dass auf Java 1.4 Stufe zu machen, daher keine Verwendung generischer Typen):
Code:
import java.util.LinkedList;
import java.util.List;
/*
* Knobel-Aufgabe:
*
* Dieses Programm berechnet aus einer gegebenen Liste von Elementen der Groeße
* n alle n-Fakultaet Permutationen, die sich daraus ergeben. Als Datenstrukturen
* werden List bzw. LinkedList zur Rueckgabe verwendet.
*/
public class Permutationen
{
/*
* Berechnet zu einer gegebenen Zahl n die Fakultaet und gibt sie zurueck.
*/
public static int fakultaet(int n)
{
int fakultaet = 1;
for(;n > 1;n--)
{
fakultaet *= n;
}
return fakultaet;
}
/*
* Erstellt zu einer gegebenen List von Elementen eine LinkedList-Array, dessen
* LinkedList-Instanzen jeweils eine Permutation (Erhebung) darstellen.
* Dabei wird das Prinzip verwendet, dass besagt, dass eine Vollerhebung (n! Permutationen)
* eines Feldes daraus zustande kommt, dass man jeweils alle Permutationen des Teilfeldes der Laenge
* n-1 bildet und zu jeder dieser Teilerhebungen neue Erhebungen erstellt in denen jeweils das letzte
* (nicht in das permutierte Teilfeld einbezogene) Element durch alle moeglichen Stellen der Teilerhebungen
* wandert. Pro Teilerhebung der Laenge l(=n-1) entstehen somit l+1(=n) neue Teilerhebungen.
* Somit entstehen insgesamt bei (n-1)! Teilerhebungen mal l+1 neue Teilerhebungen, also
* (n-1)! * n = n!
*/
public static LinkedList[] permutare(List feld)
{
if(feld.size() == 1) // einfachster Fall (Rekursionsende)
{
LinkedList vollErhebung = new LinkedList();
vollErhebung.add(feld.get(0));
return new LinkedList[] {vollErhebung}; // die Vollerhebung einer 1-stelligen Liste erzeugt eine Permutation, die Liste selbst
}
else
{
LinkedList[] teilErhebungen = permutare(feld.subList(0, feld.size()-1)); // Teilerhebung der Liste 1 ... n-1 bilden
LinkedList[] vollErhebungen = new LinkedList[fakultaet(feld.size())]; // Array mit LinkedList-Instanzen der Laenge n! vorbereiten
for(int i = 0, v = 0; i < teilErhebungen.length; i++) // das Array aller (n-1)! entstandenen Teilerhebungen iterieren
{
for(int p = 0; p <= teilErhebungen[i].size(); p++, v++) // aktuelle Teilerhebungen als LinkedList iterieren
{
teilErhebungen[i].add(p, feld.get(feld.size()-1)); // an aktuelle Teilerhebung in aktuelle Position das n-te Element der gegebenen Liste positionieren
vollErhebungen[v] = (LinkedList)teilErhebungen[i].clone(); // die daraus neu enstehende Erhebung zum Ergebnis der Vollerhebung kopieren (shallow copy)
teilErhebungen[i].remove(p); // Teilerhebung wieder in Originalzustand versetzen
}
teilErhebungen[i] = null; // GC anweisen, dass Objekt aus dem RAM zu entfernen (Perfomance)
}
teilErhebungen = null; // -""-
feld = null; // -""-
return vollErhebungen; // Vollerhebung zurueckgeben
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.add(list.size(), Integer.valueOf(1));
list.add(list.size(), Integer.valueOf(2));
list.add(list.size(), Integer.valueOf(3));
list.add(list.size(), Integer.valueOf(4));
list.add(list.size(), Integer.valueOf(5));
list.add(list.size(), Integer.valueOf(6));
list.add(list.size(), Integer.valueOf(7));
list.add(list.size(), Integer.valueOf(8));
// list.add(list.size(), Integer.valueOf(9)); // funktioniert erst wenn man der JVM mind. 128 MB RAM zuweist
// list.add(list.size(), Integer.valueOf(10));
// list.add(list.size(), Integer.valueOf(11));
LinkedList[] vollErhebung = permutare(list);
for(int i = 0; i < vollErhebung.length;i++)
{
System.out.println(vollErhebung[i]);
}
System.out.println("\nDie Liste " + list + " hat " + vollErhebung.length + " Permutationen!");
}
}
Wie ich schon im Kommentar geschrieben habe, geht das ab 9 Elementen in der Liste nimmer ohne den RAM der JVM zu vergrößern. Das kanns doch aber nich sein. Ich habe an den 3 Stellen im Code mit dem entsprechenden Kommentar schon die Objekte die nur temporär benötigt werden auf "null" gesetzt, damit sie der Garbage Collector rauswirft. Trotzdem tritt ab 9 Elementen in der zu permutierenden Liste ohne RAM-Erweiterung "heap space"-Fehler auf - der JVM geht der Speicher aus. Ich verstehe das nicht. Löscht der GC die Objekte nicht oder liegt es daran, dass eine LinkedList (oder generell eine List) nicht so viele Elementen handhaben kann?
Ich weiß, man hätte das sicher auf mit einem einzigen Array lösen können, aber ich möchte für den Erfahrungswert wissen, wo hier das Perfomance-Problem liegt. Einer von euch ne Idee?