Warum läuft dieses Programm so langsam?

[Doubleslash]

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):

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?

 

[André Uhres]

Wenn eine Variable auf null gesetzt wird dann schreitet der GC nicht sofort ein.
Man kann es mit System.gc() versuchen, aber dann dauert es noch länger!

 

[bygones]

irgendwie ist das glaub ich nicht mein Tag ^^

kannst du mir erklären, dass der Algorithmus korrekt läuft ?

LinkedList[] teilErhebungen = permutare(feld.subList(0, feld.size()-1));

solange die liste größer ist als ein element, rufst du die Methode erneut auf mit einer liste um eins kleiner. Wenn die Liste ein Element hast steckst du das in eine Liste, die in einen Array kommt....

d.h. bei einer Liste mit 3 Elementen 1,2,3:

1. permutare([1,2,3]) -> else zweig
2. permutare([1,2]) -> else zweig
3. permutare([1]) -> if und in den array und return, rekursion wird unterbrochen

d.h. teilErhebung ist nun ein Array mit einer Liste mit 1 drinnestehen.
Dann machst du weiter.... ich seh jedenfalls hier keine permutation ?!

falscher Algo oder ist deathbyaclown nun blindclown?

btw: beim adden brauchst du nicht immer size() aufrufen, wenn kein parameter ist wird immer hintan angehängt.

Zum GC - der läuft irgendwann ohne dass jemand ihn zwingen kann.... seh gc() als netten Ratschlag

 

[SlaterB]

@deathbyaclown:
ws stört dich denn? bei einem Element ist nicht viel zu tun und es wird einfach eine einelementige Liste zurückgegeben,
die dann aber im nächsten (vorherigen) Schritt sinnvoll weiterverarbeitet (zu einer Liste mit zwei Elementen: [1,2] und [2,1]),
so arbeitet doch eine Rekursion?

@Doubleslash:
viel tun kann man nicht, eine LinkedList mit 10 Elementen braucht nun mal ~240 Bytes,
363.000 Stück davon -> 87 MB,
die entstehen praktisch alle im letzten Arbeitsschritt, die 40.000 von der Teilerhebung machen nur 10% mehr aus,

für die Arrays zur Speicherung der Listen fallen auch noch mal ein paar kleine MB an..

------------

der GC hat da ne Menge zu tun wenn er bei sovielen Objekten aufräumen will ,

ich hab mal irgendwo folgendes aufgeschnappt,:

	public static void runGC () {
        // It helps to call Runtime.gc()
        // using several method calls:
        try {
        	for (int r = 0; r < 4; ++ r) {
        		_runGC ();
        	}
        } catch(Exception e) {
        	e.printStackTrace();
        }
    }

    public static void _runGC () throws Exception
    {
        long usedMem1 = usedMemory (), usedMem2 = Long.MAX_VALUE;
        for (int i = 0; (usedMem1 < usedMem2) && (i < 500); ++ i)
        {
            s_runtime.runFinalization ();
            s_runtime.gc ();
            Thread.yield ();
            
            usedMem2 = usedMem1;
            usedMem1 = usedMemory ();
        }
    }

ein solcher Aufruf (ganz am Ende) sparte bei mir am ein paar MB ein, dauerte aber viele Sekunden Bearbeitungszeit
(x-facher Aufruf vielleicht unnötig ),
mach das bloß nicht öfters im Programm, etwa in jedem Schleifendurchlauf

 

[Guest]

Danke SlaterB. Also liegts doch an der Verwendung von LinkedList. Das so viele Elemente im letzten Schritt entstehen ist halt zwangsläufig durch dei Rekursion gegeben, wir sollten das ja so machen. Ich dachte nur, ich hätte die Rekursion irgendwie ungünstig implementiert, aber so is ja alles i.O. Mit der Verwendung von reinen Arrays ist es definitiv performanter.

Das mit dem size()-Argument muss ich so machen, da von uns Java 1.4.2-Konfirmität verlangt wurde, daher auch keine generischen Typen etc. Thx nochmal für den Hinweis mit dem Speicherverbrauch. Gibts irgendwo ne Übersicht des konkreten Arbeitsspeicherverbrauchs jeder in Java nativ implementierter Datenstruktur?

 

[SlaterB]

List.add() ist sicherlich nicht Java 1.5, das gabs schon von Anfang an

---------------

Speicher: zur Not selber messen:
Speichergröße vorher auslesen, Objekte erzeugen und wieder Speicher auslesen


um Abweichungen/ Erstellung von Listen nebenbei auszugleichen evtl. 1000 Objekte auf einmal erstellen
und/ oder den Messvorgang mehrfach hintereinander durchführen

zum Messen des Speichers:

    private static final Runtime s_runtime = Runtime.getRuntime ();
    private static long memory;

    public static long totalMemory () {
    	return s_runtime.totalMemory ();
    }

    public static long usedMemory () {
        return s_runtime.totalMemory () - s_runtime.freeMemory ();
    }

    public static void initMemory () {
        memory = usedMemory();
    }

    public static long aktMemory() {
        return usedMemory() - memory;
    }