Autor Beitrag
RhoX
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: 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.

ausblenden volle Höhe 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
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
    m : longint; // Anzahl der zu generierenden Elemente die sortiert werden sollen
    Zufallszahlen : array[1..100000of 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+1to 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 user profile iconChristian S.: Topic aus VCL (Visual Component Library) verschoben am Sa 25.02.2006 um 13:06
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 4006
Erhaltene Danke: 7

Windows 10 64 bit
C# (Visual Studio 2019 Express)
BeitragVerfasst: Sa 25.02.06 14:37 
Zum genaueren Messen kannst du Suche in: Delphi-Forum, Delphi-Library GETTICKCOUNT (ungenau) oder Suche in: Delphi-Forum, Delphi-Library QUERYPERFORMANCECOUNTER (genau) verwenden.

AXMD
RhoX Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: 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:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
[...]
QueryPerformanceCounter(moment1);
[...] //Algorithmus dessen Zeitaufwand berechnet werden soll
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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Sa 25.02.06 16:03 
Bei QueryPerformanceCounter musst Du durch QueryPerformanceFrequency dividieren, um das Ergebnis in Sekunden zu bekommen:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
var
   QPF, QPC1, QPC2: Int64;

QueryPerformanceCounter(QPC1);
//Deine Messung ...
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Sa 25.02.06 17:58 
user profile iconRhoX 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



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: 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



BeitragVerfasst: So 26.02.06 15:33 
im stack laufen die lokalen variablen... also

ausblenden 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: Mo 27.02.06 00:00 
danke...eine letzte frage noch

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 4006
Erhaltene Danke: 7

Windows 10 64 bit
C# (Visual Studio 2019 Express)
BeitragVerfasst: Mo 27.02.06 00:09 
Formatierung: Fließkommazahl mit 6 Nachkommastellen.

AXMD
MiChri
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 28

Win XP, Win 2000, Win 98, Linux
D4 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17

Win XP

BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1905

W98, XP
D7 PE, Lazarus, WinAVR
BeitragVerfasst: Mi 01.03.06 14:09 
Sonst benutz doch einen Suche in: Delphi-Forum, Delphi-Library PROFILER für sowas es sei denn, du willst das irgendwie darstellen.