Out of Memory (Java Heap Space)

[torben]

Hallo java-forum,

ich habe ein kleines Programm geschrieben, dass mir alle möglichen Permutationen einer Liste von Strings erzeugt, wenn ein neuer Buchstabe hinzukommt.

        LinkedList<String> pl =new LinkedList<String>();
        pl.add("0");
        pl=HelpClass.permutate(pl, '1');
        pl=HelpClass.permutate(pl, '2');
        pl=HelpClass.permutate(pl, '3');
        pl=HelpClass.permutate(pl, '4');
        pl=HelpClass.permutate(pl, '5');
        pl=HelpClass.permutate(pl, '6');
        pl=HelpClass.permutate(pl, '7');
        pl=HelpClass.permutate(pl, '8');
        pl=HelpClass.permutate(pl, '9');

Nach dem ersten Aufruf, sollte die Liste also folgende Einträge haben [01,10]. Nach dem zweiten Aufruf [201, 021, 012, 210, 120, 102].

    public static LinkedList<String> permutate (LinkedList<String> ref, char x){
        LinkedList<String> neu = new LinkedList<String>();
        int i, j,c=0;
        String s,s2;
        for (i=0; i<ref.size(); i++){
            s=ref.get(i);
            for (j=0; j<=s.length(); j++){
                if (j==0)
                    s2=x+s;
                else{
                    s2=s.substring(0,j)+x+s.substring(j); 
                }
                c++;
                neu.add(s2);
            }
        }
        System.out.println("c= "+c);
        return neu;
    }

Die Anzahl der Permutationen wächst in diesem Fall mit der Fakultät, d.h. nach dem letzten Aufruf sollte eine Liste mit 10!=3628800 Einträgen zurückgegeben werden. Genau bei diesem Durchgang erhalte ich aber folgenden Fehler:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:3209)
at java.lang.String.<init>(String.java:215)
at java.lang.StringBuilder.toString(StringBuilder.java:430)
at euler.HelpClass.permutate(HelpClass.java:46)

Der Fehler tritt also auf, wenn der String s2 aus den beiden substrings und dem char zusammengesetzt wird.
Benutze NetBeans 7.0.1 unter Mac OSX 10.6.8.

Erfolglose Versuche den Fehler zu beseitigen:
- Einsatz des Garbage Collector
- String s2 in jedem Durchlauf für j neu anlegen
- Vergrößerung der Heap Size in /Applications/NetBeans/NetBeans 7.0.app/Contents/Resources/NetBeans/bin/netbeans

Hat jemand von euch eine Idee was ich noch machen könnte? Langsam bin ich mit meinem Latein am Ende...

Schöne Grüße
torben

 

[Gast2]

Verwende statt den Strings lieber den StringBuilder.

 

[Marco01_809]

Java Programme bekommen standard afaik maximal 256 oder 128MB, mit den Param "-Xmx" kannst du den maximalen Heap erhöhen,
auf der Konsole z.B. mittels "java -Xmx2048M -jar program.jar", wo man in Netbeans diese Params eingibt weiß ich nicht, in Eclipse geht das problemlos mittels Run/Debug-Settings -> Arguments -> VM.

 

[SlaterB]

jeder String bis zu 100 Byte, damit muss man schon rechnen, gerade bei LinkedList wo für jeden Eintrag ein neues Objekt mit Referenzen usw. benötigt wird, also allein dafür 30 Bytes und mehr, String dann vielleicht nur 70,
bei 4 Mio. jedenfalls brauchst du 400 MB Speicher..,
dann läuft das Programm auch, allerdings arg langsam, hab nach paar Minuten bei 1.5 Mio. aufgehört

ArrayList lieft danach in 5 sec durch, brauchte 'nur' 250 MB 😉
allerdings zwischendurch bisschen mehr, solange die alte Liste parallel noch vorhanden ist

@Marco01_809
64 MB soweit ich weiß/ so ist es bei mir

 

[torben]

Java Programme bekommen standard afaik maximal 256 oder 128MB, mit den Param "-Xmx" kannst du den maximalen Heap erhöhen,
auf der Konsole z.B. mittels "java -Xmx2048M -jar program.jar", wo man in Netbeans diese Params eingibt weiß ich nicht, in Eclipse geht das problemlos mittels Run/Debug-Settings -> Arguments -> VM.

In NetBeans gehts so: Rechtsklick auf das verwendete Projekt -> Properties -> Run -> bei VM Options "-Xmx2048M" eingeben.

Vielen Dank für die Hilfe 🙂

@ SlaterB: Ja das Programm ist langsam, bei mir dauert es etwas mehr als 100 Sekunden. Bin für gute Ideen immer offen.

 

[SlaterB]

falls Teile von meinem Posting durch edits übersehen:
mit ArrayList rasend schnell

 

[torben]

Das habe ich tatsächlich überlesen, danke 🙂

 

[emailundlos]

so kannst du das machen:

    public static char[][] perumtationen(char[] ca) {
        char[][] resul = new char[(int) Math.pow(2, ca.length)][ca.length];
        for (int i = 0; i < resul.length; i++) {
            int j = 0;
            for (int k = 0; k < ca.length; k++) {
                if (((i >> k) & 1) == 1) {
                    resul[i][j++] = ca[k];
                }
            }
        }
        return resul;
    }

 

[Morinho]

Ich bedanke mich für alle Bemühungen aber ich habe selbst eine Lösung gefunden 🙂

 

[Joose]

Hast du dich im Thread geirrt oder warum grabst du so einen alten aus?