Newsgroup: it.comp.programmare
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

...

..penso anche io che nn ci sia molta differenza..cmq dipende anche
cosa controlli con l'IF.. se fai x esempio if (a>b) impiega meno tempo
rispetto ad un if (a!=0 && b>=(Prova>1) && Dividi(Prova, a)).. nel
primo caso puoi lasciare il controllo così com'è, nel secondo caso io
setterei una flag di tipo BOOLEAN, e porrei il controllo prima di
eseguire il tuo IF..
Esegui_If = TRUE;
<TUA FUNZIONE RICORSIVA>
if (Esegui_If){
   if (a!=0 && b>=(Prova>1) && Dividi(Prova, a)){
      Esegui_If = FALSE;  
      ...
   }
   <TUA FUNZIONE RICORSIVA>
}
Ciao..

Cosa ne pensate?
Se lo scopo e' la velocita' , allora le prestazioni migliorano usando
anche la funzione2.
Il fatto che raddoppia il codice non ha nessuna importanza sulle
prestazioni a tempo di esecuzione  : si tratta di una proprieta'
statica del codice: che preoccupazione puo' darti questo?
    bYBy Max      -------Contact me!!
e-Mail Address   :  
m.d...@tiscalinet.it
Internet Address :  
web.tiscali.it/maxdrudi/
  (<--under construction)
ICQ Number       :  131119449

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();
}

 statica del codice: che preoccupazione puo' darti questo?
Beh, la mia preoccupazione è che aumentando il codice c'è meno probabilità
di tenersi in cache tutto quanto, il che rallenta il processore!

Prova a vedere quanto occupano a livello di codice i due processi...
da quello che so, quando compili, al posto di una chiamata a funzione viene
copiata la funzione che hai chiamato. Quindi a livello di quantità di
memoria occupata dal codice dei due processi, non credo ci sia differenza.
Anzi, credo che occupi meno spazio la seconda soluzione! Ed è anche più
performante a livello di chiamate alle svc. Io propendo per la seconda,
soprattutto se la funzione ricorsiva deve essere chiamata molte volte!

 soprattutto se la funzione ricorsiva deve essere chiamata molte volte!
La funzione ricorsiva è breve e viene richiamata molte volte.
Anch'io propendo per la seconda ... ma non mi hai convinto.
Grazie lo stesso



Mentre il codice e' in esecuzione, ogni volta che avviene una nuova
chiamata di funzione, viene allocato nuovo spazio di memoria nello
stack segment per memorizzare le variabili locali (della nuova
funzione) ed alcune altre cose.
Caso 1: solo funzione1
In memoria si trova allocato staticamente il codice di funzione1.
Ogni chiamata di funzione1 fa aumentare di una cera quantita' la
dimensione dello stack
Caso 2: funzione1 e funzione2
In memoria si trova allocato staticamente il codice di funzione1 ed il
codice di funzione2.
Ogni chiamata a funzione1 o funzione2 fa aumentare di una cera
quantita' la dimensione dello stack. 
A questo punto io farei due osservazioni:
1) lo stack e' gestito come fosse una pila. Ogni volta che si chiama
una funzione la sua dimensione aumenta, e corrispondentemente ogni
volta che una funzione termina la sua dimensione diminuisce.
Indipendentemente dalla dimensione dello stack (che puo' diventare
molto molto grande), in un certo istante viene usata solo la sua
testa, dove ci sono le info della funzione attualmente in esecuzione.
QUINDI anche se la funzione si richiama molte volte, la cache dovra'
tenere traccia solo ed esclusivamente della testa dello stack (non di
tutto lo stack che contiene info di tutte le funzioni chiamate), e
dovra' seguire i sui spostamenti ...
2)se abbiamo due programmi (uno in linea co il caso 1 e l'altro in
linea con il caso 2) e gli diamo lo stesso input, la variazione nel
tempo della memoria allocata per lo stack e' identica in entrambi i
casi. Se nel caso 1 la funzione1 si chiama ricorsivamente 100 (e' un
esempio) volte, allora nel caso 2 succede che la funzione1 si
chiamera' ricorsivamente x1 volte, la funzione2 si chiamera'
ricorsivamente x2 volte e risultera' in definitiva che x1+x2=100 ...
quindi anche in questo caso viene allocato spazio nello stack per 100
chiamate di funzione.
QUINDI dal punto di vista dell'uso dello stack nel tempo  (quantita'
di memoria che nel tempo viene allocata e deallocata) non c'e' nessuna
differenza tra il caso 1 ed il caso 2.
Scusa se ho scritto molto. Il concetto di stack e' il nocciolo della
questione. Nel contesto che hai descritto non esiste nessun motivo a
sfavore dell'uso di funzione2. Esiste invece un motivo a favore
del''uso di funzione2 (una if in meno...avendo la garanzia che si
tratta di un controllo con esito certo).
Salvo qualche proprieta' particolare di questo programma che magari
non e' ancora stata messa in evidenza, io userei senza dubbio anche la
funzione2.


 quantita' la dimensione dello stack.
