Laufzeitmessung scheint fehlerhaft zu sein?

BunterVogel

Hallo, ich habe folgenden Code, der von 2 Zahlenpaaren den ggT ermitteln soll, einmal iterativ und einmal rekursiv - parallel dazu sollen die Laufzeiten beider Vorgänge gemessen werden. Das Problem momentan ist

a) beim Iterativen spuckt er mir ein negatives Ergebnis aus
b) bei jeder Programmausführung kommen verschiedene Werte dabei raus
Irgendwas habe ich hier also falsch gemacht, aber was?

// iterativ

int iterativ(int a, int b)
{

    if (a == 0)                          //Wenn a=0 ist b der größte gemeinsame Teiler laut Definition
    {
        printf("ggT Iterativ: %d\n",b);
        return b;

    }
    while(b != 0)                        //Solange wiederholen, solange b nicht 0 ist.
    {
        if (a > b)
        {
                a = a - b;               //Wenn a größer als b, subtrahiere b von a.
        } else
        {
                b = b - a;               //In jedem anderen Fall subtrahiere a von b.
        }

    }
    printf("ggT Iterativ: %d\n",a);
    return a;                            //In a steht jetzt der größte gemeinsame Teiler von a und b.

}

// rekursiv

int euklid(int c, int d){

{
            if (d == 0) {
                printf("ggT Rekursiv : %d\n",c);
                return c;

        } else if (c == 0) {
               printf("ggT Rekursiv : %d\n",d);
                return d;
        } else if (c > d) {

                return euklid(c - d, d);
        } else {
                return euklid(c, d - c);
        }

}
}

// main Funktion

int main()
{
int a,b;
int c,d;

long iIterativ;
     float zeitIterativ;

     clock_t startIterativ, endeIterativ;

     startIterativ = clock();

     printf("Geben Sie bitte a ein");
     scanf("%d",&a);
     printf("Geben Sie bitte b ein");
     scanf("%d",&b);
     int ggT = iterativ(a,b);

     for(iIterativ=0; iIterativ<200000000; iIterativ++);

     endeIterativ = clock();

     zeitIterativ = (float)(startIterativ-endeIterativ) / (float)CLOCKS_PER_SEC;

     printf("Die Laufzeitmessung ergab %.2f Sekunden\n",zeitIterativ);

     long i;
     float zeit;

     clock_t start, ende;

     start = clock();
     printf("Geben Sie bitte c ein");
     scanf("%d",&c);
     printf("Geben Sie bitte d ein");
     scanf("%d",&d);

         int ggT2 = euklid(c,d);

     for(i=0; i<200000000; i++);

     ende = clock();

     zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;

     printf("Die Laufzeitmessung ergab %.2f Sekunden\n",zeit);

     return 0;
    }

Beim iterativen rechnest du start-ende, beim rekursiven ende-start.

Und du misst eigentlich nur die Zeit der Leerschleifen aus Zeilen 77 und 106.
Und die darf der Compiler wegoptimieren indem er iIterativ=200000000; schreibt. Sonst passiert darin nichts.

Und da du die Startzeit vor deiner Zahleingabe nimmst, hängt das ganze natürlich ganz stark davon ab, wie schnell du die Werte eintippst.

BunterVogel

Ja, das mit dem Schnell eintippen habe ich gerade auch feststellen müssen.
Nun klappt das ganze ganz gut.

Ich habe mal das Programm 2 Mal für Iterativ durchlaufen lassen, um zu schauen ob beides das gleiche Ergebnis ausspuckt. Das tut es oft, aber manchmal sind zwischen den beiden Werten minimale Unterschiede. da kommt dann z.b für den gleichen iterativen ablauf 0,59 und 0,61 heraus. Ist das normal so? Wenn ja, woran liegt das, kann man das optimieren?

Das zweite was mir aufgefallen ist, dass zwischen Rekursiv und Iterativ so gut wie kein zeitlicher Unterschied vorhanden ist, ebenfalls 0,01-0,02 unterschied - obwohl ich da auch schon überlege ob das die selben Abweichungen wie bei dem obigen sind.

SeppJ

BunterVogel schrieb:

Ich habe mal das Programm 2 Mal für Iterativ durchlaufen lassen, um zu schauen ob beides das gleiche Ergebnis ausspuckt. Das tut es oft, aber manchmal sind zwischen den beiden Werten minimale Unterschiede. da kommt dann z.b für den gleichen iterativen ablauf 0,59 und 0,61 heraus. Ist das normal so? Wenn ja, woran liegt das, kann man das optimieren?

Computer sind komplexe Gebilde. Dein Programm läuft nicht im Nichts. Obwohl du die Prozessorzeit deines Programms misst, kann es vorkommen, dass irgendetwas anderes was in deinem Computer passiert dir irgendwie dazwischen funkt und dein Programm kurz ausbremst. Übliche Methode ist daher, sehr oft zu messen und den besten(!) Wert zu nehmen.

Das zweite was mir aufgefallen ist, dass zwischen Rekursiv und Iterativ so gut wie kein zeitlicher Unterschied vorhanden ist, ebenfalls 0,01-0,02 unterschied - obwohl ich da auch schon überlege ob das die selben Abweichungen wie bei dem obigen sind.

Compiler können sehr gut optimieren, auch Rekursionen können aufgerollt werden, unbenutzte Werte werden gerne gar nicht erst berechnet. Dein Programm ist ein Musterbeispiel dafür. Der Wert wird einmal berechnet, danach nicht ausgegeben, dann ist da noch eine leere Schleife die gar nichts tut. Totaler Mist was einen Benchmark angeht.

Gib dem Rechner was zum rechnen

int main()
{
 int a,b;

 int i, anz = 100000;
 float zeit;
 clock_t start, ende;
 int ggT;
/*
     printf("Geben Sie bitte a ein");
//     scanf("%d",&a);
     printf("Geben Sie bitte b ein");
//     scanf("%d",&b);
*/
     a =  378897;

     printf("CLOCKS_PER_SEC: %ld\n", (long)CLOCKS_PER_SEC);
     start = clock();
     for(i=0; i<anz ; i++)
        ggT = iterativ(a,i);
     ende = clock();

     zeitIterativ = (float)(ende-start) / (float)CLOCKS_PER_SEC;
     printf("Die Laufzeitmessung ergab %f Sekunden, %d\n",zeitIterativ, ggT );

     start = clock();
     for(i=0; i<anz ; i++)
        ggT = euklid(a,i);
     ende = clock();

     zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC;
     printf("Die Laufzeitmessung ergab %f Sekunden, %d\n",zeit, ggT );

     return 0;
    }

Zudem werden die Werte von clock() nicht unbedingt um 1 erhöht. das können auch 1000 sein.( oder 200 oder 5000 oder )

Wutz

= (float)(ende-start) / (float)CLOCKS_PER_SEC;

Ein Cast reicht hier, vorzugsweise der rechte.