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
    { 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


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.


AXMD - 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 - 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);
[...] //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 - 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);
//Deine Messung ...
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

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 ... ;-)


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 Suche in: Delphi-Forum, Delphi-Library PROFILER für sowas es sei denn, du willst das irgendwie darstellen.