| 
| Autor | Beitrag |  
| RhoX 
          Beiträge: 17
 
 Win XP
 
 
 | 
Verfasst: Sa 25.02.06 13: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
 MfGModeriert 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 13: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 13: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 13:37 
 
Zum genaueren Messen kannst du   GETTICKCOUNT  (ungenau) oder   QUERYPERFORMANCECOUNTER  (genau) verwenden.
 AXMD |  |  |  
| RhoX  
          Beiträge: 17
 
 Win XP
 
 
 | 
Verfasst: Sa 25.02.06 14: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 15: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:
 
 | varQPF, 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 16: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 16: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 18: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 14: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 14: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 14:33 
 
im stack laufen die lokalen variablen... also
 		                       Delphi-Quelltext 
 									| 1:2:
 
 | vardies_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: So 26.02.06 23: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: So 26.02.06 23: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 12: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 13: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 13:09 
 
Sonst benutz doch einen   PROFILER für sowas es sei denn, du willst das irgendwie darstellen. |  |  |  |