[c] Tempo di esecuzione di un algoritmo

[markz88]

Salve,
volevo chiedere come poter calcolare in C il tempo di esecuzione di un pezzo di programma, io ho adottato questo metodo:


#include <time.h>

int main(){

clock_t inizio, fine;
double tempo;

inizio = clock();

/*pezzo di codice*/

fine = clock();

tempo = (double)(fine - inizio)/(double) CLOCKS_PER_SEC;

printf("Il tempo di esecuzione e': %f", tempo);

system("pause");
return 0;
}


ma il tempo è espresso in secondi, quando il tempo di esecuzione è minore del secondo il tempo stampato è 0.000000. Come potrei fare per calcolare il tempo di esecuzione in millisecondi per poter avere dei valori? Devo scrivere una relazione tenendo conto del tempo di esecuzione di alcuni algoritmi quindi non posso considerare lo 0. Come potrei fare? Conoscete un altro metodo?

Grazie

[Shinnok.Exor]

...
tempo = (double)(fine - inizio)/(double) CLOCKS_PER_SEC;
...


Beh se lo dividi per CLOCKS_PER_SEC certo che restituisce il tempo in secondi.

[WarDuck]

Sei sotto Windows o sotto Linux?

Sotto Windows ci sono le funzioni QueryPerformanceCounter e QueryPerformanceFrequency.

http://msdn.microsoft.com/en-us/library/ff468913%28v=VS.85%29.aspx

[GByTe87]

Ti conviene inoltre eseguire "/*pezzo di codice*/" qualche centinaio di migliaia di volte, in modo da poter rilevare differenze apprezzabili.

[markz88]

Sei sotto Windows o sotto Linux?

Sotto Windows ci sono le funzioni QueryPerformanceCounter e QueryPerformanceFrequency.

http://msdn.microsoft.com/en-us/library/ff468913%28v=VS.85%29.aspx

Quale dovrei utilizzare tra le due funzioni? Non è che mi metteresti un esempio di codice...

[markz88]

Per favore come posso esprimere il tempo in millisecondi?? E' urgente

[Supdario]

Sotto Windows, il modo più preciso (mooolto preciso, mi pare che si possa arrivare alla precisione di meno di un nanosecondo) è di usare il Performance Counter, questo è un esempio:


#include <windows.h>
...
LARGE_INTEGER a, b, oh, freq;
double tempo;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&a);
QueryPerformanceCounter(&b);
oh.QuadPart = b.QuadPart - a.QuadPart;
QueryPerformanceCounter(&a);
//Inserisci qui il codice da eseguire
QueryPerformanceCounter(&b);
tempo = (double)(b.QuadPart - a.QuadPart - oh.QuadPart)/freq;

Questo ti restituirà il tempo in secondi. Se vuoi i millisecondi ti basta moltiplicare quel valore per 1000.
La parte iniziale è il calcolo dell'overhead, cioè serve per aumentare l'accuratezza rimuovendo il tempo necessario alla chiamata della funzione QueryPerformanceCounter.

[markz88]

Sotto Windows, il modo più preciso (mooolto preciso, mi pare che si possa arrivare alla precisione di meno di un nanosecondo) è di usare il Performance Counter, questo è un esempio:


#include <windows.h>
...
LARGE_INTEGER a, b, oh, freq;
double tempo;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&a);
QueryPerformanceCounter(&b);
oh.QuadPart = b.QuadPart - a.QuadPart;
QueryPerformanceCounter(&a);
//Inserisci qui il codice da eseguire
QueryPerformanceCounter(&b);
tempo = (double)(b.QuadPart - a.QuadPart - oh.QuadPart)/freq;

Questo ti restituirà il tempo in secondi. Se vuoi i millisecondi ti basta moltiplicare quel valore per 1000.
La parte iniziale è il calcolo dell'overhead, cioè serve per aumentare l'accuratezza rimuovendo il tempo necessario alla chiamata della funzione QueryPerformanceCounter.


