[Java] Viele Vergleiche beschleunigen

Werbeanzeige

Affje

Treue Seele

Beiträge: 89

Beruf: Student

03.01.2012, 08:42

[Java] Viele Vergleiche beschleunigen

Hallo,

ich programmiere derzeit gerade an einem Mastermind-Spiel herum. Das Spiel ansich ist eigentlich fertig, nur eine Zusatzfunktion bereitet mir noch etwas Probleme. Ich möchte anfangs alle möglichen Farbkombinationen bei Spielstart erstellen und während dem Spiel dann nach jedem Tipp Kombinationen anhand vorheriger Tipps ausschließen.

Bei einfachem Schwieirgkeitsgrad (4 Pins und 6 Farben) sind es 6^4 = 1296 Möglichkeiten. Die Liste wird in knapp 4ms erstellt und das Streichen geht ebenfalls so schnell.

Beim mittleren Schwierigkeitsgrad (6 Pins und 8 Farben) sind es 8^6 = 262.144 Möglichkeiten. Die Liste wird je nach Rechner in 400-3000ms Sekunden erstellt, was auch noch in Ordnung ist. Das eigentliche Problem ist, dass ich beim ersten Durchgehen der Liste ja alle ~263k Möglichkeiten überprüfen muss, was selbst bei meinem Rechner knapp 20 Sekunden dauert.

Hier ist erstmal der Code:

Quellcode

     /**
     * Entfernt alle nicht konsistenten Codes aus der Liste
     * @param last Der zu vergleichende Tipp
     * @param blacks Anzahl schwarzer Pins
     * @param whites Anzahl weißer Pins
     */
    private void removeWrongCodes(final Guess last, final int blacks, final int whites)
    {
        Thread thread = new Thread()
        {
            @Override
            public void run() 
            {
                long start = Calendar.getInstance().getTimeInMillis();
                CompareResult comparison = null;
                for (Guess temp : possibilities)
                {
                    comparison = new CompareResult(temp, last.ReturnGuessAsResult());
                    if (comparison.Blacks() == blacks && comparison.Whites() == whites)
                    {
                        remaining.add(temp);
                    }
                    comparison = null;
                }
                possibilities.retainAll(remaining);
                remaining.clear();
                long end = Calendar.getInstance().getTimeInMillis();
                System.out.println((end - start) + " ms - new Size: " + possibilities.size());   
            };    
        };
        thread.start();
    }

Ein Guess-Objekt besteht aus einem int[], indem die Farbcodes dementsprechend als Integer gespeichert werden. Die CompareResult-Klasse ist für den Vergleich von zwei Guess-Objekten zuständig, ebenfalls mit 2 for-Schleifen (eine für schwarze, eine für weiße Pins, da kann man nichts optimieren glaub ich).

Ich habe schon versucht alle Farbcodes als Byte statt als Integer zu speichern, aber am Ergebnis hat das leider nichts geändert. Gibt es eine Möglichkeit, das zu beschleunigen? 20 Sekunden sind einfach zu viel

MfG

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

03.01.2012, 09:05

Also ich weiß ja nicht, wie gut der Java Compiler und die VM mittlerweile optimiert, aber ohne optimierung ist es ziemlich tödlich, aber das erstellen neuer Objekte könnte einen nicht unerheblichen Zeitaufwand bedeuten. Es muss eventuell eine leere Stelle im Speicher gefunden werden, das Objekt wird initialisiert und alle paar Durchläufe muss der Garbage Collector wieder aufräumen. Ich habe gehört, dass mittlerweile recht gut optimiert wird, aber vielleicht wäre es ja einen Versuch wert.

Dann gibt es vielleicht auch die Möglichkeit, Elemente aus dem Guess Container zu löschen, während du über ihn iterierst. retainAll muss im unsortierten Fall jedes Objekt von remaining suchen, was irgendwie der Laufzeit von n*log(n) (für jedes Objekt eine Suche) entspricht. Wenn CompareResult nicht vollkommen verrückte Dinge macht, könnte dass die Laufzeit mehr als halbieren.

