Autor |
Beitrag |
RhoX
      
Beiträge: 17
Win XP
|
Verfasst: Sa 25.02.06 14:04
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.
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
|
|
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: 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.
Zuletzt bearbeitet von Grenzgaenger am Sa 25.02.06 14:38, insgesamt 1-mal bearbeitet
|
|
AXMD
      
Beiträge: 4006
Erhaltene Danke: 7
Windows 10 64 bit
C# (Visual Studio 2019 Express)
|
Verfasst: Sa 25.02.06 14:37
Zum genaueren Messen kannst du GETTICKCOUNT (ungenau) oder QUERYPERFORMANCECOUNTER (genau) verwenden.
AXMD
|
|
RhoX 
      
Beiträge: 17
Win XP
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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]); |
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
RhoX 
      
Beiträge: 17
Win XP
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 ... 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: 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 
      
Beiträge: 17
Win XP
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 26.02.06 15:25
Weise der Variablen RandSeed einfach einen Wert zwischen 0 <= x < 1 zu.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: 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: de.wikibooks.org/wik...sche_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 
      
Beiträge: 17
Win XP
|
Verfasst: 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
      
Beiträge: 4006
Erhaltene Danke: 7
Windows 10 64 bit
C# (Visual Studio 2019 Express)
|
Verfasst: Mo 27.02.06 00:09
Formatierung: Fließkommazahl mit 6 Nachkommastellen.
AXMD
|
|
MiChri
      
Beiträge: 28
Win XP, Win 2000, Win 98, Linux
D4 Prof
|
Verfasst: 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 
      
Beiträge: 17
Win XP
|
Verfasst: 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
      
Beiträge: 1905
W98, XP
D7 PE, Lazarus, WinAVR
|
Verfasst: Mi 01.03.06 14:09
Sonst benutz doch einen PROFILER für sowas es sei denn, du willst das irgendwie darstellen.
|
|
|