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? :wall:

[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 :-D

[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. :thuimb:
Meine Version stimmt da schon.

[PhaTTy]

Zitat:

Zitat von Toxman

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

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

[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. :gruebel:

[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

[Luckie]

GetTickCount ist gänzlich ungeeignet solche Messungen durchzuführen. Der Grund ist der, dass GetTickCount nicht die tatsächliche Zeit messen kann die ein Thread wirklich an Rechenzeit zugeteilt bekommen hat. Es misst nur den zeitlichen Abstand zweier Punkte so zu sagen. Nehmen wir mal folgen den Code:

Delphi-Quellcode:

Start := getTickCount;
// aufwendige Berechnungen
Ende := GetTickCount;

Der Scheduler von Windows weißt nun deinem Thread jeweils eine Rechenzeiut von ca. 22 ms zu. Da dein Thread aber nicht der einzigeste im System ist und es Threads mit gleicher oder höherer Priorität gibt, wird im für eine unbstimmte Zeit Rechnezeit entzogen und der Thread und wird in den "zuteilungsfähigen" Zustand versetzt, das heißt er wartet darauf, dass er wieder "an die Reihe" kommt.

Will man nun ermitteln wie lange der Thread tatsächlich an einer Aufgabe "rechnet", muss man die Zeit ermitteln, die der Thread wirklich Rechnezeit zugeteilt bekommt und auch wirklich Code von der CPU ausgeführt wird und das kann man nur mit der API-Funktion GetThreadTimes. Ein Beispiel dafür findet man auch in meinem Threading-Tutorial.

Eine andere Möglichkeit die Geschwindigkeit zu ermitteln, ist das Zählen der tatsächlich von der CPU benötigten Taktzyklen.

[negaH]

Zitat:

auch wirklich Code von der CPU ausgeführt wird und das kann man nur mit der API-Funktion GETTHREADTIMES.

Das ist besser als GetTickCount(), ist aber denoch nicht 100%'tig exakt unter Windows. Interuptroutinen, von denen es ne Menge gibt mit sehr kurzen periodischen Intervallen, werden dem aktuelle Thread "gutgeschrieben" ohne das GetThreadTimes() dies berücksichtigen kann. Desweiteren der Overhead des Threadwechsels der alleine schon aus Sicht der CPU mindestens 200 Taktzyklen dauert, wird ebenfalls dem Threadcontext gutgeschrieben.

Will man exakte Messungen dann gibt es nur zwei Alternativen:
1.) ein spezielles OS das ALLES blocken kann
2.) eine spezieller Realtime Simulator der den zu analysierenden Code in einer virtuellen und vom OS unabhänigen Box simuliert. Ähnlich dem Intel VTune.

Gruß Hagen

[nailor]

wenn man aber nicht einen einzelnen zyklus sodern sagen wir 10.000 misst, dann sollte sich das relativ egal bleiben...

[mirage228]

Ich würde einfach eine riesige Anzahl (n > 1.000.000) unter Berücksichtigung der genannten Vorschläge sortieren. Hierbei dürften die paar ms Abweichung das Endergebnis nicht allzu sehr verfälschen.

mfG
mirage228

[Nikolas]

Danke schon mal für alle Vorschläge. :thuimb: Nur hab ich leider noch nicht mit Threads gearbeitet und werde mir da wohl noch ein paar Sachen beibringen müssen um eine halbwegs exakte Zeitmessung hinzubekommen. :mrgreen:

THXbyTOX