C Bestimmung der Rechenzeit einer Funktion

[Danny787]

Ich habe einen Algorithmus programmiert, welcher beliebige Zahlenfolgen in richtiger Reihenfolge ordnet. Nun würd ich gern die Rechenzeit bestimmen, also wie lange mein Algorithmus für 100 Zahlen, 1000 Zahlen usw. benötigt.
Gibt es in C eine solche Funktion oder auch ein externes Tool, mit welchem ich mein Anliegen bewerkstelligen kann?

Danke schon mal im voraus

 

[XunnD]

Windows: GetTickCount
Linux: gettimeofday

 

[Velines]

Ja, einfach den Timestamp vorher und nachher vergleichen.
Noch ein Tipp: Lass das sortieren oft laufen (50x oder öfter, je nach Laufzeit) und bilde den Durchschnitt, um aussagekräftige Werte zu bekommen.
Gesamtlaufzeit > 5s sollte es schon sein.

 

[claW.]

müsstest es nur in c übertragen.

#pragma once

#include <sys/timeb.h>

class Stopwatch
{
  private :
    timeb mStart;
    timeb mStop;

  public:
    void Start( void ) { ftime( &mStart ); }
    void Stop( void ) { ftime( &mStop ); }
    // abfolge durch x->start() und x->stop(), danach diese funktion aufrufen
    long GetMilliseconds( void ) { return (long)(1000 * (mStop.time - mStart.time) + mStop.millitm - mStart.millitm); }
    long TimeSinceStart( void ) // gibt die zeit in ms zurück und kann während der "timer" läuft aufgerufen werden
    {
      timeb CurrentTime;
      ftime( &CurrentTime );
      return (long)(1000 * (CurrentTime.time - mStart.time) + CurrentTime.millitm - mStart.millitm);
    }
};

 

[IceMatrix]

mit GetTickCount() und ftime() brauchste unter Windows nicht anfangen. Die sind meistens zu ungenau. Besser bist du bei QueryPerformanceCounter() aufgehoben.

 

[XunnD]

Mit QueryPerformanceCounter kann man eher Geschwindigkeiten auf derselben Maschine gegeneinander vergleichen. Z.B. um Implementierungsvarianten hinsichtlich Effektivität zu untersuchen.
Die anderen Funktionen kommen dennoch in Betracht, wenn man Laufzeiten hochrechnen will, denn diese sind bereits auf Zeit ausgerichtet, während der Counter nur Zählschritte zurückliefert, diese aber von Rechner zu Rechner unterschiedlich sind.

 

[7H3 N4C3R]

@XunnD:
Dafür teilt man dann den Wert durch das, was einem QueryPerformanceFrequency (ich hoffe, die Funktion heißt tatsächlich so, die MSDN verweist auf jeden Fall auf die Richtige) zurückgibt. Das ist auch direkt korrekt mehrerern Cores.

Alternativ - direkt nen Profiler nehmen. Unter Linux z.B. gprof. Compileroptionen weiß ich gerade nicht... -gprof glaub ich.

 

[IceMatrix]

So isses.. QueryPerformanceCounter() wird als Multicore-alternative für RDTSC genutzt, insbesondere wenn die CPUs (was besonders bei änderen Modellen der Fall ist) keine konstante TSC haben. Neuere CPUs haben dies oft, auch ist die Clock auf den unterschiedlichen Cores gesynched.

Wie dem auch sei, wie 7H3 N4C3R schon gesagt hat, gibt QueryPerformanceFrequency() die Frequenz zurück, womit sich der Counter auf jede x-beliebige CPU normieren lässt.

 

[petap]

Mach doch mal ne theoretische Laufzeitanalyse^^. Guck dir deinen Algorithmus genau an und daraus kannst du ja dann ne worstcase Bewertung vornehmen.

 

[mitschie]

Wenn man es noch genauer haben will, dann kann man auch einen Performance Profiler drüber laufen lassen. Der sagt dir dann auch noch welcher Teil deines Codes wie lange gebraucht hat und wo eventuell Flaschenhälse sind.

Ich kenne persönlich nur ein Produkt und das ist kostenpflichtig, allerdings gibt es ne Demo:

http://www.red-gate.com/products/ants_performance_profiler/index.htm

Alternativ befindet sich in Visual Studio Team System 2010 auch ein Profiler. Den kenne ich allerdings nicht.