{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Mémoïsation, en Python et en OCaml\n",
"\n",
"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/)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## En Python"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples de fonctions à mémoïser\n",
"On commence avec des fonctions inutilement lentes :"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from time import sleep"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"def f1(n):\n",
" sleep(3)\n",
" return n + 3\n",
"\n",
"def f2(n):\n",
" sleep(4)\n",
" return n * n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3 s ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%timeit f1(10)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4 s ± 1.25 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%timeit f2(10)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Mémoïsation générique, non typée\n",
"C'est étrangement court !"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def memo(f):\n",
" memoire = {} # dictionnaire vide, {} ou dict()\n",
" def memo_f(n): # nouvelle fonction\n",
" if n not in memoire: # verification\n",
" memoire[n] = f(n) # stockage\n",
" return memoire[n] # lecture\n",
" return memo_f # ==> f memoisée !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Essais"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3 secondes...\n",
"13\n",
"0 secondes !\n",
"13\n",
"3 secondes...\n",
"13\n",
"3 secondes...\n",
"13\n"
]
}
],
"source": [
"memo_f1 = memo(f1)\n",
"\n",
"print(\"3 secondes...\")\n",
"print(memo_f1(10)) # 13, 3 secondes après\n",
"print(\"0 secondes !\")\n",
"print(memo_f1(10)) # instantanné !\n",
"\n",
"# différent de ces deux lignes !\n",
"\n",
"print(\"3 secondes...\")\n",
"print(memo(f1)(10))\n",
"print(\"3 secondes...\")\n",
"print(memo(f1)(10)) # 3 secondes aussi !"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"122 ns ± 5.67 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit memo_f1(10) # instantanné !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et :"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4 secondes...\n",
"100\n",
"0 secondes !\n",
"100\n"
]
}
],
"source": [
"memo_f2 = memo(f2)\n",
"\n",
"print(\"4 secondes...\")\n",
"print(memo_f2(10)) # 100, 4 secondes après\n",
"print(\"0 secondes !\")\n",
"print(memo_f2(10)) # instantanné !"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"120 ns ± 3.43 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit memo_f2(10) # instantanné !"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Mémoïsation générique et typée\n",
"Ce n'est pas tellement plus compliquée de typer la mémoïsation."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"def memo_avec_type(f):\n",
" memoire = {} # dictionnaire vide, {} ou dict()\n",
" def memo_f_avec_type(n):\n",
" if (type(n), n) not in memoire:\n",
" memoire[(type(n), n)] = f(n)\n",
" return memoire[(type(n), n)]\n",
" return memo_f_avec_type"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Avantage, on obtient un résultat plus cohérent \"au niveau de la reproducibilité des résultats\", par exemple :"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"def fonction_sur_entiers_ou_flottants(n):\n",
" if isinstance(n, int):\n",
" return 'Int'\n",
" elif isinstance(n, float):\n",
" return 'Float'\n",
" else:\n",
" return '?'"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Int\n",
"Float\n",
"?\n"
]
}
],
"source": [
"test0 = fonction_sur_entiers_ou_flottants\n",
"print(test0(1))\n",
"print(test0(1.0)) # résultat correct !\n",
"print(test0(\"1\"))"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Int\n",
"Int\n",
"?\n"
]
}
],
"source": [
"test1 = memo(fonction_sur_entiers_ou_flottants)\n",
"print(test1(1))\n",
"print(test1(1.0)) # résultat incorrect !\n",
"print(test1(\"1\"))"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Int\n",
"Float\n",
"?\n"
]
}
],
"source": [
"test2 = memo_avec_type(fonction_sur_entiers_ou_flottants)\n",
"print(test2(1))\n",
"print(test2(1.0)) # résultat correct !\n",
"print(test2(\"1\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Bonus : on peut utiliser la syntaxe d'un décorateur en Python"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Test de fibo() non mémoisée :\n",
"F_0 = 1\n",
"F_1 = 1\n",
"F_2 = 2\n",
"F_3 = 3\n",
"F_4 = 5\n",
"F_5 = 8\n",
"F_6 = 13\n",
"F_7 = 21\n",
"F_8 = 34\n",
"F_9 = 55\n"
]
}
],
"source": [
"def fibo(n):\n",
" if n <= 1: return 1\n",
" else: return fibo(n-1) + fibo(n-2)\n",
"\n",
"print(\"Test de fibo() non mémoisée :\")\n",
"for n in range(10):\n",
" print(\"F_{} = {}\".format(n, fibo(n)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Cette fonction récursive est terriblement lente !"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"3.15 s ± 74.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"%timeit fibo(35)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Test de fibo() mémoisée (plus rapide) :\n",
"F_0 = 1\n",
"F_1 = 1\n",
"F_2 = 2\n",
"F_3 = 3\n",
"F_4 = 5\n",
"F_5 = 8\n",
"F_6 = 13\n",
"F_7 = 21\n",
"F_8 = 34\n",
"F_9 = 55\n"
]
}
],
"source": [
"# version plus rapide !\n",
"@memo\n",
"def fibo2(n):\n",
" if n <= 1: return 1\n",
" else: return fibo2(n-1) + fibo2(n-2)\n",
"\n",
"print(\"Test de fibo() mémoisée (plus rapide) :\")\n",
"for n in range(10):\n",
" print(\"F_{} = {}\".format(n, fibo2(n)))"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"118 ns ± 2.59 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit fibo2(35)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Autre exemple, ou le gain de temps est moins significatif."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Test de factorielle() non mémoisée :\n",
"0! = 0\n",
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n",
"5! = 120\n",
"6! = 720\n",
"7! = 5040\n",
"8! = 40320\n",
"9! = 362880\n"
]
}
],
"source": [
"def factorielle(n):\n",
" if n <= 0: return 0\n",
" elif n == 1: return 1\n",
" else: return n * factorielle(n-1)\n",
"\n",
"print(\"Test de factorielle() non mémoisée :\")\n",
"for n in range(10):\n",
" print(\"{}! = {}\".format(n, factorielle(n)))"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4.53 µs ± 214 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
]
}
],
"source": [
"%timeit factorielle(30)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Test de factorielle() mémoisée :\n",
"0! = 0\n",
"1! = 1\n",
"2! = 2\n",
"3! = 6\n",
"4! = 24\n",
"5! = 120\n",
"6! = 720\n",
"7! = 5040\n",
"8! = 40320\n",
"9! = 362880\n"
]
}
],
"source": [
"@memo\n",
"def factorielle2(n):\n",
" if n <= 0: return 0\n",
" elif n == 1: return 1\n",
" else: return n * factorielle2(n-1)\n",
"\n",
"print(\"Test de factorielle() mémoisée :\")\n",
"for n in range(10):\n",
" print(\"{}! = {}\".format(n, factorielle2(n)))"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"124 ns ± 6.32 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit factorielle2(30)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Conclusion\n",
"En Python, c'est facile, avec des dictionnaires génériques et une syntaxe facilitée avec un décorateur.\n",
"\n",
"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) !"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [],
"source": [
"from functools import lru_cache # lru = least recently updated"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Test de fibo() mémoisée avec functools.lru_cache (plus rapide) :\n",
"F_0 = 1\n",
"F_1 = 1\n",
"F_2 = 2\n",
"F_3 = 3\n",
"F_4 = 5\n",
"F_5 = 8\n",
"F_6 = 13\n",
"F_7 = 21\n",
"F_8 = 34\n",
"F_9 = 55\n"
]
}
],
"source": [
"@lru_cache(maxsize=None)\n",
"def fibo3(n):\n",
" if n <= 1: return 1\n",
" else: return fibo3(n-1) + fibo3(n-2)\n",
"\n",
"print(\"Test de fibo() mémoisée avec functools.lru_cache (plus rapide) :\")\n",
"for n in range(10):\n",
" print(\"F_{} = {}\".format(n, fibo3(n)))"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"115 ns ± 2.83 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit fibo2(35)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"86.6 ns ± 1.62 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit fibo3(35)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"117 ns ± 1.44 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit fibo2(70)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"86.2 ns ± 1.12 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
]
}
],
"source": [
"%timeit fibo3(70)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(On obtient presque les mêmes performances que notre implémentation manuelle)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## En OCaml\n",
"\n",
"Je traite exactement les mêmes exemples.\n",
"\n",
"> 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*."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Préliminaires\n",
"\n",
"Quelques fonctions nécessaires pour ces exemples :"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val print : ('a, Format.formatter, unit) format -> 'a = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val sprintf : ('a, unit, string) format -> 'a = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val time : unit -> float = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val sleep : int -> int = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let print = Format.printf;;\n",
"let sprintf = Format.sprintf;;\n",
"let time = Unix.time;;\n",
"let sleep n = Sys.command (sprintf \"sleep %i\" n);;"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val timeit : int -> ('a -> 'a) -> 'a -> unit -> float = \n"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let timeit (repet : int) (f : 'a -> 'a) (x : 'a) () : float =\n",
" let time0 = time () in\n",
" for _ = 1 to repet do\n",
" ignore (f x);\n",
" done;\n",
" let time1 = time () in\n",
" (time1 -. time0 ) /. (float_of_int repet)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples de fonctions à mémoïser"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val f1 : int -> int = \n"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let f1 n =\n",
" ignore (sleep 3);\n",
" n + 2\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 12\n"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = f1 10;; (* 13, après 3 secondes *)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 3.\n"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 3 f1 10 ();; (* 3 secondes *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et un autre exemple similaire :"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val f2 : int -> int = \n"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let f2 n =\n",
" ignore (sleep 4);\n",
" n * n\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 100\n"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let _ = f2 10;; (* 100, après 3 secondes *)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 4.\n"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 3 f2 10 ();; (* 4 secondes *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Mémoïsation pour des fonctions d'un argument"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On utilise le module [Hashtbl](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html#VALcreate) de la bibliothèque standard."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val memo : ('a -> 'b) -> 'a -> 'b = \n"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let memo f =\n",
" let memoire = Hashtbl.create 128 in (* taille 128 par defaut *)\n",
" let memo_f n =\n",
" if Hashtbl.mem memoire n then (* lecture *)\n",
" Hashtbl.find memoire n\n",
" else begin\n",
" let res = f n in (* calcul *)\n",
" Hashtbl.add memoire n res; (* stockage *)\n",
" res\n",
" end\n",
" in\n",
" memo_f (* nouvelle fonction *)\n",
";;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Essais"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Deux exemples :"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val memo_f1 : int -> int = \n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 12\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 12\n"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let memo_f1 = memo f1 ;;\n",
"let _ = memo_f1 10 ;; (* 3 secondes *)\n",
"let _ = memo_f1 10 ;; (* instantanné *)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 0.03\n"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 100 memo_f1 20 ();; (* 0.03 secondes *)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val memo_f2 : int -> int = \n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 100\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"- : int = 100\n"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let memo_f2 = memo f2 ;;\n",
"let _ = memo_f2 10 ;; (* 4 secondes *)\n",
"let _ = memo_f2 10 ;; (* instantanné *)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 0.04\n"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 100 memo_f2 20 ();; (* 0.04 secondes *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> 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 !"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 0.0004\n"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 10000 memo_f2 50 ();; (* 0.04 secondes *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemple de la suite de Fibonacci"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val fibo : int -> int = \n"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let rec fibo = function\n",
" | 0 | 1 -> 1\n",
" | n -> (fibo (n - 1)) + (fibo (n - 2))\n",
";;"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 165580141\n"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fibo 40;;"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 4.2\n"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 10 fibo 40 ();; (* 4.2 secondes ! *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Et avec la mémoïsation automatique :"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"val memo_fibo : int -> int = \n"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let memo_fibo = memo fibo;;"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : int = 165580141\n"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"memo_fibo 40;;"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"- : float = 0.7\n"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"timeit 10 memo_fibo 41 ();; (* 0.7 secondes ! *)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Conclusion\n",
"\n",
"En OCaml, ce n'était pas trop dur non plus en utilisant une table de hachage (dictionnaire), disponibles dans le module Hashtbl.\n",
"\n",
"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..."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.3"
},
"toc": {
"colors": {
"hover_highlight": "#DAA520",
"running_highlight": "#FF0000",
"selected_highlight": "#FFD700"
},
"moveMenuLeft": true,
"nav_menu": {
"height": "343px",
"width": "251px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": true,
"toc_section_display": "block",
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 2
}