buongiorno,

di Python non sono un esperto, ma per farvi capire il mio livello di conoscenze posso dirvi che sono arrivato alla fine dell'undicesimo capitolo del libro gratuito "pensare in python":

http://www.ferrarialberto.com/scuola/as1819/3/materiale/thinkpython_italian.pdf


ed è proprio li, esattamente al paragrafo 11.6 dal titolo "memorizzazione" che ho problemi. nel paragrafo l'autore mette a confronto due codici diversi in cui è possibile creare una funzione "fibonacci" in modo differente. di seguito un programma che mette a confronto entrambi i codici (quando vedete memon? è in realtà "memo n" con "n" chiusa da delle parentesi quadre. è un dizionario. non so perché il sito mi da questo errore):

# funzione "fibonacci" con l'uso di un dizionario. il dizionario ci permette di
# memorizzare le prime due coppie di numeri, velocizzando il programma:
memo = {0:0, 1:1}

def fibonacci_1(n):
	if n in memo:
		return memon
	risultato = fibonacci_1(n-1) + fibonacci_1(n-2)
	memon = risultato
	return risultato

# funzione "fibonacci" senza l'uso di un dizionario. in questo caso le proime
# due coppie di numeri dovranno sempre essere calcolate:
def fibonacci_2(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fibonacci_2(n-1) + fibonacci_2(n-2)

# test per verificare la velocità di entrambe le funzioni:	
valore = int(input("\ndammi un intero ed io ti calcolerò la sequenda di fibonacci associata: "))

print ("\ncalcolo della sequenza di fibonacci per il valore", valore, "(con dizionario):\n")
print(fibonacci_1(valore))
print("memoria:", memo)

print ("\ncalcolo della sequenza di fibonacci per il valore", valore, "(no dizionario):\n")
print(fibonacci_2(valore))

la mia domanda è: come mai la prima funzione è più veloce della seconda? questo è quello che mi sembra di aver capito:

1. la prima funzione esegue se stessa utilizzando un dizionario come metodo per memorizzare il risultato delle altre chiamate di funzioni che avvengono durante la ricorsione. nel codice infatti, oltre al risultato, stampo a video anche il dizionario che tiene in memoria tutti i risultati delle diverse ricorsioni.

2. il secondo calcola, ad ogni ricorsione, il risultato senza utilizzare alcun tipo di memorizzazione. questo significa che ogni chiamata di funzione dovrà essere calcolata ogni volta, e questo rallenta il programma.


se quello che ho scritto è giusto quello che sicuramente non riesco a capire è come la prima funzione riesca a sfruttare la memorizzazione che implementa. anche nella prima funzione bisogna per forza calcolare tutte le ricorsioni prima di arrivare ad un risultato, poi quel risultato verrà posto in memoria ma quando viene utilizzato allora? non riesco a capire.. spero di essermi fatto capire perché senza un pezzo di carta sotto mano è un po difficile da spiegare..


--- Ultima modifica di TurboC in data 2019-05-12 18:22:48 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:23:13 ---


--- Ultima modifica di TurboC in data 2019-05-12 18:23:44 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:24:23 ---


--- Ultima modifica di TurboC in data 2019-05-12 18:24:57 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:25:46 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:25:54 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:26:13 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:26:38 ---

--- Ultima modifica di TurboC in data 2019-05-12 18:28:56 ---

Mah, per una volta devo dire che quel paragrafo di Pensare da Informatico spiega le cose abbastanza bene (davvero incredibile vista la qualità generale del libro). Direi che basta leggere con attenzione, a partire dal fatto che questa tecnica si chiama "memoizzazione" e non "memoRizzazione". Banalmente, la versione con la cache esce prima non appena incontra un ramo di ricorsione che è già stato calcolato, e di cui quindi si sa già il risultato. In questo modo si evita di ri-calcolare tutte le volte gli stessi rami di ricorsione, e si risparmia un po' di tempo. Se guardi la "figura 11.2" come ti suggerisce il libro, per esempio se vuoi calcolare fibonacci(4) prima o poi ti trovi a dover calcolare fibonacci(2) due volte (una nel ramo di destra e una in quello di sinistra, li hai visti nel disegno?). Ora, con la cache la prima volta effettivamente percorri ricorsivamente tutto l'albero, ma la seconda volta non ne hai bisogno perché la cache conserva già il valore di fibonacci(2), e puoi subito uscire da quel ramo di ricorsione col risultato in mano.


La memoizzazione è una tecnica molto comune soprattutto accoppiata con la ricorsione... Se vuoi un altro esempio spiegato in Italiano, mi è tornato in mente che nel glorioso e ormai abbandonato sito Stacktrace niente meno che Marco Beri spiega come risolvere l'esercizio 14 del Progetto Eulero (sulla congettura di Collatz), e ovviamente fa uso della memoizzazione https://stacktrace.it/2008/03/03/progetto-eulero-problema-14/

ti ringrazio per avermi fatto notare il nome "memoizzazione". pensavo fosse un errore del libro. il libro in se però non mi sembra cosi terribile. dici che dovrei affidarmi a qualcos'altro? fino ad ora non ho mai avuto problemi di comprensione anche se dire che è perfetto è un parolone, lo ammetto. spesso quando non capisco sono solito rileggere lo stesso argomento anche su altre fonti.

Se guardi la "figura 11.2" come ti suggerisce il libro, per esempio se vuoi calcolare fibonacci(4) prima o poi ti trovi a dover calcolare fibonacci(2) due volte (una nel ramo di destra e una in quello di sinistra, li hai visti nel disegno?)

si li ho visti ma, correggimi se sbaglio, anche se il programma dovrà calcolare la stessa funzione in entrambi i rami, prima di calcolare il loro risultato, e prima che questo venga salvato nel dizionario "memo" che funge da memoria, bisognerà aspettare che l'alberatura venga completata. solo nel momento in cui arriviamo alle funzioni che stanno alla base dell'alberatura, possiamo calcolare e alla fine salvare il risulatto di fibonacci(2). una volta calcolato il risultato si può finalmente risalire l'alberatura e calcolare tutto il resto.. nel risalire l'alberatura però troviamo numeri sempre più grandi. fibonacci(3) per esempio deve essere ancora calcolato! non ho ancora in memoria il suo risultato, per adesso ho solo il risultato di fibonacci(2). lo stesso vale anche per n = 4, 5, 6 e cosi via.. per calcolare fibonacci(4) dunque, dovrò prima arrivare in fondo all'alberatura e man mano che la risalgo, calcolare tutte le funzioni fibonacci(n) che compaiono.

sicuramente sbaglio qualcosa ma attualmente questo è ciò che leggo dal mio programma python. da come lo intepreto io, non arriveremo mai ad un punto in cui i valori salvati in memoria possano servire a qualcosa. dov'è che sbaglio?

Ora, con la cache la prima volta effettivamente percorri ricorsivamente tutto l'albero, ma la seconda volta non ne hai bisogno perché la cache conserva già il valore di fibonacci(2), e puoi subito uscire da quel ramo di ricorsione col risultato in mano.

forse ho capito cosa intendi, ma da come lo descrivi, sembra che python prima percorra il ramo a sinistra, e poi, quello a destra. in questo modo.. si, ho già fibonacci(2) in memoria e quindi posso evitare di andare avanti con l'alberatura. io invece pensavo che ogni ramo fosse calcolato allo stesso tempo. voglio dire, che in fibonacci(4), python calcolasse poi fibonacci(3) e fibonacci(2) contemporaneamente. non è cosi? puoi farmi chiarezza sul flusso di esecuzione?


--- Ultima modifica di TurboC in data 2019-05-13 00:52:35 ---

si, probabilmente python calcola prima l'alberatura a sinistra e poi quella a destra. perché nella somma "fibonacci_1(n-1) + fibonacci_1(n-2)", fibonacci_1(n-1) viene prima di fibonacci_1(n-2):

# attenzione! il sito visualizza "n" chiusa da parentesi quadre come "n?" non so perché..
def fibonacci_1(n):
	if n in memo:
		return memon
	risultato = fibonacci_1(n-1) + fibonacci_1(n-2)
	memon = risultato
	return risultato

quindi in "fibonacci_1(4)" python calcola prima tutta l'alberatura di fibonacci_1(3). successivamente viene anche calcolato fibonacci_1(2), ma il suo risultato è già in memoria per cui il calcolo è più veloce.

è giusto? mi dai una conferma per favore?


--- Ultima modifica di TurboC in data 2019-05-13 08:39:06 ---

--- Ultima modifica di TurboC in data 2019-05-13 08:39:54 ---

E dai però, prova un po' a immaginare: NON ha importanza se calcola prima la parte a destra o quella a sinistra: dipende banalmente da come scrivi la funzione. Se scrivi "fibonacci(n-1) + fibonacci(n-2)" andrà da una parte (quale? boh!), se scrivi "fibonacci(n-2) + fibonacci(n-1)" andrà dall'altra (quale? boh!). Che differenza c'è? Almeno l'ultima volta che ho controllato l'addizione aveva la proprietà commutativa. E' ancora così?
E già che ci siamo, dipende anche da come disegni la figura, no? Se (per dire) arrivi a capire che in quella figura percorre prima l'albero a destra, allora basta disegnare la figura al contrario, o metterla davanti allo specchio... e voilà, percorre prima l'albero a sinistra. E' solo una questione di convenzioni.





L'importante è capire che, ogni volta che deve chiamare fibonacci(x), per prima cosa vede se il risultato di fibonacci(x) sta già nella cache: se no, lo calcola. Quindi, la prima volta che lo incontra lo calcola percorrendo effettivamente il ramo (che sia il ramo di destra, ramo di sinistra, ramo di sotto o ramo di sopra... come vuoi tu, puoi divertirti a girare la figura in tutte le direzioni), la seconda volta no.








Detto questo, prima o poi scriverò una serie di articoli sulla c****ate più atroci di Pensare da Informatico... Ma almeno quel paragrafo non è scorretto... basta seguirlo con attenzione.

ho immaginato bene allora. non c'è bisogno di ironizzare comunque. ho avuto problemi di comprensione partendo dal presupposto, sbagliato ovviamente, che entrambe le funzioni (o alberature), venissero calcolate contemporaneamente, dimenticandomi completamente della proprietà commutativa come mi hai fatto giustamente notare. grazie. ora mi è tutto chiaro. vado avanti a studiare..

Eh sai, il problema non è tanto l'ironia, il problema è se hai capito davvero oppure no... e ogni tanto scrivi qualcosa che spalanca una voragine, che mi fa pensare che...


Per esempio, adesso, che cosa vuol dire "calcolate contemporaneamente"?... Poi guardo meglio la figura di quel maledetto libro (veramente... ma proibirlo una volta per tutte?!) e mi accorgo che ogni box di quella figura ha curiosamente due frecce... una cosa innocua, dopo tutto, giusto un modo per dire "va di qua E POI di là"..., ma intanto mi viene l'orrendo sospetto che tu *veramente* pensi che l'esecuzione del codice sia "contemporanea"... E da questo, che cosa *davvero* pensi che sia la ricorsione... Non so, è che Pensare da Informatico è talmente tanto un frattale di pessimo insegnamento, che non riesco mai a capire come la gente finisce per capire quello che c'è scritto sopra...





Comunque, alla fine ho preso spunto da questa conversazione e mi sono deciso a buttar giù un primo articolo di debunking di Pensare da Informatico... a futura memoria: https://pythoninwindows.blogspot.com/2019/05/non-pensare-da-informatico.html