c++: funktion für die zeitdauer von sortieralgorithmen?!

[hasugoon]

ich vergleiche gerade verschiedene sortieralgorithmen anhand der anzahl von vergleichs-/austauschoperationen. gibt es in c++ auch eine funktion, die mir die benötigte zeit in z.b [ms] ausgibt?

danke im voraus

 

[X!X]

Als nicht C++ Programmierer würde ich jetzt einfach mal Endezeit - Startzeit sagen.
Also nimm dir ne variable speicher die aktuelle Zeit rein und zieh diese am Ende von der neuen aktuellen Zeit ab = Zeit die benötigt wurde.

 

[TK-Shockwave]

Also ich Stimme dem bei..
Bau dir einen Timespan Counter der durch Start- und endzeit die benötigte Zeit berechnet.

sortierst du Strings/Array/Pointer?

Im Allg. sagt man das BubbleSort für große Dinge zu lahm ist..der Binäre-Suchalgorythmus dagegen sehr schnell bei großen Daten mengen.

 

[Quidoff]

include <windows.h>

int main() {
    DWORD startzeit = GetTickCount();
    DWORD endezeit, dauer;
    //code

    endezeit = GetTickCount();
    dauer = endezeit - startzeit;
}

So würde ich das machen. (unter Windows)

 

[hasugoon]

danke für die schnelle hilfe. ich denk mal wieder viel zu kompliziert

ich habe bis jetzt int-arrays der größe 100k mittels selection-/insertionsort sortiert. darüber muss ich erst mal den stack vergrößern und quicksort beschäftigt mich noch etwas. haben erst heute in der vorlesung das erste mal rekursion gehabt oO

______________insertionsort____________selectionsort

vergleiche:______~2.5e9_________________~5.0e9
austauschen:____~2.5e9 (worst case)______ ~1.0e4
zeit:___________~26500ms_______________~31000ms

=> vergleiche sind teuer

 

[7H3 N4C3R]

=> vergleiche sind teuer

Öhm, das ist genau der falsche Schluss. Vergleiche sind bei weitem nicht so teuer wie Vertauschungen.

Deine Ergebnisse belegen das auch. Doppelt soviele Vergleiche, aber trotzdem bei weitem nicht die doppelte Zeit. D.h. dass Vergleiche im Vergleich zu Vertauschungen billiger sein müssen.

Btw, die GetTickCount-Funktion "tickt" nur ca. im 51ms Takt und wird bei hoher Rechenbelastung des PC's ungenau. Von daher solltest du - wenn du sie benutzen möchtest - immer ausreichend viele Operationen durchführen.

 

[hasugoon]

Öhm, das ist genau der falsche Schluss. Vergleiche sind bei weitem nicht so teuer wie Vertauschungen.

Deine Ergebnisse belegen das auch. Doppelt soviele Vergleiche, aber trotzdem bei weitem nicht die doppelte Zeit. D.h. dass Vergleiche im Vergleich zu Vertauschungen billiger sein müssen.

hm aber in der summe kommen beide algorithmen auf die gleiche summe an operationen.
aber mal davon abgesehn, dass der 2te sortieralgorithmus u.U. vom code nicht so optimal ist und die zeitliche differenz eigentlich marginal ist, kann man das glaub eh net unbedingt miteinander vergleichen

 

[7H3 N4C3R]

Also mal das ganze Anhand der ungefähren Arbeitsweise eines Mikroprozessors beschrieben.

Vergleichen:
- Wert1 aus dem Speicher in Register 1 laden
- Wert2 aus dem Speicher in Register 2 laden
- Register1 mit Register2 vergleichen und Ergebnis in einem Flag ablegen
( - bedingter Sprung anhand des Flags)

Vertauschen:
- Wert1 aus dem Speicher in Register 1 laden
- Wert2 aus dem Speicher in Register 2 laden
- Register1 in den Speicher schreiben an die Speicherstelle von Wert2
- Register2 in den Speicher schreiben an die Stelle von Wert1

Zweiteres sind 4 Operationen, ersteres nur 3. Zusätzlich sind Routinen, die auf den Speicher zugreifen im Vergleich zu Operationen, die rein auf Prozessorregistern arbeiten (oder solche die rein den Programmfluss steuern, z.B. bedingte Sprünge) "extrem" (!) teuer.
Normalerweise stehen die benötigten Werte im Prozessor-Cache, was die Zugriffe schon wesentlich billiger macht - aber immernochnicht so billig wie eine Operation innerhalb der Register. Sobald es aber tatsächlich auf den Arbeitsspeicher geht, ist das wie Fahren mit gezogener Handbremse.


Das ist die Theorie. Compiler und Prozessor optimieren hier gewaltig und sorgen beispielsweise dafür, dass möglichst viele Daten im Cache stehen. Außerdem kann das Laden von einem der beiden Werte in ein Register entfallen, wenn dieser Wert in einer Schleife z.B. konstant bleibt. Trotzdem ist vertauschen amortisiert immer teurer als vergleichen.

 

[MagicAndre1981]

Schau dir mal die QueryPerformanceCounter Function an.

 

[Quidoff]

@MagicAndre1981
Tausend dank für diesen Link. Ich suche schon seit langem einen Ersatz für das unzuverlässige GetTickCount().