Aber Java zu optimieren, hört sich auch irgendwie schon komisch an. Rein von Prinzip her, könnte die selbe Implementierung in C++ locker 20 mal schneller laufen (weil es wirklcih sehr low Level ist), aber da weiß ich wieder nicht genau, wie viel Optimiert wird - im Hintergrund passieren da viele Komplexe Dinge.

Wenn das nichts hilft, wirst du wohl einen neuen Algorithmus und vermutlich eine neue Datenstruktur brauchen. Das effizient zu berechnen ist sicherlich ein sehr interessantes Problem.

Aber versuch erstmal, das retainAll los zu werden.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

Affje

Treue Seele

Beiträge: 89

Beruf: Student

03.01.2012, 09:57

Zitat von »Jonathan_Klein«

Also ich weiß ja nicht, wie gut der Java Compiler und die VM mittlerweile optimiert, aber ohne optimierung ist es ziemlich tödlich, aber das erstellen neuer Objekte könnte einen nicht unerheblichen Zeitaufwand bedeuten. Es muss eventuell eine leere Stelle im Speicher gefunden werden, das Objekt wird initialisiert und alle paar Durchläufe muss der Garbage Collector wieder aufräumen. Ich habe gehört, dass mittlerweile recht gut optimiert wird, aber vielleicht wäre es ja einen Versuch wert.

Dann gibt es vielleicht auch die Möglichkeit, Elemente aus dem Guess Container zu löschen, während du über ihn iterierst. retainAll muss im unsortierten Fall jedes Objekt von remaining suchen, was irgendwie der Laufzeit von n*log(n) (für jedes Objekt eine Suche) entspricht. Wenn CompareResult nicht vollkommen verrückte Dinge macht, könnte dass die Laufzeit mehr als halbieren.

Aber Java zu optimieren, hört sich auch irgendwie schon komisch an. Rein von Prinzip her, könnte die selbe Implementierung in C++ locker 20 mal schneller laufen (weil es wirklcih sehr low Level ist), aber da weiß ich wieder nicht genau, wie viel Optimiert wird - im Hintergrund passieren da viele Komplexe Dinge.

Wenn das nichts hilft, wirst du wohl einen neuen Algorithmus und vermutlich eine neue Datenstruktur brauchen. Das effizient zu berechnen ist sicherlich ein sehr interessantes Problem.

Aber versuch erstmal, das retainAll los zu werden.

Okay, dann werde ich mich mal daran setzen. Wichtig ist mir nicht, wie (umständlich) man es machen muss, sondern dass man es generell lösen kann, dass es in fast nicht messbarer Zeit abläuft.

MfG

Zum Seitenanfang

Saik0

Treue Seele

Beiträge: 171

Beruf: Anwendungsentwickler

03.01.2012, 10:03

Mh ich kenne jetzt den Guess Container nicht aber wenn du für deine Objekte eine Liste brauchst und etwas mehr Performance raus holen willst, kannst du auch eine LinkedList verwenden. Hier ein Beispiel: klick

Zum Seitenanfang

Affje

Treue Seele

Beiträge: 89

Beruf: Student

03.01.2012, 10:12

Danke euch. Alleine durch das retainAll() ist es jetzt von über 20 Sekunden auf knapp 900ms gesunken....

Die LinkedList werde ich mir auch mal anschauen.

Edit: Der Wechsel zur LinkedList hat die Zeit auf fast 90 Sekunden gedrückt.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Affje« (03.01.2012, 10:22)

Zum Seitenanfang

foreach

Frischling

Beiträge: 87

Beruf: Student

03.01.2012, 12:14

Versuche mal folgendes:

Java-Quelltext

 // Verwende die Klasse HashSet statt einer Liste

import java.util.Arrays;

class Guess {
    private int array[];

    // ...

    public int hashCode() {
        return Arrays.hashCode(array);
    }

    // keine CompareResult-Klasse sondern hier vergleichen
    public boolean equals(Object o) {
        if(! o instanceof Guess)
            return false;
        return Arrays.equals(array, ((Guess)o).array);
    }

}

Zitat von »Jonathan_Klein«

