Ce document montre deux exemples d'implémentations d'un procédé générique (mais basique) de mémoïsation en Python et en OCaml
On commence avec des fonctions inutilement lentes :
from time import sleep
def f1(n):
sleep(3)
return n + 3
def f2(n):
sleep(4)
return n * n
%timeit f1(10)
%timeit f2(10)
C'est étrangement court !
def memo(f):
memoire = {} # dictionnaire vide, {} ou dict()
def memo_f(n): # nouvelle fonction
if n not in memoire: # verification
memoire[n] = f(n) # stockage
return memoire[n] # lecture
return memo_f # ==> f memoisée !
memo_f1 = memo(f1)
print("3 secondes...")
print(memo_f1(10)) # 13, 3 secondes après
print("0 secondes !")
print(memo_f1(10)) # instantanné !
# différent de ces deux lignes !
print("3 secondes...")
print(memo(f1)(10))
print("3 secondes...")
print(memo(f1)(10)) # 3 secondes aussi !
%timeit memo_f1(10) # instantanné !
Et :
memo_f2 = memo(f2)
print("4 secondes...")
print(memo_f2(10)) # 100, 4 secondes après
print("0 secondes !")
print(memo_f2(10)) # instantanné !
%timeit memo_f2(10) # instantanné !
Ce n'est pas tellement plus compliquée de typer la mémoïsation.
def memo_avec_type(f):
memoire = {} # dictionnaire vide, {} ou dict()
def memo_f_avec_type(n):
if (type(n), n) not in memoire:
memoire[(type(n), n)] = f(n)
return memoire[(type(n), n)]
return memo_f_avec_type
Avantage, on obtient un résultat plus cohérent "au niveau de la reproducibilité des résultats", par exemple :
def fonction_sur_entiers_ou_flottants(n):
if isinstance(n, int):
return 'Int'
elif isinstance(n, float):
return 'Float'
else:
return '?'
test0 = fonction_sur_entiers_ou_flottants
print(test0(1))
print(test0(1.0)) # résultat correct !
print(test0("1"))
test1 = memo(fonction_sur_entiers_ou_flottants)
print(test1(1))
print(test1(1.0)) # résultat incorrect !
print(test1("1"))
test2 = memo_avec_type(fonction_sur_entiers_ou_flottants)
print(test2(1))
print(test2(1.0)) # résultat correct !
print(test2("1"))
def fibo(n):
if n <= 1: return 1
else: return fibo(n-1) + fibo(n-2)
print("Test de fibo() non mémoisée :")
for n in range(10):
print("F_{} = {}".format(n, fibo(n)))
Cette fonction récursive est terriblement lente !
%timeit fibo(35)
# version plus rapide !
@memo
def fibo2(n):
if n <= 1: return 1
else: return fibo2(n-1) + fibo2(n-2)
print("Test de fibo() mémoisée (plus rapide) :")
for n in range(10):
print("F_{} = {}".format(n, fibo2(n)))
%timeit fibo2(35)
Autre exemple, ou le gain de temps est moins significatif.
def factorielle(n):
if n <= 0: return 0
elif n == 1: return 1
else: return n * factorielle(n-1)
print("Test de factorielle() non mémoisée :")
for n in range(10):
print("{}! = {}".format(n, factorielle(n)))
%timeit factorielle(30)
@memo
def factorielle2(n):
if n <= 0: return 0
elif n == 1: return 1
else: return n * factorielle2(n-1)
print("Test de factorielle() mémoisée :")
for n in range(10):
print("{}! = {}".format(n, factorielle2(n)))
%timeit factorielle2(30)
En Python, c'est facile, avec des dictionnaires génériques et une syntaxe facilitée avec un décorateur.
Bonus : ce décorateur est dans la bibliothèque standard dans le module functools !
from functools import lru_cache # lru = least recently updated
@lru_cache(maxsize=None)
def fibo3(n):
if n <= 1: return 1
else: return fibo3(n-1) + fibo3(n-2)
print("Test de fibo() mémoisée avec functools.lru_cache (plus rapide) :")
for n in range(10):
print("F_{} = {}".format(n, fibo3(n)))
%timeit fibo2(35)
%timeit fibo3(35)
%timeit fibo2(70)
%timeit fibo3(70)
(On obtient presque les mêmes performances que notre implémentation manuelle)
Je traite exactement les mêmes exemples.
J'expérimente l'utilisation de deux kernels Jupyter différents pour afficher des exemples de codes écrits dans deux langages dans le même notebook... Ce n'est pas très propre mais ça marche.
Quelques fonctions nécessaires pour ces exemples :
let print = Format.printf;;
let sprintf = Format.sprintf;;
let time = Unix.time;;
let sleep n = Sys.command (sprintf "sleep %i" n);;
let timeit (repet : int) (f : 'a -> 'a) (x : 'a) () : float =
let time0 = time () in
for _ = 1 to repet do
ignore (f x);
done;
let time1 = time () in
(time1 -. time0 ) /. (float_of_int repet)
;;
let f1 n =
ignore (sleep 3);
n + 2
;;
let _ = f1 10;; (* 13, après 3 secondes *)
timeit 3 f1 10 ();; (* 3 secondes *)
Et un autre exemple similaire :
let f2 n =
ignore (sleep 4);
n * n
;;
let _ = f2 10;; (* 100, après 3 secondes *)
timeit 3 f2 10 ();; (* 4 secondes *)
On utilise le module Hashtbl de la bibliothèque standard.
let memo f =
let memoire = Hashtbl.create 128 in (* taille 128 par defaut *)
let memo_f n =
if Hashtbl.mem memoire n then (* lecture *)
Hashtbl.find memoire n
else begin
let res = f n in (* calcul *)
Hashtbl.add memoire n res; (* stockage *)
res
end
in
memo_f (* nouvelle fonction *)
;;
Deux exemples :
let memo_f1 = memo f1 ;;
let _ = memo_f1 10 ;; (* 3 secondes *)
let _ = memo_f1 10 ;; (* instantanné *)
timeit 100 memo_f1 20 ();; (* 0.03 secondes *)
let memo_f2 = memo f2 ;;
let _ = memo_f2 10 ;; (* 4 secondes *)
let _ = memo_f2 10 ;; (* instantanné *)
timeit 100 memo_f2 20 ();; (* 0.04 secondes *)
Ma fonction
timeitfait un nombre paramétrique de répétitions sur des entrées non aléatoires, donc le temps moyen observé dépend du nombre de répétitions !
timeit 10000 memo_f2 50 ();; (* 0.04 secondes *)
let rec fibo = function
| 0 | 1 -> 1
| n -> (fibo (n - 1)) + (fibo (n - 2))
;;
fibo 40;;
timeit 10 fibo 40 ();; (* 4.2 secondes ! *)
Et avec la mémoïsation automatique :
let memo_fibo = memo fibo;;
memo_fibo 40;;
timeit 10 memo_fibo 41 ();; (* 0.7 secondes ! *)
En OCaml, ce n'était pas trop dur non plus en utilisant une table de hachage (dictionnaire), disponibles dans le module Hashtbl.
On est confronté à une limitation de Caml, à savoir que la la fonction memo_f doit être bien typée pour être renvoyée par memo f donc memo ne peut pas avoir un type générique : il faut écrire un décorateur de fonction pour chaque signature bien connue de la fonction qu'on veut mémoïser...