Geschwindigkeit berechnen

[Binggi]

Hallo zusammen
Ich muss ein Programm schreiben, welches ein Sudoku lösen kann.
Dazu habe ich 2 verschiedene Algorithmen gewählt:
Backtracking und einen selbst entwickelten (noch am entwickeln)
Nun möchte ich feststellen, wie lange die Prüfung einer Zahl geht beim Backtracking. Wie kann ich das am besten machen? Mit dem Debugger das ganze anschauen und alle Assemberbefehle zählen?

Ich weiss ausserdem nicht ob ich Java oder C++ nehmen soll. Ich tendiere eher zu Java, da ich die Sprache besser behersche. Ist es in beiden Sprachen gleich einfach/schwer das Problem zu lösen?
Gruss Binggi

[Swordfish]

...

[Binggi]

Ja ich möchte nachher berechnen können wie lange es im schlechtesten/besten Fall dauert, das Rätsel zu lösen.
z.B 10 Mio Versüche in 1s mit 10GHz...

[Hi]

Zeitmessung mit dem performance counter (QueryPerformanceCounter etc.), dazu findest bestimmt genug Beispiele.

Vergiss Java

[SeppJ]

Binggi schrieb:

Ja ich möchte nachher berechnen können wie lange es im schlechtesten/besten Fall dauert, das Rätsel zu lösen.
z.B 10 Mio Versüche in 1s mit 10GHz...

Wirklich gut hochrechnen kann man solche Ergebnisse nicht. Wenn du mit 2 GHz 2 Millionen Versuche in 1 s schaffst, dann heißt das noch lange nicht, dass ein 10 GHz Prozessor 10 Millionen Versuche schafft (wahrscheinlich schafft er nämlich sehr viel mehr). Computer sind heutzutage sehr komplexe Maschinen und der Ansatz

Assemberbefehle zählen?

geht schon seit Jahrzehnten nicht mehr. Genaue Vorhersagen mittels Skalierung funktionieren bloß in zwei Fällen mit guter Genauigkeit:
1. (hypothetisch) Du übertaktest bei einem Rechner alle(!) Komponenten gleichmäßig
2. (realistisch) Wenn du ein trivial (oder zumindest sehr, sehr gut) parallelisierbares Problem hast und dieses auf mehrere Rechner verteilst.

Daher: Einfach messen. Das C++ wird voraussichtlich ein bisschen schneller sein (aber nicht um eine Größenordnung oder mehr, selbst ein Faktor 2 wäre schon hoch), aber wenn du in C++ wesentlich länger zum Programmieren bräuchtest, dann nimm Java.

[nwp3]

So wie ich das verstanden habe soll ja nicht der Performanceunterschied zwischen Java und C++ (3 oder 5 Millisekunden, wen interessierts?) sondern zwischen Backtracking und selbst entwickeltem Verfahren untersucht werden. Wobei mir dieses "Prüfung einer Zahl" missfällt, kommt halt auf die Position der Zahl an. Dann lieber die Zeit nehmen, die für das Lösen eines kompletten Sudokus nötig ist. Btw. Backtracking ist beim Sudoku lösen nicht sonderlich performant im Vergleich zu anderen Verfahren.

Es gibt Betriebssystem-Funktionen die die Performance messen. Man will nämlich nicht einfach die Realzeit messen, weil zwischendurch noch andere Programme laufen, sondern nur die Zeit die das Programm tatsächlich gelaufen ist. Obwohl der Unterschied zwischen Backtracking und selbt entwickeltem Verfahren groß genug sein sollte, dass es auf den Unterschied zwischen Real- und Laufzeit nicht so ankommt.

[Gast]

Frag mal den Wolfgang!

[nwp3]

Decimad schrieb:

Frag mal den Wolfgang!

Lieber nicht. Der postet dir 1000 Zeilen Templatemagie mit der man eine einzelne Sudokuzahl darstellen kann.

[hustbaer]

nwp3 schrieb:

