Newsgroup: it.comp.lang.c
Titolo: algoritmo da ottimizzare

Ciao,
ho un problema da porvi, devo verificare se un istante <t> appartiene ad un
intervallo centrato in <t_rif> di lunghezza <delta> dunque se <t> appartiene
a [(t_rif-delta) , (t_rif+delta)] il tutto è complicato dal fatto che tutti
i riferimenti temporali sono memorizzati su un unsigned int (32bit) e dunque
bisogna gestire l'overflow (Il passaggio da 0xFFFFFFFF a 0x00000000).
Un modo semplice per gestiro è questo:
//-----------------------------------
unsigned int TRif;
int Delta;
int IsInInterval(unsigned int T)
{
    if (TRif > -Delta)
    {
        if (T>TRif-Delta || T<TRif+Delta)
            return 1;
        else
            return 0;
    }
    else if (TRif < Delta)
    {
        if (T<TRif+Delta || T>TRif-Delta)
            return 1;
        else
            return 0;
    }
    else
    {
        if (T<TRif+Delta && T>TRif-Delta)
            return 1;
        else
            return 0;
    }
}
//-----------------------------------
Funziona ma  è troppo "pesante" infatti il caso pessimo prevede 5 confronti
mentre il caso ottimo 2 confronti ... c'e' un modo migliore?
Grazie ciao
Alessio C.

 mentre il caso ottimo 2 confronti ... c'e' un modo migliore?
Non ho voglia di cercare di capire il problema, scusami per questo.
Voglio pero' dirti che di solito quando si parla di ottimizzare un algoritmo
si parla di ottimizzare "ordini di grandezza" o per lo meno notazioni big-Oh
etc...
In pratica un algoritmo che svogle un determinato compito in tempo n*n e'
molto peggio di uno che lo svolge in tempo n*log n  e questo a sua volta e'
peggio di uno che lo svolge in tempo n.
Ad esempio il primo per n=100 ci mette 10.000 (qualchecosa), il secondo solo
100! Wow, 100 volte piu' veloce!
Nel tuo caso, 5 confronti cosa vuoi che siano, il tuo non solo e' un tempo
basso, ma meglio ancora e' COSTANTE.
Non vedo quindi la necessita' di cercare di migliorarlo...
Se si riuscisse passare da 5 nel caso peggiore a 4, cosa cambierebbe?!?
Beh, lascio agli altri del NG che abbiano voglia di risponderti "il compito"
di trovare un modo.... io mi evito di perdere tempo.
Tommy

Ho scritto ... intervallo di lunghezza <Delta> ma in relatà la lunghezza è
maggiore essendo +/- Dellta ... comunque il problema è quello ... ci siamo
capiti!! :)
Ciao

Hai ragione e torno allo stesso tempo infatti questo algoritmo è in un ciclo
che viene eseguito molte volte dunque se ruiscissi a dimezzarne il costo
raddoppierei di fatto la velocità di quella porzione di codice che per me è
significativa dunque ... i conti tornano ... comunque è vero esistono
problemi più affascinanti ... spero comunque che ci sia qualche creativo che
voglia aiutarmi in questa sega mentale!!
Ciao

 wrote in message
news:KAzY9.80243$0v.24...@news1.tin.it...

se puoi ( C99 ) usa gli u64_t cosi' non devi testare l'overflow..
inline o macro..
ma.. sei sicuro che sia la parte da ottimizzare?
"Premature optimization is the root of all evil" -- Donald Knuth
Sbirish

 confronti mentre il caso ottimo 2 confronti ... c'e' un modo migliore?
puoi togliere gli else, visto che se entri in un if, non ne esci senza 
un return, quindi o non entri nell'if, o lasci la funzione
cosi' il codice e' piu' leggibile. E mi sembra l'unica ottimizzazione 
necessaria: le altre le fa il compilatore, se e' buono. se non lo e' 
cambialo :)

 cambialo :)
Grazie, veramente speravo che uno di voi conoscesse un qualche "trucco" per
evitare tutti quei confronti, mi sembra troppo per fare una cosa cosě
semplice ... evidentemente non č cosě!!!
Grazie di nuovo per l'aiuto

 wrote in message
news:AZXY9.117451$AA2.5...@news2.tin.it...

il trucco si chiama C99 o meglio uint64_t
ciao
 sbirish.