Grazie mille ma con DevC++ mi da l'errore:

"Invalid operands to binary /"

sulla stringa

tempo = (double)(b.QuadPart - a.QuadPart - oh.QuadPart)/freq;

[Supdario]

Errore mio, devi dividere per freq.QuadPart

[Shinnok.Exor]

Beh se lo dividi per CLOCKS_PER_SEC certo che restituisce il tempo in secondi.

Volevo dire di togliere la divisione per CLOCKS_PER_SEC.

Sotto Windows, il modo più preciso (mooolto preciso, mi pare che si possa arrivare alla precisione di meno di un nanosecondo) è di usare il Performance Counter, questo è un esempio:


#include <windows.h>
...
LARGE_INTEGER a, b, oh, freq;
double tempo;
QueryPerformanceFrequency(&freq);
QueryPerformanceCounter(&a);
QueryPerformanceCounter(&b);
oh.QuadPart = b.QuadPart - a.QuadPart;
QueryPerformanceCounter(&a);
//Inserisci qui il codice da eseguire
QueryPerformanceCounter(&b);
tempo = (double)(b.QuadPart - a.QuadPart - oh.QuadPart)/freq;

Questo ti restituirà il tempo in secondi. Se vuoi i millisecondi ti basta moltiplicare quel valore per 1000.
La parte iniziale è il calcolo dell'overhead, cioè serve per aumentare l'accuratezza rimuovendo il tempo necessario alla chiamata della funzione QueryPerformanceCounter.

clock(); funziona allo stesso modo.
Ritorna il numero di cicli di clock della CPU fino a quel momento, ed è la misurazione di temporizzazione più precisa che puoi fare su un PC, in quanto non esistono secondi, microsecondi e nanosecondi come di tu, ma solo cicli di clock del generatore.

Quindi clock () (standard, quindi funzionerà su tutti i PC che implementano librerie C) e QueryPerformanceCounter() (non portabile) fanno esattamente la stessa cosa, anzi quasi sicuramente QueryPerformanceCounter () usa clock() per recuperare il numero di clock . Non dividendo il risultato di clock(); per CLOCKS_PER_SEC recuperi il numero di cicli di clock.

Ti consiglio di usare clock() che almeno è portabile tra i SO


#include <time.h>

int main() {
clock_t inizio;
long tempo_esec;

inizio = clock();

.............

tempo_esec = (clock() - inizio) / (CLOCKS_PER_SEC / 3600) // TEmpo di esec in millisecondi

}

[markz88]

Volevo dire di togliere la divisione per CLOCKS_PER_SEC.



clock(); funziona allo stesso modo.
Ritorna il numero di cicli di clock della CPU fino a quel momento, ed è la misurazione di temporizzazione più precisa che puoi fare su un PC, in quanto non esistono secondi, microsecondi e nanosecondi come di tu, ma solo cicli di clock del generatore.

Quindi clock () (standard, quindi funzionerà su tutti i PC che implementano librerie C) e QueryPerformanceCounter() (non portabile) fanno esattamente la stessa cosa, anzi quasi sicuramente QueryPerformanceCounter () usa clock() per recuperare il numero di clock . Non dividendo il risultato di clock(); per CLOCKS_PER_SEC recuperi il numero di cicli di clock.

Ti consiglio di usare clock() che almeno è portabile tra i SO


#include <time.h>

int main() {
clock_t inizio;
long tempo_esec;

inizio = clock();

.............

tempo_esec = (clock() - inizio) / (CLOCKS_PER_SEC / 3600) // TEmpo di esec in millisecondi

}


Seguendo il metodo da te consigliatomi mi da l'errore [Warning] Division by zero ed il programma crasha :(

[Shinnok.Exor]

Seguendo il metodo da te consigliatomi mi da l'errore [Warning] Division by zero ed il programma crasha :(

uhm mi sa che ho sbagliato il calcolo, prova:


tempo_esec = ((clock() - inizio)/CLOCKS_PER_SEC)*3600


