#!/usr/bin/env python
# coding: utf-8
# # Table of Contents
#
# # Mémoïsation, en Python et en OCaml
#
# Ce document montre deux exemples d'implémentations d'un procédé générique (mais basique) de [mémoïsation](https://fr.wikipedia.org/wiki/M%C3%A9mo%C3%AFsation) en [Python](https://python.org/) et en [OCaml](https://ocaml.org/)
# ## En Python
# ### Exemples de fonctions à mémoïser
# On commence avec des fonctions inutilement lentes :
# 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]:
get_ipython().run_line_magic('timeit', 'f1(10)')
# In[4]:
get_ipython().run_line_magic('timeit', 'f2(10)')
# ### Mémoïsation générique, non typée
# C'est étrangement court !
# 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 !
# ### Essais
# 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]:
get_ipython().run_line_magic('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]:
get_ipython().run_line_magic('timeit', 'memo_f2(10) # instantanné !')
# ### Mémoïsation générique et typée
# Ce n'est pas tellement plus compliquée de typer la mémoïsation.
# 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"))
# ### Bonus : on peut utiliser la syntaxe d'un décorateur en Python
# 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]:
get_ipython().run_line_magic('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]:
get_ipython().run_line_magic('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]:
get_ipython().run_line_magic('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]:
get_ipython().run_line_magic('timeit', 'factorielle2(30)')
# ### Conclusion
# 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](https://docs.python.org/3/library/functools.html#functools.lru_cache) dans le [module functools](https://docs.python.org/3/library/functools.html) !
# 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]:
get_ipython().run_line_magic('timeit', 'fibo2(35)')
# In[36]:
get_ipython().run_line_magic('timeit', 'fibo3(35)')
# In[37]:
get_ipython().run_line_magic('timeit', 'fibo2(70)')
# In[38]:
get_ipython().run_line_magic('timeit', 'fibo3(70)')
# (On obtient presque les mêmes performances que notre implémentation manuelle)
# ----
# ## En OCaml
#
# 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*.
# ### Préliminaires
#
# Quelques fonctions nécessaires pour ces exemples :
# In[7]:
let print = Format.printf;;
let sprintf = Format.sprintf;;
let time = Unix.time;;
let sleep n = Sys.command (sprintf "sleep %i" n);;
# 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)
("")("")
# ### Exemples de fonctions à mémoïser
# In[12]:
let f1 n =
ignore (sleep 3);
n + 2
("")("")
# In[13]:
let _ = f1 10;; (* 13, après 3 secondes *)
# In[14]:
timeit 3 f1 10 ();; (* 3 secondes *)
# Et un autre exemple similaire :
# In[15]:
let f2 n =
ignore (sleep 4);
n * n
("")("")
# In[18]:
let _ = f2 10;; (* 100, après 3 secondes *)
# In[19]:
timeit 3 f2 10 ();; (* 4 secondes *)
# ### Mémoïsation pour des fonctions d'un argument
# On utilise le module [Hashtbl](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html#VALcreate) 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 *)
("")("")
# ### Essais
# Deux exemples :
# In[21]:
let memo_f1 = memo f1 ;;
let _ = memo_f1 10 ;; (* 3 secondes *)
let _ = memo_f1 10 ;; (* instantanné *)
# In[24]:
timeit 100 memo_f1 20 ();; (* 0.03 secondes *)
# In[28]:
let memo_f2 = memo f2 ;;
let _ = memo_f2 10 ;; (* 4 secondes *)
let _ = memo_f2 10 ;; (* instantanné *)
# In[29]:
timeit 100 memo_f2 20 ();; (* 0.04 secondes *)
# > Ma fonction `timeit` fait 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 *)
# ### Exemple de la suite de Fibonacci
# In[32]:
let rec fibo = function
| 0 | 1 -> 1
| n -> (fibo (n - 1)) + (fibo (n - 2))
("")("")
# In[38]:
fibo 40;;
# In[42]:
timeit 10 fibo 40 ();; (* 4.2 secondes ! *)
# Et avec la mémoïsation automatique :
# In[48]:
let memo_fibo = memo fibo;;
# In[49]:
memo_fibo 40;;
# In[50]:
timeit 10 memo_fibo 41 ();; (* 0.7 secondes ! *)
# ### Conclusion
#
# 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...