Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Algorithmus - Zeit messen
Marco D. - Fr 02.03.07 23:06
Titel: Algorithmus - Zeit messen
Wie kann man die Zeit messen, die ein Algorithmus braucht? Am besten in ms. ;) Macht man so etwas mit GetTickCount?
Gausi - Fr 02.03.07 23:11
Kann man machen, ja. Allerdings sagt das relativ wenig über die "Güte" eines Algorithmus aus. Dafür sind theoretische Analysen eher geeignet. Zum Beispiel indem man abschätzt, wieviele Vergleiche/Vertauschungen maximal/im Durchschnitt (bei Sortieralgorithmen) durchgeführt werden, bis man fertig ist.
Marco D. - Fr 02.03.07 23:14
@Gausi: Du studierst doch Informatik, oder? Wo bekommt man das Spezialwissen her, um einen Algorithmus zu bewerten? Links? Literatur?
Gausi - Fr 02.03.07 23:23
Auf Anhieb kann ich dich nur mit ein paar Wikpedia-Links totschlagen.
Laufzeiten von Algorithmen werden i.A. im
O-Kalkül [
http://de.wikipedia.org/wiki/Landau-Symbole] angegeben. Man betrachtet meistens die
asymptotische Laufzeit [
http://de.wikipedia.org/wiki/Asymptotische_Laufzeit], d.h. man ist daran interessiert, was passiert wenn die Eingabe sehr groß wird (weil man z.B. drölftausend Zahlen sortieren will).
Ansonsten: Etwas gesunder Menschenverstand und etwas Mathematik hilft da auch schon. Wenn man so was hat wie
Delphi-Quelltext
1:
2:
3:
4:
|
for i := 1 to n do
for j := i to n do
|
dann sind das n + (n-1) + (n-2) + ... 2 + 1 viele Schritte. Der kleine Gauß hat das mal in der Schule ausgerechnet, das sind n*(n+1)/2. Im besagten O-Kalkül lässt man Konstanten weg (kauft man sich halt nen Rechner, der doppelt so schnell ist). Das wären dann als O(n^2) viele Schritte. Der Bubblesort funktioniert in etwa so.
BenBE - Fr 02.03.07 23:25
In Bezug auf die Güte von Algorithmen gibt es mehrere Dinge:
1. Man rechnet selber (geht für einfache Algos recht einfach ... Für Kompliziertere muss man ggf. Erzeugende Funktionen, Differential-Gleichungen uns andere Grausamkeiten lösen
ODER man vertraut auf
2. schaut in die Wiki oder andere erGOOGLEte Quellen, die den Algorithmus behandeln.
Also gerade so, wie's
Gausi in diesem mir grad orange angezeigten Posting erklärt hat ;-)
Marco D. - Fr 02.03.07 23:31
| BenBE hat folgendes geschrieben: |
| 1. Man rechnet selber |
Was mache ich denn, wenn ich keine for-Schleifen verwende?
r2c2 - Sa 03.03.07 10:42
| Marco D. hat folgendes geschrieben: |
| BenBE hat folgendes geschrieben: | | 1. Man rechnet selber |
Was mache ich denn, wenn ich keine for-Schleifen verwende? |
Ohne Schleifen hast du immer O(1). Außer es wird rekursiv. Dann kanns lustig werden. Siehe z.B. meine
Facharbeit [
http://r2c2.weingut-rehn.de/facharbeit.htm]
mfg
Christian
Marco D. - Sa 10.03.07 14:21
Und wenn es mir nur um die reine Laufzeit geht?
Macht man dass dann so, dass man vor dem Algo GetTickCount aufruft, dann den Algo startet, dann wieder GetTickCount aufruft und die Differenz der beiden Zahlen entspricht dann der Laufzeit?
wulfskin - Sa 10.03.07 14:39
| Marco D. hat folgendes geschrieben: |
Und wenn es mir nur um die reine Laufzeit geht?
Macht man dass dann so, dass man vor dem Algo GetTickCount aufruft, dann den Algo startet, dann wieder GetTickCount aufruft und die Differenz der beiden Zahlen entspricht dann der Laufzeit? |
Jo genau, wobei die ja Rechnerspezifisch ist. Sinnvoller ist es die Takte zu messen (ich glaube das geht mit QueryPerformanceCount) oder eben wissen, wieviele Takte ein Befehl hat (das kenn ich von µC, beim PC geht das wohl eher schwer)...
Gruß Hape!
Marco D. - Sa 10.03.07 14:44
Kannst du mir das mit den Takten genauer erklären? ;)
Robinator - Sa 10.03.07 15:02
Mit QueryPerformanceFrequency bekommst du die Takte pro Sekunde, mit QueryPerformanceCounter die Takte seit Systemstart . Wenn du nun den Wert zu beginn deines algos vom Wert am Ende deines algos abziehst, und diesen durch die Frequzen teilst, dann hast du eigentlich was du brauchst ;)
gruss, Rob
Marco D. - Sa 10.03.07 15:08
Okay und wenn ich nun den Wert habe. Was sagt der mir?
Robinator - Sa 10.03.07 15:12
Hmmm.. das sollte dir doch jetzt eigentlich klar sein, falls nicht. F1 -> QueryPerformanceCounter & QueryPerformanceFrequency ;)
gruss, Rob
Marco D. - Sa 10.03.07 15:13
| Robinator hat folgendes geschrieben: |
Hmmm.. das sollte dir doch jetzt eigentlich klar sein, falls nicht. F1 -> QueryPerformanceCounter & QueryPerformanceFrequency ;)
gruss, Rob |
Okay Frage blöd formuliert: Was sagt mit dieser Wert über den Algorithmus aus?
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!