Insomma,


tempo_esec =(clock() - inizio)/CLOCKS_PER_SEC


ti ritorna il tempo di esecuzione in secondi, sai matematicamente come portare quei secondi in millisecondi.

[bobbytre]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#include <windows.h>

int main(int argc, char *argv[])
{

SYSTEMTIME sysTime;
FILETIME fileTime;

LARGE_INTEGER start;
LARGE_INTEGER end;
LARGE_INTEGER diff;


GetLocalTime(&sysTime);
SystemTimeToFileTime(&sysTime, &fileTime);
memcpy(&start, &fileTime, sizeof(LARGE_INTEGER));

Sleep(1000); // 1 Secondo

GetLocalTime(&sysTime);
SystemTimeToFileTime(&sysTime, &fileTime);
memcpy(&end, &fileTime, sizeof(LARGE_INTEGER));

diff.QuadPart = end.QuadPart - start.QuadPart;

printf("%22lld - \n",end.QuadPart);
printf("%22lld = \n",start.QuadPart);
printf("------------------------ \n");
printf("%22lld x 100-nanosecond = %lld seconds \n",diff.QuadPart ,diff.QuadPart/10000000 );

return 0;
}

[markz88]

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#include <windows.h>

int main(int argc, char *argv[])
{

SYSTEMTIME sysTime;
FILETIME fileTime;

LARGE_INTEGER start;
LARGE_INTEGER end;
LARGE_INTEGER diff;


GetLocalTime(&sysTime);
SystemTimeToFileTime(&sysTime, &fileTime);
memcpy(&start, &fileTime, sizeof(LARGE_INTEGER));

Sleep(1000); // 1 Secondo

GetLocalTime(&sysTime);
SystemTimeToFileTime(&sysTime, &fileTime);
memcpy(&end, &fileTime, sizeof(LARGE_INTEGER));

diff.QuadPart = end.QuadPart - start.QuadPart;

printf("%22lld - \n",end.QuadPart);
printf("%22lld = \n",start.QuadPart);
printf("------------------------ \n");
printf("%22lld x 100-nanosecond = %lld seconds \n",diff.QuadPart ,diff.QuadPart/10000000 );

return 0;
}



Ti ringrazio mille per il codice, funziona :)

Ma vorrei porti una domanda, come mai per trasfomare i microsecondi in secondi dividi per 10.000.000 e non per 1.000.000 come indicato nella tabella di conversione della matematica? :doh:

[bobbytre]

Ti ringrazio mille per il codice, funziona :)

Ma vorrei porti una domanda, come mai per trasfomare i microsecondi in secondi dividi per 10.000.000 e non per 1.000.000 come indicato nella tabella di conversione della matematica? :doh:

L'avevo scritto nel printf , dipende dal fatto che non sono microsecondi ma un ordine di grandezza inferiore (100-ns cioe' 10^-7)

la struct FILETIME contiene appunto:
FILETIME Structure

Contains a 64-bit value representing the number of 100-nanosecond intervals since January 1, 1601 (UTC).

[||ElChE||88]

clock(); funziona allo stesso modo.
Ritorna il numero di cicli di clock della CPU fino a quel momento, ed è la misurazione di temporizzazione più precisa che puoi fare su un PC, in quanto non esistono secondi, microsecondi e nanosecondi come di tu, ma solo cicli di clock del generatore.

Quindi clock () (standard, quindi funzionerà su tutti i PC che implementano librerie C) e QueryPerformanceCounter() (non portabile) fanno esattamente la stessa cosa, anzi quasi sicuramente QueryPerformanceCounter () usa clock() per recuperare il numero di clock . Non dividendo il risultato di clock(); per CLOCKS_PER_SEC recuperi il numero di cicli di clock.
Ma anche no, dipende dall'implementazione. Quella di Windows ha una precisione di millisecondi, non microsecondi come QueryPerformanceCounter.

[markz88]

Grazie a tutti per le risposte :)

