Newsgroup: it.comp.lang.c++
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

 wrote in message
news:4fVw8.49578$vF6.1...@news2.tin.it...


il fatto che mi risparmio il controllo (if).
Vorresti fare una funzione col copia/incolla?
Non è più semplice:
void f1(int a){
    if (a)
        f2(a);
}
void f2(int a){
    // algoritmo
}
?
-- 
Marco Barisione (ICQ 84277092)

 Lato negativo: raddoppio il codice (funzione1 e funzione2)
Se le due funzioni sono identiche ad eccezione dell'if puoi farne una
template:
 template< bool PerformTest >
 void func()
 { 
	if( PerformTest ) 
        {
           if( /* ... */  )
           {  
		func<false>(); // ricorsione senza test
           }
        } else
        {
         func<PerformTest>(); // ricorsione normale
        }
 }
Così ottieni le medesime prestazioni che avresti con due funzioni
distinte, senza raddoppiare il codice. (Mi riferisco al codice C++, non al
codice compilato, che sarà comunque duplicato.)
Max

 ha scritto nel messaggio
news:67g8cu84esfa5cu7i...@4ax.com...

Si col copia/incolla!
Non hai capito il problema!
Intendevo qualcosa del genere:
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();
}

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!!)


 ha scritto nel messaggio
news:4fVw8.49578$vF6.1...@news2.tin.it...

Indubbiamente eliminare un pezzo di codice migliorerà le prestazioni. Ed è
altrettanto vero che un raddoppio del codice di una funzione critica,
riferito alla centinaia di megabyte di ram disponibili sui sistemi attuali
sia in genere trascurabile. Vorrei farti però notare che per funzioni
ricorsive un grosso carico di lavoro consiste nel meccanismo di chiamata
(push e pop dei registri e passaggio dei valori). Risparmiare una
sottrazione ed un salto condizionale in rapporto al totale del codice della
funzione più il costo di chiamata potrebbe essere irrilevante e forse
potrebbe essere conveniente concentrarsi anche su questi altri punti. Ad
esempio passaggio di parametri tramite variabili statiche o attraverso
registri del processore. Considera a tal proposito le funzioni di
ottimizzazione del tuo compilatore.
La soluzione ideale sarebbe quella di convertire una soluzione ricorsiva in
una soluzione iterativa (risparmieresti i costi di chiamata e del passaggio
di parametri sullo stack)
----
Sergio Bianchi

>Quale di queste due soluzioni è più performante?
Se vuoi essere performante, allora scordati la ricorsione. Ogni
chiamata ricorsiva ti fa perdere tempo a salvare parametri sullo
stack. IMHO è meglio una scelta iterativa.
---
Massimiliano Iannotta
Università degli studi del Sannio
Informatic Engineering in progress ...