Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Laufzeit eines Algorithmus berechnen
RhoX - Sa 25.02.06 14:04
Titel: Laufzeit eines Algorithmus berechnen
Hi,
ich will berechnen wie lange zwei Algoithmen für verschiedene Mengen zu bearbeitender Elemente brauchen. Dabei bekomme ich zwei Probleme:
1. Ich benutze Now was ganz offensichtlich, oder zumindest so wie ich es geschrieben habe, keinen Sekundenwert zurückgibt.
2. Sobald ich statt 100000 Elementen 1000000 Elemente nehme Kommt ein Fehler "...Stack Overflow..."
Die Algorithmen, die ich untersuchen will, sind Shellsort und Bubblesort.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106:
| unit pasToll;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type TForm1 = class(TForm) btGenerate: TButton; btShellSort: TButton; btBubblesort: TButton; lbText1: TLabel; lbText2: TLabel; lbZeit1: TLabel; lbZeit2: TLabel; lbText3: TLabel; procedure btGenerateClick(Sender: TObject); procedure btShellSortClick(Sender: TObject); procedure btBubblesortClick(Sender: TObject); private public m : longint; Zufallszahlen : array[1..100000] of longint; end;
var Form1: TForm1; const n = 100000;
implementation
{$R *.dfm}
procedure TForm1.btGenerateClick(Sender: TObject); var i, zufallszahl :longint; zahlen : array[1..n] of longint; erfolg : boolean; begin for i := 1 to n do zahlen[i] := -1; randomize; for i := 1 to n do begin erfolg := false; while not erfolg do begin zufallszahl := random(n) + 1; if zahlen[zufallszahl] = -1 then begin zahlen[zufallszahl]:= zufallszahl; Zufallszahlen[i] := zufallszahl; erfolg := true; end; end; end; end;
procedure TForm1.btShellSortClick; var i, j, h, v : longint; moment1, moment2 : TDateTime; begin moment1 := Now; h:= 1; repeat h := (3 * h) +1; until (h > N); repeat h := (h div 3); for i := (h+1) to N do begin v := Zufallszahlen[i]; j := i; while ((j > h) and (Zufallszahlen[j-h] > v)) do begin Zufallszahlen[j]:= Zufallszahlen[j-h]; dec(j, h); end; Zufallszahlen[j]:= v; end; until (h = 1); moment2 := Now; lbZeit1.Caption := FloatToStr(StrToFloat(Inttostr( Round((moment2 - moment1) * n))) / n) + ' Sekunden'; end;
procedure TForm1.btBubblesortClick(Sender: TObject); var i, j, hilf : longint; moment1, moment2 : TDateTime; begin moment1 := Now; for i := N downto 1 do for j:= 1 to i do if (Zufallszahlen[j-1] > Zufallszahlen[j]) then begin hilf := Zufallszahlen[i]; Zufallszahlen[i] := Zufallszahlen[i +1]; Zufallszahlen[i +1] := hilf; end; moment2 := Now; lbZeit2.Caption := FloatToStr(StrToFloat(Inttostr( Round((moment2 - moment1) * n))) / (n / 10)) + ' Sekunden'; end;
end. |
Bis auf die zwei genannten probleme funktioniert das Programm
Danke schon mal
MfG
Moderiert von
Christian S.: Topic aus VCL (Visual Component Library) verschoben am Sa 25.02.2006 um 13:06
Delete - Sa 25.02.06 14:35
hallo rhox,
deine funktion liefert keine vergleichbaren werte resp. ergebnisse. (dein 3. problem, wenn auch einfach zu lösen) um dies zu erreichen müsstest du deine zufallszahlen entweder in identischer wertreihenfolge generieren oder dir deinen sortierstring für den vergleich mit den anderen algo. speichern.
zu deinen ersten problem, mit dem stack, schau doch mal unter projekt, optionen, linker... da kannst du den stack vergrössern.
für dein zweites problem, hab ich aus dem stegreif auch keine antwort.
dennoch noch viel erfolg.
RhoX - Sa 25.02.06 15:18
Also ehrlich gesagt komm ich trotzdem nicht so ganz weiter..
StackOverflow konnte ich beseitigen jedoch kann man den Maximun Wert nur bis zu einer bestimmten Zahl (16777216) erhöhen, was mir zu wenig ist ;)
Für die Zeitberechnung wollte ich einen genauen Wert haben, daher habe QUERYPERFORMANCECOUNTER benutzt. Das sieht dann etwa so aus:
Delphi-Quelltext
1: 2: 3: 4: 5:
| [...] QueryPerformanceCounter(moment1); [...] QueryPerformanceCounter(moment2); lbZeit1.Caption := FloatToStr(Round((moment2 - moment1) * 10000) / 10000) + ' Sekunden'; |
Dann bekomme ich einen Fehler: Incompatible Types
moment1 und moment2 sind vom Typ Int64
BenBE - Sa 25.02.06 16:03
Bei QueryPerformanceCounter musst Du durch QueryPerformanceFrequency dividieren, um das Ergebnis in Sekunden zu bekommen:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| var QPF, QPC1, QPC2: Int64;
QueryPerformanceCounter(QPC1); QueryPerformanceCounter(QPC2); QueryPerformanceFrequency(QPF); Label1.Caption := Format('%.6f Sekunden', [(QPC2 - QPC1) / QPF]); |
RhoX - Sa 25.02.06 17:04
Danke!, das fnktioniert schon mal sehr gur, nur wäre echt nett wenn du das noch erklären könntest damit ich das nachvollziehen kann. Diese Programm ist Teil meiner Facharbeit und ich sollte daher auch wissen was ich da eigentlich mache ;)
BenBE - Sa 25.02.06 17:58
RhoX hat folgendes geschrieben: |
Danke!, das fnktioniert schon mal sehr gur, nur wäre echt nett wenn du das noch erklären könntest damit ich das nachvollziehen kann. Diese Programm ist Teil meiner Facharbeit und ich sollte daher auch wissen was ich da eigentlich mache ;) |
Jo, NP.
Mit QueryPerformanceCounter fragst Du einen CPU\OS-internen Zähler ab, der die Anzahl der Instruktionen die seit dem Einschalten des Computers vergangen sind, enthält. Dieser ist von der Hardware und der CPU-Taktfrequenz abhängig.
Um nun von diesem Wert auf die exakte Laufzeit schließen zu können, gibt es nun die zweite Funktion QueryPerformanceFrequency, die einemm nun exakt mitteilt, WIEVIELE solcher Zählschritte von der Hardware pro Sekunde vorgenommen werden. Dieser Wert liegt je nach Hardware zwischen 3,1 Millionen (Intel-CPUs) und der eigentlichen Taktfrequenz der CPU (bei vielen AMD-CPUs).
Wenn man nun die tatsächlich vergangenen Zählzyklen ins Verhältnis setzt, zu den Pro Sekunde vergehenden Zählzyklen, erhält man die vergangene Zeit dieser Messung. Also nicht anders, als wenn Du zählst, wie oft dein Cursor auf dem Bildschirm blinkt und dann gegenrechnest mit dem Wert, wie oft er pro Minute normalerweise blinkt ... ;-)
Delete - Sa 25.02.06 19:01
und klappts mit der laufzeitmessung? falls ja, wirst wohl beim ausführen des gleichen sortieralgo. unterschiedliche werte erhalten.
probier mal auf randomize zu verzichten und stattdessen den startwert manuell zu setzen. damit sollt es dann auch nachvollziehbar werden.
Nachtrag: kein wunder dass dir der stack knapp wird. schieb doch den ganzen sche*** auf den heap, da ist genügend platz. jonglieren kannst du dann mit pointern... die brauchen kaum speicherplatz....
RhoX - So 26.02.06 15:02
Danke erstmal, also das Programm an sich funktioniert, aber wie du bereits sagtest, die Messungen ergeben unterschiedliche Werte. Das mit dem Heap und den Pointern kenne ich nicht...was auch immer das seien mag.
Wie setzte ich einen startwert manuell ?
mfg
BenBE - So 26.02.06 15:25
Weise der Variablen RandSeed einfach einen Wert zwischen 0 <= x < 1 zu.
Delete - So 26.02.06 15:33
im stack laufen die lokalen variablen... also
Delphi-Quelltext
1: 2:
| var dies_ist_eine_variable: mein_typ; |
wenn du das ganze auf den heap schiebst, brauchst du im haupt progi nur 4 byte um drauf zugreifen zu können. das beansprucht deinen stack so gut wie gar nicht.
zum heap schau mal unter:
http://de.wikibooks.org/wiki/Programmierkurs:_Delphi:_Dynamische_Datenstrukturen
dort sollten die grundlegenden fragen geklärt werden. um deine struktur dann im heap aufzubauen hast dann eine ganze reihe von möglichkeiten (einfach/doppelt) verkettete listen, baumstrukturen (binär und mit mehreren knoten).
noch viel erfolg.
ps: das mit der variable RANDSEED hat ja BEN schon gesagt. diese wird durch randomize gesetzt, nimm daher randomize raus. und wenn du deinen algo neu startst, einfach RANDSEED wieder auf den ursprünglichen wert setzen, dann sind die ergebnisse auch wiederholbar.
pps: vielleicht kennt ja noch jemand ein besseres tutorial zur dynamischen speicherverwaltung...
ppps: ggf. hierfür einen neuen thread eröffnen. ist ja nicht mehr das thema...
RhoX - Mo 27.02.06 00:00
danke...eine letzte frage noch
Delphi-Quelltext
1:
| Format('%.6f Sekunden', [(moment2 - moment1) / QPF]); |
also anscheinend formatiert die funktion format das ergebnis dass ich aus (moment2 - moment1) / QPF zu den Sekunden in einen String, aber was genau bedeuted %.6f ?
AXMD - Mo 27.02.06 00:09
Formatierung: Fließkommazahl mit 6 Nachkommastellen.
AXMD
MiChri - Mo 27.02.06 13:08
Hallo
RhoX: Dein Topic heisst doch Laufzeit berechnen das was Ihr hier macht ist aber nix anderes als einfaches Messen.
Das ist 1. ungenau und 2. von der Maschine abhängig. Da du aber anscheinend die Performance des Algorithmuses und nicht deiner Implementierung des Algos haben willst würde ich mir lieber die Schleifen-Struktur anschauen. Also: wie oft werden abhängig von der Anzahl der Zahlen die einzelnen Befehle ausgeführt. Bei verschachtelten Schleifen ist das etwas tricky, bei den beiden Algos gut zu machen.
Danach hast du gezeigt und bewiesen, wie schnell die beiden Sortierverfahren zueinander sind.
Stichwort: O-Notation
Gruß Christian
RhoX - Mi 01.03.06 14:02
Ja diese Notattion kenne ich und auch darauf beziehe ich mich. Vielleicht habe ich mich etwas falsch ausgedrückt
Mfg
digi_c - Mi 01.03.06 14:09
Sonst benutz doch einen
PROFILER für sowas es sei denn, du willst das irgendwie darstellen.
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!