[Supdario]

Volevo dire di togliere la divisione per CLOCKS_PER_SEC.



clock(); funziona allo stesso modo.
Ritorna il numero di cicli di clock della CPU fino a quel momento, ed è la misurazione di temporizzazione più precisa che puoi fare su un PC, in quanto non esistono secondi, microsecondi e nanosecondi come di tu, ma solo cicli di clock del generatore.

Quindi clock () (standard, quindi funzionerà su tutti i PC che implementano librerie C) e QueryPerformanceCounter() (non portabile) fanno esattamente la stessa cosa, anzi quasi sicuramente QueryPerformanceCounter () usa clock() per recuperare il numero di clock . Non dividendo il risultato di clock(); per CLOCKS_PER_SEC recuperi il numero di cicli di clock.

Ti consiglio di usare clock() che almeno è portabile tra i SO


#include <time.h>

int main() {
clock_t inizio;
long tempo_esec;

inizio = clock();

.............

tempo_esec = (clock() - inizio) / (CLOCKS_PER_SEC / 3600) // TEmpo di esec in millisecondi

}


Non è esattamente così.
La funzione clock() del C returna una certa quantità di clock, che però non sono i cicli di clock del processore, ma si basano su una costante CLOCKS_PER_SEC sempre fissa, decisa dal compilatore (di solito è qualcosa tipo 1000000).
Invece il PerformanceCounter usa direttamente la frequenza del processore come unità di misura (quindi se il tuo processore è da 3 GHz, avrai 1/(3 GHz) di risoluzione, cioè 0.33 nanosecondi).

In ogni caso concordo sul fatto che forse in questo caso la funzione clock() del C è più appropriata, sia perché non penso che gli sia richiesta tantissima precisione, ed inoltre è portabile.

[markz88]

Non è esattamente così.
La funzione clock() del C returna una certa quantità di clock, che però non sono i cicli di clock del processore, ma si basano su una costante CLOCKS_PER_SEC sempre fissa, decisa dal compilatore (di solito è qualcosa tipo 1000000).
Invece il PerformanceCounter usa direttamente la frequenza del processore come unità di misura (quindi se il tuo processore è da 3 GHz, avrai 1/(3 GHz) di risoluzione, cioè 0.33 nanosecondi).

In ogni caso concordo sul fatto che forse in questo caso la funzione clock() del C è più appropriata, sia perché non penso che gli sia richiesta tantissima precisione, ed inoltre è portabile.

Si ma a me serve sapere il tempo di esecuzione degli algoritmi di ordinamento Bubblesort, Insertionsort, Selectionsort, Mergesort e Heapsort presenti nel mio programma ed utilizzando la funzione clock() ottengo come tempo di esecuzione 0 secondi e non posso costruire i grafici, capite? Invece con quello scritto da bobbytre ottengo un numero moltiplicato per 10^-7 su cui mi posso basare per costruire dei grafici... ma sinceramente non so quale unità di misura poter usare xD visto che non sono ne millisecondi ne nanosecondi se non ho capito male xD aiutooooo!! Se volessi utilizzare clock() con la variabile tempo di tipo double e finish e start di tipo clock_t, l'espressione corretta è:


tempo = (double)(finish - start)/CLOCKS_PER_SEC;


oppure no?

[bobbytre]

io ti posso consigliare cosi:

...
printf("%22lld x 100-nanosecond = %lld MILLISECONDI \n",diff.QuadPart ,diff.QuadPart/10000 );

[markz88]

io ti posso consigliare cosi:

...
printf("%22lld x 100-nanosecond = %lld MILLISECONDI \n",diff.QuadPart ,diff.QuadPart/10000 );


Grazie mille mi da lo stesso risultato del clock() più o meno... ora visto che ho capito come funzionano entrambi... quale uso? xD ci devo pensare, quale mi consigliate per l'esame?

[bobbytre]

visto che è solo per un esame ti conviene usare quello che ti viene piu facile da ricordare ...