{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Mémoïsation, en Python et en OCaml
1.1  En Python
1.1.1  Exemples de fonctions à mémoïser
1.1.2  Mémoïsation générique, non typée
1.1.3  Essais
1.1.4  Mémoïsation générique et typée
1.1.5  Bonus : on peut utiliser la syntaxe d'un décorateur en Python
1.1.6  Conclusion
1.2  En OCaml
1.2.1  Préliminaires
1.2.2  Exemples de fonctions à mémoïser
1.2.3  Mémoïsation pour des fonctions d'un argument
1.2.4  Essais
1.2.5  Exemple de la suite de Fibonacci
1.2.6  Conclusion
" ] }, { "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 obtiens 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 }