Java Permutationen zu rechenintensiv

[Duardo]

Hallo, ich habe mein Programm, in denen Permutationen durchgeführt werden, abgeschlossen. Nun stehe ich vor einem Problem, nämlich probierte ich das Programm immer auf einem Windows 7 Notebook mit 8GB RAM aus. Jetzt soll dieses Programm auf einem Windows Vista Notebook mit 4GB RAM laufen. Wenn man zum Beispie eine Kombination der Größe 18 hat und man in der JComboBox 6 angibt, scheitert es an einem heap size error. Gibt es irgendwelche Möglichkeiten dies zu lösen, außer die Heap size bei Java zu erhöhen? Oder hilft hier vielleicht Multithreading?Hier mein Code:

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Vector;

import javax.swing.DefaultComboBoxModel;
import javax.swing.JButton;
import javax.swing.JComboBox;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.ScrollPaneConstants;

public class test extends JFrame implements ActionListener {
  
    private JPanel panel;
    private JButton ok;
    private JTextArea text;
    private JComboBox<Integer> drop;
    private DefaultComboBoxModel<Integer> model;
    private Vector<Integer> zahlen;
    private String str;
    private int zahlKombi;
    private JScrollPane scroll;
  
    public test() {  
        panel = new JPanel();
        drop = new JComboBox<Integer>();
        ok = new JButton("OK");
        ok.addActionListener(this);
        str = ("1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, ");
        text = new JTextArea(str, 16, 16);
        text.setEditable(true);  
        scroll = new JScrollPane(text);
        scroll.setVerticalScrollBarPolicy(ScrollPaneConstants.VERTICAL_SCROLLBAR_AS_NEEDED);
      
        zahlen = new Vector<Integer>();
        int i = 0;
        for (i=3; i<11; i++) {
            zahlen.add(i); }
      
        model = new DefaultComboBoxModel<Integer>(zahlen);
        drop.setModel(model);
  
        panel.add(scroll);
        panel.add(ok);
        panel.add(drop);
        add(panel);  
      
        pack();
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(true);
    }

    public static void main(String[] args) {
        new test();
    }
  
    //-----------------------------------------------------------------------------------
    public void permute(java.util.List<Integer> intList, int k, int max) {
          if(k == max) {
            text.append(Arrays.toString(intList.subList(0, max).toArray()).replaceAll( "\\[|\\]", "") + ", \n");
          } else {
            for(int i = k; i < intList.size(); i++){
              java.util.Collections.swap(intList, i, k);
              permute(intList, k+1, max);
              java.util.Collections.swap(intList, k, i);
            }
          }
    }


    //-----------------------------------------------------------------------------------
  
    @Override
    public void actionPerformed(ActionEvent arg0) {
        zahlKombi = (int)drop.getSelectedItem();
        String a = text.getText();  
        text.setText("");
  
        String[] zahlenstring = a.split(", ");
        int[] zahlenint = new int[zahlenstring.length];
      
        for(int i = 0; i < zahlenstring.length ;i++) {
            zahlenint[i] = Integer.parseInt(zahlenstring[i]); }
      
        ArrayList<Integer> intList = new ArrayList<Integer>();
        for (int i = 0; i < zahlenint.length; i++) {
            intList.add(zahlenint[i]); }

        permute(intList, 0, zahlKombi);
    }
}

Bei Unklarheiten nachfragen. Schonmal danke im voraus.

 

[JStein52]

Multithreading hilft da gar nix weil ja alle Threads in der gleichen JVM laufen. Da hilft wohl nur der JVM mehr Speicher zu geben. Wobei ich jetzt nicht "nachgerechnet" habe wieviel du brauchst. Wobei es aber komisch ist dass es auf dem einen Rechner geht, die defaultgrösse für den JVM-Speicher sollte doch auf beiden gleich sein, egal wieviel physikalisches Memory drinsteckt.

 

[JStein52]

Hallo,
ich habe das jetzt mal bei mir (Win7, 32 Bit, Dual-Core, 4 GByte physikalischer Speicher) ausgeführt und beobachtet.
Deine permute()-Methode wird ja ziemlich schnell sehr oft ausgeführt. Ich habe z.B. immer mit den Werten:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 im Textfeld getestet und die Zahl neben dem Button erhöht. Ist diese Zahl dann z.B. 10 wir deine permute ja 9,8 Mio. mal aufgerufen. Soweit kam ich aber nur wenn ich der JVM auch 1,5 GByte Speicher gegeben habe (-mx ) Dabei ist mir dann aufgefallen dass dieser Wert auch nicht bei mehreren Versuchen exakt reproduzierbar ist sondern es kann bei gleichen Werten passieren dass er nach 7 Mio. Aufrufen die outOfMemory-Exception schmeisst. Ich vermute mal, dass die Java-Objekte die du in der permute() direkt oder indirekt anlegst vom GarbageCollector manchmal nicht schnell genug wieder aufgeräumt werden und es dann eben schon früher zum Crash kommt. Ich kenne dazu aber das MemoryManagement der JVM nicht gut genug um da was sagen zu können. Und auch deinen Algorithmus habe ich mir noch nicht angeschaut, kann also nicht sagen ob man da etwas speicherschonender programmieren könnte.

Edit: mir war aufgefallen dass er die Exception immer in javax.swing.text schmeisst. Ich habe dann mal in deiner permute() den Aufruf "text.append( ... ) auskommentiert. Jetzt kommt zwar keine Ausgabe mehr in dem Textfeld aber der Speicherverbrauch ist ziemlich stabil bei 0 !!! Also ist diese Zeile der Übeltäter.

 

[Duardo]

@JStein52 Da hast du vollkommen recht, nur irgendwie muss ich ja an die Permutationen kommen. Ich hab eben versucht die Permutationen einfach mal in der Konsole auszugeben, dies klappt, leider nur wenn die Konsole begrenzt wird.

 

[JStein52]

Ja, ist klar, aber vielleicht kannst du mal ein bisschen rumprobieren, zum Beispiel dir in permute() eine Liste von int's aufzubauen und die am Ende erst in dein Textfeld zu schreiben. Vielleicht ist das weniger speicherintensiv. Wären jedenfalls keine String-Operationen. Die sind mir in so rauhen Mengen immer suspekt.

 

[Thallius]

text.append(Arrays.toString(intList.subList(0, max).toArray()).replaceAll("\\[|\\]", "")+", \n");

So etwas im innersten einer rekursiven Methode, dass muss ja scheitern.

Gruß

Claus

 

[JStein52]

Die Rekursion war nicht das Problem, die Tiefe ist in der Grössenordnung 10-20. Aber die Aufrufe in der Schleife führten zu einigen zig-Millionen Aufrufen von permute().