Newsgroup: it.comp.programmare.win32
Titolo: ottimizzare la mia ricorsività?

ciao a Tutti.
Sto implementando un mio algoritmo altamente ricorsivo in cui è fondamentale
la velocità di calcolo.
Ecco il dubbio:
Nella funzione1 ricorsiva faccio un controllo (if) sulla base del quale
eseguire o meno un'istruzione.
La particolarità della mia funzione1 è che se l'if è verificato so già che
d'ora in poi l'if sarà sempre verificato.
Mi chiedo allora se, quando l'if viene verificato la prima volta,  non sia
meglio chiamare una funzione2 indentica in tutto alla funzione1 tranne per
il fatto che mi risparmio il controllo (if).
Lato positivo: chiamando ricorsivamente la funzione2 risparmio ogni volta il
tempo di calcolo dell'istruzione if
Lato negativo: raddoppio il codice (funzione1 e funzione2)
Credo che in via teorica non esista una soluzione migliore dell'altra.
Probabilmente dipenderà da quanto "grossa" è la mia funzione ricorsiva e dal
numero di ricorsioni.
Cosa ne pensate?
Grazie.
DANILO

 il fatto che mi risparmio il controllo (if).
Ma questo controllo if cosa contiene? Calcoli pesanti? Altrimenti non
penso che un if possa incidere in alcun modo sul computo del tempo
occupato.
Piuttosto io comunque prevederei un parametro aggiuntivo nella funzione
ricorsiva che puoi settare quando non vuoi piu` verificare la
condizione, qualcosa tipo:
int FunzioneRicorsiva( ... , BOOL bVerifica)
{
    if( bVerifica)
        if( condizione)
        {
            ...
            bVerifica = FALSE;
        }
    ...
}
In questo modo quando andrai a chiamare FunzioneRicorsiva() ripassandole
i parametri, gli passerai bVerifica impostata a FALSE e non controllerai
piu` la condizione.
--
Lorenzo

Forse sono stato poco chiaro.
Quale di queste due soluzioni è più performante?
(ricordo che la particolarità della mia funzione è che se (a == TRUE) allora
lo sarà per sempre!!)
soluzione1:
void f1()
{
    // algoritmo
    if (a) pippo = 1;
    f1();
}
soluzione 2:
void f1()
{
     // algoritmo
    if (a)
    {
        pippo = 1;
        f2();
    }
    else f1();
}
void f2()
{
    // algoritmo
    pippo = 1;
    f2();
}


Addesso si che sei stato poco chiaro: non si capisce
quale è la condizione che termina la ricorsione (il passo
basse, per intendersi). Scritto così non si capisce che
senso abbia risolvere il tuo problema con la ricorsione.
In generale concordo con Lorenzo: non ottieni un grosso
miglioramento. Forse puoi migliorare gestendo tu uno
stack per la ricorsione ed evitando di usare quello di
sistema; cos' eviti le istruzioni di call e il passaggio di
eventuali parametri...
Federico Molara.

 eventuali parametri...
E qual'è il vantaggio di gestirmi da solo un mio stack?
Credo siano più veloce i push e i relativi pop anzichè la mia gestione dello
stack!!
Comunque grazie.

 stack!!
Siccome il guadagno che si ha evitando di valutare la condizione dell'if
è molto limitato (sempre che la condizione sia poco complessa), l'unico
margine di miglioramento che hai è nel migliorare il più possibile
l'efficienza
della ricorsione. Questo significa che occorre rendere globali tutti i dati
che non sono legati il livello n-esimo di ricorsione. Inoltre (ma la mia era
una ipotesi) se hai dei parametri "voluminosi" (ad esempio delle strutture
che devi passare per copia) allora puoi ottenere un guadagno appoggiandoti
ad uno stack creato da te. D'altro canto questo ti costringe a scegliere a
priori il livello max di ricorsione.
La mia era una ipotesi/suggerimento, chiaramente la sua applicabilità
dipende dallo specifico problema.
Federico Molara.

 dipende dallo specifico problema.
Grazie per i consigli.
L'algoritmo che ho realizzato è molto complesso e credo sia molto difficile
renderlo meno ricorsivo di com'è adesso.
Mi sono già preoccupato di "passare" meno cose possibili.
Se proprio devo passare, passo solo puntatori.
Tutte le funzioni utilizzate nell'algoritmo le ho dichiarate inline, ma come
ho già detto, nel caso di ricorsione il compilatore non può "esplodere"
ricorsivamente una funzione.
Alla luce di quanto già fatto sto cercando qualche ultima "limatina" nel
codice qua e la.

 codice qua e la.
Ti rimane solo "potatura" ed euristiche se applicabili...
Ciao. Federico.

 Ti rimane solo "potatura" ed euristiche se applicabili...
L'algoritmo è gia un euristico per un problema classico che è NP-hard.;-)
Ciao e GRAZIE!!
DANILO