Algoritm de memoizare

Am gasit intr-o carte un foarte interesant algoritm de memoizare. Practic este vorba despre o functie (memoize) care ia ca argument functia pe care vrem sa o memoizam , si intoarce ca si valoare -> un local scope in care declaram tabelul in care tinem valorile calculate. Acest local scope intoarce ca si rezultat o functie care ia un argument.
   Avem :

  
(define (memoize f)
					   (let  ((table (make-table)))
						   (lambda (x)
							  (let  ((seen (lookup x table)))
								 (if (not (null? seen))
									  seen
									  (let ((ans (f x)))
											(insert! x ans table)
											ans))))))
  

unde : (make-table) este o functie care returneaza un tabel
  (lookup x table) este o functie care verifica daca intr-un table oarecare exista un obiect cu cheia x
  (insert! x ans table) este o functie care insereaza ans intr-un tabel , si ii atribuie cheia x.
aceste trei functii sunt implementate in functie de limbajul folosit, vointa si imaginatia fiecaruia.
   sintaxa pentru let : let este folosit in general petru a creea variabile locale
          Ex :
                

							  (let ((a 5))
								  (*  (+ a 1) 2) ))
				

echivalent logic cu :

	   ( (lambda  (a) (* (+ a 1) 2)) 5)
												

iar functia care calculeaza numerele fibonacci :

	  
 (define  mem-fib
			(memoize (lambda (n)
									 (cond ((= n 0) 0)
											   ((= n 1) 1)
											   (else (+  (mem-fib (- n 1))
															 (mem-fib (- n 2)))))))

Edited by Ltschmer, 19 July 2018 - 12:49.