Flashcenhals im Programm
-
Hallo mal heute eine sportliche Frage .
Ich habe ein TicTacToe vor zu programmieren und will mir alle möglichen Endzustände berechnen lassen. Allerdings dauert das fast 3 Minuten. Ich habe eigenlich einen ziemlich schnellen Recher ( 3 Kerne) . Da es nur 9! Möglichkeiten gibt sind 3 Minuten echt lang. Vielleicht seht ihr noch einige Möglichekeiten die Performance hcochzuschrauben. Hier also meine Klassen :
PlayingFieldimport java.awt.Point; import java.beans.FeatureDescriptor; import java.util.ArrayList; import java.util.Vector; class PlayingField implements Cloneable{ /** * Ruft den Konstruktor auf um den das Spielfel */ public PlayingField(){ this(PLAYER1); } /** * Initialisiert das Spielfeld mit default Daten * Initialisiert den aktiven Spieler * @params player : aktiver Spieler */ public PlayingField(int player){ initField(); initActivePlayer(player); } /** * Liefert den Wert eines Feldes zurück @params x : x Koordinate des Feldes @params y : y Koordinate des Feldes @return Wert an der Stelle x, y */ public int getFieldValue(int x, int y){ return field[x][y]; } /** * Beschreibt den Wert eines Feldes mit der aktuellen Spielfarbe * @params x : x Koordinate des Feldes * @params y : y Koordinate des Feldes * @return true bei Erfolg , false bei einem Fehler */ public boolean setFieldValue(int x, int y){ if (field[x][y] != DEFAULTVALUE){ return false; } else{ field[x][y] = activePlayer; // Add field to history History.add(new Point(x,y)); return true; } } /** * Liefert den Gewinner des Spiels * @return PLAYER1 oder PLAYER2 bei einem Sieg * @return NOWINNER bei einem Unentschieden * @return NOTFINISHED wenn das Spiel noch nicht beendet ist. */ public int getWinner(){ for (int x = 0; x < 3; x++){ if ((getFieldValue(x,0) == getFieldValue(x,1)) && (getFieldValue(x,0) == getFieldValue(x,2)) && (getFieldValue(x,0) != DEFAULTVALUE)){ return getFieldValue(x,0); } } for (int y = 0; y < 3; y++){ if ((getFieldValue(0,y) == getFieldValue(1,y)) && (getFieldValue(0,y) == getFieldValue(2,y)) && (getFieldValue(0,y) != DEFAULTVALUE)){ return getFieldValue(0,y); } } if ((getFieldValue(0,2) == getFieldValue(1,2)) && (getFieldValue(0,2) == getFieldValue(2,2)) && (getFieldValue(0,2) != DEFAULTVALUE)){ return getFieldValue(0,2); } if ((getFieldValue(0,0) == getFieldValue(1,1)) && (getFieldValue(0,0) == getFieldValue(2,2)) && (getFieldValue(0,0) != DEFAULTVALUE)){ return getFieldValue(0,0); } if (History.size() == 9) return NOWINNER; return NOTFINISHED; } /** * Erzeugt eine Kopie des Objecktes * @return eine neue Referenz zu dem Objekt */ public PlayingField clone(){ try{ PlayingField newField = (PlayingField) super.clone(); // Kopiere die Feldinhalte newField.field = new int[3][3]; for (int x = 0; x < 3; x++){ for (int y = 0; y < 3; y++){ field[x][y] = this.getFieldValue(x, x); } } // Kopiere die Historie newField.History = new Vector<Point>(); for (int i = 0; i < History.size(); i++){ newField.History.add(this.History.get(i)); } return newField; }catch(CloneNotSupportedException e){ } return null; } /** * Initialisert den aktiven Spieler * @param player aktiver Spieler */ private void initActivePlayer(int player){ // Init active player with player activePlayer = player; } /** * Initialisiert das Spielfeld mit default Werten */ private void initField(){ // Init Field with default values for (int x = 0; x < 3; x++){ for (int y = 0; y < 3; y++){ field[x][y] = DEFAULTVALUE; } } } // Public Constants public static final int DEFAULTVALUE = 0; public static final int PLAYER1 = 1; public static final int PLAYER2 = 2; public static final int NOWINNER = 3; public static final int NOTFINISHED = 4; public static final int FINISHED = 5; // Private Variables private int[][] field = new int[3][3]; private int activePlayer = DEFAULTVALUE; private Vector<Point> History = new Vector<Point>(); }ExpandField
import java.awt.Point; import java.util.Vector; class ExpandField { public ExpandField(PlayingField field) { Queue.add(field); while (Queue.size() > 0){ ExpandNode(Queue.get(0)); Queue.remove(0); } } public void ExpandNode(PlayingField field){ Point nextField = new Point(UNDEFINED,UNDEFINED); do{ nextField = getNextField(nextField); if (nextField.x != UNDEFINED){ if (field.getFieldValue(nextField.x, nextField.y) == PlayingField.DEFAULTVALUE){ PlayingField newField = field.clone(); newField.setFieldValue(nextField.x, nextField.y); if (newField.getWinner() == PlayingField.NOTFINISHED){ Queue.add(newField); }else{ ResultQueue.add(newField); } } } }while (nextField.x != UNDEFINED); } private Point getNextField(Point start){ if ((start.x == UNDEFINED) && (start.y == UNDEFINED)){ return new Point(0,0); } if ((start.x == 0) && (start.y == 0)){ return new Point(0, 1); } if ((start.x == 0) && (start.y == 1)){ return new Point(0, 2); } if ((start.x == 0) && (start.y == 2)){ return new Point(1, 0); } if ((start.x == 1) && (start.y == 0)){ return new Point(1, 1); } if ((start.x == 1) && (start.y == 1)){ return new Point(1, 2); } if ((start.x == 1) && (start.y == 2)){ return new Point(2, 0); } if ((start.x == 2) && (start.y == 0)){ return new Point(2, 1); } if ((start.x == 2) && (start.y == 1)){ return new Point(2, 2); } if ((start.x == 2) && (start.y == 2)){ return new Point(UNDEFINED,UNDEFINED); } return new Point(UNDEFINED,UNDEFINED); } private final static int UNDEFINED = -1; public static Vector<PlayingField> Queue = new Vector<PlayingField>(); public static Vector<PlayingField> ResultQueue = new Vector<PlayingField>(); }Zu guter letzt die Applicaction:
public class Application { /** * @param args * @throws InterruptedException */ public static void main(String[] args) throws InterruptedException { long zeit1 = 0, zeit2 = 0; zeit1 = System.nanoTime(); PlayingField playingField = new PlayingField(); zeit2 = System.nanoTime(); System.out.println("Init : " + (zeit2 - zeit1) / 1000000 + " Sekunde"); zeit1 = System.nanoTime(); playingField.setFieldValue(2,2); zeit2 = System.nanoTime(); System.out.println("Werte schreiben : " + (zeit2 - zeit1) / 1000000 + " Sekunde"); zeit1 = System.nanoTime(); playingField.getWinner(); zeit2 = System.nanoTime(); System.out.println("Gewinner : " + (zeit2 - zeit1) / 1000000 + " Sekunde"); zeit1 = System.nanoTime(); playingField.clone(); zeit2 = System.nanoTime(); System.out.println("Clone : " + (zeit2 - zeit1) / 1000000 + " Sekunde"); zeit1 = System.nanoTime(); ExpandField expandField = new ExpandField(playingField); zeit2 = System.nanoTime(); System.out.println(" Expand Field : " + (zeit2 - zeit1) / 1000000 + " Sekunde"); } }Vielen Dank
-
Hi,
1. ist es meiner Meinung nach üblich die Variablendefinitionen am Anfang zu schreiben
2. getNextField() - lässt sich schöner/schneller LÖsen, wenn du einfach y++ machst und bei y = 3 x erhöst
3. getWinner() - teste doch nur alle Möglichkeiten, die es vom letzten gesetzten Stein aus gibtIch krieg beim testen leider eine Exception:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap spaceDas macht es mir unmöglich zu testen^^
-
Danke für deine Ratschläge, ja das mit der Exception habe ich auch schon gesehen.Komisch weiß nicht was meine letzten Änderungen waren. Naja muss noch mal reinsehen.
Was ich nicht verstehe ist das mit der Variablendklaration was meinst du damit genau ?Und : getWinner() muss doch immer alle Möglichkeiten abtesten. Ich wüsste nicht wie es anders gehen soll
-
ja habs gefunden. den heapspace kann man mit -Xmx?m auf ? mb anheben(weißt du zufällig wieviel du eingestellt hast?)
und wenn ich deinen Code richtig verstehe, sieht dein Code so aus:
nimm Spielfeld suche nächstes freies Feld setzte Spielstein prüfe alle reihen/spalten/diagonalen auf 3 gleicheBei dem Prüfen testest du jedesmal 3 spalten, 3 Zeilen, 2 Diagonalen => 8 Tests
Allerdings kann man, wenn man z.b. links oben gestzt hat, ja nur durch die obere Zeile, linke Spalte oder die eine Diagonale gewinnen => 3 Tests
Außerdem ist es denke ich schneller zu prüfen, ob alle 3 Steine mit der zahl des letzten spielers übereinstimmen, denn momentan rufst du bei jedem Test 4 mal getFieldValue() auf. 3 mal dürfte reichenThema variablendeklaration:
Du schreibst(schematisch)class a { void f1() {} void f2() {} int a; int b; }Meiner Meinung nach üblich ist:
class a { int a; int b; void f1() {} void f2() {} }Aber das ist nicht geschwindigkeitsrelevant
-
Oh cool
Aber macht das wirklich so viel aus. Viel schnell läuft es beid dir
-
Bei mir läuft es noch gar nicht, weil ich noch nicht genügend speicher zur verfügung gestellt habe. Aber es dauert definitiv viel länger als 3 Minuten.
Ich denke du berechnest etwas viel und vor allem das ständige Klonen kostet Zeit. Aber genauer ahbe ich das noch nicht untersucht^^
-
Danke für deine Antwort
Aber das Klonen ist doch notwendig oder gibt des da eine Möglichkeit
-
Hast du deinen Code schon mal mit einem Profiler untersucht?
-
26 Sekunden!
Wie konnte das bei dir laufen? Ich bin in einer Endloschleifen geraten xD
Beim clonen suchst du den Wert von (x, x)
(wenn es imemr noch nicht geht, hab ich irgendwo noch was entscheidendes geändert, was ich aber geradenicht mehr finde)
Schreib dann einfach nochmal. Ich werde heute abend meinen Quellcode posten(muss jetzt weg)
-
Ich muss jetzt leider auch weg und werde vor so nicht zum testen kommne, erst mal allen vielen dank.
ich habe leider bisher noch nie mit profilern gearbeitet. nutze als entwicklungumgebung eclipser
-
Poste bitte mal deinen Code. Bei mir geht es leider nicht
-
Kannst du mir die Anzahl der Elemente in der Result Queue anzeigen lassen. Wie viele sind es bei dir ?
Habe den Fehler gefunden aber bei mir sind es 1786 aber das ist nicht richtig
-
2754 (wieviele sollen es denn sein?)
Application.java(ich hab die files etwas gekürtz(Kommentare etc.), damit ich einen besseren Überblick habe^^)
import java.awt.Point; public class Application { public static void main(String[] args) throws InterruptedException { long zeit1 = 0, zeit2 = 0; PlayingField playingField = new PlayingField(); playingField.setFieldValue(2,2); playingField.getWinner(); playingField.clone(); ExpandField expandField = new ExpandField(playingField); System.out.println(expandField.ResultQueue.size()); for(PlayingField pf : expandField.ResultQueue) { for (Point p : pf.History) { //System.out.print(p.x + "/" + p.y + "\t"); } //System.out.println(); } } }ExpandField
import java.awt.Point; import java.util.Vector; class ExpandField { public ExpandField(PlayingField field) { Queue.add(field); while (Queue.size() > 0){ ExpandNode(Queue.get(0)); Queue.remove(0); } } public void ExpandNode(PlayingField field){ Point nextField = new Point(UNDEFINED,UNDEFINED); do{ nextField = getNextField(nextField); if (nextField.x != UNDEFINED){ if (field.getFieldValue(nextField.x, nextField.y) == PlayingField.DEFAULTVALUE){ PlayingField newField = field.clone(); newField.setFieldValue(nextField.x, nextField.y); if (newField.getWinner() == PlayingField.NOTFINISHED){ Queue.add(newField); }else{ ResultQueue.add(newField); } } } } while (nextField.x != UNDEFINED); } private Point getNextField(Point start){ if ((start.x == UNDEFINED) && (start.y == UNDEFINED)){ return new Point(0,0); } if ((start.x == 2) && (start.y == 2)){ return new Point(UNDEFINED,UNDEFINED); } start.x++; if (start.x == 3) { start.x = 0; start.y++; } return start; //return new Point(UNDEFINED,UNDEFINED); } private final static int UNDEFINED = -1; public static Vector<PlayingField> Queue = new Vector<PlayingField>(); public static Vector<PlayingField> ResultQueue = new Vector<PlayingField>(); }PlayingField
import java.awt.Point; import java.beans.FeatureDescriptor; import java.util.ArrayList; import java.util.Vector; class PlayingField implements Cloneable{ /** * Ruft den Konstruktor auf um den das Spielfel */ public PlayingField(){ this(PLAYER1); } /** * Initialisiert das Spielfeld mit default Daten * Initialisiert den aktiven Spieler * @params player : aktiver Spieler */ public PlayingField(int player){ initField(); initActivePlayer(player); } /** * Liefert den Wert eines Feldes zurueck @params x : x Koordinate des Feldes @params y : y Koordinate des Feldes @return Wert an der Stelle x, y */ public int getFieldValue(int x, int y){ return field[x][y]; } /** * Beschreibt den Wert eines Feldes mit der aktuellen Spielfarbe * @params x : x Koordinate des Feldes * @params y : y Koordinate des Feldes * @return true bei Erfolg , false bei einem Fehler */ public boolean setFieldValue(int x, int y){ if (field[x][y] != DEFAULTVALUE){ return false; } else{ field[x][y] = activePlayer; // Add field to history History.add(new Point(x,y)); return true; } } /** * Liefert den Gewinner des Spiels * @return PLAYER1 oder PLAYER2 bei einem Sieg * @return NOWINNER bei einem Unentschieden * @return NOTFINISHED wenn das Spiel noch nicht beendet ist. */ public int getWinner(){ for (int x = 0; x < 3; x++){ if ((getFieldValue(x,0) == getFieldValue(x,1)) && (getFieldValue(x,0) == getFieldValue(x,2)) && (getFieldValue(x,0) != DEFAULTVALUE)){ return getFieldValue(x,0); } } for (int y = 0; y < 3; y++){ if ((getFieldValue(0,y) == getFieldValue(1,y)) && (getFieldValue(0,y) == getFieldValue(2,y)) && (getFieldValue(0,y) != DEFAULTVALUE)){ return getFieldValue(0,y); } } if ((getFieldValue(0,2) == getFieldValue(1,2)) && (getFieldValue(0,2) == getFieldValue(2,2)) && (getFieldValue(0,2) != DEFAULTVALUE)){ return getFieldValue(0,2); } if ((getFieldValue(0,0) == getFieldValue(1,1)) && (getFieldValue(0,0) == getFieldValue(2,2)) && (getFieldValue(0,0) != DEFAULTVALUE)){ return getFieldValue(0,0); } if (History.size() == 9) return NOWINNER; return NOTFINISHED; } public PlayingField clone(){ try{ PlayingField newField = (PlayingField) super.clone(); // Kopiere die Feldinhalte newField.field = new int[3][3]; for (int x = 0; x < 3; x++){ for (int y = 0; y < 3; y++){ newField.field[x][y] = this.getFieldValue(x, y); } } // Kopiere die Historie newField.History = new Vector<Point>(); for (int i = 0; i < History.size(); i++){ newField.History.add(this.History.get(i)); } return newField; }catch(CloneNotSupportedException e){ } return null; } private void initActivePlayer(int player){ // Init active player with player activePlayer = player; } /** * Initialisiert das Spielfeld mit default Werten */ private void initField(){ // Init Field with default values for (int x = 0; x < 3; x++){ for (int y = 0; y < 3; y++){ field[x][y] = DEFAULTVALUE; } } } // Public Constants public static final int DEFAULTVALUE = 0; public static final int PLAYER1 = 1; public static final int PLAYER2 = 2; public static final int NOWINNER = 3; public static final int NOTFINISHED = 4; public static final int FINISHED = 5; // Private Variables private int[][] field = new int[3][3]; private int activePlayer = DEFAULTVALUE; public Vector<Point> History = new Vector<Point>(); }
-
Danke für deine Antwort. Aber es müssen 9! sein also 362880
-
ne müssens nicht, denn wenn du die oberste reihe füllst fallen 6! Möglichkeiten weg, dadurch, dass schon jemand gewonnen hat, oder überseh ich da was?
-
Es geht doch dann nicht darum wer gewinnt, sondern alle möghlichkeiten also auch unentschieden. und dann gibt es doch so viele möglichkeiten oder nicht
-
Wenn du einen Stein setzt, sodass es folgendermaßen aussieht:
111 000 000Dann gibt dir die getWinner() funktion 1 zurück.
Du testest in der If-abfrage danach auf == NOTFINISHED (also 4)
Somit kommst du in den else-Zweig, der das Spielfeld nur in die resultQueue packt und nciht in die Queue. Dadurch werden nciht weiter die 6 verbleibenden Felder besetzt(was auch irgendwie sinnvoll ist^^)Wenn du wirklich an alle möglichen Füllungen kommen willst(also das das Feld auf jeden Fall gefüllt wird, musst du bei Rückgabe von NOWINNER es in die RQ packen, in allen anderen Fällen in die QUEue. Wobei NOWINNER bedeutet, alle Felder sind belegt(-> History == 9) und dieses NOWINNER muss priorität haben, d.h. in getWinner() muss am anfang auf == 9 getestet werden.
Wenn du diese änderungen vornimmst, kommst du auf 9!Achja, ich hab auch ganz am anfang das setzten von (2,2) und clonen weggelassen
-
Sieht nach einer Hausaufgabe aus
-
Ließe sich das nicht mit Backtracking lösen?
-
Hallo. Also es ist keine Hasuaufgabe. Denn ich versuche gerade mich in Java einzuarbeiten.
Naja das Problem ist das es ich ja alle möglichen Endzustände haben will. Also ntürlich nur die , dei auch logisch sind. Wenn ein Spielfeld bereits den Zustand Fertig hat, braucht man natürlich nicht weiter zu versuchen irgendwelche Felder zu beschreiben. Ich dachte immer, dass das dem Backtracking schon ziemlich nahe kommt.