Java Permutationen zu rechenintensiv

Duardo

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

Java:
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.
 
Zuletzt bearbeitet von einem Moderator:

JStein52

Top Contributor
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

Top Contributor
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.
 
Zuletzt bearbeitet:

Duardo

Mitglied
@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

Top Contributor
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

Top Contributor
Code:
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

Top Contributor
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().
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Java Permutationen werden zu lange berechnet Allgemeine Java-Themen 3
D Hat Java eine Library um JavaScript auszuwerten? Allgemeine Java-Themen 2
Zrebna Wieso sind eigentlich JUnit-Tests in src/test/java platziert - nur Konvention? Allgemeine Java-Themen 7
N LlaMA, KI, java-llama.cpp Allgemeine Java-Themen 39
V Java-Codierungsherausforderung: Navigieren durch die Macken der Datumsmanipulation Allgemeine Java-Themen 2
E Output Fehler (Java-Programm Kuchen) Allgemeine Java-Themen 11
M java: unexpected type Allgemeine Java-Themen 2
harrytut Java Input/Output Tests Junit Allgemeine Java-Themen 3
B Java Discord bot auf ein Root Server? Allgemeine Java-Themen 1
BetziTheRealOne Java PKIX path building failed as non Admin Allgemeine Java-Themen 15
D Linux, Java-Version wird nicht erkannt bzw. welche Einstellung fehlt noch? Allgemeine Java-Themen 19
KonradN Java 21 Release Allgemeine Java-Themen 5
V Umgang mit fehlenden Daten in einer Java-Datenanalyseanwendung Allgemeine Java-Themen 5
P Fehler: Hauptklasse Main konnte nicht gefunden oder geladen werden Ursache: java.lang.ClassNotFoundException: Main Allgemeine Java-Themen 24
K Java Anwendung machen Anleitung Allgemeine Java-Themen 5
G java.io.listFiles() Allgemeine Java-Themen 3
8u3631984 Frage zu Java Streams min / max Allgemeine Java-Themen 17
S Java Programm lässt sich vom USB-Stick starten, aber nicht von HDD Allgemeine Java-Themen 16
K Java-Projekt Allgemeine Java-Themen 11
K Java-Projekt Allgemeine Java-Themen 0
ruutaiokwu Welcher Browser unterstützt heutzutage noch Java Applets? Allgemeine Java-Themen 5
Jose05 Java-Klasse im extra cmd-Fenster ausführen Allgemeine Java-Themen 3
rode45e Java Threads Allgemeine Java-Themen 4
G java.io.listFiles() Allgemeine Java-Themen 2
N Java Dynamic Proxy Allgemeine Java-Themen 3
N Leichte Java Gegner Ki Allgemeine Java-Themen 10
A Java modul Problem Allgemeine Java-Themen 4
Thomasneuling Java Jar datei erstellen, von Projekt, dass auch Javafx Dateien, FXML Dateien und CSS Dateien, sowie Bilder enthält? Allgemeine Java-Themen 14
V Funktionale Schnittstelle in Java Allgemeine Java-Themen 3
OnDemand Java String in Hashmap als Key NULL Allgemeine Java-Themen 27
urmelausdemeis Exception in thread "main" java.lang.Error: Unresolved compilation problem: Allgemeine Java-Themen 7
berserkerdq2 Wenn ich bei Intelij javafx mit maven importieren will, muss ich das in die pom.xml reintun, aber warum noch in module-info.java? Allgemeine Java-Themen 3
KonradN Java 20 am 21. März Allgemeine Java-Themen 1
O Java Website Stock Bot Allgemeine Java-Themen 3
J Front-/Backend in Java Allgemeine Java-Themen 14
doopexxx JAVA Google Webcrawler Allgemeine Java-Themen 1
J JavaScript innerhalb eines Java Projekts ausführen Allgemeine Java-Themen 2
A Java Programm erstellen hilfe Allgemeine Java-Themen 10
G java.lang.NoClassDefFoundError: org/aspectj/lang/Signature Allgemeine Java-Themen 2
lalex1491 Java Aktienkurse nachfragen Allgemeine Java-Themen 4
J Class to link Java Allgemeine Java-Themen 4
V Wie funktioniert das Schlüsselwort "final" von Java? Allgemeine Java-Themen 19
mrStudent Inferenz JAVA Allgemeine Java-Themen 6
U URI Rechner (Java Script) Allgemeine Java-Themen 7
TheSkyRider Java Geburtsdatum Textfeld Allgemeine Java-Themen 7
mihe7 Java 19 JavaDocs: Browserintegration Allgemeine Java-Themen 0
Encera Gleichzeitiges Ausführen und verbinden von 2 Java-Klassen über die Eingabeaufforderung und Eclipse Allgemeine Java-Themen 21
H Java Rechner Programmierung der Mathematik Allgemeine Java-Themen 33
Lennox Schinkel Java Kara Auf einen Java Host laufen lassen Allgemeine Java-Themen 17
C Fußnoten von DocX mit Java Allgemeine Java-Themen 2
C Fußnoten in DocX mit Java Allgemeine Java-Themen 1
M Aussagenlogik in Java Programmieren Allgemeine Java-Themen 22
B Per Java Word Dokument schreiben? Allgemeine Java-Themen 8
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
KonradN Oracle übergibt (Java Teile der) GraalVM Community Edition an OpenJDK Community Allgemeine Java-Themen 2
Momo16 Brauche Hilfe - Java Projekt kann nicht erstellt werden Allgemeine Java-Themen 12
B Java mit command line und jars benutzen? Allgemeine Java-Themen 18
M Java Überprüfen ob .exe-Datei bereits ausgeführt wird Allgemeine Java-Themen 2
B HTTP Allgemeine Fragen über Suchmaschine nutzen mit Java Allgemeine Java-Themen 20
Mick P. F. Wie kriege ich die Fehlermeldung "java: symbol lookup error: ..." weg? Allgemeine Java-Themen 11
K Nachhilfe Java Allgemeine Java-Themen 11
KonradN Java 19 Allgemeine Java-Themen 11
F IDEA IntelliJ Java Songliste erstellen Allgemeine Java-Themen 6
TheSepp Java bestimmtes Array auf den Wert 0 setzen Allgemeine Java-Themen 32
B Java Reflection Probleme beim wehcselseitigen Referenzieren zweier Klassen/Objekte Allgemeine Java-Themen 14
Sachinbhatt Sind alle Methoden in Java implizit virtuell Allgemeine Java-Themen 2
E Java und integrierte Grafikkarten Allgemeine Java-Themen 18
Sachinbhatt Wie wird die Typumwandlung bei Mehrfachvererbung in Java implementiert? Allgemeine Java-Themen 3
Peterw73 Hilfe bei Java gesucht Allgemeine Java-Themen 3
A Java unter Win 10 Allgemeine Java-Themen 1
B Woher kommen die Bildschirmkoordinaten beim java Robot? Allgemeine Java-Themen 14
P9cman java.Lang Klassen fehlen in JRE System Library Allgemeine Java-Themen 1
T Java Robot Class - Bot Allgemeine Java-Themen 3
E Wie Java Heap Space vergrößern? Allgemeine Java-Themen 3
B Java Programm auf virutellem Desktop laufen lassen? Allgemeine Java-Themen 1
D VBA Code mit Java ausführen möglich? Allgemeine Java-Themen 10
berserkerdq2 Threads, wie genau läuft das in Java ab? (Ich kann Threads erstellen und nutzen, nur das Verständnis) Allgemeine Java-Themen 6
izoards Java Home Pfad unabhängig von der Version Allgemeine Java-Themen 7
N JAVA-Code mit Grafikfenster zeichnet in Windows, aber nicht Mac. Allgemeine Java-Themen 4
L Java überprüfen lassen, ob sich ein gegebener Pfad / das Programm an sich auf einer CD oder Festplatte befindet Allgemeine Java-Themen 14
KonradN CVE-2022-21449: Fehler in Java bei Signaturprüfung Allgemeine Java-Themen 20
berserkerdq2 Java sql Allgemeine Java-Themen 15
JordenJost Unverständlicher Java code? Allgemeine Java-Themen 21
LimDul XSD To Java - Überschreiben von Assoziationen Allgemeine Java-Themen 1
Aartiyadav Comparisons and Swapa in Bubble-sort Java Allgemeine Java-Themen 6
KonradN Java 18 Allgemeine Java-Themen 8
N Statistische Auswertung von Logfiles (Einlesen, auswerten und grafische Aufbereitung von logfiles) mit Java Allgemeine Java-Themen 9
ME2002 Fragen aus einer Java Klausur Allgemeine Java-Themen 67
Z Mit Java 8+ Streams Zeilen nummern zu Zeilen hinzufügen Allgemeine Java-Themen 17
M Verständnisfrage java.util.TimerTask Allgemeine Java-Themen 2
V Hilfe mit Java Code Allgemeine Java-Themen 4
S Processing Java Code verstehen Allgemeine Java-Themen 4
O Newton Algorithmus Java Allgemeine Java-Themen 1
P Java Quellen finden Allgemeine Java-Themen 3
M Java Analyse/ SWOT-Analyse Allgemeine Java-Themen 13
J c Programm läuft nicht in compilierter Version des Java Projektes Allgemeine Java-Themen 7
Atten007 Java-Klasse auf macOS entpacken? Allgemeine Java-Themen 2
E java mithilfe url .jar datei öffnen Allgemeine Java-Themen 9
M Warum hat Java dieses und jenes nicht... Allgemeine Java-Themen 8
E Java .exe Datei mit args starten Allgemeine Java-Themen 2

Ähnliche Java Themen

Neue Themen


Oben