Pagina 1 di 1

Inviato: 14 aprile 2010, 16:18
da ArchGuy
Domanda stupidotta... quanto impiega il vostro sistema a calcolare in 50' numero di fibonacci, tramite interprete ocaml (E opportuna definizione ricorsiva).

Io sinceramente non mi aspettavo impiegasse cosi' tanto... non vorrei aver fornito una definizione un poco "farlocca", sebbene il risultato sia corretto.

Inviato: 14 aprile 2010, 16:27
da Asa
Non so cosa significhi
tramite interprete ocaml (E opportuna definizione ricorsiva).
ma so che il calcolo dei numeri di fibonacci non andrebbe trattato mai per ricorsione se non al fine didattico di dimostrare che è uno spreco di risorse.

Per calcolare il 50mo numero devi chiamare qualcosa tipo 2^50 volte la funzione e questo per me basta a giustificare dei tempi epocali. con un ciclo sempilce te la cavi con 50 cicli di poche istruzioni.

Inviato: 14 aprile 2010, 16:40
da ArchGuy
Asa ha scritto:Non so cosa significhi
tramite interprete ocaml (E opportuna definizione ricorsiva).
ma so che il calcolo dei numeri di fibonacci non andrebbe trattato mai per ricorsione se non al fine didattico di dimostrare che è uno spreco di risorse.

Per calcolare il 50mo numero devi chiamare qualcosa tipo 2^50 volte la funzione e questo per me basta a giustificare dei tempi epocali. con un ciclo sempilce te la cavi con 50 cicli di poche istruzioni.
Non lo metto in dubbio ma la mia domanda riguardava proprio il fatto che impiegasse cosi' tanto tramite una definizione ricorsiva della funzione anziche' una piu' opportuna iterazione.

Inviato: 14 aprile 2010, 18:36
da Howl
Non conosco ocaml però per questo genere di problemi se li vuoi risolvere con la ricorsione è opportuno utilizzare la memoizzazione: ti salvi in un array i valori già calcolati così li eviti di ricalcolare in futuro. Tra l'altro se non sbaglio ocaml è un linguaggio funzionale e in genere questi tipi di linguaggi possiedono dei costrutti appositi per accedere a valori precedentemente calcolati.

Su wiki c'è proprio fibonacci come esempio di applicazione della memoizzazione.

Inviato: 14 aprile 2010, 18:43
da ArchGuy
Il fatto e' che dal punto di vista strettamente funzionale non c'e' il concetto di "memoria" per cui credo che fare come dici (Ovviamente possibile visto che ocaml ha ben altro oltre che un "nucleo" puramente funzionale) "violerebbe" un poco il concetto vero e proprio di programmazione funzionale.

Inviato: 14 aprile 2010, 18:54
da aleph
non conosco ocaml, ma in haskell (che è pure funzionale) userei una struttura detta 'lista infinita' che permette di definire in maniera funzionale ed efficiente qualcosa del genere

Codice: Seleziona tutto

fibo@(1:tfibo) = 1:2:[x+y|(x,y) <- zip fibo tfibo
questo dovrebbe essere i8l costrutto equivalente in ocalm (se hai voglia di studiarlo): http://enfranchisedmind.com/blog/posts/ ... roduction/

e un pò di varianti per fibonacci in ocaml: http://cubbi.com/fibonacci/ocaml.html

Inviato: 14 aprile 2010, 19:03
da ArchGuy
L'implementazione che ho dato per il calcolo della serie e' esattamente di quella data al secondo link (nativa).
Le altre varianti prevedono, mi pare, tecniche di caching e memorizzazione varia che a me non interessano.
Mi premeva sapere esclusivamente le effettive prestazioni in caso di imlementazione funzionale naive.

Inviato: 14 aprile 2010, 20:01
da aleph
ArchGuy ha scritto:Mi premeva sapere esclusivamente le effettive prestazioni in caso di imlementazione funzionale naive.
l'implementazione ricorsiva costa O(2^n), quindi, come hai notato, è mostruosamente lenta. Un'implementazione migliore arriva facilmente a O(n) (lineare) . .

ti consiglio di studiarti le liste infinite, che sono comode per risolvere i problemi che richiedono un minimo di memorizzazione senza abbandonare il paradigma funzionale ;)

Inviato: 15 aprile 2010, 9:15
da ArchGuy
Ma in ocaml, se non sbaglio il "concetto" di lista e' proprio quello di lista infinita.

Quello che non mi e' molto chiaro e' come sia effettivamente possibile fornire una implementazione ricorsiva senza ricorrere a memorizzazione e senza incorrere nel "ricalcolo" di valori in realta' gia' calcolati in precedenza.

Inviato: 17 aprile 2010, 18:53
da psychoweb
attenzione archguy, nonostante la funzione di fibonacci sia definita tramite una relazione di ricorrenza non è affatto detto che la ricorsione sia il modo più efficente per implementarla in un linguaggio di programmazione.
Concettualmente la ricorsione è considerata elegante dal punto di vista del coding, ma nei casi pratici spesso si preferisce un approccio iterativo per avere sotto controllo memoria e tempi di calcolo.
In questo preciso caso il problema è che dentro la definizione c'è una ricorsione doppia, per cui la funzione ti "esplode" in spazio e tempo, parlando di ricorsione pura e senza strutture/tecniche ausiliari.

Inviato: 19 aprile 2010, 10:40
da ArchGuy
QUesto mi sembra si sia detto sin dall'inizio.
Il fatto e' che per "necessita"/interesse vorrei fare riferimento esclusivamente al paradigma funzionale ed eventualmente alla possibilita' di una diversa implementazione, che risulti essere meno ineficciente rispetto alla soluzione naive, pur non ricorrendo a "tecniche" di memorizzazione/caching.