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
In [1]:
from time import sleep
In [2]:
def f1(n):
sleep(3)
return n + 3
def f2(n):
sleep(4)
return n * n
In [3]:
%timeit f1(10)
In [4]:
%timeit f2(10)
In [5]:
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 !
In [6]:
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 !
In [7]:
%timeit memo_f1(10) # instantanné !
Et :
In [8]:
memo_f2 = memo(f2)
print("4 secondes...")
print(memo_f2(10)) # 100, 4 secondes après
print("0 secondes !")
print(memo_f2(10)) # instantanné !
In [9]:
%timeit memo_f2(10) # instantanné !
In [10]:
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 obtiens un résultat plus cohérent "au niveau de la reproducibilité des résultats", par exemple :
In [11]:
def fonction_sur_entiers_ou_flottants(n):
if isinstance(n, int):
return 'Int'
elif isinstance(n, float):
return 'Float'
else:
return '?'
In [12]:
test0 = fonction_sur_entiers_ou_flottants
print(test0(1))
print(test0(1.0)) # résultat correct !
print(test0("1"))
In [14]:
test1 = memo(fonction_sur_entiers_ou_flottants)
print(test1(1))
print(test1(1.0)) # résultat incorrect !
print(test1("1"))
In [15]:
test2 = memo_avec_type(fonction_sur_entiers_ou_flottants)
print(test2(1))
print(test2(1.0)) # résultat correct !
print(test2("1"))
In [16]:
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 !
In [18]:
%timeit fibo(35)
In [33]:
# 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)))
In [21]:
%timeit fibo2(35)
Autre exemple, ou le gain de temps est moins significatif.
In [22]:
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)))
In [23]:
%timeit factorielle(30)
In [24]:
@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)))
In [25]:
%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 !
In [32]:
from functools import lru_cache # lru = least recently updated
In [34]:
@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)))
In [35]:
%timeit fibo2(35)
In [36]:
%timeit fibo3(35)
In [37]:
%timeit fibo2(70)
In [38]:
%timeit fibo3(70)
(On obtient presque les mêmes performances que notre implémentation manuelle)
In [7]:
let print = Format.printf;;
let sprintf = Format.sprintf;;
let time = Unix.time;;
let sleep n = Sys.command (sprintf "sleep %i" n);;
Out[7]:
Out[7]:
Out[7]:
Out[7]:
In [11]:
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)
;;
Out[11]:
In [12]:
let f1 n =
ignore (sleep 3);
n + 2
;;
Out[12]:
In [13]:
let _ = f1 10;; (* 13, après 3 secondes *)
Out[13]:
In [14]:
timeit 3 f1 10 ();; (* 3 secondes *)
Out[14]:
Et un autre exemple similaire :
In [15]:
let f2 n =
ignore (sleep 4);
n * n
;;
Out[15]:
In [18]:
let _ = f2 10;; (* 100, après 3 secondes *)
Out[18]:
In [19]:
timeit 3 f2 10 ();; (* 4 secondes *)
Out[19]:
On utilise le module Hashtbl de la bibliothèque standard.
In [20]:
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 *)
;;
Out[20]:
Deux exemples :
In [21]:
let memo_f1 = memo f1 ;;
let _ = memo_f1 10 ;; (* 3 secondes *)
let _ = memo_f1 10 ;; (* instantanné *)
Out[21]:
Out[21]:
Out[21]:
In [24]:
timeit 100 memo_f1 20 ();; (* 0.03 secondes *)
Out[24]:
In [28]:
let memo_f2 = memo f2 ;;
let _ = memo_f2 10 ;; (* 4 secondes *)
let _ = memo_f2 10 ;; (* instantanné *)
Out[28]:
Out[28]:
Out[28]:
In [29]:
timeit 100 memo_f2 20 ();; (* 0.04 secondes *)
Out[29]:
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 !
In [31]:
timeit 10000 memo_f2 50 ();; (* 0.04 secondes *)
Out[31]:
In [32]:
let rec fibo = function
| 0 | 1 -> 1
| n -> (fibo (n - 1)) + (fibo (n - 2))
;;
Out[32]:
In [38]:
fibo 40;;
Out[38]:
In [42]:
timeit 10 fibo 40 ();; (* 4.2 secondes ! *)
Out[42]:
Et avec la mémoïsation automatique :
In [48]:
let memo_fibo = memo fibo;;
Out[48]:
In [49]:
memo_fibo 40;;
Out[49]:
In [50]:
timeit 10 memo_fibo 41 ();; (* 0.7 secondes ! *)
Out[50]:
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...