Newsgroup: it.comp.lang.c
Titolo: calcolo del tempo

Salve a tutti,
ho un piccolo problema con un programma: devo calcolare il tempo di
esecuzione e per farlo uso le due funzioni StartTime e TakeTime.
Ora, da quel che ho capito StartTime serve per far partire il calcolo (visto
che inizializza il tempo di inizio) e taketime per farmelo restituire.
t_u č il tempo utente e t_s č tempo macchina?
Non mi risulta chiaro cosa si intenda per l'uno e per l'altro nel senso che
il programma che ho creato richiede solo alcuni parametri all'inizio, che
gli vengono dati dall'utente; poi esegue una serie di calcoli senza piů
ricevere alcun input: genera una serie di grafi e calcola il cammino minimo.
Tuttavia per ogni generazione calcola un tempo utente anche discretamente
alto se confrontato con quello che mi viene dato per tempo della macchina...
Per miglior chiarezza riporto le 2 funzioni.
void StartTime(void)
{
    tk.Begin_c = tk.End_c = clock();
    tk.Begin_t = tk.End_t = time(NULL);
}
double TakeTime(void)
{
    double t_u, t_s, clocks_per_sec = (double) CLOCKS_PER_SEC;
    tk.End_c = clock();
    tk.End_t = time(NULL);
    t_u = (tk.End_c - tk.Begin_c) / clocks_per_sec;
    t_s = (tk.End_t - tk.Begin_t) / clocks_per_sec;
    return (t_u);
}
Ringrazio anticipamente...
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/


Dimenticavo : c' č un modo per avere tempi + precisi di quelli restituiti da
taketime? con 1000 nodi e 15000 che č la prova che devo fare, restituisce
sempre o quasi zero....


Mi scuso per il post, non conosco la soluzione al tuo problema anche perchè 
non ho mai usato funzioni per calcolare il tempi.
Ho letto che molti post in questo ng che chiedevano delucidazioni su come 
fare e la mia domanda è se il calcolo è necessiario per sapere quanto è 
"buono" il programma o la funzione implementata, perchè non sfruttare in 
fase di progettazione le pagine e pagine di teoria che spiegano come 
calcolare la buontà di un algoritmo ed eventualmente utilizzare tecniche di 
ottimizzazione o strutture dati adeguate ?
Ad esempio, se il tuo è un problema di ottimizzazione o calcolo della bontà 
:
un algoritmo ottimale per la costruzione dovrebbe avere se non erro avere 
una complessità di tempo lineare sulla dimensione del grafo 
T(n)=theta(|V|+|E|) dove V è l'insieme dei nodi ed E l'insieme degli archi.
un algoritmo per la ricerca dei percorsi minimi ad esempio Dijkstra  se la 
coda a priorità è implementata tramite un semplice array ha complessità pari 
a T(n)=O(V^2) il che significa che non può andare peggio del quadrato del 
numero dei vertici. Se utilizzi un heap minimo per implementare la coda il 
tempo diventa
O((V+E)logV)) che si riduce a O(E logV) se tutti i nodi sono raggiungibili 
dalla sorgente. Se invece la coda la realizzi con un heap di fibonacci il 
tutto diviene O(V log(V) + E).  (Introduzione agli algoritmi - Cormen)
Tramite un analisi asintotica si ottengono i tempi di riferimento, che 
prescindono dalla macchina e che quindi sono caratterizzanti dell'algoritmo.
ReDiCuori 

     t_s = (tk.End_t - tk.Begin_t) / clocks_per_sec;
questa istruzione sopra e' sbagliata, perche' come ti ho detto
la funzione time() riporta un valore intero in secondi e quindi
non va divisa per CLOCKS_PER_SEC. Inoltre non capisco perche'
la calcoli se poi non la ritorni in alcun modo.
Se hai bisogno di calcolare tempi con maggior precisione
devi far riferimento a funzionalita' specifiche del tuo sistema
operativo e quindi ti invito a riproporre la domanda
su uno dei gruppi
it.comp.programmare.win32
oppure
it.comp.linux.development
per esempio sotto linux potrebbe esserci la funzione gettimeofday che mi
sembra permettesse di avere "l'ora" come per time() ma con anche 
frazioni di secondo.
ciao,
g.

 ottimizzazione o strutture dati adeguate ?
