Serie di fibonacci

Se avete dubbi o domande sulla programmazione in generale, fatele qui
Rispondi
ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 14 aprile 2010, 16:18

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Asa
Arciere Provetto
Messaggi: 456
Iscritto il: 3 giugno 2009, 14:53
Località: Milano
Contatta:

Messaggio da Asa » 14 aprile 2010, 16:27

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.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 14 aprile 2010, 16:40

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Howl
Arciere Provetto
Messaggi: 435
Iscritto il: 28 luglio 2008, 19:32

Messaggio da Howl » 14 aprile 2010, 18:36

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.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 14 aprile 2010, 18:43

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

aleph
Robin Hood
Messaggi: 1530
Iscritto il: 12 febbraio 2008, 16:30
Contatta:

Messaggio da aleph » 14 aprile 2010, 18:54

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
ImmagineOutside of a dog, computers are a man's best friend, inside a dog it's too dark to type.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 14 aprile 2010, 19:03

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

aleph
Robin Hood
Messaggi: 1530
Iscritto il: 12 febbraio 2008, 16:30
Contatta:

Messaggio da aleph » 14 aprile 2010, 20:01

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 ;)
ImmagineOutside of a dog, computers are a man's best friend, inside a dog it's too dark to type.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 15 aprile 2010, 9:15

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

psychoweb
Novello Arciere
Messaggi: 108
Iscritto il: 15 luglio 2008, 8:58

Messaggio da psychoweb » 17 aprile 2010, 18:53

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.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 19 aprile 2010, 10:40

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.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Rispondi