Seite 2 von 2 « Erste 12
Ergebnis 21 bis 37 von 37

Java - Grafik

  1. #21 Zitieren
    Forschungsreisender  Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    3.622
     
    600 ms ist auf einem i7 eine halbe Ewigkeit. Trotzdem gute Arbeit!

    Mein noch unoptimiertes Beispiel dort oben ist auf einem alten Laptop (Core2DuoT6600@1,8GHz) locker im zweistelligen Millisekunden-Bereich für den ersten Durchgang und später, wenn der Optimierer endlich die Füße stillhält, bei 10...11 ms. Bei dir wäre das rund 2 ms. Dabei habe ich sogar zu meinen Ungunsten das Kopieren in den Ausgabepuffer für das GUI mitgemessen.

    Der erste Durchgang deiner Lösung deutet mit 600 ms bei dir und 3 s bei mir auf einen Performance-Bug (s.u.) hin. Meiner ist beim ersten Durchgang rund fünfzig mal so schnell wie deiner, während er in späteren Durchgängen viel langsamer als deiner ist, was wegen der Kopieraktionen nicht verwundert.

    Die weiteren Durchgänge bewegen sich bei dir nämlich im Mikrosekundenbereich, falls du das messen kannst. Falls nicht oder zur Bequemlichkeit, bitte schön:
    Code:
    long num = 100;
    long average = 0;
    for (int i=0; i<num; i++) {
        final long startTime = System.nanoTime();
        soli(A,0);        
        long dT = (System.nanoTime() - startTime);
        average += dT;
        System.out.printf("Time:%1$11.3f µs\n", ((double)dT) / 1000);
    }
    average /= num;
    System.out.printf("-------------------\nMean:%1$11.3f µs\n", ((double)average)/1000);
    Das kannst du einfach so einfügen, braucht weiter nichts. Mit einem Timer, der an den groben Interruptintervallen von 1...15,625 ms hängt, kommst du nämlich nicht weit, wenn es mal feiner oder schneller wird.

    Deine Rekursion ist schön schlank geworden, doch steckt dort noch ein kaum auffallender Performance-Bug drin, den ich bei mir mit als erstes entfernt habe. Wenn der bei dir draußen ist, kippst du vor Staunen aus den Latschen. Rate mal, woran es liegt...
    jabu ist offline

  2. #22 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    Welcher Perfomance-Bug? Sag mal.

    Bekomme mit deiner Schleife einen Durchschnitt von 0,304 µs. Das ist in Sekunden wie viel?

    Wobei das sowieso nicht stimmt. Bei dir ist das gleiche, wie bei der Schleife von Kellendil.
    Zumindest bei meinem Code ist das so, dass wenn soli(A,i) zum ersten mal durchlaufen ist, in A logischerweise die Endposition gespeichert ist. Da ist also nur noch ein Stein drauf. Da es bei einem Stein nichts zurechnen gibt, ist er deshalb bei den folgenden Umläufen auch so schnell. Bevor man A erneut aufruft, muss man A wieder die Grundstellung zuweisen.
    Sergej Petrow ist gerade online Geändert von Sergej Petrow (31.12.2016 um 14:25 Uhr)

  3. #23 Zitieren
    Knight Avatar von Kellendil
    Registriert seit
    Jul 2009
    Beiträge
    1.691
     
    Zitat Zitat von Sergej Petrow Beitrag anzeigen
    EDIT2:
    Ich glaube, deine Zeitmessung stimmt nicht. Habe das auch mal mit 100 mal gemacht und hatte auf einmal die gleiche Zeit, war sogar noch etwas schneller, als bei dir. Das kam mir sehr spanisch vor.

    Das Problem ist, dass das ursprüngliche Array nicht mehr passt. Man übergibt zwar das Array, aber es wird mit Aufruf trotzdem alle Änderungen haben, die die Methode ermittelt hat. Am Ende ist also im Array A nur noch ein Stein vorhanden. Und dieses Array mit dem einen Stein wird dann über die Zeit Ermittlungsschleife gejagt. Da es da aber keinen Zug mehr gibt, wird Soli sofort beendet. Weiß nicht mehr genau, wie das heißt, wenn ein Array übergeben wird. Da wird quasi nicht ein neues Array aufgemacht, sondern es wird nur die Adresse übergeben. Ein Point war das nicht, das war noch ein anderer Begriff. EDIT3: Referenzen war das Wort, welches ich suchte. Ich habe das jetzt jedenfalls mal probiert, in dem ich jedes Mal das Array wieder neu erstellt habe auf die Ausgangsstellung und dann passt es auch. 117,455 Sekunden /100 ergibt 1,17455 Sekunden pro Versuch.
    Dass das mit der Zeit schneller wird ist ganz normal bei Java, da läuft sich einfach die JVM warm. Deswegen muss man bei Java-Microbenchmarks auch immer die ersten paar Ergebnisse wegwerfen. Der Compiler-betreibt JIT, was nach ein paar Runden immer besser wird.

    Und das Problem was du beschreibst gibt es in meinem Code nicht (den ich jetzt nochmal so verändert habe, dass er auf jeden Fall kompilierbar ist). In das Lösungsarray schreibe ich ja nur was rein (per "speichern" Methode), da wird nix gelesen, da können die alten Werte also auch nix beeinflussen. Erst die paint-Methode ließt das array. Die Startfeld (die "field" Variable bei mir) wird in jedem Durchlauf komplett neu erstellt und in der Startkonfiguration besetzt.

    Außerdem sehe ich gerade, dass ich sogar das Lösungsarray in jedem Durchlauf komplett neu erstelle in der Zeile mit dem Code "loesung = new Spot[numberOfSpots][fieldSize][fieldSize]", daran kanns also wirklich nicht liegen.

    Und ich glaube auch nicht, dass jabu's Code so ein Problem hat.

    Hier der hoffentlich kompilierbare Code:
    Spoiler:(zum lesen bitte Text markieren)

    Code:
    import java.awt.Color;
    import java.awt.Graphics;
    import java.awt.Graphics2D;
    import java.awt.Point;
    
    import javax.swing.JFrame;
    
    public class Solit {
    
    	public enum Spot {
    		FULL,
    		FREE,
    		NO_SPOT // für ecken
    	}
    	
    	private final boolean zeichnen = true;
    	
    	private final int fieldSize; // z.B. 7: wie viele Stellen/Spots es in jede Richtung gibt
    	private final int edgeSize; // z.B. 2: wie viele Stellen/Spots bei jeder Ecke frei bleiben (in jede Richtung)
    	
    	private Spot[][][] loesung; // pro step pro x pro y
    	
    	public Solit(int fieldSize, int edgeSize, Point freeStartSpotCoords) {
    		this.fieldSize = fieldSize;
    		this.edgeSize = edgeSize;
    		
    		int numberOfSpots = (fieldSize * fieldSize) - (edgeSize * edgeSize * 4) - 1;
    		
    		long totalTime = 0;
    		int tests = 100;
    		for (tests = 0; tests < 100; tests++) {
    			long startTime = System.currentTimeMillis();
    			Spot[][] field = initField(edgeSize, freeStartSpotCoords);
    			
    			loesung = new Spot[numberOfSpots][fieldSize][fieldSize];
    			loesung[0] = field;
    			soli(field, 0);
    			long time = System.currentTimeMillis() - startTime;
    			System.out.println("Time: " + time);
    			totalTime += time;
    		}
    		System.out.println("Average: " + totalTime/tests);
    
    		if (zeichnen) {
    			SolitViewerFrame frame = new SolitViewerFrame(loesung[0]);
    			for (int i = 0; i < numberOfSpots; i++)
    			{
    				frame.field = loesung[i];
    				frame.repaint();
    				try {
    					Thread.sleep(1000);
    				} catch (InterruptedException e) {}
    			}
    		}
    	}
    	
    	private Spot[][] initField(int edgeSize, Point startFieldIndex) {
    		
    		// Spielfeld bestehend aus "Löchern"(Spots), siehe FieldSpot enum
    		Spot[][] field = new Spot[fieldSize][fieldSize];
    		
    		// felder besetzten, ecken entfernen
    		for (int x = 0; x < field.length; x++) {
    			for (int y = 0; y < field[x].length; y++) {
    				field[x][y] = isEdgeSpot(new Point(x, y)) ? Spot.NO_SPOT : Spot.FULL;
    			}
    		}
    		// startfeld
    		field[startFieldIndex.x][startFieldIndex.y] = Spot.FREE;
    		
    		return field;
    	}
    	
    	private boolean isEdgeSpot(Point p) {
    		return p.x < edgeSize && (p.y < edgeSize || p.y >= fieldSize-edgeSize)
    			|| p.x >= fieldSize - edgeSize && (p.y < edgeSize || p.y >= fieldSize-edgeSize);
    	}
    	
    	private boolean jump(Spot[][] field, Point from, Point dir, boolean reverse) {
    		Point over = new Point(from.x + dir.x, from.y + dir.y);
    		Point to = new Point(over.x + dir.x, over.y + dir.y);
    		boolean inBounds = !isEdgeSpot(over) &&
    				dir.y == -1 ? to.y >= 0 : dir.y == 1 ? to.y < fieldSize :
    				dir.x == -1 ? to.x >= 0 : dir.x == 1 ? to.x < fieldSize : false;
    		boolean canJump = inBounds
    			&& field[from.x][from.y] == Spot.FULL
    			&& field[over.x][over.y] == Spot.FULL
    			&& field[to.x][to.y] == Spot.FREE;
    		if (inBounds && (canJump || reverse)) {
    			field[from.x][from.y] = reverse ? Spot.FULL : Spot.FREE;
    			field[over.x][over.y] = reverse ? Spot.FULL : Spot.FREE;
    			field[to.x][to.y] = reverse ? Spot.FREE : Spot.FULL;
    		}
    		return canJump;
    	}
    	
    	private void speichern(Spot[][] field, int step) {
    		Spot[][] result = field.clone();
    		for (int i = 0; i < result.length; i++) {
    			result[i] = result[i].clone();
    		}
    		loesung[step] = result;
    	}
    
    	private int soli(Spot[][] field, int step) {
    		int ergebnis = 0;
    		if (step < loesung.length - 1) {
    			step++;
    			for (int x = 0; x < field.length; x++) {
    				for (int y = 0; y < field[x].length; y++) {
    					// try all 4 directions for jumping
    					final Point currentCoord = new Point(x, y);
    					final Point[] directions =
    						{ new Point(0,-1), new Point(0,1), new Point(-1,0), new Point(1,0) };
    					for (final Point dir : directions) {
    						if (jump(field, currentCoord, dir, false)) {
    							ergebnis = soli(field, step);
    							if (ergebnis == -1) {
    								speichern(field, step);
    								jump(field, currentCoord, dir, true);
    								return -1;
    							} else if (ergebnis == -2) {
    								jump(field, currentCoord, dir, true);
    							}
    						}
    					}
    				}
    			}
    			step--;
    			return -2;
    		} else {
    			return -1;
    		}
    	}
    	
    	@SuppressWarnings("serial")
    	private static class SolitViewerFrame extends JFrame {
    		
    		public Spot[][] field;
    		
    		public SolitViewerFrame(Spot[][] first) {
    			super();
    			this.field = first;
    			setDefaultCloseOperation(EXIT_ON_CLOSE);
    			setSize(field.length * 100, field[0].length * 100);
    			setVisible(true);
    		}
    
    		@Override
    		public void paint(Graphics gs) {
    			Graphics2D g = (Graphics2D) gs;
    			g.setColor(Color.WHITE);
    		    g.fillRect(0, 0, getWidth(), getHeight());
    
    			for (int x = 0; x < field.length; x++) {
    				for (int y = 0; y < field[x].length; y++) {
    					Spot inhalt = field[x][y];
    					
    					if (inhalt == Spot.FREE) {
    						g.setColor(Color.WHITE);
    						g.fillOval(x * 60 + 150, y * 60 + 150, 30, 30);
    						g.setColor(Color.BLACK);
    						g.drawOval(x * 60 + 150, y * 60 + 150, 30, 30);
    					}
    					else if (inhalt == Spot.FULL) {
    						g.setColor(Color.GREEN);
    						g.fillOval(x * 60 + 150, y * 60 + 150, 30, 30);
    					}
    				}
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		new Solit(7, 2, new Point(3, 3));
    //		new Solit(9, 3, new Point(4, 4));
    	}
    }
    Kellendil ist offline Geändert von Kellendil (31.12.2016 um 19:19 Uhr)

  4. #24 Zitieren
    Forschungsreisender  Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    3.622
     
    Zitat Zitat von Sergej Petrow Beitrag anzeigen
    Welcher Perfomance-Bug? Sag mal.
    Es hat sich inzwischen herausgestellt, dass das bei dir kein Bug ist (sorry ), sondern dass der Grund dafür, dass mein Code, je nach Version, rund 120 bis 400 Mal so schnell wie deiner fertig ist und trotzdem akkurate Ergebnisse liefert, ein anderer ist, den du dir vielleicht schon gedacht hast, denken kannst, wie auch immer. Die falsche Fährte erkläre ich selbstverständlich, denn an irgendetwas muss es ja liegen, dass der Code von Kellendil und mir schneller fertig ist und dass es bei dir nach einem Bug ausgesehen hat.

    Angefangen hat alles damit, dass bei deinem Code etwas gemacht wurde, was normalerweise zu vermeiden wäre, nämlich die äußeren anstatt die inneren Array-Indices am Stück durchlaufen zu lassen, was ich natürlich geändert habe und wobei ich durchgängig auf zeilenweise Betrachtung umgestellt habe und dabei nebenbei noch eine Kleinigkeit verändert habe, die mathematisch äquivalent ist, wenn man nur auf das Ergebnis guckt. Was das ist, dürfte jetzt für interessierte Mitleser leicht herauszufinden sein.

    Warum habe ich das gemacht? Um den Code für das Forum und für mich kompakt zu halten, denn ich wollte mich auf das GUI konzentrieren, denn der eigentliche Grund für die Aktion war bei mir nicht der Algorithmus, denn Rekursionen und die Art und Weise, wie man sie abwickelt, kenne ich bereits und du auch. Ich dachte also, dass ich eher etwas beim GUI beisteuern kann, was dir nützt, da du selber Spaß an dieser Rekursion hast und das GUI eher nach einer Baustelle aussah (was auch vor der letzten Version, als du meintest, es wäre flüssig, nicht ganz gelöst war, denn es flackerte bei mir noch heftig, aus bekanntem Grund). Vielleicht guckst du mal bei mir in den GUI-Teil hinein, was dort mit dem Panel geschieht. Das ist zwar weder perfekt noch vollständig, aber es ist bereits alles drin, was deine Probleme löst (ich weiß wohl, dass du inzwischen einiges selbst hast), wobei ich das bewusst einfacher als in der offiziellen Doku gemacht habe, sodass es an den ersichtlichen Unterschieden liegt und man sich nicht den Kopf darüber zerbrechen muss, was wesentlich ist und was nicht, wobei natürlich keine Vollständigkeit angestrebt wurde (es fehlt mindestens ein Cast zu Graphics2D, den du aber drin hast sowie das Erstellen eines Threads). Es tut eben mit minimalem Aufwand, was bei dir noch fehlt.

    Doch zurück zum Array:

    Zumindest bei solchen Sprachen, bei denen Arrays linear im Speicher liegen (hier weiß man nicht vorher, was am Ende herausfällt, woanders ist es garantiert), wäre das ein potentieller Performance-Bug, der sich oftmals auswirkt, aber nicht immer. Deswegen kann man schon mal vermuten, dass das den Laufzeitoptimierer auf Abwege bringt, indem er das zu ändern versucht, was reichlich komplex wäre, aber nicht schafft. Damit wäre sogar erklärbar gewesen, dass mehrere Sekunden verlorengehen. Aber gut, es sieht zumindest danach aus, dass es der JIT wohl erst gar nicht versucht, was nicht mal zu kritisieren ist, wenn der Vorteil geringfügig ausfällt oder der Overhead nicht tragbar ist. Oder er hat sie bereits umsortiert, sozusagen vom Modell der Referenzen zur bestmöglichen Lösung hin. Das wäre natürlich grandios.

    Jedenfalls hat die Neuanordnung inklusiver dieser Äquivalenzumformung den Effekt ausgelöst, dass der Code in 1/400 der Zeit durchläuft. Dabei habe ich die Auswirkungen der Umformung unterschätzt. Das ist im Grunde nichts anderes, als was ein Programmierer macht, wenn er neuen Code schreibt oder ein Refactoring macht. Da dachte ich mir: Wenn das sowieso äquivalent ist, dann gucke ich mir die Ausführungsreihenfolge nicht extra an, wenn es nachher wenigstens nicht langsamer wird! Gut, wenn es dann so schnell wird, hätte man das mal in ausgeschlafenem Zustand auseinandernehmen sollen! Wenn es um ein ernsthaftes Projekt gegangen wäre, hätte ich das auch nicht so leichtfüßig gehandhabt.

    Bei dir ist das gleiche, wie bei der Schleife von Kellendil.
    Dieser elegante und flexible Code, der mir insgesamt gut gefällt, braucht bei mir leider 160 ms. Die Anzahl der Funktionsaufrufe ist dieselbe wie bei mir, was die wesentliche Gemeinsamkeit bei der Geschwindigkeit ist. Deine Annahme trifft jedoch etwa zur Hälfte, und zwar an der wichtigsten Stelle, nicht zu, denn er hat bereits Speichern beim Rücksprung anstatt beim Vorwärtslaufen drin, was die Zahl der Speichervorgänge drastisch vermindert, wie auch inzwischen bei dir und mir, was ich allerdings im geposteten Code noch nicht hatte, weshalb seiner da strukturell viel besser als mein alter ist und bereits dicht an deinem liegt. Nur das Vermeiden des Zurückziehens bei Erfolg hat er - ebenso wie ich derzeit - noch nicht gehabt. Was den Punkt angeht, hast du natürlich Recht. Allerdings ist dieser Vorgang, den man natürlich eliminieren möchte, nicht so teuer, dass dieser Umstand den Geschwindigkeitsnachteil auch nur ansatzweise erklären würde, seine Ausführung jedoch schon, denn die sollte wohl durch die doppelte Verwendung der Funktion mitsamt Umschaltung wohl mit einem ziemlich großen Overhead einhergehen. Das ist wohl der Preis für die Eleganz (wogegen man allgemein anrät, dass eine Funktion immer nur eine bestimmte Aufgabe erledigen sollte, was hier wohl geholfen hätte). Aber so detailliert habe ich das noch nicht durchmessen, um jetzt genau sagen zu können, wieviel hier und wieviel woanders verbraten wird. Dort alles herauszuholen, ist wohl nicht sein Ansatz gewesen, bei mir übrigens auch nicht. Das Drumherum hat ja bei ihm sowie bei mir fast die ganze Zeit beansprucht, der Algorithmus, der fast derselbe geblieben ist, wohl weniger.

    Bekomme mit deiner Schleife einen Durchschnitt von 0,304 µs. Das ist in Sekunden wie viel?

    Wobei das sowieso nicht stimmt. [...]
    Zumindest bei meinem Code ist das so, dass wenn soli(A,i) zum ersten mal durchlaufen ist, in A logischerweise die Endposition gespeichert ist. Da ist also nur noch ein Stein drauf. Da es bei einem Stein nichts zurechnen gibt, ist er deshalb bei den folgenden Umläufen auch so schnell. Bevor man A erneut aufruft, muss man A wieder die Grundstellung zuweisen.
    Ja, weil die Initialisierung beim geposteten Zeitmessungscode in der Schleife gefehlt hat. Den hättest du natürlich gerne für dich anpassen dürfen, indem du einfach die Erstellung des Arrays hineinschiebst.

    Also dürfte das jetzt so aussehen (etwas Kosmetik, die nichts an der Berechnung rührt, sei mir erlaubt):
    Code:
    final int num = 100;
    long mean = 0;
    for (int i=0; i<num; i++) {
        final long startTime = System.nanoTime(); //muss long sein!
        short [][] A = new short [][]{
            { 9,9,1,1,1,9,9 },
            { 9,9,1,1,1,9,9 },
            { 1,1,1,1,1,1,1 },
            { 1,1,1,0,1,1,1 },
            { 1,1,1,1,1,1,1 },
            { 9,9,1,1,1,9,9 },
            { 9,9,1,1,1,9,9 }		
        };
        speichern(A,0);
        soli(A,0);        
        long dT = (System.nanoTime() - startTime);
        mean += dT;
        System.out.format("Time:%1$12.3f \u00B5s - Z\u00e4hler:%2$8d%n", (double)dT/1000, zaehler);
        zaehler = 0;
    }
    mean /= (long)num;
    System.out.format("--------------------\nMean:%1$12.3f \u00B5s%n", (double)mean/1000);

    Mit allen Durchgängen wäre es dann bei deinem Code dieses:
    Spoiler:(zum lesen bitte Text markieren)
    Code:
    java version "1.8.0_112"
    Java(TM) SE Runtime Environment (build 1.8.0_112-b15)
    Java HotSpot(TM) 64-Bit Server VM (build 25.112-b15, mixed mode)
    Time: 2959640,496 µs - Zähler: 7667770
    Time: 3056573,672 µs - Zähler: 7667770
    Time: 3023821,034 µs - Zähler: 7667770
    Time: 3024355,782 µs - Zähler: 7667770
    Time: 3025333,355 µs - Zähler: 7667770
    Time: 3023731,909 µs - Zähler: 7667770
    Time: 3023772,038 µs - Zähler: 7667770
    Time: 3025467,741 µs - Zähler: 7667770
    Time: 3023894,293 µs - Zähler: 7667770
    Time: 3025121,042 µs - Zähler: 7667770
    Time: 3024345,516 µs - Zähler: 7667770
    Time: 3022613,417 µs - Zähler: 7667770
    Time: 3024531,232 µs - Zähler: 7667770
    Time: 3023187,828 µs - Zähler: 7667770
    Time: 3025311,890 µs - Zähler: 7667770
    Time: 3057735,560 µs - Zähler: 7667770
    Time: 3074599,266 µs - Zähler: 7667770
    Time: 3068229,413 µs - Zähler: 7667770
    Time: 3044427,511 µs - Zähler: 7667770
    Time: 3122744,352 µs - Zähler: 7667770
    Time: 3050274,280 µs - Zähler: 7667770
    Time: 3108544,588 µs - Zähler: 7667770
    Time: 3024736,079 µs - Zähler: 7667770
    Time: 3032486,664 µs - Zähler: 7667770
    Time: 3024256,392 µs - Zähler: 7667770
    Time: 3022128,597 µs - Zähler: 7667770
    Time: 3025210,633 µs - Zähler: 7667770
    Time: 3030377,535 µs - Zähler: 7667770
    Time: 3024668,418 µs - Zähler: 7667770
    Time: 3024783,208 µs - Zähler: 7667770
    Time: 3023585,389 µs - Zähler: 7667770
    Time: 3024805,606 µs - Zähler: 7667770
    Time: 3024158,402 µs - Zähler: 7667770
    Time: 3023513,530 µs - Zähler: 7667770
    Time: 3025710,851 µs - Zähler: 7667770
    Time: 3025871,369 µs - Zähler: 7667770
    Time: 3024246,126 µs - Zähler: 7667770
    Time: 3027790,584 µs - Zähler: 7667770
    Time: 3024466,371 µs - Zähler: 7667770
    Time: 3025261,494 µs - Zähler: 7667770
    Time: 3044188,135 µs - Zähler: 7667770
    Time: 3024454,706 µs - Zähler: 7667770
    Time: 3027009,460 µs - Zähler: 7667770
    Time: 3047586,073 µs - Zähler: 7667770
    Time: 3024095,407 µs - Zähler: 7667770
    Time: 3027443,418 µs - Zähler: 7667770
    Time: 3024727,680 µs - Zähler: 7667770
    Time: 3034548,198 µs - Zähler: 7667770
    Time: 3024543,831 µs - Zähler: 7667770
    Time: 3023319,416 µs - Zähler: 7667770
    Time: 3024289,055 µs - Zähler: 7667770
    Time: 3024678,685 µs - Zähler: 7667770
    Time: 3023120,168 µs - Zähler: 7667770
    Time: 3026875,073 µs - Zähler: 7667770
    Time: 3024912,462 µs - Zähler: 7667770
    Time: 3024764,542 µs - Zähler: 7667770
    Time: 3025085,578 µs - Zähler: 7667770
    Time: 3026177,006 µs - Zähler: 7667770
    Time: 3026575,501 µs - Zähler: 7667770
    Time: 3024495,768 µs - Zähler: 7667770
    Time: 3025983,359 µs - Zähler: 7667770
    Time: 3025764,513 µs - Zähler: 7667770
    Time: 3023972,686 µs - Zähler: 7667770
    Time: 3041896,555 µs - Zähler: 7667770
    Time: 3026263,798 µs - Zähler: 7667770
    Time: 3023073,506 µs - Zähler: 7667770
    Time: 3027497,546 µs - Zähler: 7667770
    Time: 3032609,385 µs - Zähler: 7667770
    Time: 3023303,550 µs - Zähler: 7667770
    Time: 3025577,864 µs - Zähler: 7667770
    Time: 3024499,968 µs - Zähler: 7667770
    Time: 3025782,711 µs - Zähler: 7667770
    Time: 3025065,981 µs - Zähler: 7667770
    Time: 3024053,412 µs - Zähler: 7667770
    Time: 3023768,772 µs - Zähler: 7667770
    Time: 3025940,429 µs - Zähler: 7667770
    Time: 3024440,708 µs - Zähler: 7667770
    Time: 3025932,497 µs - Zähler: 7667770
    Time: 3022605,951 µs - Zähler: 7667770
    Time: 3024479,904 µs - Zähler: 7667770
    Time: 3027116,783 µs - Zähler: 7667770
    Time: 3023339,480 µs - Zähler: 7667770
    Time: 3024732,812 µs - Zähler: 7667770
    Time: 3032106,368 µs - Zähler: 7667770
    Time: 3023621,320 µs - Zähler: 7667770
    Time: 3025223,698 µs - Zähler: 7667770
    Time: 3035171,605 µs - Zähler: 7667770
    Time: 3031603,816 µs - Zähler: 7667770
    Time: 3023767,839 µs - Zähler: 7667770
    Time: 3025271,760 µs - Zähler: 7667770
    Time: 3025048,716 µs - Zähler: 7667770
    Time: 3024879,332 µs - Zähler: 7667770
    Time: 3024547,564 µs - Zähler: 7667770
    Time: 3025288,092 µs - Zähler: 7667770
    Time: 3024134,136 µs - Zähler: 7667770
    Time: 3026169,541 µs - Zähler: 7667770
    Time: 3025550,800 µs - Zähler: 7667770
    Time: 3024169,600 µs - Zähler: 7667770
    Time: 3023793,036 µs - Zähler: 7667770
    Time: 3024330,118 µs - Zähler: 7667770
    --------------------
    Mean: 3029115,831 µs

    3 s (bei dir 600 ms, sagtest du, was gut passt, wenn man unsere CPUs vergleicht), wäre nämlich auf den ersten Blick verdammt schlecht, wenn man es z.B. mit Code vergleicht, wie ich ihn gepostet hatte und bei dem der Algorithmus von dir übernommen wurde (da mein Schwerpunkt beim GUI lag (s.o.), Performance ist später aufgefallen, wobei dein Code bei mir ca. 8 s auf einer 64-Bit-JVM und ca. 18 s auf einer 32-Bit-JVM brauchte und meiner plötzlich nur noch zweistellige Millisekunden!). Aber du hast Recht, dass es unter den gegebenen Umständen gut ist. Die Unterschiede sind dermaßen krass, allerdings fehlte derzeit noch der Zähler, der mich auf die richtige Fährte geführt hätte:
    Spoiler:(zum lesen bitte Text markieren)
    Code:
    java version "1.8.0_112"
    Java(TM) SE Runtime Environment (build 1.8.0_112-b15)
    Java HotSpot(TM) 64-Bit Server VM (build 25.112-b15, mixed mode)
    Time:   95567,375 µs - Zähler:   20276
    Time:   79615,447 µs - Zähler:   20276
    Time:   99869,160 µs - Zähler:   20276
    Time:   88794,362 µs - Zähler:   20276
    Time:   52499,132 µs - Zähler:   20276
    Time:   83306,891 µs - Zähler:   20276
    Time:   90971,618 µs - Zähler:   20276
    Time:   67159,916 µs - Zähler:   20276
    Time:   79557,120 µs - Zähler:   20276
    Time:   56126,648 µs - Zähler:   20276
    Time:   23522,862 µs - Zähler:   20276
    Time:   23144,899 µs - Zähler:   20276
    Time:   23136,033 µs - Zähler:   20276
    Time:   25168,171 µs - Zähler:   20276
    Time:   23249,423 µs - Zähler:   20276
    Time:   23909,225 µs - Zähler:   20276
    Time:   23626,452 µs - Zähler:   20276
    Time:   26757,484 µs - Zähler:   20276
    Time:   23207,426 µs - Zähler:   20276
    Time:   23670,782 µs - Zähler:   20276
    Time:   25190,568 µs - Zähler:   20276
    Time:   25198,501 µs - Zähler:   20276
    Time:   23232,624 µs - Zähler:   20276
    Time:   23869,562 µs - Zähler:   20276
    Time:   23583,523 µs - Zähler:   20276
    Time:   25104,710 µs - Zähler:   20276
    Time:   23493,932 µs - Zähler:   20276
    Time:   25814,441 µs - Zähler:   20276
    Time:   23742,174 µs - Zähler:   20276
    Time:   28172,747 µs - Zähler:   20276
    Time:   25046,382 µs - Zähler:   20276
    Time:   23732,376 µs - Zähler:   20276
    Time:   24251,726 µs - Zähler:   20276
    Time:   28443,854 µs - Zähler:   20276
    Time:   23892,893 µs - Zähler:   20276
    Time:   24922,727 µs - Zähler:   20276
    Time:   24133,670 µs - Zähler:   20276
    Time:   26243,266 µs - Zähler:   20276
    Time:   23273,220 µs - Zähler:   20276
    Time:   24373,514 µs - Zähler:   20276
    Time:   26249,799 µs - Zähler:   20276
    Time:   24610,091 µs - Zähler:   20276
    Time:   23477,133 µs - Zähler:   20276
    Time:   23504,665 µs - Zähler:   20276
    Time:   27230,638 µs - Zähler:   20276
    Time:   25245,163 µs - Zähler:   20276
    Time:   23135,100 µs - Zähler:   20276
    Time:   23517,263 µs - Zähler:   20276
    Time:   24574,161 µs - Zähler:   20276
    Time:   24132,270 µs - Zähler:   20276
    Time:   23406,207 µs - Zähler:   20276
    Time:   23966,153 µs - Zähler:   20276
    Time:   25148,572 µs - Zähler:   20276
    Time:   24003,949 µs - Zähler:   20276
    Time:   26126,144 µs - Zähler:   20276
    Time:   26024,888 µs - Zähler:   20276
    Time:   23606,854 µs - Zähler:   20276
    Time:   27512,010 µs - Zähler:   20276
    Time:   23269,020 µs - Zähler:   20276
    Time:   27880,641 µs - Zähler:   20276
    Time:   29023,865 µs - Zähler:   20276
    Time:   23438,870 µs - Zähler:   20276
    Time:   24262,925 µs - Zähler:   20276
    Time:   26870,407 µs - Zähler:   20276
    Time:   23392,208 µs - Zähler:   20276
    Time:   23899,893 µs - Zähler:   20276
    Time:   23603,588 µs - Zähler:   20276
    Time:   25211,567 µs - Zähler:   20276
    Time:   23353,479 µs - Zähler:   20276
    Time:   24171,000 µs - Zähler:   20276
    Time:   23819,167 µs - Zähler:   20276
    Time:   25009,053 µs - Zähler:   20276
    Time:   24398,711 µs - Zähler:   20276
    Time:   25500,405 µs - Zähler:   20276
    Time:   24637,155 µs - Zähler:   20276
    Time:   24857,867 µs - Zähler:   20276
    Time:   23639,518 µs - Zähler:   20276
    Time:   28530,180 µs - Zähler:   20276
    Time:   26990,328 µs - Zähler:   20276
    Time:   23967,553 µs - Zähler:   20276
    Time:   27491,946 µs - Zähler:   20276
    Time:   26743,018 µs - Zähler:   20276
    Time:   26717,820 µs - Zähler:   20276
    Time:   24819,604 µs - Zähler:   20276
    Time:   25256,362 µs - Zähler:   20276
    Time:   27004,793 µs - Zähler:   20276
    Time:   26491,976 µs - Zähler:   20276
    Time:   27798,050 µs - Zähler:   20276
    Time:   26785,014 µs - Zähler:   20276
    Time:   27603,936 µs - Zähler:   20276
    Time:   26082,282 µs - Zähler:   20276
    Time:   26547,037 µs - Zähler:   20276
    Time:   25125,708 µs - Zähler:   20276
    Time:   27703,793 µs - Zähler:   20276
    Time:   27369,224 µs - Zähler:   20276
    Time:   26609,098 µs - Zähler:   20276
    Time:   27856,844 µs - Zähler:   20276
    Time:   31447,498 µs - Zähler:   20276
    Time:   26992,195 µs - Zähler:   20276
    Time:   28497,049 µs - Zähler:   20276
    --------------------
    Mean:   30647,185 µs

    Und mit dem Shortcut innerhalb der Schleife sowie mit Speichern nur noch bei Erfolg, also beim Rückwärtsabwickeln, was ich auch schon früh drin hatte, ohne es hier angebracht zu haben, aber immer noch mit den Kopieraktionen(!), ergab sich:
    Spoiler:(zum lesen bitte Text markieren)
    Code:
    java version "1.8.0_112"
    Java(TM) SE Runtime Environment (build 1.8.0_112-b15)
    Java HotSpot(TM) 64-Bit Server VM (build 25.112-b15, mixed mode)
    
    Time:19379 µs   Time:23749 µs   Time:21814 µs   Time:7016 µs    Time:7757 µs
    Time:7006 µs    Time:8101 µs    Time:7349 µs    Time:8407 µs    Time:6975 µs
    Time:7811 µs    Time:6973 µs    Time:7885 µs    Time:6969 µs    Time:7842 µs
    Time:6973 µs    Time:7808 µs    Time:6972 µs    Time:7775 µs    Time:7305 µs
    Time:8261 µs    Time:6975 µs    Time:7347 µs    Time:6977 µs    Time:7159 µs
    Time:7474 µs    Time:7030 µs    Time:7488 µs    Time:7184 µs    Time:7556 µs
    Time:7067 µs    Time:7513 µs    Time:7723 µs    Time:7928 µs    Time:7377 µs
    Time:7440 µs    Time:7055 µs    Time:7395 µs    Time:6978 µs    Time:6900 µs
    Time:7143 µs    Time:6899 µs    Time:7835 µs    Time:6905 µs    Time:7588 µs
    Time:7358 µs    Time:7911 µs    Time:6920 µs    Time:7611 µs    Time:6904 µs
    Time:7527 µs    Time:6941 µs    Time:7623 µs    Time:6906 µs    Time:6973 µs
    Time:7383 µs    Time:7674 µs    Time:7444 µs    Time:7698 µs    Time:8472 µs
    Time:7001 µs    Time:8621 µs    Time:6927 µs    Time:8029 µs    Time:6899 µs
    Time:7491 µs    Time:6891 µs    Time:7883 µs    Time:7279 µs    Time:7974 µs
    Time:6901 µs    Time:7936 µs    Time:6888 µs    Time:7798 µs    Time:6891 µs
    Time:7648 µs    Time:6889 µs    Time:6957 µs    Time:7354 µs    Time:7104 µs
    Time:7472 µs    Time:7791 µs    Time:7871 µs    Time:7087 µs    Time:7439 µs
    Time:6964 µs    Time:7548 µs    Time:7073 µs    Time:7425 µs    Time:6964 µs
    Time:6890 µs    Time:7435 µs    Time:6892 µs    Time:7435 µs    Time:7279 µs
    Time:8104 µs    Time:6893 µs    Time:7731 µs    Time:6890 µs    Time:7891 µs
    
    Average: 7808 µs

    Der Code hinter der Messung ist nämlich noch von neulich, als es um das GUI ging und Kellendil seine erste Lösung anbrachte, also 7 bis 8 ms, wobei sogar noch der Browser läuft, was die Ausreißer auf 8 ms erklärt. 7 ms bei mir, rund 160 ms bei Kellendil und bestenfalls 3 s bei dir. Da muss man doch stutzig werden, wenn stets dasselbe Ergebnis wie bei dir herauskommt, aber die Rekursion rund 378 mal so schnell fertig ist! Kellendil hatte sich auch gewundert, wenn ich mich recht entsinne, warum sein Code plötzlich schneller war. Ich habe ihn inzwischen auszählen lassen, ist dieselbe Anzahl an Durchgängen wie bei mir.

    Jetzt der Wermutstropfen: Diese Optimierung bei Kellendil und mir eignet sich nicht für allgemeine Lösungen, sondern ist ein Spezialfall, bei dem man vorher wissen muss, was sich ergibt. Es muss schon vorher bekannt sein, dass es um genau dieses Spielbrett geht, um diese Optimierung vornehmen zu können. Damit nimmt man natürlich einen Teil der Lösung vorweg. Wenn man das Spiel "gut durchrüttelt" oder variabel gestaltet (wobei erst mal geklärt sein müsste, dass es überhaupt eine Lösung gibt), hilft es natürlich nicht mehr, schadet aber auch nicht, weil die Lösung gleichwertig ist. Es gibt ja kein Richtung und Falsch in diesem Sinne. Sie kann dann allerdings ebenso zum Worst Case werden. Aber für den Anfang kann man Regeln aufstellen.

    Na, woran liegt es, und wie kann man es beeinflussen?

    Mist, wieder etwas übersehen: Laufvariablen, insbesondere im Schleifenkopf, machen als short überhaupt keinen Sinn, denn Inkrementieren usw. kann die CPU nur mit der natürlichen Wortbreite ihrer Register, weshalb das sowieso in irgendeiner Verarbeitungsstufe vor der Ausführung (normalerweise Compilerebene) dazu aufgeweitet wird (meistens implizit und kostenlos). Ich habe das mal bei der Zeitmessung angepasst. Im Code hast du das ja öfters. Und dein i-- innerhalb der rekursiven Funktion kannst du ruhigen Gewissens löschen, denn es ist bei Verlassen der Funktion außerhalb des Gültigkeitsbereichs, weshalb der Compiler das sowieso wegwirft. Wenn er es nicht tun würde, läge die Variable zwar noch auf dem Stack, würde aber ignoriert und überschrieben werden. Sie hat so oder so keinerlei Auswirkungen. Ich habe das mal allgemeiner verfasst, nicht speziell für Java. Nicht dass einer meckert, so hardwarenah dürfe man nicht argumentieren. Das ist mir schon bewusst. Es ist allerdings so, dass die Sprachen dort ihre Wurzeln haben, weswegen dann letztendlich die eine oder andere Abstraktion so gewählt ist und es darauf hinausläuft.

    PS
    Wenn ich mich hier auf Kellendil bezogen habe, dann auf seinen ersten Code, den anderen muss ich mir noch ansehen!

    Edit#2: speichern(A,0) war doch noch für das GUI nötig, fixed (ist aber im Sinne der Problemstellung irrelevant).
    jabu ist offline Geändert von jabu (03.01.2017 um 00:02 Uhr)

  5. #25 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Auf einer Einsamen Insel
    Beiträge
    9.972
     
    Da Ich meinen Code nicht zum laufen bekomme (Nach jedem Zug die möglichen Lösungen Aktualisieren und dann auf dieser Liste Züge ausführen, anstelle das man alle Aktiven Felder durchprobiert).

    Einen Vorschlag zum Lösungsarray hätte Ich aber dennoch, welcher auch das GUI Vereinfacht, bzw. es erlaubt leicht zu erweitern.
    Eine Liste von Objekten welche in diesem Fall drei Werte kennen muss:
    StartpositionX des Zuges
    StartpositionY des Zuges
    Richtung
    Auf dieser Liste kann man hin und her fahren, denn Jedes dieser Elemente kann das Spielfeld in beide Richtungen 'Bearbeiten'.

    Ohne das man dazu jedesmal das ganze Spielfeld speichern muss. Auch für Export/Import gibt dieses Objekt eine kleinere Datenmenge zurück als das Dreidimensionale Array.

    Gruss Multi

    PS: Der Ansatz, welcher ewig und 3 Tage zum Durchlaufen braucht:
    Spoiler:(zum lesen bitte Text markieren)
    Code:
     public class PlayingField
        {
            private int _x;
            private int _y;
    
            public List<Field> FieldList { get; set; } = new List<Field>();
    
            public PlayingField(int x, int y)
            {
                _x = x;
                _y = y;
    
                InizialisiereFelder();
            }
    
            /// <summary>
            /// Liste aller Gültigen Spielzüge erstellen
            /// </summary>
            /// <returns></returns>
            public LinkedList<Spielzug> GetAllValidPlays()
            {
                var tmpSpielzugList = new LinkedList<Spielzug>();
    
                foreach (var tmpField in FieldList)
                {
                    if (tmpField.Value != 0)
                    {
                        continue;
                    }
                    tmpField.GetNewValidPlays(tmpSpielzugList);
                }
    
                return tmpSpielzugList;
            }
    
            private long roundaboutCount = 0;
    
            private LinkedList<Spielzug> CopyList(LinkedList<Spielzug> inList)
            {
                var tmpSpielzugList = new LinkedList<Spielzug>();
    
                foreach (var tmpField in inList)
                {
                    tmpSpielzugList.AddLast(new Spielzug { Field = tmpField.Field, Direction = (Direction)((int)tmpField.Direction) });
                }
                return tmpSpielzugList;
            }
    
            public int Resolve(LinkedList<Spielzug> inWiningPlays, LinkedList<Spielzug> inValidPlays, int n)
            {
                if (HasWon(n))
                {
                    return 1;
                }
                n++;
    
                foreach (var tmpPlay in inValidPlays)
                {
                    roundaboutCount++;
                    var tmpField = tmpPlay.Field;
                    
                    if ((tmpPlay.Direction & Direction.Up) == Direction.Up)
                    {
                        tmpField.Value = 0; tmpField.Up.Value = 0; tmpField.Up.Up.Value = 1;
                        var tmpNewValidPlaysList = CopyList(inValidPlays);
                        //Aktualisieren der möglichen Züge
                        tmpField.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Up.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Up.Up.GetNewValidPlays(tmpNewValidPlaysList);
                        if (Resolve(inWiningPlays, tmpNewValidPlaysList, n) == 1)
                        {
                            inWiningPlays.AddFirst(new Spielzug { Field = tmpField, Direction = Direction.Up });
                            return 1;
                        }
                        tmpField.Value = 1; tmpField.Up.Value = 1; tmpField.Up.Up.Value = 0;
                    }
    
                    if ((tmpPlay.Direction & Direction.Down) == Direction.Down)
                    {
                        tmpField.Value = 0; tmpField.Down.Value = 0; tmpField.Down.Down.Value = 1;
                        var tmpNewValidPlaysList = CopyList(inValidPlays);
                        //var tmpNewValidPlaysList = new LinkedList<Spielzug>();
                        tmpField.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Down.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Down.Down.GetNewValidPlays(tmpNewValidPlaysList);
                        if (Resolve(inWiningPlays, tmpNewValidPlaysList, n) == 1)
                        {
                            inWiningPlays.AddFirst(new Spielzug { Field = tmpField, Direction = Direction.Down });
                            return 1;
                        }
                        tmpField.Value = 1; tmpField.Down.Value = 1; tmpField.Down.Down.Value = 0;
                    }
    
                    if ((tmpPlay.Direction & Direction.Left) == Direction.Left)
                    {
                        tmpField.Value = 0; tmpField.Left.Value = 0; tmpField.Left.Left.Value = 1;
                        var tmpNewValidPlaysList = CopyList(inValidPlays);
                        //var tmpNewValidPlaysList = new LinkedList<Spielzug>();
                        tmpField.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Left.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Left.Left.GetNewValidPlays(tmpNewValidPlaysList);
                        if (Resolve(inWiningPlays, tmpNewValidPlaysList, n) == 1)
                        {
                            inWiningPlays.AddFirst(new Spielzug { Field = tmpField, Direction = Direction.Left });
                            return 1;
                        }
                        tmpField.Value = 1; tmpField.Left.Value = 1; tmpField.Left.Left.Value = 0;
                    }
    
                    if ((tmpPlay.Direction & Direction.Right) == Direction.Right)
                    {
                        tmpField.Value = 0; tmpField.Right.Value = 0; tmpField.Right.Right.Value = 1;
                        var tmpNewValidPlaysList = CopyList(inValidPlays);
                        //var tmpNewValidPlaysList = new LinkedList<Spielzug>();
                        tmpField.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Right.GetNewValidPlays(tmpNewValidPlaysList);
                        tmpField.Right.Right.GetNewValidPlays(tmpNewValidPlaysList);
                        if (Resolve(inWiningPlays, tmpNewValidPlaysList, n) == 1)
                        {
                            inWiningPlays.AddFirst(new Spielzug { Field = tmpField, Direction = Direction.Right });
                            return 1;
                        }
                        tmpField.Value = 1; tmpField.Right.Value = 1; tmpField.Right.Right.Value = 0;
                    }
                }
    
                return 0;
            }
    
            /// <summary>
            /// Inizialisieren der Felder.
            /// </summary>
            private void InizialisiereFelder()
            {
                short[,] A = new short[,]{
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 },
                { 1,1,1,1,1,1,1 },
                { 1,1,1,0,1,1,1 },
                { 1,1,1,1,1,1,1 },
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 } };
    
                var tmpFieldArray = new Field[_x, _y];
                for (int y = 0; y < _y; y++)
                {
                    for (int x = 0; x < _x; x++)
                    {
                        tmpFieldArray[x, y] = new Field();
                        tmpFieldArray[x, y].Value = A[x, y];
    
                        //An die Feldliste anfügen, wir brauchen das Array dann nicht mehr
                        FieldList.Add(tmpFieldArray[x, y]);
    
                        //Elemente Verlinken
                        if (x > 0)
                        {
                            tmpFieldArray[x, y].Left = tmpFieldArray[x - 1, y];
                            tmpFieldArray[x - 1, y].Right = tmpFieldArray[x, y];
                        }
                        if (y > 0)
                        {
                            tmpFieldArray[x, y].Up = tmpFieldArray[x, y - 1];
                            tmpFieldArray[x, y - 1].Down = tmpFieldArray[x, y];
                        }
                    }
                }
            }
    
            public bool HasWon(int inN)
            {
                var tmpCount = 0;
    
                //Prüfen ob nur noch ein Feld gesetzt ist. LINQ Magie
                return FieldList.All(inItem => (inItem.Value == 1 ? tmpCount++ : tmpCount) < 1);
            }
    
            //Wo soll der Letzte Stein liegen?
            public int RemainingX { get; set; }
            public int RemainingY { get; set; }
        }
    
    public class Field
        {
            public Field Left { get; set; }
            public Field Right { get; set; }
            public Field Up { get; set; }
            public Field Down { get; set; }
    
            public int Value { get; set; }
    
            //Gültige Spielzüge ausloten
            public LinkedList<Spielzug> GetNewValidPlays(LinkedList<Spielzug> inList)
            {
                if (Value == 1)
                {
                    //if (Up?.Value == 0 || Up?.Up?.Value == 1)
                    //{
                    //    RemoveSpeilzugFromList(inList, Up.Up, Direction.Down);
                    //}
                    //if (Down?.Value == 0 || Down?.Down?.Value == 1)
                    //{
                    //    AddSpeilzugToList(inList, Down.Down, Direction.Up);
                    //}
                    //if (Left?.Value == 0 || Left?.Left?.Value == 1)
                    //{
                    //    AddSpeilzugToList(inList, Left.Left, Direction.Right);
                    //}
                    //if (Right?.Value == 0 || Right?.Right?.Value == 1)
                    //{
                    //    AddSpeilzugToList(inList, Right.Right, Direction.Left);
                    //}
    
                    RemoveSpeilzugFromList(inList, Up?.Up, Direction.Down);
                    RemoveSpeilzugFromList(inList, Down?.Down, Direction.Up);
                    RemoveSpeilzugFromList(inList, Left?.Left, Direction.Right);
                    RemoveSpeilzugFromList(inList, Right?.Right, Direction.Left);
                }
                else if (Value == 0)
                {
                    if (Up?.Value == 1 && Up?.Up?.Value == 1)
                    {
                        AddSpeilzugToList(inList, Up.Up, Direction.Down);
                    }
                    if (Down?.Value == 1 && Down?.Down?.Value == 1)
                    {
                        AddSpeilzugToList(inList, Down.Down, Direction.Up);
                    }
                    if (Left?.Value == 1 && Left?.Left?.Value == 1)
                    {
                        AddSpeilzugToList(inList, Left.Left, Direction.Right);
                    }
                    if (Right?.Value == 1 && Right?.Right?.Value == 1)
                    {
                        AddSpeilzugToList(inList, Right.Right, Direction.Left);
                    }
                    RemoveSpeilzugFromList(inList, this, Direction.None);
                    RemoveSpeilzugFromList(inList, Up, Direction.Down);
                    RemoveSpeilzugFromList(inList, Down, Direction.Up);
                    RemoveSpeilzugFromList(inList, Left, Direction.Right);
                    RemoveSpeilzugFromList(inList, Right, Direction.Left);
                }
                return inList;
            }
    
            private LinkedList<Spielzug> RemoveSpeilzugFromList(LinkedList<Spielzug> inPlays, Field inField, Direction inDirection)
            {
                if (inField == null)
                {
                    return inPlays;
                }
    
                var tmpContains = inPlays.FirstOrDefault(inItem => inItem.Field == inField);
                if (tmpContains != null)
                {
                    tmpContains.Direction &= ~inDirection;
                    if (tmpContains.Direction == Direction.None || tmpContains.Field.Value != 1)
                    {
                        inPlays.Remove(tmpContains);
                    }
                }
                return inPlays;
            }
    
            private LinkedList<Spielzug> AddSpeilzugToList(LinkedList<Spielzug> inPlays, Field inField, Direction inDirection)
            {
                var tmpContains = inPlays.FirstOrDefault(inItem => inItem.Field == inField);
                if (tmpContains != null)
                {
                    tmpContains.Direction |= inDirection;
                }
                else
                {
                    inPlays.AddFirst(new Spielzug { Field = inField, Direction = inDirection });
                }
                return inPlays;
            }
        }
    
    
        /// <summary>
        /// Spielzug, welcher zum Sieg führt
        /// </summary>
        public class Spielzug
        {
            public Field Field { get; set; }
            
            public Direction Direction { get; set; }
        }
    
        [Flags]
        public enum Direction
        {
            None = 0,
            Up = 1,
            Down = 2,
            Left = 4,
            Right = 8
        }
    [Bild: Umextreme_sniper_fluttershy_by_speccysy_rechts_nach_links_sig_gr_sse.png] Bei Hardware gibt es kein eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: tfHoa3ooSEraFH63.png]
    Multithread ist offline

  6. #26 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    ^^Meine GUI läuft genauso, wie Du es vorhast. Es wird lediglich der Zug gespeichert. Also X/Y-Koordinate des Zuges und Richtung. Das läuft einwandfrei und man braucht bei der GUI lediglich pro Zug tatsächlich nur drei Positionen zu ändern. Den Start, der übersprungende Stein und das Ziel.
    http://forum.worldofplayers.de/forum...1#post25247069

    Ich denke, dass ist mittlerweile gut gelöst.

    Ich hänge derzeit mehr daran, die Lösung von Kellendil zu verstehen, dessen Rekursion so verflucht schnell ist. (Immerhin kann ich von meinem Code sagen, dass er verständlicher ist. ) Aber sein Code ist fast 15 mal so schnell.
    Sergej Petrow ist gerade online

  7. #27 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Auf einer Einsamen Insel
    Beiträge
    9.972
     
    Ok, das habe Ich nicht gesehen, Ich habe mich nur der 'lösung' geachtet, welche ein Dreidimensionales Array ist/war.
    [Bild: Umextreme_sniper_fluttershy_by_speccysy_rechts_nach_links_sig_gr_sse.png] Bei Hardware gibt es kein eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: tfHoa3ooSEraFH63.png]
    Multithread ist offline

  8. #28 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    Zitat Zitat von Multithread Beitrag anzeigen
    Ok, das habe Ich nicht gesehen, Ich habe mich nur der 'lösung' geachtet, welche ein Dreidimensionales Array ist/war.
    Ist jedenfalls wieder unglaublich spannend, wie ein an sich so kleines Problem so viele Problemfelder hervorrufen kann.
    Sergej Petrow ist gerade online

  9. #29 Zitieren
    Forschungsreisender  Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    3.622
     
    Zitat Zitat von Multithread Beitrag anzeigen
    [...]
    PS: Der Ansatz, welcher ewig und 3 Tage zum Durchlaufen braucht:
    [...]
    Puh, den habe ich mir noch gar nicht angucken können, nicht dass du dich übergangen fühlst, ist nicht so gemeint.

    Beim Überfliegen aufgefallen:
    Ganz grundsätzlich sind Listen ziemlich unperformant und verkettete Listen besonders unperformant, habe mir aber noch nicht angesehen, wie du die einsetzt. Innerhalb der Rekursion ist das jedenfalls nicht glücklich. Da wäre das höchste der Gefühle, ein Element anzuhängen. Aber dann muss der Speicher dafür schon vorher alloziiert sein. Sich da jedesmal einen Pointer vom Betriebssystem herausgeben zu lassen, welches noch irgendwelche Tabellen durchgehen muss, kann man sich kaum erlauben. Natürlich sind die API- bzw. Framework-Entwickler auch nicht doof und lassen sich gleich einen Pool reservieren. Aber irgendwann ist der ausgeschöpft. Also muss man eine entsprechend große Default-Größe angeben, falls das geht.

    Zitat Zitat von Sergej Petrow Beitrag anzeigen
    [...]
    Ich hatte übersehen, dass dein speichern(A,0) doch noch wichtig ist, habe es jetzt mit in die Loop gepackt, fixed. An der Sache, um die es geht, verändert es natürlich nichts, weshalb es in diesem Zusammenhang eigentlich irrelevant ist.

    Ich hänge derzeit mehr daran, die Lösung von Kellendil zu verstehen, dessen Rekursion so verflucht schnell ist. (Immerhin kann ich von meinem Code sagen, dass er verständlicher ist. ) Aber sein Code ist fast 15 mal so schnell.
    Dein alter Code, den ich übernommen und nur minimal verändert habe (die Formatierung täuscht!), ist doch ein paarmal so schnell wie seiner (Werte s.o.) und genauso verständlich wie deiner, denn es ist deiner. Die Unterschiede sind dermaßen minimal, dass du damit viel leichter herausfinden könntest, woran es liegt. Der Grund ist bei Kellendil derselbe wie bei mir, was mein letzter Beitrag übrigens darlegt. Aber ganz so schnell wollte ich nicht mit der Tür ins Haus fallen (nicht spoilern), weil du so gerne knobelst.
    jabu ist offline

  10. #30 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Auf einer Einsamen Insel
    Beiträge
    9.972
     
    Zitat Zitat von jabu Beitrag anzeigen
    Natürlich sind die API- bzw. Framework-Entwickler auch nicht doof und lassen sich gleich einen Pool reservieren. Aber irgendwann ist der ausgeschöpft. Also muss man eine entsprechend große Default-Größe angeben, falls das geht.
    Danke erstmal für den Hinweis.
    Nicht verkettete Listen in C# sind im Hintergrund ein Arrays, dessen Default Grösse 10 ist, sobald nun ein Element mehr als die Grösse des Arrays angefügt wird, wird das Array in ein neues Array kopiert, welches Doppelt so Gross ist wie das Vorherige.
    Auch die Default Grösse lässt sich angeben, in diesem Fall reichen 10 Elemente aber bereits aus.

    Und danke für den Hinweis mit denn Linked Listen, das wusste Ich noch nicht. Ich habe anfangs auch überlegt ein Dictionary zu verwenden, aber dafür ist die anzahl Elemente in der Liste zu niedrig.


    PS: Ich habe durch das Foreach jetzt mal etwas durchlaufen lassen: 336 965 984 Durchgänge in einigen Minuten. Das sind MEHR, als wenn man alle Möglichkeiten durchprobiert. Irgendwo muss Ich den Code verbockt haben, denn eigentlich müssten es Deutlich weniger sein. Die maximale Anzahl möglicher Steine mit Zügen im Solitär ist bei 7 oder 8 Stück, wobei fast immer ein Stein nur einen Möglichen Zug kennt.
    Und n<7 als Bedingung erreiche Ich nicht.

    Ich nehme auch nicht an, das es von Vorteil ist das ganze auf eine Queue umzustellen, da Ich dann mehr als Ein Spielfeld im Speicher halten müsste, andererseits wäre danach eine 2-8 Kern Multithread Implementation ein leichtes, für mehr sollte man dann auch mehr als eine Queue vorhalten(wegen den Locks). Solange aber die Grundlegende Performance nicht stimmt, macht sowas auch keinen Sinn
    [Bild: Umextreme_sniper_fluttershy_by_speccysy_rechts_nach_links_sig_gr_sse.png] Bei Hardware gibt es kein eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: tfHoa3ooSEraFH63.png]
    Multithread ist offline Geändert von Multithread (03.01.2017 um 11:58 Uhr)

  11. #31 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    Ja, da scheint wirklich ein Bock drin zu sein. Bei mir muss er die Rekursivmethode etwa 7,8 Mio mal aufrufen. Da ist zu 336 Mio Durchgängen noch viel Luft.

    EDIT:
    @Jabu
    Eine Idee hab ich jetzt, wie ich den Code schneller bekomme, aber ob das tatsächlich so viel ausmacht. Das wäre ja was. Habe gesehen, dass Du direkt deine Returnwerte in die Richtungsmethoden eingetragen hast ohne If-Abfrage. An sich viel logischer. Weiß gar nicht, warum ich das nicht gleich gemacht habe. Na, heute abend weiß ich mehr.

    EDIT2:
    Nein, das hat es nicht gebracht. Außer das der Code etwas kürzer wurde, kam nichts bei rum.
    Sergej Petrow ist gerade online Geändert von Sergej Petrow (03.01.2017 um 16:07 Uhr)

  12. #32 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     


    Yeahahey

    Ich hab es fast schon aufgegeben. Immer mal ein wenig probiert, aber wenn überhaupt nur winzige Verbesserungen oder teilweise auch völlig überraschende Verschlechterungen gefunden.

    Aber dann kam der Geistesblitz unter der Dusche. Und siehe da, von 7,7 Mio Aufrufe ist er auf 2.02 Mio Aufrufe runter.
    Das bedeutet in Sekunden: 0,00508 Sekunden. Kellendil braucht mit seinem letzten Code im Schnitt 0,0447 Sekunden. Hab mir dafür erlaubt, die Zeit mit dem gleichen Zeitmesser zu messen, mit dem ich meine Zeit gemessen habe. Damit ist mein Code 8 mal so schnell wie der von Kellendil. (Gemessen jeweils 100 Durchgänge)
    Das die Idee eine Verbesserung der Leistung ergeben musste, war mit klar. Das die aber so gravierend sein kann, hätte ich nie und nimmer erwartet. Dabei ist mein Code immer noch sehr gut lesbar.

    Für die Idee musste ich ein wenig was ändern.

    Für die vier Richtungsprüfungsmethoden oben, unten, rechts, links gibt es jetzt nur noch eine Richtungsprüfungsmethode. Dafür musste mit einer Richtungsangabe r (1 OBEN 2 UNTEN 3 RECHTS 4 LINKS) eingefügt werden. An sich ist das aber kein Zeitvorteil. Trotzdem war diese Änderung notwendig.

    Spoiler:(zum lesen bitte Text markieren)
    Code:
    	static boolean richtung(int A[][], int x, int y, int r)
    	{
    	switch (r)
    	{
    	case OBEN:
    		if ((y>1) && (A[x][y-1]==1) && (A[x][y-2]==0))return true;
    		else return false;
    	case UNTEN:
    		if ((y<5) && (A[x][y+1]==1) && (A[x][y+2]==0))return true;
    		else return false;
    	case LINKS:
    		if ((x>1) && (A[x-1][y]==1) && (A[x-2][y]==0))return true;
    		else return false;
    	case RECHTS:
    		if ((x<5) && (A[x+1][y]==1) && (A[x+2][y]==0))return true;
    		else return false;
    	default:
    		return false;
    	}
    }


    ebenso habe ich die Feldänderungen als Vorbereitung zum nächsten Soli Aufruf, als auch das Zurückändern, wenn ein Weg nicht funktioniert in jeweils eine Methode gepackt. Es war für die Hauptänderung nötig. Aber auch hier ist es an sich kein Zeitvorteil.

    Spoiler:(zum lesen bitte Text markieren)
    Code:
    	static void zug_zurueck(int A[][], int x, int y, int r)
    	{
    	switch (r)
    		{
    		case OBEN:
    			A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;
    			break;
    		case UNTEN:
    			A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;
    			break;
    		case LINKS:
    			A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;
    			break;
    		case RECHTS:
    			A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;
    			break;
    		default:
    		}
    	
    	}
    	
    	static void zug_aktuell(int A[][], int x, int y, int r)
    	{
    	switch (r)
    		{
    		case OBEN:
    			A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
    			break;
    		case UNTEN:
    			A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
    			break;
    		case LINKS:
    			A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
    			break;
    		case RECHTS:
    			A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
    			break;
    		default:
    		}
    	
    	}


    Aber was habe ich noch gemacht? Was war der Geistesblitz? Dieses mal dürft ihr ein wenig knobeln.
    Ein Hinweis am Rande. Es ist natürlich eine kleine, aber gravierende Änderung in der Rekursivmethode. Durch diese Änderung gibt es diesen enormen Geschwindigkeitszuwachs.

    Hier der vollständige Code:
    Spoiler:(zum lesen bitte Text markieren)

    Code:
    import java.awt.Color;
    import java.awt.Graphics;
    import java.awt.Graphics2D;
    
    
    import javax.swing.JFrame;
    
    public class Solit extends JFrame
    {
    
    	
    	private static final long serialVersionUID = -4382011225551225106L;
    	
    	final static int OBEN=1;
    	final static int UNTEN=2;
    	final static int LINKS=3;
    	final static int RECHTS=4;
    	
    	final static int KEIN_STEIN=0;
    	final static int STEIN=1;
    	
    	static int [][][] loesung= new int[1][7][7];
    	static Zug [] zug=new Zug[32];
    	static int currentStep=0;
    	static boolean zeichnen=false;
    	static boolean zugzeichnen=false;
    	static long zaehler=0;
    	
    	public Solit() 
    	{
    		super(); 
            setDefaultCloseOperation(EXIT_ON_CLOSE);  
            
            for (int i=0;i<32;i++)
            {
            	zug[i]= new Zug();
            }		
    
    	}
    	
    	
    	public void paint(Graphics gs) 
    	{ // @Override ermöglicht dem Compiler die Kontrolle
    		
    	Graphics2D g=(Graphics2D)gs;
    
    	int x,y;
    	int inhalt;
    
    	if(zeichnen)
    	{
    	g.setColor(Color.lightGray);
    	g.fillRect(0, 0, getWidth(), getHeight());
    	
    	{
    	for (y=0;y<7;y++)
    		{
    		for (x=0;x<7;x++)
    			{
    			inhalt=loesung[currentStep-1][x][y];
    		
    			if (inhalt == KEIN_STEIN)
    				{
    				g.setColor(Color.WHITE);
    				g.fillOval(x*100+150, y*100+150, 30, 30);
    				g.setColor(Color.BLACK);
    				g.drawOval(x*100+150, y*100+150, 28, 28);
    
    				}
    		
    			else if(inhalt == STEIN)
    				{
    				g.setColor(Color.GREEN);
    				g.fillOval(x*100+150, y*100+150, 30, 30);
    
    				}
    
    			}
    		}
    	}
    	}
    	
    	if(zugzeichnen)
    	{
    		switch (zug[currentStep-1].richtung)
    		{
    		case OBEN:
    			g.setColor(Color.WHITE);
    			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);			
    			g.setColor(Color.BLACK);
    			g.setColor(Color.lightGray);
    			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);			
    			g.setColor(Color.GREEN);
    			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-2)*100+150, 30, 30);			
    			break;
    			
    		case UNTEN:
    			g.setColor(Color.WHITE);
    			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);			
    			g.setColor(Color.BLACK);
    			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);			
    			g.setColor(Color.GREEN);
    			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+2)*100+150, 30, 30);			
    			break;
    
    		case LINKS:
    			g.setColor(Color.WHITE);
    			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.fillOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			g.setColor(Color.BLACK);
    			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.drawOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			g.setColor(Color.GREEN);
    			g.fillOval((zug[currentStep-1].x-2)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			break;
    
    		case RECHTS:
    			g.setColor(Color.WHITE);
    			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.fillOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			g.setColor(Color.BLACK);
    			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
    			g.drawOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			g.setColor(Color.GREEN);
    			g.fillOval((zug[currentStep-1].x+2)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
    			break;
    			
    		default:
    
    		}
    	}
     }
    
    	static void zug_zurueck(int A[][], int x, int y, int r)
    	{
    	switch (r)
    		{
    		case OBEN:
    			A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;
    			break;
    		case UNTEN:
    			A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;
    			break;
    		case LINKS:
    			A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;
    			break;
    		case RECHTS:
    			A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;
    			break;
    		default:
    		}
    	
    	}
    	
    	static void zug_aktuell(int A[][], int x, int y, int r)
    	{
    	switch (r)
    		{
    		case OBEN:
    			A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
    			break;
    		case UNTEN:
    			A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
    			break;
    		case LINKS:
    			A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
    			break;
    		case RECHTS:
    			A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
    			break;
    		default:
    		}
    	
    	}
    	
    	static boolean richtung(int A[][], int x, int y, int r)
    	{
    	switch (r)
    	{
    		case OBEN:
    		return (y>1) && (A[x][y-1]==1) && (A[x][y-2]==0);
    	        case UNTEN:
    		return (y<5) && (A[x][y+1]==1) && (A[x][y+2]==0);
    	        case LINKS:
    		return (x>1) && (A[x-1][y]==1) && (A[x-2][y]==0);
    	        case RECHTS:
    		return (x<5) && (A[x+1][y]==1) && (A[x+2][y]==0);
    
    	default:
    		return false;
    	}
    		
    		
    	}
    	
    	static void speichern(int A[][], int i)
    		{
    		for(int y=0;y<7;y++)
    			{
    			  for(int x=0;x<7;x++)
    				{
    				loesung[i][x][y]=A[x][y];
    				}
    			}
    		
    		}
    	
    	static void zug_speichern(int x, int y, int richtung, int zug)
    	{
    		Solit.zug[zug].x=x;
    		Solit.zug[zug].y=y;
    		Solit.zug[zug].richtung=richtung;
    	}
    	
    	static boolean  soli (int A[][], int i, int r1, int r2, int r3, int r4)
    	{
    	boolean inhalt;	
    	zaehler++;
    	if (i<31) 
    		{
    		i++;
    		for (int y=0;y<7;y++)
    			{
    			for (int x=0;x<7;x++)
    				{
    				if(A[x][y]==STEIN)
    				{	
    					if(richtung(A,x,y,r1))
    						{						
    						zug_aktuell(A,x,y,r1);
    						inhalt=soli(A,i,UNTEN,RECHTS,LINKS,OBEN);
    						if(inhalt) {
    							zug_speichern(x,y,r1,i);
    							return true;
    							}
    						else 
    							{
    							zug_zurueck(A,x,y,r1);
    							}
    						}
    					
    					if(richtung(A,x,y,r2))
    						{
    						zug_aktuell(A,x,y,r2);
    						inhalt=soli(A,i,LINKS,OBEN,UNTEN,RECHTS);
    						if(inhalt) {
    							zug_speichern(x,y,r2,i);
    							return true;
    							}
    						else 
    							{
    							zug_zurueck(A,x,y,r2);
    							}
    						}
    					
    					if(richtung(A,x,y,r3))
    						{
    						zug_aktuell(A,x,y,r3);
    						inhalt=soli(A,i,OBEN,LINKS,RECHTS,UNTEN);
    						if(inhalt) {
    							zug_speichern(x,y,r3,i);
    							return true;
    							}
    						else {
    							zug_zurueck(A,x,y,r3);
    							}
    						}
    				
    					if(richtung(A,x,y,r4))
    						{
    						zug_aktuell(A,x,y,r4);
    						inhalt=soli(A,i,RECHTS,UNTEN,OBEN,LINKS);
    						if(inhalt) {
    							zug_speichern(x,y,r4,i);
    							return true;
    							}
    						else {
    							zug_zurueck(A,x,y,r4);
    							}
    						}
    					}
    				}	
    				
    			}
    		i--;
    		return false;
    		}
    	else	
    		{
    		return true;
    		}
    
    	}
    
    	public static int[][] initialisierung(int A[][])
    	{
    		A = new int [][]{
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 },
                { 1,1,1,1,1,1,1 },
                { 1,1,1,0,1,1,1 },
                { 1,1,1,1,1,1,1 },
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 }		
            };
            
            return A;
    		
    	}
    	
    	public static void main(String[] args)
    	{
    		Solit f= new Solit();	
    		f.setSize(1000, 1000);
    		f.setVisible(true);
    
    		
    		int [][] A= new int [][]{
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 },
                { 1,1,1,1,1,1,1 },
                { 1,1,1,0,1,1,1 },
                { 1,1,1,1,1,1,1 },
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 }		
            };
        
    	
    	speichern(A,0);
    	
    	Zeitmesser.startZeitmessung(1);
    	for (int i=0;i<100;i++)
    	{
    	A=initialisierung(A);
    	soli(A,0,OBEN,UNTEN,LINKS,RECHTS);
    	}
    	System.out.println(Zeitmesser.getZeitmessung(1)/1000./100.);
    	Zeitmesser.stopZeitmessung(1);
    	System.out.println();
    	System.out.println(zaehler);
    
    	zeichnen=true;
    		currentStep++;
    		f.repaint();
    		try {
    			Thread.sleep(2000);
    		} catch (InterruptedException e) {
    			// TODO Auto-generated catch block
    			e.printStackTrace();
    		}
    	zeichnen=false;	
    	
    	zugzeichnen=true;
    	for (int i=1;i<32;i++)
    	{
    		currentStep++;
    		f.repaint();
    		try {
    			Thread.sleep(2000);
    		} catch (InterruptedException e) {
    			// TODO Auto-generated catch block
    			e.printStackTrace();
    		}
    	}
    }
    	
    	
    class Zug
    	{
    int x,y;
    int richtung;
    
    public Zug()
    	{
    	x=0;
    	y=0;
    	richtung=0;
    	}
    
    
    	
    	}
    
    }
    Sergej Petrow ist gerade online Geändert von Sergej Petrow (05.01.2017 um 00:08 Uhr)

  13. #33 Zitieren
    Forschungsreisender  Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    3.622
     
    Klingt interessant, junger Pardawan, und schön, dass Ihr Euch freut, doch ist Ihr Code bereits dreimal so schnell gewesen:
    Code:
        import java.awt.Color;
        import java.awt.Graphics;
        import java.awt.Graphics2D;
    
    
        import javax.swing.JFrame;
    
        public class Solit extends JFrame
        {
    
        	/**
        	 * 
        	 */
        	private static final long serialVersionUID = -4382011225551225106L;
        	
        	final static int OBEN=1;
        	final static int UNTEN=2;
        	final static int LINKS=3;
        	final static int RECHTS=4;
        	
        	final static int STEIN=1;
        	
        	static short [][][] loesung= new short[1][7][7];
        	static Zug [] zug=new Zug[32];
        	static int currentStep=0;
        	static boolean zeichnen=false;
        	static boolean zugzeichnen=false;
        	static long zaehler=0;
        	
        	public Solit() 
        	{
        		super(); 
                setDefaultCloseOperation(EXIT_ON_CLOSE);  
                
                for (int i=0;i<32;i++)
                {
                	zug[i]= new Zug();
                }		
    
        	}
        	
        	
        	public void paint(Graphics gs) 
        	{ // @Override ermöglicht dem Compiler die Kontrolle
        		
        	Graphics2D g=(Graphics2D)gs;
    
        	int x,y;
        	short inhalt;
    
        	if(zeichnen)
        	{
        	g.setColor(Color.lightGray);
        	g.fillRect(0, 0, getWidth(), getHeight());
        	
        	{
        	for (y=0;y<7;y++)
        		{
        		for (x=0;x<7;x++)
        			{
        			inhalt=loesung[currentStep-1][x][y];
        		
        			if (inhalt == 0)
        				{
        				g.setColor(Color.WHITE);
        				g.fillOval(x*100+150, y*100+150, 30, 30);
        				g.setColor(Color.BLACK);
        				g.drawOval(x*100+150, y*100+150, 28, 28);
    
        				}
        		
        			else if(inhalt == 1)
        				{
        				g.setColor(Color.GREEN);
        				g.fillOval(x*100+150, y*100+150, 30, 30);
    
        				}
    
        			}
        		}
        	}
        	}
        	
        	if(zugzeichnen)
        	{
        		switch (zug[currentStep-1].richtung)
        		{
        		case OBEN:
        			g.setColor(Color.WHITE);
        			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);			
        			g.setColor(Color.BLACK);
        			g.setColor(Color.lightGray);
        			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);			
        			g.setColor(Color.GREEN);
        			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-2)*100+150, 30, 30);			
        			break;
        			
        		case UNTEN:
        			g.setColor(Color.WHITE);
        			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);			
        			g.setColor(Color.BLACK);
        			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);			
        			g.setColor(Color.GREEN);
        			g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+2)*100+150, 30, 30);			
        			break;
    
        		case LINKS:
        			g.setColor(Color.WHITE);
        			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.fillOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			g.setColor(Color.BLACK);
        			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.drawOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			g.setColor(Color.GREEN);
        			g.fillOval((zug[currentStep-1].x-2)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			break;
    
        		case RECHTS:
        			g.setColor(Color.WHITE);
        			g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.fillOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			g.setColor(Color.BLACK);
        			g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
        			g.drawOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			g.setColor(Color.GREEN);
        			g.fillOval((zug[currentStep-1].x+2)*100+150, zug[currentStep-1].y*100+150, 30, 30);			
        			break;
        			
        		default:
    
        		}
        	}
         }
    
        	
        static boolean oben(short A[][], short x, short y)
        {
    
        if(y>1 && A[x][y]==1 && A[x][y-1]==1 && A[x][y-2]==0) return true;
            
        return false;
        }
    
        static boolean unten(short A[][], short x, short y)
        {
    
        if(y<5 && A[x][y]==1 && A[x][y+1]==1 && A[x][y+2]==0) return true;
            
        return false;
        }
    
        static boolean links(short A[][], short x, short y)
        {
    
        if(x>1 && A[x][y]==1 && A[x-1][y]==1 && A[x-2][y]==0) return true;
            
        return false;
        }
    
        static boolean rechts(short A[][], short x, short y)
        {
    
        if(x<5 && A[x][y]==1 && A[x+1][y]==1 && A[x+2][y]==0) return true;
            
        return false;
        }
    
        static void speichern(short A[][], int i)
            {
            for(int y=0;y<7;y++)
                {
                  for(int x=0;x<7;x++)
                    {
                    loesung[i][x][y]=A[x][y];
                    }
                }
            
            }
    
        static void zug_speichern(int x, int y, int richtung, int zug)
        {
            Solit.zug[zug].x=x;
            Solit.zug[zug].y=y;
            Solit.zug[zug].richtung=richtung;
        }
        
        static boolean  soli (short A[][], int i)
        {
        boolean inhalt;	
        zaehler++;
        if (i<31) 
            {
            i++;
            for (short y=0;y<7;y++)
                {
                for (short x=0;x<7;x++)
                    {
                    if(A[x][y]==STEIN)
                        {                         
                        if(links(A,x,y))
                            {
                            A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
                            inhalt=soli(A,i);
                            if(inhalt) {
                                zug_speichern(x,y,LINKS,i);
                                return true;
                            }
                        else {A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;}
                            }
                    
                        if(rechts(A,x,y)) 
                            {
                            A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
                            inhalt=soli(A,i);
                            if(inhalt) {
                            zug_speichern(x,y,RECHTS,i);
                            return true;
                            }
                        else {A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;}
                            }                           
    
                        if(oben(A,x,y)) 
                            {
                            A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
                            inhalt=soli(A,i);
                            if(inhalt) {
                                zug_speichern(x,y,OBEN,i);
                                return true;
                            }
                        else {A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;}						
                            }
    
                        if(unten(A,x,y))
                            {
                            A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
                            inhalt=soli(A,i);
                            if(inhalt) {
                                zug_speichern(x,y,UNTEN,i);
                                return true;
                            }
                        else {A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;}
                            }
                        }
                    }
                }
            i--;
            return false;
            }
        else	
            {
            return true;
            }
    
        }
    
        public static void main(String[] args)
        {
            Solit f= new Solit();	
            f.setSize(1000, 1000);
            f.setVisible(true);
    
            final long num = 100;
            long mean = 0;
            for (short i=0; i<num; i++) {
                final long startTime = System.nanoTime();
                short [][] A = new short [][]{
                    { 9,9,1,1,1,9,9 },
                    { 9,9,1,1,1,9,9 },
                    { 1,1,1,1,1,1,1 },
                    { 1,1,1,0,1,1,1 },
                    { 1,1,1,1,1,1,1 },
                    { 9,9,1,1,1,9,9 },
                    { 9,9,1,1,1,9,9 }		
                };
                speichern(A,0);
                soli(A,0);        
                long dT = (System.nanoTime() - startTime);
                mean += dT;
                System.out.format("Time:%1$12.3f \u00B5s - Z\u00e4hler:%2$8d%n", (double)dT/1000, zaehler);
                zaehler = 0;
            }
            mean /= num;
            System.out.format("--------------------\nMean:%1$12.3f \u00B5s%n", (double)mean/1000);
    
            zeichnen=true;
            currentStep++;
            f.repaint();
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            zeichnen=false;	
            
            zugzeichnen=true;
            for (int i=1;i<32;i++)
            {
                currentStep++;
                f.repaint();
                try {
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
        
        
        class Zug
            {
        int x,y;
        int richtung;
    
        public Zug()
            {
            x=0;
            y=0;
            richtung=0;
            }
    
    
            
            }
    
    }
    ...mit der winzigen Änderung, die bei Kellendil und mir von Anfang an drin ist (worum es in meinem länglichen Beitrag ging, der anhand der Messergebnisse in den Spoilern ein Wink mit dem Zaunpfahl gewesen ist)! Ich weiß also schon seit ein paar Tagen, woran es liegt. Außerdem wäre sonst in den Spoilern nicht die 20276 im Zähler. Wie hätte ich die sonst wissen können, da sie sich auch hier ergibt (mit den "2.02 Mio" hast du dich vielleicht verlesen).

    Was meinst du denn, warum ich einen Nanosekundentimer empfohlen habe? Weil ich längst auf so niedrige Zeiten herunter war und zwar vor einer Woche schon. Wenn du einen Millisekundentimer verwendest (sieht man hier nicht), dann springt der immer um Vielfache des Timer-Interrupt-Intervalls um und zeigt manchmal 0 an, wobei es in Wahrheit irgendwas unterhalb 15,625 ms sein kann (Standard unter Windows).

    Dann wären die Werte in diesem niedrigen Bereich manchmal beschönigt, was aber sofort anhand der geradzahligen Vielfachen des Intervalls auffällt. Dieses Problem hatte ich bereits vor einer Woche auf meinem alten Core2Duo mobile, weshalb ich eben auf einen Nanosekundentimer ausweichen musste, welcher seinen Takt von woanders abgeleitet bekommt (unter Windows vermutlich von der Kernelfunktion QueryPerformanceCounter, welche ihrerseits einen Takt aus den besten verfügbaren Quellen bezieht und daraus einen CPU-Takt emuliert, ja nach Hardware, manchmal mit reichlich Overhead. Aber das ist ein Thema für sich.).

    Wenn 1 ms an Auflösung genügt, kannst du einen Medienplayer im Hintergrund mitlaufen lassen. Denn solche lassen Windows das Interruptintervall (sozusagen der Herzschlag des Betriebssystems) auf 1 ms umprogrammieren. Das ist ein ganz brauchbarerer Workaround, der allerdings irgendwann auch nicht mehr reicht.
    jabu ist offline

  14. #34 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    Nein, verlesen habe ich mich nicht. Aber ich habe vergessen, den Wert durch 100 zu teilen. 20276 ist der richtige Wert.

    Also eigentlich ist in deinem Code meine Idee gar nicht drin. Also weiß ich noch immer nicht, woher deine Geschwindigkeit kommt.

    Meine Idee ist, dass ich dem Rechner bei seinem Weg etwas helfe. Es ist nicht wahrscheinlich, dass man den richtigen Weg hat, wenn man z.B. zwei mal in Folge nach oben springt. Wenn also beim ersten Aufruf der erste Weg ist, nach unten zu springen, dann steht beim nächsten Aufruf unten ganz unten, dafür steht dann oben ganz oben. Springt er in einem Aufruf nach rechts, steht beim nächsten mal die Prüfung links ganz oben, usw..
    Daraus resultiert mein Geschwindigkeitszuwachs.
    Sergej Petrow ist gerade online

  15. #35 Zitieren
    Forschungsreisender  Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    3.622
     
    Zitat Zitat von Sergej Petrow Beitrag anzeigen
    Nein, verlesen habe ich mich nicht. Aber ich habe vergessen, den Wert durch 100 zu teilen. 20276 ist der richtige Wert.
    Genau.

    Also eigentlich ist in deinem Code meine Idee gar nicht drin. Also weiß ich noch immer nicht, woher deine Geschwindigkeit kommt.
    Das ist ja gerade der Witz, auf den ich seit Tagen hinaus will, sozusagen Dreh- und Angelpunkt hier und zwar schon die ganze Zeit über. An deiner Idee liegt es nicht. Aber ihre konkrete Umsetzung bringt zufällig etwas mit, woran es liegt und zwar genau so wie bei Kellendil und mir. Warum ist der Code auf einmal so schnell? Es liegt an einem ganz trivialen Detail, dass es bei mir schon immer nur 20276 Durchgänge gewesen sind (für meine eigenen Benchmarks benutze ich inzwischen aber immer die Version mit dem Maximum). Deswegen habe ich dir deinen Code, eben mit dieser minimalen Veränderung versehen, einfach mal zurückgegeben.

    Meine Idee ist, dass ich dem Rechner bei seinem Weg etwas helfe. Es ist nicht wahrscheinlich, dass man den richtigen Weg hat, wenn man z.B. zwei mal in Folge nach oben springt. Wenn also beim ersten Aufruf der erste Weg ist, nach unten zu springen, dann steht beim nächsten Aufruf unten ganz unten, dafür steht dann oben ganz oben. Springt er in einem Aufruf nach rechts, steht beim nächsten mal die Prüfung links ganz oben, usw..
    Das Alternieren der Reihenfolge ist verstanden!

    Daraus resultiert mein Geschwindigkeitszuwachs.
    Nein, es sieht nur so aus als ob. Dabei hat sich zufällig ganz konkret etwas anderes verändert, woran es liegt. Und es ist mir voll bewusst.

    Deine Lösung macht deinen Code sogar noch langsamer: Der zusätzliche Aufwand übersteigt den Nutzen leider gewaltig! Es liegt an etwas anderem, worauf ich dich seit Tagen hinzuweisen versuche, allerdings mit dem Zaunpfahl gewedelt, deswegen jetzt mit dem ganz dicken Balken: Was so schnell ist, ist dein nahezu unveränderter Code, wie auch schon in meinem ersten Beitrag, als es noch um das GUI ging.

    Ich mache lieber kein Geheimnis darum, dass ich etwas in der Schublade habe, was noch schneller ist. Aber das können wir uns ansehen, nachdem dieses Rätsel gelöst ist.
    jabu ist offline

  16. #36 Zitieren
    Feind von neun Welten  Avatar von Sergej Petrow
    Registriert seit
    Jul 2005
    Beiträge
    28.125
     
    Klär mich auf. Habe keine Lust mehr, noch mehr Zeit zu investieren.
    Sergej Petrow ist gerade online

  17. #37 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Auf einer Einsamen Insel
    Beiträge
    9.972
     
    Zitat Zitat von jabu Beitrag anzeigen
    600 ms ist auf einem i7 eine halbe Ewigkeit. Trotzdem gute Arbeit!

    Mein noch unoptimiertes Beispiel dort oben ist auf einem alten Laptop (Core2DuoT6600@1,8GHz) locker im zweistelligen Millisekunden-Bereich für den ersten Durchgang und später, wenn der Optimierer endlich die Füße stillhält, bei 10...11 ms. Bei dir wäre das rund 2 ms. Dabei habe ich sogar zu meinen Ungunsten das Kopieren in den Ausgabepuffer für das GUI mitgemessen.

    Deine Rekursion ist schön schlank geworden, doch steckt dort noch ein kaum auffallender Performance-Bug drin, den ich bei mir mit als erstes entfernt habe. Wenn der bei dir draußen ist, kippst du vor Staunen aus den Latschen. Rate mal, woran es liegt...
    Es ist ja schön, das du versuchst das die Leute selber auf eine Lösung komme.
    ABER: Teilweise fehlen den anderen Personen dabei Mathematische Grundlagen oder anderes Spezifisches Wissen, welches du als Selbstverständlich ansiehst.
    Ich ziehe Hier mal das Beispiel mit der Kollisionsabfrage nach: Ich habe über mehrere WOchen Versucht zu Verstehen was du mir sagen willst, bis Ich ansatzweise eine Ahnung hatte was Ich machen muss, damit es geht. Und der Code war grösstenteils von woanders Kopiert. Denn obwohl Ich als Mathematisch Hochbegabt eingestufft werde , haben mir dort einige Grundlagen der Mathematik gefehlt, bzw. Fehlen eben immer noch zum Teil.

    Ich habe Heute morgen ne Stunde damit Verbracht die einzelnen Code Versionen miteinander zu Vergleichen, konnte aber den 'Essenziellen' Unterschied denn du ansprichst nirgendwo finden.

    Dass kann schnell dazu führen das es dem Gegenüber verleidet und es sich Frustriert etwas anderem zuwendet.

    Du schreibst selber das es kaum zu finden Ist, es wäre deshalb mehr als Nett wenn du uns aufklärst.

    Was es mit den 20276 auf sich hat, glaube Ich zu wissen, das ist die Anzahl Schleifendurchläufe bis eine Lösung gefunden wird, Ich komme aber nicht auf diese Zahl, egal was Ich mache, meine Minimale Anzahl Züge die Ich brauche sind 35 Milionen aufwärts, dafür brauche Ich dann knapp 1,5 Sekunden.

    Spoiler:(zum lesen bitte Text markieren)
    Code:
        class IterateAll
        {
            private int _x;
            private int _y;
    
            public List<Field> FieldList { get; set; } = new List<Field>();
            public List<Spielzug> inWiningPlays = new List<Spielzug>();
            public long roundaboutCount = 0;
    
            public IterateAll(int x, int y)
            {
                _x = x;
                _y = y;
    
                InizialisiereFelder();
            }
    
            /// <summary>
            /// Inizialisieren der Felder.
            /// </summary>
            private void InizialisiereFelder()
            {
                short[,] A = new short[,]{
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 },
                { 1,1,1,1,1,1,1 },
                { 1,1,1,0,1,1,1 },
                { 1,1,1,1,1,1,1 },
                { 9,9,1,1,1,9,9 },
                { 9,9,1,1,1,9,9 } };
    
                var tmpFieldArray = new Field[_x, _y];
                for (int y = 0; y < _y; y++)
                {
                    for (int x = 0; x < _x; x++)
                    {
                        tmpFieldArray[x, y] = new Field { X = x, Y = y };
                        tmpFieldArray[x, y].Value = A[x, y];
    
                        if (tmpFieldArray[x, y].Value == 9)
                        {
                            continue;
                        }
    
                        //An die Feldliste anfügen, wir brauchen das Array dann nicht mehr
                        FieldList.Add(tmpFieldArray[x, y]);
    
                        //Elemente Verlinken
                        if (x > 0)
                        {
                            tmpFieldArray[x, y].Left = tmpFieldArray[x - 1, y];
                            tmpFieldArray[x - 1, y].Right = tmpFieldArray[x, y];
                        }
                        if (y > 0)
                        {
                            tmpFieldArray[x, y].Up = tmpFieldArray[x, y - 1];
                            tmpFieldArray[x, y - 1].Down = tmpFieldArray[x, y];
                        }
                    }
                }
                FieldListCount = FieldList.Count;
            }
            private int FieldListCount;
    
            private bool links(Field A)
            {
                return (A.Left?.Value == 1) && (A.Left?.Left?.Value == 0);
            }
            private bool rechts(Field A)
            {
                return (A.Right?.Value == 1) && (A.Right?.Right?.Value == 0);
            }
            private bool oben(Field A)
            {
                return (A.Up?.Value == 1) && (A.Up?.Up?.Value == 0);
            }
            private bool unten(Field A)
            {
                return (A.Down?.Value == 1) && (A.Down?.Down?.Value == 0);
            }
    
            public int Resolve(int n)
            {
                if (n > 30) return -1;
                n++;
    
                //Ergebnis Prüfen
                var ergebnis = 0;
                for (var tmpX = 0; tmpX < FieldList.Count; tmpX++)
                {
                    var tmpField = FieldList[tmpX];
                    if (tmpField.Value != 1)
                    {
                        continue;
                    }
                    roundaboutCount++;
                    if (oben(tmpField))
                    {
                        tmpField.Value = 0; tmpField.Up.Value = 0; tmpField.Up.Up.Value = 1;
                        ergebnis = Resolve(n);
                        if (ergebnis == -1)
                        {
                            inWiningPlays.Add(new Spielzug { Field = tmpField, Direction = Direction.Up });
                            return -1;
                        }
                        else if (ergebnis == -2)
                        {
                            tmpField.Value = 1; tmpField.Up.Value = 1; tmpField.Up.Up.Value = 0;
                        }
                    }
    
                    if (unten(tmpField))
                    {
                        tmpField.Value = 0; tmpField.Down.Value = 0; tmpField.Down.Down.Value = 1;
                        ergebnis = Resolve(n);
                        if (ergebnis == -1)
                        {
                            inWiningPlays.Add(new Spielzug { Field = tmpField, Direction = Direction.Down });
                            return -1;
                        }
                        else if (ergebnis == -2)
                        {
                            tmpField.Value = 1; tmpField.Down.Value = 1; tmpField.Down.Down.Value = 0;
                        }
                    }
    
                    if (links(tmpField))
                    {
                        tmpField.Value = 0; tmpField.Left.Value = 0; tmpField.Left.Left.Value = 1;
                        ergebnis = Resolve(n);
                        if (ergebnis == -1)
                        {
                            inWiningPlays.Add(new Spielzug { Field = tmpField, Direction = Direction.Left });
                            return -1;
                        }
                        else if (ergebnis == -2)
                        {
                            tmpField.Value = 1; tmpField.Left.Value = 1; tmpField.Left.Left.Value = 0;
                        }
                    }
    
                    if (rechts(tmpField))
                    {
                        tmpField.Value = 0; tmpField.Right.Value = 0; tmpField.Right.Right.Value = 1;
                        ergebnis = Resolve(n);
                        if (ergebnis == -1)
                        {
                            inWiningPlays.Add(new Spielzug { Field = tmpField, Direction = Direction.Right });
                            return -1;
                        }
                        else if (ergebnis == -2)
                        {
                            tmpField.Value = 1; tmpField.Right.Value = 1; tmpField.Right.Right.Value = 0;
                        }
                    }
                }
                return -2;
            }
        }
    [Bild: Umextreme_sniper_fluttershy_by_speccysy_rechts_nach_links_sig_gr_sse.png] Bei Hardware gibt es kein eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: tfHoa3ooSEraFH63.png]
    Multithread ist offline

Seite 2 von 2 « Erste 12

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •