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

Java - Grafik

  1. #21 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    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
    Sergej Petrow
    Gast
    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.
    Geändert von Sergej Petrow (31.12.2016 um 14:25 Uhr)

  3. #23 Zitieren
    Knight Commander Avatar von Kellendil
    Registriert seit
    Jul 2009
    Beiträge
    2.093
    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
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    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
    Crystal Empire
    Beiträge
    11.228
    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: AMD_Threadripper.png] Bei Hardware gibt es keine 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: i6tfHoa3ooSEraFH63.png]
    Multithread ist gerade online

  6. #26 Zitieren
    Sergej Petrow
    Gast
    ^^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.

  7. #27 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Crystal Empire
    Beiträge
    11.228
    Ok, das habe Ich nicht gesehen, Ich habe mich nur der 'lösung' geachtet, welche ein Dreidimensionales Array ist/war.
    [Bild: AMD_Threadripper.png] Bei Hardware gibt es keine 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: i6tfHoa3ooSEraFH63.png]
    Multithread ist gerade online

  8. #28 Zitieren
    Sergej Petrow
    Gast
    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.

  9. #29 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    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
    Crystal Empire
    Beiträge
    11.228
    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: AMD_Threadripper.png] Bei Hardware gibt es keine 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: i6tfHoa3ooSEraFH63.png]
    Multithread ist gerade online Geändert von Multithread (03.01.2017 um 11:58 Uhr)

  11. #31 Zitieren
    Sergej Petrow
    Gast
    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.
    Geändert von Sergej Petrow (03.01.2017 um 16:07 Uhr)

  12. #32 Zitieren
    Sergej Petrow
    Gast


    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;
    	}
    
    
    	
    	}
    
    }
    Geändert von Sergej Petrow (05.01.2017 um 00:08 Uhr)

  13. #33 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    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
    Sergej Petrow
    Gast
    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.

  15. #35 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    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
    Sergej Petrow
    Gast
    Klär mich auf. Habe keine Lust mehr, noch mehr Zeit zu investieren.

  17. #37 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Crystal Empire
    Beiträge
    11.228
    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: AMD_Threadripper.png] Bei Hardware gibt es keine 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: i6tfHoa3ooSEraFH63.png]
    Multithread ist gerade online

  18. #38 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.322
    Zitat Zitat von Multithread Beitrag anzeigen
    Es ist ja schön, das du versuchst das die Leute selber auf eine Lösung komme.
    Finde ich tatsächlich sehr wichtig, um sich weiterzuentwickeln. Beispielsweise habe ich nie irgendwelche konkrete Hilfe gehabt, ganz egal bei welchen technischen Problemstellungen. Ich bin damit immer alleine gewesen und musste irgendwie sehen, wie ich zurechtkomme, was dann bedeutete, dass ich mich einarbeiten musste. Wenn ich zunächst irgendetwas von irgendwoher übernommen hatte, ohne es zu verstehen, war ich unzufrieden, denn ich wusste, dass ich im Zweifel nicht in der Lage wäre, ein ähnliches Problem selbst zu lösen, wenn es mal darauf ankommt. Also verschaffte ich mir mehr Methodenkompetenz als konkretes Wissen.

    Wenn man einmal dieses Mindset hat (wie ich es in meiner Jugend zwangsläufig entwickeln musste (kein Internet, kaum gescheite Bücher, technikfeindliche Schule (sprachliche Ausrichtung) und Umgebung)), sich selber zu helfen, dann kommen die Lösungen irgendwie irgendwann fast von selbst. Das heißt natürlich nicht, dass die einem zufallen würden, sondern man braucht meistens nur Ansatzpunkte, damit irgendwann der Groschen fällt. Und mit der Macht des Ansatzes steigt der Erlös. Ohne Anstrengung geht es natürlich nicht, bin kein Überflieger.

    ABER: Teilweise fehlen den anderen Personen dabei Mathematische Grundlagen oder anderes Spezifisches Wissen, welches du als Selbstverständlich ansiehst.
    Tatsächlich halte ich einige Grundlagen für ziemlich erwartbar (nicht für selbstverständlich), denn ich befinde mich hier, im Vergleich mit mir, ausnahmslos zwischen Leuten mit höherem sozialen Status und teilweise auch Bildungsgrad, die es eigentlich besser wissen sollten, zumal ein gewisses Grundlagenwissen und eine ingenieursmäßige Arbeitsweise zu deren Berufsbild gehört. Warum sollte ich ausgerechnet denjenigen so wenig zutrauen? Für meinen Teil mag ich so kleine Rätsel, die mich auf eine Fährte bringen, doch sehr. Aber vielleicht schließe ich da zu viel von mir auf andere. So weit, das in jedem Fall zu erwarten, gehe ich gar nicht, weil es jedem sein eigenes Bier ist, wofür er sich interessiert und wofür nicht, was ich selbstverständlich respektiere.
    Es kann dich trotzdem enttäuschen, wenn du merkst, dass selbst Offensichtliches nicht mal durchgelesen wurde. Dann fühlt es sich für mich falsch an, den Gegenstand dessen auch noch auf dem silbernen Tablett zu servieren.

    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.
    Mit Vektorkomponenten rechnest du nicht anders als mit anderen Zahlen auch. Innerhalb deiner Engine musstest du sowieso die Grundrechenarten, die Quadratwurzel und die Winkelfunktionen benutzen. Nichts anderes machst du mit den Vektorkomponenten. Der Unterschied besteht in der abstrakteren Betrachtungsweise, indem man die Komponenten gemeinsam behandelt.
    Das verschafft dir eine strukturiertere und sicherere Betrachtungs- und Vorgehensweise, bei der im Rahmen gleichwertiger Operationen so manche problematische Winkelfunktionen und Quadratwurzeln durch Grundrechenarten ersetzt werden können, was dazu führt, dass einige Probleme mit Mehrdeutigkeiten, Polstellen, Definitionslücken und Fließkommaauflösung wegfallen. Performance, Genauigkeit, Robustheit, Lesbarkeit/Wartbarkeit und Wiederverwendbarkeit werden verbessert. Der nächste Schritt ist vielleicht eine 3D-Engine, bei der diese Betrachtungen ihre Gültigkeit behalten!
    Ich habe bei dir weniger Probleme bei den Vektoren an sich vermutet, sondern bei zu wenig Erfahrung im Umstellen von mathematischen Ausdrücken, z.B. von Gleichungen, was vielleicht an der Schule gelegen haben kann. Wenn dort etwas fehlt, ist mitunter schwer nachzuvollziehen, warum der Ausdruck in der nächsten Zeile mit der aktuellen gleichbedeutend ist, sodass man irgendwann nicht mehr folgen kann. Allerdings möchte man auch verstehen, warum diese doch ziemlich elegante und knappe Lösung, auf die es hinausläuft, korrekt ist.
    Ich hatte ja nicht nur die Umformungen angebracht, sondern dazu auch noch die gleichbedeutenden grafischen Interpretationen, sodass man sich die Vektoren vorstellen kann, weshalb es dann notfalls auch ohne die Äquivalenzumformungen nachvollziehbar gewesen wäre, wobei es natürlich besser ist, beides gleichermaßen durchzuspielen.
    Sicher hat man dazu nicht immer Zeit und Ruhe und Nerv und was weiß der Geier. Vielleicht hast du trotzdem einen Fuß in die Tür bekommen. Wenn einer schon Grafik- oder Spieleengines programmiert, dann sollte die Beschäftigung mit Vektorrechnung eine lohnende Investition sein, von der man lange zehren kann. Du hast ja gesehen, wie elegant und knapp die Lösung ist. Vielleicht siehst du auch, wie offensichtlich sie eigentlich ist, wenn man erst mal diese Perspektive eingenommen hat. Dabei kann man gerade wegen des Abstraktionslevels viel leichter die Korrektheit einsehen, was mit einem Wust an einzelnen Winkelfunktionen gar nicht so leicht machbar wäre.
    Aber nein, man bekommt das nicht geschenkt. Und wenn man wieder aus der Materie raus ist, braucht man etwas Zeit, um sich hineinzuversetzen. Das ist doch alles ganz normal, zumindest bei mir.

    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.
    Der ist viel einfacher gemeint, als du es bei mir vielleicht erwartest. Man müsste bloß genauer hingucken. Es hat nichts mit Java, Programmierung oder Mathematik (im engeren Sinne) zu tun. Ich wollte es auch gar nicht so hoch gehängt haben. Vielmehr war das als harmlose Neckerei von mir gedacht, mehr nach dem Motto: "Wer sieht es?"
    Um es aufzulösen: Die Priorisierung der durchzuprobierenden Richtungen ist natürlich anders und zwar nicht mehr eine der, nur von der Wahrscheinlichkeit her (kein bewiesenes Faktum), ungünstigsten. Dann käme die nächste Quizfrage: "Warum?"
    Es ist aber vollkommen in Ordnung, dass Sergej eine der ungünstigen nimmt, weil man damit besser testen kann. Seine neuerliche Lösung, deren zugrundeliegende Idee ich übrigens für klug halte, hat viel mit dem Problem zu tun. Letztendlich ist diese allgemeiner und damit systematisch besser. Trotzdem hätte man eigentlich sehen dürfen, dass die Reihenfolge sich grundlegend unterscheidet, wenn man schon so tief eintaucht.

    Dass kann schnell dazu führen das es dem Gegenüber verleidet und es sich Frustriert etwas anderem zuwendet.
    Ich mag diese Neckereien, die gar nicht böse gemeint sind, ganz im Gegenteil (sondern konstruktiv).

    Du schreibst selber das es kaum zu finden Ist, es wäre deshalb mehr als Nett wenn du uns aufklärst.
    Ne, ist wohl ein Missverständnis. Es ist eine Kleinigkeit, die man zwar leicht übersehen kann, aber sie ist eben trotzdem trivial und leicht zu finden, wenn man gut hinguckt, bzw. müsste man sich das als Möglichkeit eigentlich so schon gedacht haben, wenn man so tief einsteigt, s.o.

    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.
    Das ist ja gerade das Problem, welches ich meine. Es wird nicht richtig hingeguckt, obwohl man immerhin so tief im Problem drinsteckt, dass man sich an irgendwas stört.
    Es handelt sich natürlich um die Anzahl an rekursiven Aufrufen der Funktion und nicht um die der Schleifendurchläufe. Deswegen ist das bei dir gar nicht so unplausibel.



    Ich hatte vor einigen Wochen jeweils eine Antwort für dich und für Sergej vorbereitet, aber dann fehlte mir die Ruhe (habe noch so einiges an Messungen gemacht), also hier wenigstens auszugsweise aus den groben Entwürfen:

    Dieses sollte an dich (Multithread) gehen:
    Zitat Zitat von Multithread Beitrag anzeigen
    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. [...]
    Da helfe ich doch gerne mit Referenzmaterial aus:
    In einem Anfall an Wahnsinn habe ich alle 4*3*2*1=24 (kurz: 4!) Kombinationsmöglichkeiten der Reihenfolgen für {oben, unten, links, rechts} durchprobiert, was folgende unterschiedliche Zählerstände (es kommen trotz der 24 verschiedenen Reihenfolgen nur die drei vor) für die Aufrufe der rekursiven Funktion ergeben hat:
    Code:
       20 276
       20 279
    7 667 770
    Inkrementiert wurde mit jedem Eintritt in die rekursive Funktion, nicht mit probierten Zügen. Also sind alle erfolglosen Fährten mitgezählt und auch der eine Durchgang am Schluss.

    Die Anzahl der Schleifendurchgänge innerhalb der rekursiven Funktion ist natürlich größer (jeweils aufsteigend sortiert):
    Nur Durchgänge mit besetzten Positionen:
    Code:
        97 976
        97 986
    38 770 477
    Nur Durchgänge mit Positionen des Spielfeldes:
    Code:
        668 662
        668 563
    253 035 857
    Alle Durchgänge über das gesamte 7x7-Array (incl. Padding in den Ecken):
    Code:
        992 707
        992 854
    375 719 903
    Also sollten deine Zahlen schon passen, zumindest von der Größenordnung her. Es dauert bei dir bloß länger.


    Dieses ist ein Auszug aus dem Entwurf (noch teils zu umständlich formuliert), was an Sergej gehen sollte:
    Zitat Zitat von Sergej Petrow Beitrag anzeigen
    Klär mich auf. Habe keine Lust mehr, noch mehr Zeit zu investieren.
    Es lag natürlich von vornherein an der Reihenfolge der Auswertung (4! = 4*3*2*1 unterschiedliche Möglichkeiten):
    Code:
     1. Time: 2462194,351 µs - Zähler: 7667770 //oben,unten,links,rechts //was du ursprünglich hattest
     2. Time: 2458672,295 µs - Zähler: 7667770 //oben,unten,rechts,links
     3. Time: 2448552,681 µs - Zähler: 7667770 //oben,rechts,unten,links
     4. Time: 2450758,400 µs - Zähler: 7667770 //oben,rechts,links,unten
     5. Time: 2520070,777 µs - Zähler: 7667770 //oben,links,rechts,unten
     6. Time: 2506109,938 µs - Zähler: 7667770 //oben,links,unten,rechts
     7. Time: 2507313,354 µs - Zähler: 7667770 //unten,oben,links,rechts
     8. Time: 2538674,964 µs - Zähler: 7667770 //unten,oben,rechts,links
     9. Time: 2656885,043 µs - Zähler: 7667770 //rechts,oben,unten,links
    10. Time: 2684068,060 µs - Zähler: 7667770 //rechts,oben,links,unten
    11. Time:    8716,950 µs - Zähler:   20276 //links,oben,rechts,unten
    12. Time:    8835,472 µs - Zähler:   20279 //links,oben,unten,rechts
    13. Time:    8779,011 µs - Zähler:   20279 //unten,links,oben,rechts
    14. Time: 3434770,091 µs - Zähler: 7667770 //unten,rechts,oben,links
    15. Time: 3464988,479 µs - Zähler: 7667770 //rechts,unten,oben,links
    16. Time:    9044,518 µs - Zähler:   20276 //rechts,links,oben,unten
    17. Time:    8847,605 µs - Zähler:   20276 //links,rechts,oben,unten //was ich dir gepostet hatte
    18. Time:    9367,420 µs - Zähler:   20279 //links,unten,oben,rechts
    19. Time:    8810,275 µs - Zähler:   20279 //unten,links,rechts,oben
    20. Time:    9106,579 µs - Zähler:   20279 //unten,rechts,links,oben
    21. Time:    9563,401 µs - Zähler:   20276 //rechts,unten,links,oben
    22. Time:    9274,096 µs - Zähler:   20276 //rechts,links,unten,oben
    23. Time:    8663,755 µs - Zähler:   20276 //links,rechts,unten,oben
    24. Time:    9261,031 µs - Zähler:   20279 //links,unten,rechts,oben
    Mit dieser direkten Korrelation zwischen Zeiten und Funktionsaufrufen dürfte auf der Hand liegen, dass es für die Zeiten nicht besonders darauf ankommt (für weitere Optimierungen u.U. schon), ob einige Richtungen unnötig abgeprüft werden (sonst müsste mehr Varianz drin sein), sondern vielmehr darauf, dass man unglückliche Fährten vermeidet. Je später sie abreißen und je mehr sich davon vordrängelt, desto mehr wurde verschenkt.

    Es ist nicht grundsätzlich schlimm, als nächstes noch einmal dieselbe Richtung abprüfen, weil die unnötigen Checks vor dem Funktionsaufruf stattfinden und damit die Rekursionstiefe nicht erhöhen (sonst müsste dein Code die Beispiele aus o.g. Liste unterbieten können). Aber mit der Herabstufung der Wiederholung hast du einen wichtigen Punkt getroffen (s.u.)!

    Doch gibt es noch diese Eigenschaft zu berücksichtigen, was sozusagen eine "faule" und damit schnellere Lösung über eine statische Priorisierung ermöglicht:

    Feststellung:
    Weil das Spielbrett symmetrisch ist, kann die Richtung als solche keine Rolle spielen, sondern nur ihr Bezug zu den anderen Richtungen sowie ihr Bezug zur Laufrichtung, wobei die Betrachtung der Laufrichtung im Gegensatz zu den Richtungen untereinander nicht nur ein in sich geschlossenes System bildet, sondern auch äußere Relevanz hat, weshalb es sich lohnen sollte, dort anzusetzen.

    Kernpunkt:
    Wenn ein Feld, von oben links ausgehend, zeilenweise abgetastet wird, dann werden die Steine tendenziell nach unten und nach rechts getrieben, weil das die ersten Möglichkeiten sind. Bei dieser Neigung spielt es in erster Linie keine Rolle, welche Richtungen man zuerst abprüft, den unmögliche Richtungen führen nicht zu Funktionsaufrufen.
    Die ersten möglichen liegen aber zuerst unten und dann rechts, was dazu führt, dass hinter sich abgeräumt wird und das Feld diagonal von oben links nach unten rechts zusammengetrieben wird.
    Und nun kommt die Gefahr: Ich treibe das Feld ohne Not auseinander, obwohl es auch andere Sprungmöglichkeiten gibt!
    Was wäre also am dümmsten, wenn ich nichts anderes weiß? Die Steine prioritär nach oben zu treiben, wo mit größerer Wahrscheinlichkeit alles leer ist, sodass der Anschluss verloren wird! Also vermeide ich das.

    Bei den anderen Richtungen lässt sich das nicht mehr so leicht sagen, nur als Beispiel: Wenn ich prioritär nach links treibe, so habe ich, obwohl das gegen die Richtung geht, unten immer noch viele Steine und gerade nach links hin geeignete Lücken. Dann kommt noch die Geometrie hinzu, sodass sich sichere Aussagen auf dieser Ebene nicht mehr treffen lassen. Selbst die Annahme, dass "oben" schädlich ist, beschreibt eben wegen der Geometrie, welche die Muster wesentlich manipuliert (Sie stellt in erster Linie Inhibitoren für Richtungen dar, was in zweiter Linie über die dadurch erzeugten Muster die Chancen massiv manipuliert.), nur eine tendenzielle Wahrscheinlichkeit. Sicher ist da also gar nichts, aber es sollte eben öfter zum Erfolg führen, die unglücklichste Variante "oben" schon mal in der Priorität herabzustufen.

    Es ist ein wenig Glück dabei, dass es hier bereits genügt, die Prioritäten zu ordnen und die Wiederholungen durchaus zuzulassen, zumal sie nicht notwendigerweise denselben Stein betreffen. Jedoch wenn sie ihn betreffen, kann damit das Feld auseinandergetrieben werden, weshalb deine Lösung darüber eine Funktion erfüllen könnte, welche über die Vermeidung von "oben" evtl. hinausgeht, was zu zeigen wäre, denn so einfach ist es nicht, z.B. wenn mehrere Steine parallel nach rechts getrieben werden, ist das erst mal gut (doch gibt es "Unfälle"?). Und wenn es nicht weiter nach rechts geht, ist es ebenfalls gut, sie nach unten zu treiben. Nach links ist es wohl eher riskant. Es ist wohl mehr Hirnschmalz nötig, um zu allgemeinen Aussagen zu kommen, wobei die spezielle Geometrie die leider angreift.

    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.
    Stimme zu: Wie wir inzwischen gesehen haben, ist das im speziellen Fall "oben" sogar richtig, da es das Feld recht wahrscheinlich zerfallen lässt.

    Wenn es nach unten oder nach rechts geht, sollte das, allgemein gesprochen, selten etwas ausmachen, nach links jedoch schon eher. Aber gut, wenn man es allgemein vermeidet, hat man auf jeden Fall auch für "oben" das Risiko mitreduziert und vielleicht auch woanders. Aus allgemeiner Sicht hast du wohl eine gute Idee. Man müsste sie performanter umsetzen.

    Was mich daran wirklich interessiert: Die Trefferwahrscheinlichkeit, wenn man sie zufällig in alle möglichen Konstellationen umstellt, so wie ich es mit den 24 (s.o.) gemacht habe. Wenn du damit 100 % erreichst, bist du wirklich weiter. Doch fehlte mir bisher die Zeit dafür, die alle durchzuprobieren. Man müsste das automatisieren, zeigen oder beweisen (bei Misserfolg, wie weit es greift). Denn deine Lösung hat großes Potential, ein Auseinanderdriften des Feldes zu vermeiden, andererseits geschieht dieses nicht notwendigerweise in jedem Fall, eben wegen der Vorzugsrichtung. Dafür passiert es bei mir eben nur statisch.

    Grob zusammengefasst:
    Meine Variante: "oben" immer herabstufen, genügt
    Deine Variante: "zweimal dasselbe" herabgestufen, genügt

    Ich gebe zu, dass mir der allgemeinere Charakter deiner Variante zusagt, denn meine nimmt etwas vorweg, was man nicht unbedingt wissen kann. Man müsste deine irgendwie performanter umsetzen.



    Nun möchte ich auch nicht vorenthalten, was bei mir entstanden ist (nicht perfekt, aber vllt. interessant):
    Und zwar hatte ich die Rekursion aufgelöst und das zweidimensionale Array zu einem eindimensionalen linearisiert, damit es noch schneller geht (insgesamt ungefähr doppelt so schnell).
    Dazu habe ich noch das GUI verfeinert, etwas Anpassbarkeit eingebracht und einigermaßen berücksichtigt, was die Doku zur Threading-Problematik mit dem Event Dispatch Thread besagt.
    Erklärende Kommentare sind auch eingefügt.
    Code:
    import java.awt.*;
    import javax.swing.JComponent;
    import javax.swing.JFrame;
    import javax.swing.JPanel;
    import javax.swing.RepaintManager;
    import javax.swing.SwingUtilities;
    
    
    public class Solit
    {
        // Constants
        // ================================================================================================
        //
        // This block allows adjustments, feel free to modify.
        private static final String appTitle = new String("Solitaire-bfs (brute-force search) v0.10alpha");
        private static final String textLine1 = new String("GUI initialization took [\u00B5s]: "); 
        private static final String textLine2 = new String("Calculations took, mean [\u00B5s]: ");
        private static final int interval  = 1500;
        private static final int numIters  = 1000;
        private static final int boardSizY =  740;
        private static final int boardSizX =  740;
        private static final int boardPadY =  110;
        private static final int boardPadX =  110;
        private static final int boardOfsY =    6;
        private static final int boardOfsX =    0;   
        private static final int tokenDiam =   62;
        private static final int tokenOuterPercentage = 10;
        private static final Color tokenInnerColor = new Color(63, 255, 128);
        private static final Color tokenOuterColor = new Color(8, 32, 16);
        private static final Color tokenUnsetColor = new Color(110, 128, 96);   
        private static final Color fieldColor = new Color(110, 110, 96);
        private static final Color boardColor = new Color(192, 192, 160);
        private static final Font textFont = new Font(Font.MONOSPACED, Font.BOLD, 17);
        private static final Color textColor = new Color(0, 0, 0);
        private static Object antialiasMode = RenderingHints.VALUE_ANTIALIAS_ON;//ON/OFF/DEFAULT
        //
        // This block can be modified, but keep it consistent.
        private static final int nMoves      =   31;  // must fit to initBoard
        private static final int fieldNumY   =    7;  // must fit to initBoard
        private static final int fieldNumX   =    7;  // must fit to initBoard
        private static final int boardPosBegin = 10;  // must fit to initBoard
        private static final int boardPosEnd  =  61;  // must fit to initBoard
        private static final int OFS_RIGHT = 1;          // must fit to initBoard
        private static final int OFS_LEFT = -OFS_RIGHT;  // must fit to initBoard
        private static final int OFS_DOWN = 8;           // must fit to initBoard
        private static final int OFS_UP = -OFS_DOWN;     // must fit to initBoard  
        private static final int[] initBoard = new int[]{
            9,9,9,9,9,9,9,9,
            9,9,1,1,1,9,9,9,
            9,9,1,1,1,9,9,9,
            1,1,1,1,1,1,1,9,
            1,1,1,0,1,1,1,9,
            1,1,1,1,1,1,1,9,
            9,9,1,1,1,9,9,9,
            9,9,1,1,1,9,9,9,
            9,9,9,9,9,9,9,9
        };  // must keep symbols 0,1,9
        //
        // Here the prioritization of the moves can be adjusted.
        private static final int OFS_DIR1 = OFS_LEFT;
        private static final int OFS_DIR2 = OFS_RIGHT;
        private static final int OFS_DIR3 = OFS_UP;
        private static final int OFS_DIR4 = OFS_DOWN;
        //
        // Do not modify these (hopefully) compile time calculations.
        private static final int boardStartY = boardPadY + boardOfsY;
        private static final int boardStartX = boardPadX + boardOfsX;
        private static final int tokenRadius = tokenDiam / 2;
        private static final int tokenRingThnes = tokenOuterPercentage * tokenRadius / 100;
        private static final int tokenInnerDiam = tokenDiam - (2 * tokenRingThnes);
        private static final int tokenStepY  = (boardSizY - (2 * boardPadY)) / (fieldNumY - 1);
        private static final int tokenStepX  = (boardSizX - (2 * boardPadX)) / (fieldNumX - 1);
        private static final int nBoards = nMoves + 1;
        
        // Variables, shared by threads
        // ================================================================================================
        // These are written by main thread an read by event dispatch thread, so asynchronous
        // access is forbidden (under some conditions, except for strings (immutable under Java).
        // To guarantee this, invokeAndWait does the cheap trick for us.
        private static String strAppInitTime; 
        private static String strCalculationTime;
        private static int boardNum;
        private static int[][][] fields = new int[nBoards][fieldNumY][fieldNumX];
        
        // Variables, used only in main thread
        // ================================================================================================
        // These arrays hold the moves as temporary results and have been introduced to avoid
        // unfavorable code positioning caused by improper optimizations for shared r/w access.
        private static int[] lastDir_ext = new int[nBoards];
        private static int[] lastX_ext = new int[nBoards];
     
        // Nested classes
        // ================================================================================================
        //
        // Simple timer class
        private static class Timer
        {
            public void start() {
                startTime = System.nanoTime();
            }
            public long getElapsedTimeMicroseconds() {
                return (System.nanoTime() - startTime) / cf;
            }  
            public long getElapsedTimeMilliseconds() /*unused*/ {
                return (System.nanoTime() - startTime) / (cf * cf);
            }
            private long startTime;
            private final static long cf = 1000;
        }
        //
        // Benchmark class, contains brute-force algorithm
        // -------------------------------------------------------------------
        private final class Benchmark
        {
            private final void moveDo(int[] A, int x, int offset) {
                A[x] = 0; A[x+offset] = 0; A[x+(offset*2)] = 1;
            }
            private final boolean moveTry(int[] A, int x, int offset) {
                return ((A[x+offset] == 1) && (A[x+(offset*2)] == 0));
            }
            private final void moveUndo(int[] A, int x, int offset) {
                A[x] = 1; A[x+offset] = 1; A[x+(offset*2)] = 0;
            }
            //
            // Brute-force algorithm, works with a twofold stack
            private boolean doBruteForce() {
                int[] A = new int[initBoard.length];
                System.arraycopy(initBoard, 0, A, 0, A.length);
                int[] lastDir = new int[nBoards];
                int[] lastX = new int[nBoards];
                int move = 0;
                int lastDirLock = 0;
                int x = boardPosBegin;
                next:
                while (move < nMoves) {         
                    while (x < boardPosEnd) {
                        if (A[x] != 1) {
                            x++;
                            continue;
                        }
                        if ((lastDirLock < 1) && moveTry(A, x, OFS_DIR1)) {
                            moveDo(A, x, OFS_DIR1);                  
                            move++;
                            lastDir[move] = 1;
                            lastX[move] = x;
                            x = boardPosBegin;
                            lastDirLock = 0;
                            continue next;
                        }
                        if ((lastDirLock < 2) && moveTry(A, x, OFS_DIR2)) {
                            moveDo(A, x, OFS_DIR2);                   
                            move++;
                            lastDir[move] = 2;
                            lastX[move] = x;
                            x = boardPosBegin;
                            lastDirLock = 0;               
                            continue next;
                        }
                        if ((lastDirLock < 3) && moveTry(A, x, OFS_DIR3)) {
                            moveDo(A, x, OFS_DIR3);
                            move++;
                            lastDir[move] = 3;
                            lastX[move] = x;
                            x = boardPosBegin;
                            lastDirLock = 0;
                            continue next;
                        } 
                        if ((lastDirLock < 4) && moveTry(A, x, OFS_DIR4)) {
                            moveDo(A, x, OFS_DIR4);               
                            move++;
                            lastDir[move] = 4;
                            lastX[move] = x;
                            x = boardPosBegin;
                            lastDirLock = 0;
                            continue next;
                        }
                        lastDirLock = 0;
                        x++;
                    }
                    // no move found on whole board
                    x = lastX[move];
                    lastDirLock = lastDir[move];
                    int dirOfs = 0;
                    switch(lastDirLock) {
                    case 1: dirOfs = OFS_DIR1; break;
                    case 2: dirOfs = OFS_DIR2; break;
                    case 3: dirOfs = OFS_DIR3; break;
                    case 4: dirOfs = OFS_DIR4; break;
                    }
                    moveUndo(A, x, dirOfs);
                    move--;
                }
                // save moves from stack to static arrays
                System.arraycopy(lastDir, 0, lastDir_ext, 0, nBoards);
                System.arraycopy(lastX, 0, lastX_ext, 0, nBoards);
                return true;
            }
            //
            // Run Benchmark
            public long run(long num) {
                System.out.printf("Time:\n-----\n");
                long sum = 0;
                for (long i = 0; i < num; i++) {
                    timer.start();
                    doBruteForce();          
                    final long time = timer.getElapsedTimeMicroseconds();
                    sum += time;
                    final char delimiter = (((i + 1) % 5) == 0) ? '\n' : '\t';
                    System.out.printf("%7d \u00B5s%c", time, delimiter);
                }
                final long mean = sum / num;            
                System.out.printf("\nMean:%5d \u00B5s", mean);
                return mean;            
            }
            
            private Timer timer = new Timer();
        } 
        //
        // Presentation class, provides functions for running GUI
        // -------------------------------------------------------------------
        private final class Presentation
        {
            //
            // translates moves to states and stores each of them in a board
            private void fillOneBoardPerMove() {
                int[] tmp = new int[initBoard.length];
                System.arraycopy(initBoard, 0, tmp, 0, initBoard.length);
                for (int n = 0; n < nBoards; n++) {
                    int idx = lastX_ext[n];
                    int dirOfs = 0;
                    switch(lastDir_ext[n]) {
                    case 1: dirOfs = OFS_DIR1; break;
                    case 2: dirOfs = OFS_DIR2; break;
                    case 3: dirOfs = OFS_DIR3; break;
                    case 4: dirOfs = OFS_DIR4; break;
                    }
                    tmp[idx] = 2; tmp[idx+dirOfs] = 2; tmp[idx+(dirOfs*2)] = 1;
                    for (int y = 0; y < fieldNumY; y++) {
                        for(int x = 0; x < fieldNumX; x++) {
                            fields[n][y][x] = tmp[(y+1) * (fieldNumX + 1) + x];
                        }
                    }
                    tmp[idx] = 0; tmp[idx+dirOfs] = 0;
                }
            }
            //
            // creates the GUI by constructing the frame class
            // within the event dispatch thread (EDT),
            // as recommended for thread safety,
            // then waits for full completion,
            // because otherwise the threads would overlap,
            // which would lead to illegal access and timing
            private void buildGui(long mean) throws Exception {          
                strCalculationTime = textLine2 + mean;
                Timer timer = new Timer();
                timer.start();
                SwingUtilities.invokeAndWait(new Runnable() {
                    public void run() {
                        gFrame = new Frame(appTitle);
                    }
                });
                strAppInitTime = textLine1 + timer.getElapsedTimeMicroseconds();
            }
            //
            // plays animation within the EDT
            private void playAnimation(long timeToNextMove) throws Exception {
                boardNum = 0;
                for (int n = 0; n < nBoards; n++) {
                    boardNum = n;
                    SwingUtilities.invokeAndWait(new Runnable() {
                        public void run() {
                            gFrame.repaint();
                        }
                    });
                    Thread.sleep(timeToNextMove);
                }
            }
            
            private Frame gFrame;
        }
        //
        // GUI, runs within EDT
        // -------------------------------------------------------------------
        private class Frame extends JFrame
        {
            Frame(String title) {
                super(title);
                RepaintManager.currentManager(this).setDoubleBufferingEnabled(true);
                this.setIgnoreRepaint(true);
                this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                this.add(new Panel());
                this.pack();
                this.setVisible(true);
            }
        }
        //
        private class Panel extends JPanel
        {
            Panel() {
                super();
                this.setDoubleBuffered(true);
                this.setBackground(boardColor);
                this.setOpaque(true);
            }
            
            @Override
            public Dimension getPreferredSize() {
                return new Dimension(boardSizX, boardSizY);
            }
            
            @Override
            public void paintComponent(Graphics g) {
                super.paintComponent(g);
                Graphics2D g2d = (Graphics2D)g;
                g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, antialiasMode);
                Paint oldPaint = g2d.getPaint();        
                for (int y = 0; y < fieldNumY; y++) {
                    for (int x = 0; x < fieldNumX; x++) {
                        if(fields[boardNum][y][x] == 9) {
                            continue;
                        }
                        final int posX = (x * tokenStepX) + boardStartX - tokenRadius;
                        final int posY = (y * tokenStepY) + boardStartY - tokenRadius;
                        switch (fields[boardNum][y][x]) {
                        case 0:
                            g2d.setColor(fieldColor);
                            g2d.fillOval(posX, posY, tokenDiam, tokenDiam); 
                            break;
                        case 1:
                            g2d.setColor(tokenOuterColor);
                            g2d.fillOval(posX, posY, tokenDiam, tokenDiam);
                            g2d.setColor(tokenInnerColor);
                            g2d.fillOval(posX+tokenRingThnes, posY+tokenRingThnes,
                                         tokenInnerDiam, tokenInnerDiam);
                            Paint p = new GradientPaint(posX + tokenRadius, posY,
                                                        new Color(1.0f, 1.0f, 1.0f, 0.4f),
                                                        posX + tokenRadius, posY + tokenDiam,
                                                        new Color(0.0f, 0.0f, 0.0f, 0.4f));
                            g2d.setPaint(p);
                            g2d.fillOval(posX, posY, tokenDiam, tokenDiam);
                            g2d.setPaint(oldPaint);
                            break;
                        case 2:
                            g2d.setColor(tokenUnsetColor);
                            g2d.fillOval(posX, posY, tokenDiam, tokenDiam); 
                            break;
                        }
                    }
                }
                g2d.setColor(textColor);
                g2d.setFont(textFont);
                g2d.drawString(strAppInitTime, 10, 24);
                g2d.drawString(strCalculationTime, 10, 50);
            }
        }
    
        // ================================================================================================
        // Start
        //
        // program entry point
        public static void main(String[] args) throws Exception {
            new Solit();
        }
        //
        // Constructor of the global instance
        Solit() throws Exception {
            Benchmark benchmark = new Benchmark();
            final long mean = benchmark.run(numIters);
            Presentation presentation = new Presentation();
            presentation.fillOneBoardPerMove();
            presentation.buildGui(mean);
            presentation.playAnimation(interval);
        }   
    }
    TODO: Man könnte noch etwas anders damit umgehen, wie Methoden Zustände manipulieren, die nicht ihren Klassen gehören, z.B. indem man ihnen zugehörige Referenzen übergibt. Und bei der Konfigurierbarkeit ist noch Luft nach oben, z.B. könnte man die Schrift noch automatisch mitskalieren lassen, auch was ihre Positionierung angeht.

    Manches, was sich objektorientierter lösen ließe, habe ich teils wegen der leichteren Nachvollziehbarkeit und teils wegen der Performance schlicht gehalten bzw. wieder dahingegehend rückgängig gemacht.
    jabu ist offline Geändert von jabu (10.02.2017 um 16:51 Uhr)

Seite 2 von 2 « Erste 12

Berechtigungen

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