Es gibt Betriebssystem-Funktionen die die Performance messen. Man will nämlich nicht einfach die Realzeit messen, weil zwischendurch noch andere Programme laufen, sondern nur die Zeit die das Programm tatsächlich gelaufen ist. Obwohl der Unterschied zwischen Backtracking und selbt entwickeltem Verfahren groß genug sein sollte, dass es auf den Unterschied zwischen Real- und Laufzeit nicht so ankommt.

Vorweg: ich gehe von modernen Desktop-Systeme aus. Auf Servern bzw. allgemein Systemen wo man nicht kontrollieren kann was wann wo von wem sonst noch ausgeführt wird sieht die Sache anders aus.

MMn. ist es sinnvoller wall-clock Zeit zu messen.
Mit vergleichbaren Voraussetzungen (gleicher Seed für RNGs etc.) mehrfach laufen lassen, wall-clock Zeit(spanne) messen und dann den kleinsten Wert nehmen.
Gerade auf aktuellen multicore Systemen geht das relativ gut.
Dann hat man Werte von denen man weiss dass sie der Realität entsprechen.

Wenn man CPU-Zeit misst verlässt man sich auf die (oft nicht so gute) Genauigkeit des OS beim Erfassen ebendieser, Kontext-Wechsel werden nie perfekt erfasst. Und man könnte auf die dumme Idee kommen dass man nebenher eh noch alles mögliche laufen lassen kann, weil ja eh CPU-Zeit gemessen wird. Was natürlich Unsinn ist (man denke an Cache-Thrashing, Speicherbandbreite etc.).
EDIT Und sobald IO ins Spiel kommt sind die Werte nur noch Unfug -- sofern man die Performance des gesamten Programms erfassen will. Weil's halt nicht wirklich besser ist wenn man nur 50% CPU braucht dafür aber das 10fache an IO macht. /EDIT

Bzw. wenn man ganz schlau ist kann man beide Werte parallel ermitteln. Dann kann man auch schön sehen wie weit die beiden Werte auseinanderliegen. Was, wenn man sinnvoll misst, nicht sehr weit sein sollte.

@Decimad
Welchen Wolfgang?

[volkard]

hustbaer schrieb:

Mit vergleichbaren Voraussetzungen (gleicher Seed für RNGs etc.) mehrfach laufen lassen, wall-clock Zeit(spanne) messen und dann den kleinsten Wert nehmen.

Genau. Es glaubt mir immer keiner.
Den KLEINSTEN Wert nehmen!
Damit messe ich Codeschnipsel, die oft innerhalb eines Zeitscheibensektors bleiben, auf 5 und mehr signifikante Stellen aus. Regelmäßig reproduzierbar.
Der Durchschnitt ist auf Desktopsystemen völliger Müll.

[hustbaer]

volkard schrieb:

hustbaer schrieb:

Mit vergleichbaren Voraussetzungen (gleicher Seed für RNGs etc.) mehrfach laufen lassen, wall-clock Zeit(spanne) messen und dann den kleinsten Wert nehmen.

Genau. Es glaubt mir immer keiner.
Den KLEINSTEN Wert nehmen!

Hihi, ja.
Wobei es bei multithreaded Code schon auch Sinn machen kann sich den Durchschnitt und die Standardabweichung anzugucken.
Also wenn man Dinge mitmisst wo Lock-Contention, (nötige) Context-Switches etc. mit reinspielen.

Wenn man natürlich nur eine kleine Software-Blitting Schleife misst oder eine Sort-Implementierung, dann ist alles andere als der kleinste Wert Quatsch mit Sosse.

[volkard]

Ich messe nur kleine Sachen und gehe davon aus, daß ich hochrechnen darf. Natürlich mit Beachtung von Cache-Effekten.
Ich merke mir, daß ich bei mehreren Kernen mir mal die Standardabweichung anschaue. Hab zwar noch keine Ahnung, was es mich lehren wird… Mal schauen. Dümmer kann ich davon ja nicht werden, nur schlauer.