Aber Java zu optimieren, hört sich auch irgendwie schon komisch an. Rein von Prinzip her, könnte die selbe Implementierung in C++ locker 20 mal schneller laufen (weil es wirklcih sehr low Level ist), aber da weiß ich wieder nicht genau, wie viel Optimiert wird - im Hintergrund passieren da viele Komplexe Dinge.

Den C/C++ Kompiler möchte ich mal sehen der so viel Performance herausholen kann. Vorallem wenn man viele kleine Objekte anlegt, und schnell wieder wegwirft,
ist java häufig wesentlich effizienter als wenn man das gleiche mit malloc() und free() machen würde.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »foreach« (03.01.2012, 12:31)

Zum Seitenanfang

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

03.01.2012, 12:27

Ich weiß nicht genau, wie Du vergleichst, Affje, aber 200.000 Vergleiche sollten in einem Augenzwinkern erledigt sein.

Mal ganz anders gefragt: Wozu willst Du ÜBERHAUPT beim Spielstart alle möglichen Kombinationen erstellen? Wofür soll das gut sein?

Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Zum Seitenanfang

Powerpaule

Treue Seele

Beiträge: 162

Wohnort: Berlin

Beruf: Softwareentwickler

03.01.2012, 12:39

Zitat von »foreach«

Zitat von »Jonathan_Klein«

Aber Java zu optimieren, hört sich auch irgendwie schon komisch an. Rein von Prinzip her, könnte die selbe Implementierung in C++ locker 20 mal schneller laufen (weil es wirklcih sehr low Level ist), aber da weiß ich wieder nicht genau, wie viel Optimiert wird - im Hintergrund passieren da viele Komplexe Dinge.

Den C/C++ Kompiler möchte ich mal sehen der so viel Performance herausholen kann. Vorallem wenn man viele kleine Objekte anlegt, und schnell wieder wegwirft,
ist java häufig wesentlich effizienter als wenn man das gleiche mit malloc() und free() machen würde.

Na ja, aber in C++ würde man dann solche Objekte ja eher auf dem Stack erzeugen, was deulich schneller ist als auf dem Heap bzw. als bei Java mit new.
Ansonsten stimme ich dir aber zu, dass man niemals mit C++ so viel herausholen könnte. Bei simplen Dingen wie Schleifen und ein paar einfachen Berechnungen ist Java annähernd gleichschnell wie C++, und selbst bei komplexeren Sachen habe ich in verschiedenen Tests maximal ein Zeitverhältnis von 1:3 feststellen können. Was natürlich C++ bei zeitkritischeren Sachen auf jeden Fall den Vorzug gibt, aber in der Regel unherblich ist, solange man am Algorithmus verbessern kann.

Zum Seitenanfang

foreach

Frischling

Beiträge: 87

Beruf: Student

03.01.2012, 12:50

Zitat von »Powerpaule«

Na ja, aber in C++ würde man dann solche Objekte ja eher auf dem Stack erzeugen, was deulich schneller ist als auf dem Heap bzw. als bei Java mit new.

Java sorgt dafür wenn es angebracht ist, dass auch Objekte die mit new erzeugt wurden auf dem Stack angelegt werden. Stichwort "Escape analysis". Siehe dazu hier.

Zum Seitenanfang

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

03.01.2012, 13:03

Ich find die Stelle nicht mehr genau, aber ich meine, es wäre in diesem Podcast gewesen:
http://cre.fm/cre090
Da ging es irgendwie um den Geschwindigkeitsunterschied für so quasi atomare Befehle in Programmiersprachen. Je komplexer die Befehle sind, desto weniger fällt das natürlich ins Gewicht, aber ich meine schon, dass der Faktor 1:20 ungefähr hinkam. Aber ist natürlich auch schon ein paar Jahre her.

Lieber dumm fragen, als dumm bleiben!

Zum Seitenanfang

Werbeanzeige

spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

[Java] Viele Vergleiche beschleunigen

[Java] Viele Vergleiche beschleunigen

Quellcode

Zitat von »Jonathan_Klein«

Java-Quelltext

Zitat von »Jonathan_Klein«

Zitat von »foreach«

Zitat von »Jonathan_Klein«

Zitat von »Powerpaule«

Ähnliche Themen