Seite 3 von 3 « Erste 123
Ergebnis 41 bis 51 von 51

Sudoku

  1. #41 Zitieren
    Auserwählter
    Registriert seit
    Jul 2017
    Beiträge
    6.532
    Ah, ok, das spart natürlich Zeit. Allerdings nicht genügend. Habe das jetzt auch mit Quicksort getestet. Auch da hänge ich bei etwa 950 ms rum. Wobei die auch im ungünstigsten Falle, der allerdings selten ist n², hat.

    Deine Quizfrage verstehe ich nicht ganz. So erstmal betrachtet würde ich sagen, dass beide gleich schnell sind. Es würde mich doch jetzt wundern, wenn das Rausziehen der Zählvariabeländerung ein Vorteil bringt.
    Stiller Leser ist offline

  2. #42 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Crystal Empire
    Beiträge
    11.228
    Vermutlich ist die !=0 Prüfung schneller, weil es dafür ggf. spezielle Einheiten auf der CPU gibt, welche das in einem Takt machen.
    [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 offline

  3. #43 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.328
    Zitat Zitat von Stiller Leser Beitrag anzeigen
    Ah, ok, das spart natürlich Zeit. Allerdings nicht genügend. Habe das jetzt auch mit Quicksort getestet. Auch da hänge ich bei etwa 950 ms rum. Wobei die auch im ungünstigsten Falle, der allerdings selten ist n², hat.
    Ohne es einzeln zu messen, weißt du nicht genug, um eine solche Aussage zu treffen. Außerdem hast du durch das Sortieren der Nullstellen die Abarbeitungsreihenfolge geändert, weshalb das jetzt zufällig länger dauern kann (wovon auszugehen ist). Das ist aber kein Nachteil, sondern du hattest bei deiner neuen Abarbeitungsreihenfolge (aka "Spaltenlösung") mit 116,5 ms einen Zufallsfund. Solche Funde habe auch ich immer wieder, wenn ich bei mir die Reihenfolge ändere (in Grenzen kann ich das, nur nicht so flexibel wie bei dir). Sie haben aber keine Aussagekraft hinsichtlich einer Verbesserung. Denn der Löser weiß vorher nicht, was günstiger ist. Das weiß man erst nachher, was Wissen ist, welches auf der Lösung selbst basiert und daher nicht gilt.

    Wenn man nachher die glücklichste Abarbeitungsreihenfolge herauspicken dürfte, dann läge meine Lösung bei knapp über 2 ms, also 50 mal so schnell wie deine "Spaltenlösung", auf meiner alten Hardware. Aber es wäre Selbstbeschiss. Solches habe ich hier nicht zum Vergleich angeboten, nicht dass du das meinst. Das war schon dieselbe Reihenfolge wie bei dir. Erst mit der "Spaltenlösung" sowie mit dem Sortieren ändert sich die.

    Ich zitiere mich wieder einmal selbst:
    Du meinst hoffentlich nicht das Sortieren, sondern die gesamte Zeit. Das Sortieren sollte man vielleicht extra messen. Es ist erwartbar, dass die "bestmögliche" (nach dem noch sehr simplen Kriterium) Sortierung nicht so gute Ergebnisse wie ein glücklicher Zufallsfund bringt (es gibt innerhalb der Menge der möglichen Sudokus immer beide Sudokus, wie für Zeilen- und Spaltenlösung günstig oder ungünstig hingedreht), was völlig normal wäre. Aber wenn sie die Zeiten durchschnittlich verbessert (wobei es darauf ankäme, wie dieser Durchschnitt gebildet wird), dann hast du schon was gewonnen. Zufall ist keine Leistung, geht aber mit in den Durchschnitt ein. Wenn du von 3,85 s auf 954 ms runter bist, dann ist das ein Indiz für einen besseren Durchschnitt, der vorher bei ca. ((3,85 + 0,116) / 2) s = 1,98 s lag (Indiz, weil man nur den Durchschnitt von zwei Fällen hat und die anderen Auswirkungen nicht kennt). Wenn das repräsentativ wäre, könntest du sagen, dass du die Zeiten halbiert hast.

    Tatsächlich ist dein Wert von 950 ms besser als das, was du vorher hattest (einmal 116,5 ms und einmal 3,85 s). Der Durchschnitt ist besser. Da kommt die dumme Lösung nicht mehr ganz mit. 116,5 ms ist ein ganz falscher Vergleichswert. Aber du hast noch zu wenig getestet, um das als repräsentativ gelten zu lassen (tun wir aber mal so als ob).

    Deine Quizfrage verstehe ich nicht ganz. So erstmal betrachtet würde ich sagen, dass beide gleich schnell sind. Es würde mich doch jetzt wundern, wenn das Rausziehen der Zählvariabeländerung ein Vorteil bringt.
    Das kann sogar unter speziellen Umständen etwas bringen (nicht, weil es nicht im Kopf steht, sondern weil die Reihenfolge anders ist), aber es stimmt, dass es darum nicht geht. Der Effekt wäre viel zu winzig, zu selten beobachtbar, also nicht "grundsätzlich"...

    Zitat Zitat von Multithread Beitrag anzeigen
    Vermutlich ist die !=0 Prüfung schneller, weil es dafür ggf. spezielle Einheiten auf der CPU gibt, welche das in einem Takt machen.
    Gewissermaßen richtig. "Spezielle Einheiten" klingt aber, gemessen an dem simplen Detail, etwas zu hochtrabend, weswegen dein Hinweis hoffentlich keine falschen Fährten legt. Daher ergänze ich mal: Tatsächlich konnten das bereits CPUs aus der Steinzeit (als es noch keinen PC gab). Es handelt sich um eine ganz elementare "Optimierung", die zu sinnvoll und einfach ist, um darauf verzichten zu wollen, nur welche?
    jabu ist offline

  4. #44 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
    Gewissermaßen richtig. "Spezielle Einheiten" klingt aber, gemessen an dem simplen Detail, etwas zu hochtrabend, weswegen dein Hinweis hoffentlich keine falschen Fährten legt.
    Da kann Ich nur raten.
    Ich kenne zwar gewisse CPU Tricks, aber nur von der Software Seite her.

    Vermutlich hat es etwas mit einem boolean vergleich zu tun.
    [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 offline

  5. #45 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.328
    Zitat Zitat von Multithread Beitrag anzeigen
    Da kann Ich nur raten.
    Ich kenne zwar gewisse CPU Tricks, aber nur von der Software Seite her.
    Du kennst vermutlich längst Cache-Lokalität. Aber man denkt nicht immer daran. Und Software ist das hier auch, würde ich mal so sagen, ist wohl alles eine Frage der Perspektive.

    Vermutlich hat es etwas mit einem boolean vergleich zu tun.
    Irgendwie ist "alles" ein Vergleich. Diese High-Level-Ebene ist nicht gemeint (wobei boolean das auch ausnutzen kann).

    Wink mit dem Zaunpfahl (du hast es eigentlich schon, nur mal konkret): Fast alle CPUs haben ein besonderes Register...
    jabu ist offline

  6. #46 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
    Du kennst vermutlich längst Cache-Lokalität.

    Wink mit dem Zaunpfahl (du hast es eigentlich schon, nur mal konkret): Fast alle CPUs haben ein besonderes Register...
    Ich glaube du unterschätzt mit welcher Sprache Ich gelernt habe zu Programmieren.
    C und C++ sowie andere HW nahe Sprachen standen da nie auf dem Programm.

    Ja, Ich kenne die Cache Lokalitäten: Auf meiner ebene sind das L1-L4 und RAM, wobei L4 bisher nur bei Intel und der Xbox1 vorzufinden ist (eSRam on Chip).
    Und Ich weiss das L1 meist 50/50 aufgeteilt ist in Instruction und Data Cache.

    Von Registern und deren ggf. Speziellen (abseits von Read/Write) Funktionen habe Ich keine Ahnung.
    Für mich reicht es, das Ich weiss das die Prüfung gegen 0 schneller ist, auch wenn das andere auch spannend sein kann
    [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 offline

  7. #47 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.328
    Zitat Zitat von Multithread Beitrag anzeigen
    Ich glaube du unterschätzt mit welcher Sprache Ich gelernt habe zu Programmieren.
    C und C++ sowie andere HW nahe Sprachen standen da nie auf dem Programm.
    Wenn es um Sprachen geht (geht es eigentlich nicht, es geht um Hardware):
    Erst bei Assemblersprachen wirst du darauf gestoßen. C und C++ sind High-Level-Sprachen, welche von der Maschine abstrahieren (damit man die nicht mehr kennen muss und den Code portieren kann). Dort ist das Interesse ebenso freiwillig wie bei Java oder C#.

    Man lernte diese Sache mit der Null (wenn man aufmerksam war) zum Beispiel in der guten alten Zeit, um einen modernen Videorekorder oder einen CD-Spieler reparieren zu dürfen. Plötzlich waren Computer aus der Unterhaltungselektronik nicht mehr wegzudenken.

    Also musste auch vermittelt werden (das war damals noch der Anspruch), wie eine CPU in Grundzügen funktioniert. Ein Computer ist eine Maschine zum Manipulieren von Daten, wie wir alle wissen. Also muss das auch irgendwo geschehen. Die Daten müssen an so eine Stelle, die das ermöglicht, geladen werden und von dort aus zurückgeschrieben werden können. Diese Stelle ist üblicherweise durch ein Register realisiert. Register gibt es viele. Dieses besondere in der Arithmetisch-logischen Einheit (ALU) heißt Akkumulator, wohin das Datenwort zwecks Manipulation, Auswertung oder Zwischenspeicherung (oder einer Kombination daraus) geladen wird.

    Um den Wert zu verrechnen, wird ein weiteres Register verwendet, wobei der Akkumulator das Ergebnisregister einer Operation ist. Beispielsweise wird in Register A (der Akkumulator) der Wert 42 geladen und in Register B ein weiterer Wert. Nun wird Subtraktion angewendet: Wert von A - Wert von B (Assembler: sub ax,bx). Das Ergebnis steht in Register A (bzw. ax). Vielleicht will man nicht nur das Ergebnis irgendwo hinschreiben, sondern eine Entscheidung fällen, um den Programmfluss verzweigen zu können (if, Schleife etc.). Das geht aber nicht alleine anhand des Wertes. Vielleicht will man wissen, ob beide Werte gleich groß sind. Nun kann man eine ALU bauen, die das schnell ausrechnen kann, man kann aber auch das Ergebnis der Subtraktion auf Null prüfen, was sich ganz leicht ohne zusätzliche Takte bewerkstelligen lässt, wenn man das Ergebnis schon einmal hat.

    Solche und ähnliche Auswertungen zeigt das Statusregister sowieso an. Und das ist auch schon der Trick. Sobald ein Wert im Akkumulator liegt, ist ohnehin bekannt, ob er Null ist. Bezüglich einer gewöhnlichen For-Schleife bedeutet das, dass der Wert zuvor dekrementiert wurde und immer noch im Akkumulator liegt. Die Auswertung bzgl. Null ist also ein kostenloses Abfallprodukt, wenn man so will. Speziell hier ist es (nicht grundlos) etwas anders, indem der Wert zuerst geprüft und dann dekrementiert wird.
    Die Gefahr, dass der Vergleichswert in ein anderes Register geladen werden muss, besteht demnach nicht. Zwar kann der Wert manchmal in einem Register vorgehalten werden, aber dann stünde dieses Register anderen Berechnungen bzw. temporären Werten nicht mehr zur Verfügung.
    Vieviele Takte der Vergleich dauert, ist eine Frage der CPU, während das Nullbit (zero flag) keine Frage der CPU ist, denn es wurde schon bei uralten CPUs instantan ausgewertet, da es sich um ein einfaches NOR(Bits{0...n}) handelt. Wenn also nur ein einziges Bit gesetzt ist, dann liefert das Gatter Null, sodass das Nullbit nicht gesetzt ist. Ein großes (schnelles) Logikgatter mit genügend Eingängen genügt theoretisch.

    Moderne CPUs können mehr, es sollte hier um die Grundzüge gehen, um die Sache übersichtlich zu halten.

    Ja, Ich kenne die Cache Lokalitäten: Auf meiner ebene sind das L1-L4 und RAM, wobei L4 bisher nur bei Intel und der Xbox1 vorzufinden ist (eSRam on Chip).
    Und Ich weiss das L1 meist 50/50 aufgeteilt ist in Instruction und Data Cache.
    Also weißt du doch einiges über CPUs.

    Edit:
    Hier ging es natürlich um Cache-Lokalität im Sinne von Lokalitätsausnutzung. Wenn das Nullbit abgefragt wird, entstehen solche Probleme erst gar nicht. Die zweitschnellste Lösung ist Vergleich mit einer echten Konstante (wo das geht), welche sich (idealerweise) im Instruction Cache befindet, der sowieso gerade ausgelesen wird. Die drittschnellste Lösung ist, dass der Wert nicht weit weg auf dem Stack liegt, innerhalb derselben Cache-Line. Die i.d.R. langsamste Lösung ist, den Wert aus myArrayList.length hervorzukramen (wenn er nicht wegen Operationen auf dem Array glücklicherweise und teils zufällig mit in derselben Cache-Line liegt). Wenn man den Wert nicht wenigstens noch mal dicht an der Schleife (bzw. im Schleifenkopf) zwischenspeichert, dann ist man darauf angewiesen, dass es der Compiler für einen tut. Falls nicht, wird die Abarbeitung also mit einiger Wahrscheinlichkeit (nicht, wenn er eh günstig gecacht ist (was oft vorkommt, aber nicht verlässlich ist), sonst definitiv) langsamer ausfallen (nicht selten mit Unterschieden zwischen den Durchgängen).

    Von Registern und deren ggf. Speziellen (abseits von Read/Write) Funktionen habe Ich keine Ahnung.
    Für mich reicht es, das Ich weiss das die Prüfung gegen 0 schneller ist, auch wenn das andere auch spannend sein kann
    Es kommt wie so oft auf die Umstände an:

    Es gibt auch Programmierer, die nicht ganz überwiegend aus höheren Konstrukten etwas noch Höheres zusammenbauen (Anwendungsprogrammierung), sondern eben diese Konstrukte, die du verwendest (Bibliotheksfunktionen) entwerfen. Und die müssen wirklich alles an Tempo herausquetschen.
    Manche entwerfen Algorithmen für Audiofilter, Videofilter, Packer, Entpacker, Renderer, Hochfrequenz-Börsenhandel, Simulationen, Compiler...

    Es geht hier doch nur um das Bewusstsein und nicht etwa darum, auch alles umzusetzen, wovon man weiß. Das wäre auch gar nicht gut. Erst mal ist es wohl wichtig, dass der Code den beabsichtigten Zweck ausdrückt. Solche Optimierungen sind in Geschäftsumfeldern meistens unnötig, aber darum geht es bei einem Lösungsalgorithmus auch nicht, denn der soll schnell sein. Das Thema ist also mehr eines von Algorithmen und Datenstrukturen, was eines der wichtigsten Themen der Informatik (weniger der Anwendungsprogrammierung) ist, woran dann eben auch die effiziente Implementierung hängt. Wenn man etwas davon versteht, hat das auch wenig mit Probieren zu tun (am Rande schon, aber alles kommt von Erkenntnissen, weniger vom Zufall). Und Stiller Leser hat schon richtig angemerkt, dass der Sortieralgorithmus nicht der effizienteste ist. Man könnte jetzt einen fertigen nehmen, oder man könnte was lernen (worum es geht) und das selber machen. Ob die von der Logik her schnelleren auch physisch schneller sind und was das bringt und warum, kann eine interessante Frage sein.
    jabu ist offline Geändert von jabu (09.07.2018 um 14:39 Uhr) Grund: Abschnitt zu Lokalitätsausnutzung hinzugefügt

  8. #48 Zitieren
    Auserwählter
    Registriert seit
    Jul 2017
    Beiträge
    6.532
    Zitat Zitat von jabu Beitrag anzeigen
    Und Stiller Leser hat schon richtig angemerkt, dass der Sortieralgorithmus nicht der effizienteste ist. Man könnte jetzt einen fertigen nehmen, oder man könnte was lernen (worum es geht) und das selber machen. Ob die von der Logik her schnelleren auch physisch schneller sind und was das bringt und warum, kann eine interessante Frage sein.
    Ich habe jetzt noch den Mergealgorithmus probiert. Da habe ich sogar noch Zeitverluste hinnehmen müssen. Bei dem liege ich bei knapp 1200 ms. An sich ist der laufzeitmäßig über alle Fälle günstiger. da er selbst im Worstcase kein n² als Laufzeit hat. Aber hier kann man sehr schön sehen, dass es halt noch andere Dinge gibt. Wir haben die Funktionsweisen der ganzen Sortiermöglichkeiten damals alle mal im Studium behandelt.

    Zudem gibt es ein Problem. Ich habe bei meinen ersten Sortiermethoden hier ein einfaches Intarray genommen. Auf Dauer war mir das zu nervig. Jetzt habe ich der Koordinatenklasse noch eine Int-Variable gestiftet, die nachher die Menge der besetzten Stellen erfasst, wenn der gespeicherte Wert eine 0 beinhaltet. Ist also jetzt alles in Nullstellen drin. Aber es stehen natürlich drei werte jetzt drin, x,y und besetzt, die jeweils bei der zuweisen i[j]=blabla übertragen werden oder wo nur die Adresse übertragen wird.

    Was ich am liebsten hätte, wäre, dass ich nur das besetzt-Array sortiere und wenn das sortiert ist, übertrage ich das auf das nullstellenarray. Leider ist das nur ein Wunsch (bisher), weil ich keine Ahnung hab, wie ich das anstellen soll. Das Problem ist ja, dass wenn das besetztarray sortiert ist, ich nicht mehr weiß, welches besetzt[i] zu welcher nullstelle[j] gehört.
    Stiller Leser ist offline

  9. #49 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.328
    @Stiller Leser
    Das hier von dir hat noch einen kleinen Fehler:
    Code:
    int hilf;
    Koordinaten hilf2;
        
    for (int i = besetzt_nullstellen.length - 1; i > 0; i--) {
        for (int j = 1; j < besetzt_nullstellen.length - 1; j++) { 
            if (besetzt_nullstellen[j-1] < besetzt_nullstellen[j]) { 
                hilf = besetzt_nullstellen[j]; 
                besetzt_nullstellen[j] = besetzt_nullstellen[j - 1]; 
                besetzt_nullstellen[j - 1] = hilf; 
                hilf2=nullstellen2[j];
                nullstellen2[j] = nullstellen2[j - 1]; 
                nullstellen2[j - 1] = hilf2; 
            } 
        }
    }
    Hast du ihn schon gefunden?

    Zitat Zitat von Stiller Leser Beitrag anzeigen
    Ich habe jetzt noch den Mergealgorithmus probiert. Da habe ich sogar noch Zeitverluste hinnehmen müssen.
    Scheint zu passen.

    Werte bei mir für 1 Mio. Sortierdurchgänge (brutto, steckt ein System.arraycopy zum Zurücksetzen je Durchgang mit drin, jedoch ohne Mitbehandlung von nullstellen2, um Vergleichbarkeit mit java.util.Arrays.sort, wo das nicht direkt ginge, herzustellen):
    • Deine lineare Sortierung (s.o.): 7,8 s (7,8 µs / Durchgang)
    • Lineare Sortierung mit sich reduzierenden Endwert (wie weiter oben im Thread bei mir): 5,3 s (5,3 µs / Durchgang)
    • Lineare Sortierung mit sich reduzierenden Endwert per Minimum-Wert-Suche (wie ich es bei kleinen Mengen meistens mache): 3,0 s (3,0 µs / Durchgang)
    • Merge-Sort, rekursiv: 9,1 s (9,1 µs / Durchgang)
    • Merge-Sort, rekursiv, mehr iterative Anteile: 7,0 s (7,0 µs / Durchgang)
    • Heap-Sort, rekursiv : 2,2 s (2,2 µs / Durchgang)
    • Quick-Sort (gewöhnlich), rekursiv: 2,6 s (2,6 µs / Durchgang)
    • java.util.Arrays.sort incl. Umdrehen der Reihenfolge: 0,49 s (0,49 µs / Durchgang)
      Das^ ist krass: 490 ns / Sortierdurchgang (inclusive 30 ns für System.arraycopy und dem Richtungsumkehrtrick)!
      Es sind nur 882 CPU-Takte je Sortierung. Da dürfte kaum weniger möglich sein. Vielleicht liegt java.util.Arrays.sort nativ vor.

    Natürlich wären viele dieser Werte in realen Anwendungen vielfach schlechter (typisch für Java). Man merkt das schon, wenn man die Anzahl an Durchgängen reduziert. Ganz schlecht werden die Werte bei gar keiner Wiederholung, also auch ohne vorausgehendes Sudoku a = new Sudoku(matrix); Der JIT-Compiler stört enorm. Es geht nicht ohne ihn und nicht mit ihm.

    Gescheite Tests würden jedoch zufällige Inhalte einspeisen. Daher dient dieses nur zum Vergleich zwischen deiner und meiner Seite sowie zur groben Orientierung.

    Bei dem liege ich bei knapp 1200 ms. An sich ist der laufzeitmäßig über alle Fälle günstiger. da er selbst im Worstcase kein n² als Laufzeit hat.
    Bei insgesamt einem einzigen Durchgang (ohne Sudoku a = new Sudoku(matrix);) dauert deine komplette Sortierung vom letzten Mal bei mir eine schwankende Anzahl an einstelligen Millisekunden. Mit tatsächlich zwei Durchgängen (einmal per Sudoku a = new Sudoku(matrix); und einmal zum Lösen) dauert sie 186 µs. Das ist ohne die Vorarbeit gerechnet. Mit Vorarbeit, exklusive dem Füllen der großen Matrix und inklusive dem Hochzählen von besetzt_zeilen sowie besetzt_spalten (habe ich zum Messen getrennt) komme ich auf 224 µs. In beiden Fällen ist natürlich nullstellen2 auch sortiert. Der gesamte Konstruktor braucht sehr viel länger als das Sortieren.

    Aber hier kann man sehr schön sehen, dass es halt noch andere Dinge gibt.
    Allerdings. Aber bei dir jetzt konkret dürfte das Problem doch immer noch darin bestehen, dass du kaum den Sortiervorgang misst, sondern ganz überwiegend seine Folgen. Trotzdem scheint mir da irgendwas zu lange zu dauern.

    Zudem gibt es ein Problem. Ich habe bei meinen ersten Sortiermethoden hier ein einfaches Intarray genommen. Auf Dauer war mir das zu nervig. Jetzt habe ich der Koordinatenklasse noch eine Int-Variable gestiftet, die nachher die Menge der besetzten Stellen erfasst, wenn der gespeicherte Wert eine 0 beinhaltet. Ist also jetzt alles in Nullstellen drin. Aber es stehen natürlich drei werte jetzt drin, x,y und besetzt, die jeweils bei der zuweisen i[j]=blabla übertragen werden oder wo nur die Adresse übertragen wird.
    Solche Ideen hatte ich immer wieder mal (bei ähnlichen Problemen). Meistens war der größere Speicheraufwand nachteilig, indem das nicht mehr so schön in die Caches passte. Und den Zugriff auf drei Werte kann die CPU nicht mehr so gut optimieren wie den auf zwei (falls sie überhaupt was optimiert bekommt). Aber das muss nicht auf jeder CPU so nachteilig wie bei meiner ausfallen. Aber von Ähnlichkeiten ist auszugehen.

    Was ich am liebsten hätte, wäre, dass ich nur das besetzt-Array sortiere und wenn das sortiert ist, übertrage ich das auf das nullstellenarray. Leider ist das nur ein Wunsch (bisher), weil ich keine Ahnung hab, wie ich das anstellen soll. Das Problem ist ja, dass wenn das besetztarray sortiert ist, ich nicht mehr weiß, welches besetzt[i] zu welcher nullstelle[j] gehört.
    Ich hätte dazu einige Ideen. Mit einer "etwas dreisten" hat es gleich geklappt:

    Ich habe einfach die alte Reihenfolge als Indizes (0...n) mit in den int-Werten von besetzt_nullstellen kodiert und zwar so, das es beim Sortieren nicht stört. Dann habe ich das durch das schnelle java.util.Arrays.sort gejagt und bei Extraktion (die Indizes sind nun mitsortiert) nullstellen2[0...n] gleich in nullstellen3[i] eingeordnet.
    Das Sortieren fällt kaum ins Gewicht (es sei denn, wir würden wieder "einfache" Sudokus lösen). Es dauert nun bei 100 Wiederholungen brutto 75 µs je Durchgang, mitsamt den Überresten und Umständlichkeiten, die noch bereinigt werden müssen. Während der Phase von Sudoku a = new Sudoku(matrix); ist der JIT-Compiler noch nicht fertig, wodurch das Sortieren schon mal 4...5 ms dauern kann. Später dauert es bei nur einem weiteren Durchgang dann 115...340 µs, weil der JIT-Compiler manchmal noch gerade so hineinhackt. Kompiliert dauert es also 75 µs.

    Ich habe nun einigen Overhead drin, weil ich jetzt wieder mit Koordinaten arbeite, damit das wie vor kurzem bei dir funktioniert und weil ich den Code noch nicht aufgeräumt habe, Ergebnis bei der Java-Lösung ohne Sortieren (absichtlich in der unglüchlicheren Reihenfolge ("Zeilenlösung")) : 13,6 s
    Das passt auch zum Verhältnis unserer CPUs (war bei dir 3,85 s).
    Nach dem Sortieren ergibt sich 660...670 ms. Bei 10 Durchgängen ergibt sich durchschnittlich 641 ms. Damit ist meine "dumme" Lösung geschlagen. Das gilt zwar nur für besonders unglückliche Sudokus, aber immerhin.
    jabu ist offline Geändert von jabu (10.07.2018 um 05:09 Uhr)

  10. #50 Zitieren
    Auserwählter
    Registriert seit
    Jul 2017
    Beiträge
    6.532
    Zitat Zitat von jabu Beitrag anzeigen
    @Stiller Leser
    Das hier von dir hat noch einen kleinen Fehler:
    Hast du ihn schon gefunden?
    Nicht wirklich. Hatte mich dann für quicksort entschieden und das andere rausgelöscht.

    Zitat Zitat von jabu Beitrag anzeigen
    Werte bei mir für 1 Mio. Sortierdurchgänge (brutto, steckt ein System.arraycopy zum Zurücksetzen je Durchgang mit drin, jedoch ohne Mitbehandlung von nullstellen2, um Vergleichbarkeit mit java.util.Arrays.sort, wo das nicht direkt ginge, herzustellen):
    • Deine lineare Sortierung (s.o.): 7,8 s (7,8 µs / Durchgang)
    • Lineare Sortierung mit sich reduzierenden Endwert (wie weiter oben im Thread bei mir): 5,3 s (5,3 µs / Durchgang)
    • Lineare Sortierung mit sich reduzierenden Endwert per Minimum-Wert-Suche (wie ich es bei kleinen Mengen meistens mache): 3,0 s (3,0 µs / Durchgang)
    • Merge-Sort, rekursiv: 9,1 s (9,1 µs / Durchgang)
    • Merge-Sort, rekursiv, mehr iterative Anteile: 7,0 s (7,0 µs / Durchgang)
    • Heap-Sort, rekursiv : 2,2 s (2,2 µs / Durchgang)
    • Quick-Sort (gewöhnlich), rekursiv: 2,6 s (2,6 µs / Durchgang)
    • java.util.Arrays.sort incl. Umdrehen der Reihenfolge: 0,49 s (0,49 µs / Durchgang)
      Das^ ist krass: 490 ns / Sortierdurchgang (inclusive 30 ns für System.arraycopy und dem Richtungsumkehrtrick)!
      Es sind nur 882 CPU-Takte je Sortierung. Da dürfte kaum weniger möglich sein. Vielleicht liegt java.util.Arrays.sort nativ vor.

    Natürlich wären viele dieser Werte in realen Anwendungen vielfach schlechter (typisch für Java). Man merkt das schon, wenn man die Anzahl an Durchgängen reduziert. Ganz schlecht werden die Werte bei gar keiner Wiederholung, also auch ohne vorausgehendes Sudoku a = new Sudoku(matrix); Der JIT-Compiler stört enorm. Es geht nicht ohne ihn und nicht mit ihm.
    Ich denke, dass man da viel größere Mengen brauchen, damit sie ihre wahre Stärke zeigen können. Vermutlich, so wie es bei dir rauskommt, sind hier noch die einfachen im Vorteil. Aber wie gesagt, dass ganze läuft ja so schnell ab, dass man sich über die Zeit nicht streiten braucht.

    Zitat Zitat von jabu Beitrag anzeigen
    Ich habe einfach die alte Reihenfolge als Indizes (0...n) mit in den int-Werten von besetzt_nullstellen kodiert und zwar so, das es beim Sortieren nicht stört. Dann habe ich das durch das schnelle java.util.Arrays.sort gejagt und bei Extraktion (die Indizes sind nun mitsortiert) nullstellen2[0...n] gleich in nullstellen3[i] eingeordnet.
    Das Sortieren fällt kaum ins Gewicht (es sei denn, wir würden wieder "einfache" Sudokus lösen). Es dauert nun bei 100 Wiederholungen brutto 75 µs je Durchgang, mitsamt den Überresten und Umständlichkeiten, die noch bereinigt werden müssen. Während der Phase von Sudoku a = new Sudoku(matrix); ist der JIT-Compiler noch nicht fertig, wodurch das Sortieren schon mal 4...5 ms dauern kann. Später dauert es bei nur einem weiteren Durchgang dann 115...340 µs, weil der JIT-Compiler manchmal noch gerade so hineinhackt. Kompiliert dauert es also 75 µs.
    Das ist eine geschickte Lösung, die ich auch oft anwende. Aber hier hatte ich im Vorfeld die Befürchtung, dass das wieder alles zu lange dauert und da hatte ich keine Lust, es erst auszuprobieren.

    Zitat Zitat von jabu Beitrag anzeigen
    Ich habe nun einigen Overhead drin, weil ich jetzt wieder mit Koordinaten arbeite, damit das wie vor kurzem bei dir funktioniert und weil ich den Code noch nicht aufgeräumt habe, Ergebnis bei der Java-Lösung ohne Sortieren (absichtlich in der unglüchlicheren Reihenfolge ("Zeilenlösung")) : 13,6 s
    Das passt auch zum Verhältnis unserer CPUs (war bei dir 3,85 s).
    Nach dem Sortieren ergibt sich 660...670 ms. Bei 10 Durchgängen ergibt sich durchschnittlich 641 ms. Damit ist meine "dumme" Lösung geschlagen. Das gilt zwar nur für besonders unglückliche Sudokus, aber immerhin.
    Vermutlich geht es noch schneller. Immerhin wissen wir ja jetzt, dass das Sortieren der Nullstellen was bringt. Man könnte ja nach allem möglichen sortieren. Vermutlich gibt es da noch irgendwas elegantes, mit dem man beweisen könnte, dass diese oder jene Sortierung günstiger ist. Und man muss ja auch die Folgen beachten, wie sich das entwickelt.
    Stiller Leser ist offline

  11. #51 Zitieren
    Legende Avatar von jabu
    Registriert seit
    Jul 2011
    Beiträge
    7.328
    Zitat Zitat von Stiller Leser Beitrag anzeigen
    Nicht wirklich. Hatte mich dann für quicksort entschieden und das andere rausgelöscht.
    Weil es vermutlich kein Spoiler mehr ist: Das "- 1" im Kopf der inneren Schleife muss weg. Sonst fehlt der Vergleich mit dem letzten Element.

    Ich denke, dass man da viel größere Mengen brauchen, damit sie ihre wahre Stärke zeigen können. Vermutlich, so wie es bei dir rauskommt, sind hier noch die einfachen im Vorteil.
    Irgendwann ist O(n*log(n)) naturgemäß gegenüber O(n2) klar im Vorteil, auch wenn dabei der für die jeweiligen Operationen nötige Aufwand viel größer ist. Quadratische Anteile sind hier noch verkraftbar, weil die Zahlen klein sind und weil das Durchgucken von Elementen sehr viel schneller als ein weiteres Verzweigen, Aufrufen und Umorganisieren erfolgt.

    Aber wie gesagt, dass ganze läuft ja so schnell ab, dass man sich über die Zeit nicht streiten braucht.
    Ja, mit einer (fiktiven) Ausnahme: Falls das mal auf einem Webserver laufen sollte (viele Clients), könnte sich das ändern. Man könnte dann eine Fallunterscheidung einführen: Dummer und "schneller" Algorithmus ohne jegliche Sortierung bei Sudokus mit vielen Vorbelegungen, cleverer und "langsamer" Algorithmus bei wenigen Vorbelegungen. Die Anzahl der Vorbelegungen sollte ein geeigneter Indikator dafür sein, was sich durchschnittlich eher lohnt.

    Das ist eine geschickte Lösung, die ich auch oft anwende. Aber hier hatte ich im Vorfeld die Befürchtung, dass das wieder alles zu lange dauert und da hatte ich keine Lust, es erst auszuprobieren.
    So einfach habe ich es gemacht (aus meinem Code isoliert und angepasst; bei mir geht das wegen des für die Messungen mehrerer Durchgänge nötigen Zurücksetzens nicht direkt über besetzt_nullstellen, sondern über ein temporäres Array):
    Code:
    for (int j = 0; j < len; j++) {
        besetzt_nullstellen[j] *= 1024;
        besetzt_nullstellen[j] += j;
    }
    
    MySort.ArraysSort(besetzt_nullstellen);
    	 		
    for (int j = 0; j < len; j++) {
        nullstellen3[j] = nullstellen2[besetzt_nullstellen[j]%1024];
        besetzt_nullstellen[j] /= 1024;
    }
    Mit nullstellen3 wird (anstatt mit nullstellen2) weitergearbeitet. Das ist natürlich noch unoptimiert. Der Laufzeitaufwand ist aber so gering, dass er bei den Messungen kaum auffällt.

    Vermutlich geht es noch schneller. Immerhin wissen wir ja jetzt, dass das Sortieren der Nullstellen was bringt. Man könnte ja nach allem möglichen sortieren. Vermutlich gibt es da noch irgendwas elegantes, mit dem man beweisen könnte, dass diese oder jene Sortierung günstiger ist. Und man muss ja auch die Folgen beachten, wie sich das entwickelt.
    Das Auszählen der kleinen Matrizen fehlt bekanntlich noch. Das für jede Position einzeln zu tun, geht natürlich nicht gerade schnell. Das ginge dann effizient, wenn man einen Ansatz mit Mengenoperationen hätte (was ich ganz am Anfang vor hatte, aber was sich selten lohnt), der den dafür nötigen Aufwand sowieso drin hat und zu nutzen weiß.

    Man sollte auch mitbedenken, dass die Sortieralgorithmen nicht unbedingt stabil sind. Das spielt insofern eine Rolle, dass die Nullstellen mit gleich vielen besetzten Positionen nach der Sortierung in veränderter Reihenfolge vorliegen können (und sehr oft auch werden). Das ist zwar nicht schlimm, stört aber die Vergleichbarkeit grundsätzlich. Deswegen kann ich "Glück" (oder Pech, weil ich den unglücklicheren Fall nicht sehen durfte) gehabt haben, dass es bei mir mal schneller als bei dir ging.
    jabu ist offline Geändert von jabu (16.07.2018 um 21:23 Uhr)

Seite 3 von 3 « Erste 123

Berechtigungen

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