Il motivo e' molto semplice (e ti parlo da informatico teorico, quindi 
in teoria dovrei essere partigiano dell'analisi asintotica).
In fase progettuale una qualche forma di analisi del problema e
degli  algoritmi e delle strutture dati che uno andra' ad utilizzare e'
necessaria.
Questa analisi se uno ha abbastanza conoscenze ed esperienze pregresse
dovrebbe indirizzare verso la scelta di strutture dati e algoritmi
che meglio si adattano al problema da risolvere.
Per esempio, per fare il sort di 10 milioni di interi probabilmente
ormai solo un demente userebbe il bubble-sort.
La teoria ci fornisce degli strumenti di analisi e anche un po'
di "ricette" che si possono applicare in veri casi senza dover
reinventare la ruota.
Appunto, uno impara quale e' il costo del sort con diversi
metodi, quale e' il costo di varie operazioni in diverse implementazioni
di un heap, una coda, uno stack e cosi' via.
tutto questo va benissimo e anzi va saputo. Ma spesso non e' abbastanza.
Nella pratica ci sono almeno 3 aspetti per cui l'analisi asintotica puo'
non bastare se non e' applicata con molto sale in zucca.
1) L'analisi asintotica e' appunto asintotica, nasconde costanti che in
pratica possono fare la differenza. Per esempio
il famoso algoritmo di Strassen per fare moltiplicazioni di matrici con
meno di O(n^3) operazioni di solito nella pratica non viene usato su
matrici piccole (n < 50) perche' di fatto il risparmio "asintotico"
su piccole matrici viene "mangiato" dal fatto che l'algoritmo e'
piu' complicato.
2) Una volta scelto l'algoritmo
(o una coppia di algoritmi che sulla carta hanno lo stesso costo) 
l'implementazione puo' fare la differenza. Tieni conto che nella pratica
un fattore costante puo' avere molta importanza: se un programma invece
di 2 centesimi di secondo ce ne mette 4 chissenefrega, ma se invece di 2
giorni ce ne mette 4 la cosa puo' essere molto fastidiosa.
Trovare la migliore implementazione possibile di un algoritmo puo'
dipendere da considerazioni sull'uso della cache, sulla localita' dei
dati, e su un certo dose di inevitabile ignoranza su quello che il
compilatore prima e la CPU poi faranno del nostro codice.
per esempio sulla mia macchina, se A e B sono matrici 1024x1024 di double,
i due cicli equivalenti:
for (i=0; i<1024; i++) for(j=0; j<1024; j++) B[i][j]+=A[i][j];
e
for (i=0; i<1024; i++) for(j=0; j<1024; j++) B[j][i]+=A[j][i];
hanno entrambi complessita' asintotica O(N^2), calcolano gli stessi
valori, ma il secondo ci mette piu' di 3 volte il tempo del primo.
3) Ci sono molti algoritmi complessi, specialmente le euristiche,
per i quali il calcolo asintotico o in generale una stima teorica
e' molto difficile da fare.
Tipicamente i tempi di calcolo possono dipendere dall'input
in modi non facilmente prevedibili. Un esempio classico
(perche' ci ho lavorato....) e' il problema del commesso viaggiatore 
(TSP). Su grandi istanze la soluzione ottima e' fuori portata e ci
si accontenta di trovare una buona approssimazione.
In questi casi uno magari si inventa 3 euristiche che sulla
carta sono ragionevoli, ma poi vanno sperimentate su vari tipi di 
istanza e avranno magari anche tempi diversi a seconda della "classe"
di istanze che uno sta considerando.
Tutto questo scritto di getto e senza troppe riflessioni, ma spero
di aver reso l'idea.
Insomma, l'analisi teorica e' importantissima, specialmente per evitare
orride bischerate, tipo appunto il bubblesort su grandi array, o usare 
il metodo di Cramer per risolvere un sistema lineare 30x30,
ma tante volte quello che alla fine conta e' il tempo di esecuzione.
ciao,
g.