Zitat von
Stiller Leser
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 von
Multithread
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?