Zeit für Sortieralgos

[Nikolas]

Ich bn grad dabei ein kleines Programm über Sortieralgos zu schreiben und bin auf was komisches gestossen: Das Bild ist ein Screenshot aus meinem Programm. In schwarz hab ich die Zeitfür für den jeweiligen Sortiervorgang einzeichnen lassen.
So messe ich die Zeit:

Delphi-Quellcode:

a:= gettickcount;
Sortieren;
a:= gettickcount-a;

Hat da jemand eine Idee, warum ich da diese gequantelten Bänder bekomm?

[CReber]

Evtl. weil das Zeitmessen in der falschen procedure ist? Also rein logisch würde ich sagen muss man die Zeit ja seperat messen weil man ja nie weiß wann das tauschen fertig ist! Allerdings seh ich jetzt auch nicht wirklich bei dem Graphen durch

[Nikolas]

ich hab bis jetzt nur Selection und Bubble und da laufen zwei verschachtelte for-Schleifen ab und wenn die fertig sind, ist alles sicher sortiert.
Danke aber für die Idee

[PhaTTy]

Sollte es nicht auch a:=a+(gettickcount-a); heisen?

[Nikolas]

rechne das mal kurz mit zwei werten durch, da wirst du sehen, dass da was falsches rauskommt.
Meine Version stimmt da schon.

[PhaTTy]

Zitat von Toxman:

rechne das mal kurz mit zwei werten durch, da wirst du sehen, dass da was falsches rauskommt.
Meine Version stimmt da schon.

OK womit sich wieder der Spruch "Erst denken, dann reden" bewahrheitet hätte

[nailor]

nee, (neuezeit - altezeit) reicht vollkommen

falls du mit deinen algos unter die auflösung des tickcounters kommst, könnte es probleme geben...

[Nikolas]

Der geht ja in den ms-Bereich und fast alle Sortierungen dauern min 10 ms oder so was.
Es sieht aber fast so aus, als ob gettickcount nur alle 15-16 ms aktualisiert wird.

[nailor]

ja

[negaH]

Zitat:

Der geht ja in den ms-Bereich und fast alle Sortierungen dauern min 10 ms oder so was.

Also das kann ja wohl nicht stimmen, ich weiß ja nicht was für Sortierungen und Datenmengen du nutzt.
Ein QuickSort in Assembler benötigt ca. 5-10 Taktzyklen pro Vergleich und Elementetausch. Bei 2.0 GHz kämen wir also auf 205 Millionen solcher Quicksort Vergleiche. Ich würde also eher sagen das man weit unterhalb von Millisekunden liegt.

Nee, ich vermute das es an der Art deiner Messung liegt. GetTickCount() ist eben nur in 1 ms genau, laut Abtasttheorem kann also der Fehler schon 2ms betragen. Desweiteren misst deine Routine den Tasksheduler und die anderen Task im gesamten System mit. Statt also nur die eigentlichen Routinen zu messen wirst du unter einem Multithreading System wie Windows IMMER auch Interruptroutinen, Backgroundtasks, Ring0 Task usw. usw. mit messen, da diese sich eben zeitlich dazwischen schalten.
Eventuell rufts du in der Messung noch Application.ProcessMessages o.ä. auf, was die Sache noch verschlimbessert.

Schau dir mal QueryPeformanceCounter(), Get/SetThreadPriority(), Get/SetPriorityClass(), GetThreadTimes() an.

Ich sage dir aber jetzt schon das exakte Messungen unter Windows fast unmöglich sind. Der beste Weg dürfte es sein jede Messung 1000'ende male zu wiederholen und den bereinigten Mittelwert zu bilden. D.h. diese Mittelwertbildung muß Ausreiser-Messungen erkennen und in der Rechnung eliminieren.

Gruß Hagen