Grazie Max per la chiarissima spiegazione.
Perň hai toccato "solo" il tema dello stack.
Cosa implica il fatto che:
nel caso1 in memoria si trova allocato staticamente il codice della
funzione1.
nel caso2 in memoria si trova allocato staticamente il codice della
funzione1 e della funzione2.
Se la memoria allocata staticamente č significativamente tanta, credo che il
caso1 sia piů veloce.
Cioč, il processore deve fare meno salti qua e la' per reperire il codice
eseguibile.
In linea teorica credo dovrebbe essere cosě.
Comunque grazie ancora.


Vorrei alcune informazioni ulteriori sul problema:
1)La variabile *a* su cui esegui il famoso *if* e' il risultato di una
qualche elaborazione precedente, tale elaborazione rimarrebbe anche in
funzione2?
2)funzione1 e funzione2 sono realmente prive di parametri?
3)Qual'e' l'ordine di grandezza della ricorsione (decine, centinaia,
migliaia di ricorsioni)?
Ti faccio queste domande perche', secondo me, c'e' la possibilita' che il
tempo *sprecato* ad eseguire l'if sia trascurabile rispetto ad altri fattori
che possono influenzare il tempo d'esecuzione del programma.
Ciao, Davide.

In linea teorica credo dovrebbe essere cosě.
Ad esser sincero non so fino a che punto puo' essere ragionevole
scrivere un programma pensando ad un uso ottimale della cache. Il
fatto e' che in generale nel sistema ci sono anche altri programmi in
esecuzione.
Altra cosa ... giusto per spizzico: se la cache fosse grande
abbastanza da fare entrare tutto il programma, e nel sistema e'
avviabile un solo programma per volta, tutto questo discorso non
avrebbe molto senso ovviamente. 
Non avrebbe senso anche se la cache fosse talmente piccola, tanto
piccola da non essere neanche in grado di memorizzare tutto quello che
serve per eseguire tranquillamente la funzione1 (funzione1 e tutte le
eventuali funzioni non ricorsive che chiama, quanto occupano?).
In PRATICA e' un bel casino: quanto e' grande la cache? quanto e'
grande il codice macchina del programma? quanto e' grande e come e'
allocato il codice macchina delle singole funzioni? cosa fanno gli
altri processi (=programmi in esecuzione)  del sistema?
Dato l'estrema difficolta' o addirittura l'impossibilita' di
controllare tutte queste cose, in genere il programmatore lavora ad un
livello di astrazione ben superiore alla cache.


Concordo in tutto.
La tua spiegazione č chiarissima.
GRAZIE Max!!!
Nel mia applicazione credo quindi che convenga la soluzione2.
(Anche se č altrettanto chiaro che questa (eliminazione dell if) č una
"limatina" davvero poco significativa, in confronto alla gestione della
ricorsione.)

 migliaia di ricorsioni)?
Centinaia di migliaia, forse milioni.
E' proprio per questo che sto cercando anche le "limatine".

Proviamo a fare una stima delle prestazioni utilizzando i seguenti
parametri:
1 Milione di ricorsioni
if(a) eseguito con 2 istruzioni macchina
funzione1 con tre parametri
cpu a 300MHz con IPC=1 (Istruzioni eseguite ogni ciclo di clock)
Con questi parametri il tempo *perso* per eseguire gli if e' di 6.7 msec
mentre la memoria stack necessaria per permettere la ricorsione e' di 11.44
MByte (supponendo che i parametri siano salvati sullo stack come parole a 32
bit ed aggiungendo anche l'indirizzo di ritorno anch'esso a 32bit).
Secondo me e' piu' preoccupante lo stack che potrebbe andare in overflow
piuttosto che l'overhead dell'esecuzione dell' if.
P.S: Con CPU piu' performanti di quella da me ipotizzata il tempo di
esecuzione diminuisce (con un P4 arriviamo fino a IPC=3 e frequenze dino a
2GHz) ma non la dimensione dello stack.

 parametri:
GRAZIE anche a te!!
I numeri dei tuoi calcoli sono chiarissimi e autospieganti.
ciao, DANILO.

 E' proprio per questo che sto cercando anche le "limatine".
probabilmente e` una domanda stupida ma...
sei sicuro che stai usando l'algoritmo migliore per risolvere il tuo 
problema?
L'impressione e` che tu stia cercando di risolvere per "enumerazione 
esaustiva" un problema che forse puo` essere risolto piu` efficaciemente 
con altri algoritmi. Ripeto, e` solo una impressione e magari il tuo e` 
un problema che non ammette soluzioni migliori, pero` il dubbio viene...
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 un problema che non ammette soluzioni migliori, pero` il dubbio viene...
Cos'è che ti fa venire il dubbio?
Ho realizzato un algoritmo molto complesso capace di trovare una buona
soluzione per
un problema classico e molto diffuso nelle realtà industriali che è NP-hard.
L'esempio che ho sottoposto alla vostra attenzione è un esempio!
Il problema che volevo discutere è tutto lì nell'esempio.
Detto ciò, probabilmente esisteranno algoritmi migliori del mio.
A livello commerciale sono sicuro che non esistono.
Grazie, ciao!
DANILO

 un problema classico e molto diffuso nelle realtą industriali che č
NP-hard.
Se hai trovato una soluzione polinomiale faccelo sapere che ci interessa :)
Ciao, Davide.

> Se hai trovato una soluzione polinomiale faccelo sapere che ci interessa
:)
ROTFL
ciao

 NP-hard.
ok, detto questo mi pare ovvio che un algoritmo efficiente non esiste :-(
