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)
3 s ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit f2(10)
4 s ± 1.25 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
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 !
3 secondes... 13 0 secondes ! 13 3 secondes... 13 3 secondes... 13
%timeit memo_f1(10) # instantanné !
122 ns ± 5.67 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
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é !
4 secondes... 100 0 secondes ! 100
%timeit memo_f2(10) # instantanné !
120 ns ± 3.43 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
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 obtiens 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"))
Int Float ?
test1 = memo(fonction_sur_entiers_ou_flottants)
print(test1(1))
print(test1(1.0)) # résultat incorrect !
print(test1("1"))
Int Int ?
test2 = memo_avec_type(fonction_sur_entiers_ou_flottants)
print(test2(1))
print(test2(1.0)) # résultat correct !
print(test2("1"))
Int Float ?
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)))
Test de fibo() non mémoisée : F_0 = 1 F_1 = 1 F_2 = 2 F_3 = 3 F_4 = 5 F_5 = 8 F_6 = 13 F_7 = 21 F_8 = 34 F_9 = 55
Cette fonction récursive est terriblement lente !
%timeit fibo(35)
3.15 s ± 74.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# 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)))
Test de fibo() mémoisée (plus rapide) : F_0 = 1 F_1 = 1 F_2 = 2 F_3 = 3 F_4 = 5 F_5 = 8 F_6 = 13 F_7 = 21 F_8 = 34 F_9 = 55
%timeit fibo2(35)
118 ns ± 2.59 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
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)))
Test de factorielle() non mémoisée : 0! = 0 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880
%timeit factorielle(30)
4.53 µs ± 214 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
@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)))
Test de factorielle() mémoisée : 0! = 0 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880
%timeit factorielle2(30)
124 ns ± 6.32 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
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)))
Test de fibo() mémoisée avec functools.lru_cache (plus rapide) : F_0 = 1 F_1 = 1 F_2 = 2 F_3 = 3 F_4 = 5 F_5 = 8 F_6 = 13 F_7 = 21 F_8 = 34 F_9 = 55
%timeit fibo2(35)
115 ns ± 2.83 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit fibo3(35)
86.6 ns ± 1.62 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit fibo2(70)
117 ns ± 1.44 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit fibo3(70)
86.2 ns ± 1.12 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
(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);;
val print : ('a, Format.formatter, unit) format -> 'a = <fun>
val sprintf : ('a, unit, string) format -> 'a = <fun>
val time : unit -> float = <fun>
val sleep : int -> int = <fun>
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)
;;
val timeit : int -> ('a -> 'a) -> 'a -> unit -> float = <fun>
let f1 n =
ignore (sleep 3);
n + 2
;;
val f1 : int -> int = <fun>
let _ = f1 10;; (* 13, après 3 secondes *)
- : int = 12
timeit 3 f1 10 ();; (* 3 secondes *)
- : float = 3.
Et un autre exemple similaire :
let f2 n =
ignore (sleep 4);
n * n
;;
val f2 : int -> int = <fun>
let _ = f2 10;; (* 100, après 3 secondes *)
- : int = 100
timeit 3 f2 10 ();; (* 4 secondes *)
- : float = 4.
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 *)
;;
val memo : ('a -> 'b) -> 'a -> 'b = <fun>
Deux exemples :
let memo_f1 = memo f1 ;;
let _ = memo_f1 10 ;; (* 3 secondes *)
let _ = memo_f1 10 ;; (* instantanné *)
val memo_f1 : int -> int = <fun>
- : int = 12
- : int = 12
timeit 100 memo_f1 20 ();; (* 0.03 secondes *)
- : float = 0.03
let memo_f2 = memo f2 ;;
let _ = memo_f2 10 ;; (* 4 secondes *)
let _ = memo_f2 10 ;; (* instantanné *)
val memo_f2 : int -> int = <fun>
- : int = 100
- : int = 100
timeit 100 memo_f2 20 ();; (* 0.04 secondes *)
- : float = 0.04
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 *)
- : float = 0.0004
let rec fibo = function
| 0 | 1 -> 1
| n -> (fibo (n - 1)) + (fibo (n - 2))
;;
val fibo : int -> int = <fun>
fibo 40;;
- : int = 165580141
timeit 10 fibo 40 ();; (* 4.2 secondes ! *)
- : float = 4.2
Et avec la mémoïsation automatique :
let memo_fibo = memo fibo;;
val memo_fibo : int -> int = <fun>
memo_fibo 40;;
- : int = 165580141
timeit 10 memo_fibo 41 ();; (* 0.7 secondes ! *)
- : float = 0.7
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...