.. _adv_python-functions: ************* Les fonctions ************* En Python, tout est objet et les fonctions n'échappent pas à la règle. Les fonctions sont des objets ============================= A titre d'exemple, on considère la fonction factorielle suivante:: >>> def fact(n): return 1 if n<2 else n*fact(n-1) ... >>> fact(5) 120 .. warning:: Cette fonction est recréée ici à titre d'exemple. Le module :mod:`math` dispose d'une fonction :func:`~math.factorial` optimisée:: >>> setup="from __main__ import fact" >>> timeit.timeit("fact(200)", number=5, setup=setup) 0.0011353548208319353 >>> setup="from math import factorial" >>> timeit.timeit("factorial(200)", number=5, setup=setup) 8.306692052428843e-05 D'autre part, la version naïve utilisée ici comme exemple lève une exception :exc:`RecursionError` lorsque la profondeur de récursion est trop importante:: >>> fact(1000) # pour illustration de la profondeur de récursion ... RecursionError: maximum recursion depth exceeded in comparison Ce qui n'est pas le cas de :func:`~math.factorial`:: >>> r = factorial(1000) # pour illustration de la profondeur de récursion >>> r 402387 ... 000000 # len(str(r)) = 2568 chiffres Toute fonction étant un objet Python, elle possède des attributs et des méthodes que l'on peut obtenir avec la fonction :func:`dir`:: >>> for i in dir(fact): ... print("{:>18} : {}".format( i, eval("fact."+i))) ... __annotations__ : {} __call__ : __class__ : __closure__ : None __code__ : ", line 1> ...... __repr__ : __setattr__ : __sizeof__ : __str__ : __subclasshook__ : On peut faire un peu d'introspection sur l'attribut :attr:`code`:: >>> dir(fact.__code__) [..., 'co_argcount', 'co_cellvars', 'co_code', 'co_consts', 'co_filename', 'co_firstlineno', 'co_flags', 'co_freevars', 'co_kwonlyargcount', 'co_lnotab', 'co_name', 'co_names', 'co_nlocals', 'co_stacksize', 'co_varnames'] >>> fact.__code__.co_argcount # le nombre d'arguments de la fonction 1 >>> fact.__code__.co_code # le bytecode b'|\x00d\x01k\x00r\x0cd\x02S\x00|\x00t\x00|\x00d\x02\x18\x00\x83\x01\x14\x00S\x00' >>> fact.__code__.co_consts # les constantes utilisées (None, 2, 1) >>> fact.__code__.co_filename # la localisation de la fonction '' >>> fact.__code__.co_firstlineno 1 >>> fact.__code__.co_name 'fact' >>> fact.__code__.co_varnames # arguments et variables locales ('n',) Si l'on souhaite plonger encore plus profondément à l'intérieur des fonctions, la fonction :func:`~dis.dis` du module :mod:`dis` permet de "désassembler" le bytecode produit par l'interpréteur Python:: >>> from dis import dis >>> dis(fact) 1 0 LOAD_FAST 0 (n) 2 LOAD_CONST 1 (2) 4 COMPARE_OP 0 (<) 6 POP_JUMP_IF_FALSE 12 8 LOAD_CONST 2 (1) 10 RETURN_VALUE >> 12 LOAD_FAST 0 (n) 14 LOAD_GLOBAL 0 (fact) 16 LOAD_FAST 0 (n) 18 LOAD_CONST 2 (1) 20 BINARY_SUBTRACT 22 CALL_FUNCTION 1 24 BINARY_MULTIPLY 26 RETURN_VALUE Ceci peut être utilisé dans des cas très extrêmes d'optimisation et n'est donné ici qu'à titre d'exemple, pour mettre en avant les capacités d'introspection de Python, c'est à dire sa capacité à accéder à l'information (parfois très bas niveau comme le montre l'exemple précédent) sur les objets qu'il manipule. Dans le même esprit, le module :mod:`inspect` fournit également de puissantes fonctionnalités d'introspection sur les objets en général et les fonctions en particulier:: >>> import inspect >>> inspect.signature(fact) >>> inspect.signature(fact).parameters mappingproxy(OrderedDict([('n', )])) Fonctions *first class* ======================= Dans certains langages, on emploie souvent le terme de *first class function* pour identifier des fonctions particulières qui possèdent les propriétés suivantes: - elles peuvent être utilisées comme paramètres d'autres fonctions - elles peuvent être utilisées comme valeur de retour d'autres fonctions - elles peuvent également être affectées à des variables ou stockées dans des structures de données (:class:`list`, :class:`tuple`, :class:`dict`, etc.). Illustrons le fait qu'une fonction peut être une valeur de retour d'une autre fonction:: >>> def create_adder(x): ... def adder(y): ... return x+y ... return adder ... Ici la fonction :func:`create_adder` prend un seul argument qui sert pour la construction de la fonction interne :func:`adder`. C'est cette dernière qui est retournée. Ici la fonction :func:`add_5` est construite avec un appel à :func:`create_adder`, puis exécutée >>> add_5 = create_adder(5) >>> add_5(8) 13 On peut créer une seconde fonction sur le même principe:: >>> def create_multiplier(x): ... def multiplier(y): ... return x*y ... return multiplier ... >>> mul_3 = create_multiplier(3) >>> mul_3(7) 21 Illustrons le fait que ces fonctions peuvent être utilisées comme arguments d'autres fonctions comme n'importe quel type d'objet:: >>> def change_value(x, f): # f est ici une fonction ! ... return f(x) ... >>> change_value(10, add_5) 15 >>> change_value(10, mul_3) 30 Les fonctions peuvent également être affectées à des variables:: >>> f = add_5 >>> g = mul_3 >>> change_value(10, f) 15 >>> change_value(10, g) 30 Ce qui peut introduire des bugs vicieux si on ne prend pas la précaution d'éviter de renommer des fonctions existantes:: >>> x = dir # on sauvegarde dir() pour restauration future >>> x() # x() se comporte bien comme la fonction dir() [..., 'add_5', 'change_value', 'create_adder', 'create_multiplier',...] >>> def dir(): # on redéfinit dir() par mégarde ... import os ... return os.listdir() ... >>> dir() # elle a maintenant un autre comportement ['.git', '_build', '_templates', '_static', 'conf.py', ...] >>> dir = x # on restaure la fonction builtin >>> dir() # son comportement est de nouveau celui attendu [..., 'add_5', 'change_value', 'create_adder', 'create_multiplier', ...] >>> del x # on détruit la fonction temporaire x() La dernière caractéristique des *first class function* est que l'on peut les stocker dans des structures de données. Ici on crée par exemple une liste de l'ensemble des fonctions disponibles dans l'espace de nom global. Celles ci sont identifiées par la fonction builtin :func:`callable` qui retourne un booléen:: >>> [ i for i in dir() if callable(eval(i)) ] ['__loader__', 'add_5', 'change_value', 'create_adder', ...] En Python, **toutes les fonctions sont des first class function**. On ne fera donc aucune distinction particulière lorsqu'on les manipulera. Les arguments positionnels ========================== Python introduit les notions d'arguments positionnels et d'arguments nommés, ce qui permet beaucoup de souplesse dans l'écriture de la signature, et donc dans l'appel de la fonction. A l'inverse d'autres langages (Java par exemple), Python ne permet pas de faire de la surcharge de fonctions ou de méthodes. Il utilise le mécanisme précédent pour mettre en oeuvre la capacité d'appeler une même fonction avec des paramètres différents (le décorateur :func:`~functools.singledispatch` est également une solution élégante à ce problème). Les arguments positionnels, comme leur nom l'indique, sont identifiés par leur position dans la signature. Il est évident que cette position doit être respectée lors de l'appel pour ne pas provoquer d'erreur à l'exécution, ou plus ennuyeux encore, un résultat erroné:: >>> def f(arg1, arg2, arg3): ... return arg1 / arg2 - arg3 ... >>> f(3, 4, 5) -4.25 >>> f(4, 3, 5) -3.666666666666667 Cependant, maintenir une correspondance stricte entre le nombre d'arguments de la signature et le nombre de paramètres utilisés lors de l'appel peut être lourd et rendre le code difficilement maintenable. Un nombre variable d'arguments positionnels ------------------------------------------- Il peut donc être commode de pouvoir passer un nombre d'arguments non définis à l'avance dans la signature de la fonction. L'exemple le plus connu est la fonction :func:`print` qui affiche l'ensemble de ses arguments, quel que soit leur nombre:: >>> print('Hello') Hello >>> print('Hello', 'World') Hello World >>> print('Hello', 'World', '!') Hello World ! Python possède l'opérateur ``*`` qui permet de capturer la totalité des arguments positionnels dans une séquence, et d'utiliser cette séquence dans le corps de la fonction comme on vient de le voir pour la fonction :func:`print`. Cette syntaxe est visible dans sa signature:: print(*objects, sep=' ', end='\n', file=sys.stdout, flush=False) L'opérateur ``*`` permet également de simplifier l'appel de certaines fonctions. Prenons par exemple le cas d'une fonction qui écrète les valeurs d'une liste d'entiers. Dans sa première version, on utilise 2 arguments positionnels, le premier fixe la valeur d'écrétage et le second contient la séquence de valeurs à écréter:: import random def trigger(cutOffValue, listOfNumbers): result = [] if listOfNumbers: result = [ i for i in listOfNumbers if i < cutOffValue ] return result L'utilisation de cette fonction est immédiate:: l = [random.randint(0,100) for i in range(15 )] print(l) print(trigger(50, l)) print(trigger(50, [])) Le résultat de l'exécution:: [11, 12, 36, 78, 50, 13, 58, 75, 66, 63, 87, 41, 50, 96, 66] [11, 12, 36, 13, 41] [] Tout ceci fonctionne parfaitement, mais on est tenu de passer explicitement 2 paramètres, même si la séquence est vide. Ce qui conduit à une lisibilité dégradée. En utilisant l'opérateur ``*`` dans la signature, l'appel s'en trouve simplifié. Il est à noter que seule la signature est modifiée:: def trigger2(cutOffValue, *listOfNumbers): result = [] if listOfNumbers: result = [ i for i in listOfNumbers if i < cutOffValue ] return result L'appel s'en trouve simplifié, puisque les valeurs à traiter peuvent indifféremment être fournies sous la forme de plusieurs arguments positionnels, ou d'une séquence, cette dernière pouvant même être vide:: print(trigger2(50, 11, 12, 36, 78)) print(trigger2(50, *l)) print(trigger2(50)) [11, 12, 36] [11, 12, 36, 13, 41] [] .. tip:: La convention retenue est de nommer ``*args`` la séquence qui capture le nombre variable d'arguments positionnels, comme le montre la signature de la méthode :meth:`~str.format`. ``**kwargs`` fait référence aux arguments nommés que nous abordons ci dessous. Les arguments nommés ==================== Python permet également dans la signature de la fonction ou de la méthode, un mécanisme permettant d'identifier les arguments par leur nom, plutôt que par leur position. Ce mécanisme permet également de spécifier des valeurs par défaut qui seront retenues à l'exécution si elles ne sont pas explicitement précisées lors de l'appel:: >>> def f(arg1=0, arg2=1, arg3=0): ... return arg1 / arg2 - arg3 ... >>> f(3, 4, 5) -4.25 >>> f(3,4) 0.75 >>> f(3) 3.0 >>> f() 0.0 Les arguments nommés permettent également de les fournir dans une position quelconque lors de l'appel:: >>> f(arg3=5, arg2=4, arg1=3) -4.25 Un nombre variable d'arguments nommés ------------------------------------- Comme pour les arguments positionnels, il existe un mécanisme permettant de capturer la globalité des arguments nommés dans une structure de type :class:`dict`, l'opérateur ``**``:: >>> def f(**kwargs): ... for k,v in kwargs.items(): ... print(k, ':', v) ... Quelque soit le nombre de paramètres nommés passés lors de l'appel, le :class:`dict` ``kwargs`` permet de tous les manipuler dans le corps de la fonction. Ce mécanisme permet de recueillir et de traiter un nombre variable d'arguments nommés:: >>> f(arg3=5, arg2=4, arg1=3) arg3 : 5 arg2 : 4 arg1 : 3 >>> f(arg3=5, arg2=4, arg1=3, arg4=2) arg3 : 5 arg2 : 4 arg1 : 3 arg4 : 2 Arguments positionnels et nommés ================================ L'utilisation des deux formes d'arguments précédents permet une grande souplesse dans la signature des fonctions ou des méthodes. Il faut cependant respecter strictement la règle de placer tous les arguments positionnels avant les arguments nommés:: >>> def f(*args, **kwargs): ... print("args : ", args) ... print("kwargs : ", kwargs) ... Lors de l'appel, on récupère les arguments positionnels dans ``args`` et les arguments nommés dans ``kwargs``:: >>> f(1, 2, 3, 'a', color='blue', font='helvetica', size=10) args : (1, 2, 3, 'a') kwargs : {'color': 'blue', 'font': 'helvetica', 'size': 10} .. tip:: Les noms ``args`` et ``kwargs`` (kw pour key words) sont uniquement des conventions. C'est une bonne pratique de nommer ainsi les arguments positionnels et nommés car la lisibilité du code s'en trouve améliorée. Evaluation des arguments ======================== Les arguments d'une fonction ou d'une méthode sont évalués une seule fois, à la compilation ou à l'importation du module. Il faut bien intégrer ce mécanisme sous peine d'observer des comportements ne correspondant pas à ce que l'on attend:: >>> def f(val, l=[]): ... l.append(val) ... return l ... Le premier appel de :func:`f` se passe comme attendu:: >>> f(1) [1] Mais le second donne un résultat qui peut surprendre:: >>> f(2) [1, 2] En fait la liste :const:`l` n'est évaluée qu'une seule fois lors du premier appel. Lors du second, elle existe déjà, et la valeur 2 y est ajoutée. On choisira d'affecter ``None`` au paramètre concerné et de réaliser les initialisations à l'intérieur du corps de la fonction:: >>> def f(val, l=None): ... if l is None: ... l = [] ... l.append(val) ... return l ... Cette fois l'appel fonctionne comme attendu:: >>> f(1) [1] >>> f(2) [2] >>> l = [] >>> f(1, l) [1] >>> f(2, l) [1, 2] Observons un deuxième exemple mettant en évidence le fonctionnement de Python lors de l'appel d'une fonction. L'objectif est ici d'implémenter une version simplifiée de *logging* qui affiche le message passé en argument et un *timestamp* associé:: import datetime import time # function definition def log(message, when=datetime.datetime.now()): w = '{0:%a %d %B %Y - %H:%M:%S:%f # }'.format(when) print(w, message) #function calls log('Hello') time.sleep(1) log('World') La fonction :func:`log` définie ci dessus est appelée 2 fois avec une temporisation entre les 2 appels, mais le *timestamp* ne varie pas:: Wed 20 December 2017 - 12:06:15:952063 # Hello Wed 20 December 2017 - 12:06:15:952063 # World Lorsqu'un argument doit être évalué dynamiquement, la bonne pratique est de lui donner une valeur par défaut dans la signature de la fonction et de mettre à jour sa valeur, si nécessaire, dans le corps de la fonction. C'est également une bonne pratique que de renseigner le comportement dans la docstring:: def log2(message, when=None): """ Log a message with a timestamp. Args: message: Message to print. when: datetime of when the message occurred. Defaults to the present time. """ if when is None: when = datetime.datetime.now() w = '{0:%a %d %B %Y - %H:%M:%S:%f # }'.format(when) print(w, message) Le délai d'une seconde entre les 2 appels est bien pris en compte:: Wed 20 December 2017 - 12:10:38:091144 # Hello Wed 20 December 2017 - 12:10:39:098800 # World .. _lambda: Les *lambda* fonctions ====================== Les *lambda* fonctions sont la transcription en Python du concept de `fonctions anonymes `_. Lorsqu'il y a besoin de créer des fonctions à la volée, sans nécessiter de les manipuler à un autre endroit dans le code, on peut créer des fonctions anonymes (sans référence), ou *lambda* fonctions. Cette façon de faire permet d'écrire le corps de la fonction à l'endroit où elle est appelée, ce qui est une bonne chose pour la lisibilité et la compréhension du code, donc sa maintenance. On les trouve souvent passées en paramètres des fonctions :func:`filter`, :func:`map` et :func:`sorted`. Cependant une *lambda* fonction n'est jamais nécessaire, il s'agit juste (dans certains cas) d'une facilité de programmation. En outre, on ne peut inclure aucune structure de contrôle (boucle ou test) dans une *lambda* fonction, et son corps ne peut contenir qu'une seule expression, ce qui limite son utilisation à des fonctionnalités très simples. Son usage est souvent rencontré dans les opérations de tri, comme le montre l'exemple extrait du `tutorial de Python `_ :: >>> pairs = [(1, 'one'), (2, 'two'), (3, 'three'), (4, 'four')] >>> pairs.sort() >>> pairs [(1, 'one'), (2, 'two'), (3, 'three'), (4, 'four')] >>> pairs.sort(key=lambda pair: pair[0]) >>> pairs [(1, 'one'), (2, 'two'), (3, 'three'), (4, 'four')] >>> pairs.sort(key=lambda pair: pair[1]) >>> pairs [(4, 'four'), (1, 'one'), (3, 'three'), (2, 'two')] >>> pairs.sort(key=lambda pair: len(pair[1])) >>> pairs [(1, 'one'), (2, 'two'), (4, 'four'), (3, 'three')] >>> Les décorateurs =============== Les décorateurs sont un concept puissant, permettant de modifier le comportement de fonctions existantes. Un décorateur est avant tout une fonction prenant une fonction en argument (la fonction à décorer) et retournant une autre fonction (la fonction décorée). Son utilisation est la suivante:: @decorate def f(): print("exécution de f()") ce qui est strictement équivalent à:: def f(): print("exécution de f()") f = decorate(f) Considérons à présent l'exemple suivant, qui définit le décorateur :func:`decorate` acceptant une fonction en paramètre et retournant une autre fonction (:func:`inner`):: def decorate(f): def inner(): print("entering function :", f.__name__) # insertion d'un affichage avant exécution f() # exécution de la fonction originale print("exiting function :", f.__name__) # insertion d'un affichage avant exécution return inner Lorsque l'on décore une fonction, c'est la fonction retournée par :func:`decorate` qui est alors exécutée:: @decorate def f(): print("running f()") f() print("f = ", f) La sortie de la console montre que le décorateur joue bien son rôle en affichant un message avant et après l'exécution de la fonction. La fonction :func:`f` a bien été remplacée par la fonction :func:`inner`:: entering function : f running f() exiting function : f f = .inner at 0x000001F4C36CCC80> Lorsque la fonction est utilisée sans décorateur:: def g(): print("running g()") g() print("g = ", g) le fonctionnement est normal, et la fonction n'a pas été modifiée:: running g() g = Implémenter un décorateur ------------------------- Lorsque l'on souhaite optimiser les performances d'un code, il est intéressant de disposer de métriques permettant d'observer le temps nécessaire à l'exécution des fonctions. On se propose d'implémenter cette fonctionnalité sous la forme d'un décorateur. Pour des choses plus approfondies, on jettera un oeil aux `profilers `_ documentés dans la bibliothèque Python. Le principe de base est de construire une fonction :func:`clock` (le décorateur) prenant en argument la fonction à décorer :func:`func` et retournant la fonction décorée :func:`clocked`. La signature de :func:`clocked` (A) lui permet d'accepter tout type d'argument. Pour l'instant elle ne fait pas grand chose. Elle se contente de récupérer le résultat de la fonction à décorer (B) et de le retourner (C). Mais on dispose maintenant d'une architecture permettant d'insérer des instructions avant et après l'exécution de la fonction à décorer, ce qui est l'objectif recherché:: def clock(func): def clocked(*args, **kwargs): # A result = func(*args, **kwargs) # B return result # C return clocked Vérifions son fonctionnement avec une implémentation (très) naïve de la suite de Fibonacci:: @clock def fib(n): if n<2: return n return fib(n-2) + fib(n-1) n=10 print(fib.__name__, "(", n, ") = ", fib(n), sep="") Le résultat obtenu est bien la valeur numérique attendue, mais le nom de la fonction originale est maintenant masqué dans le contexte d'appel:: clocked(10) = 55 L'utilisation d'un décorateur du module :mod:`functools` est utilisé pour copier les attributs :attr:`__name__` et :attr:`__doc__` de :func:`func` vers :func:`clocked`:: from functools import wraps def clock(func): @wraps(func) def clocked(*args, **kwargs): result = func(*args, **kwargs) return result return clocked Le comportement est maintenant celui attendu:: fib(10) = 55 Apportons maintenant quelques modifications opérationnelles à notre décorateur. Un chronomètre est déclenché avant l'exécution (A) puis arrêté juste après (B) pour obtenir le temps d'exécution par différence. On construit une liste des arguments positionnels (C) et nommés (D) pour l'affichage:: def clock(func): @functools.wraps(func) def clocked(*args, **kwargs): t0 = time.perf_counter() # A result = func(*args, **kwargs) delta_t = time.perf_counter() - t0 # B arglist = [] if args: arglist.extend(['{0}'.format(repr(arg)) for arg in args]) # C if kwargs: kwlist = ['{0}={1}'.format(k,w) for k,w in kwargs.items() ] # D arglist.extend(kwlist) argstr = ' ,'.join(arglist) print('{:0.8f} - {}({}) = {}'.format(delta_t, func.__name__, argstr, result)) return result return clocked On dispose maintenant du temps d'exécution sur chaque appel de la fonction :func:`fib`:: 0.00000093 - fib(0) = 0 0.00000233 - fib(1) = 1 0.00252289 - fib(2) = 1 0.00000093 - fib(1) = 1 0.00000093 - fib(0) = 0 0.00000187 - fib(1) = 1 0.00806643 - fib(2) = 1 ... 0.01100171 - fib(7) = 13 0.01764249 - fib(8) = 21 0.10407800 - fib(9) = 34 0.11858461 - fib(10) = 55 fib(10) = 55 On constate ici la très grande inefficacité de cette fonction qui génére un nombre astronomique d'appels pour obtenir le résultat, induisant des temps de calcul pas du tout en rapport avec la complexité du problème. Les closures ------------ Pour compter le nombre d'appels récursifs, on va utiliser le concept de `closure `_ qui permet à une fonction d'avoir accès à des variables en dehors de son contexte local. Ce qui est étonnant à première vue si on se rappelle de la portée locale des variables dans une fonction. Le concept de closure existe lorsque l'on a des fonctions imbriquées (nested). Considérons l'exemple suivant:: def print_msg(msg): def printer(): print(msg) return printer On fabrique une fonction :func:`print_hello` à partir de :func:`print_msg` (A) puis on exécute :func:`print_hello` pour produire l'affichage proprement dit (B):: print_hello = print_msg("Hello") # A print_hello() # B Au moment de l'exécution de :func:`print_hello`, la fonction :func:`print_msg` a retourné son résultat et ses variables locales ont été détruites. Cependant la chaîne de caractères ``hello`` est encore disponible dans le contexte de :func:`print_hello`. C'est le concept de closure:: Hello Plus étonnant encore, on peut détruire :func:`print_msg` sans altérer le fonctionnement:: >>> del print_msg >>> print_hello() Hello En fait la donnée ``hello`` est stockée dans l'attribut :attr:`__closure__` de la fonction:: >>> print_hello.__closure__ (,) >>> print_hello.__closure__[0].cell_contents 'Hello' Pour notre décorateur, le concept de closure est utilisé de la façon suivante. La variable :const:`calls` est définie en dehors de la fonction :func:`clocked` (A). C'est une variable libre (free variable) pour :func:`clocked`. Cette variable est accessible à l'intérieur de :func:`clocked` avec le mot clé :keyword:`nonlocal` (B). Le nombre d'appels est incrémenté à chaque nouvel appel (C) puis est utilisé dans l'affichage:: def clock(func): calls = 0 # A # @functools.wraps(func) def clocked(*args, **kwargs): nonlocal calls # B t0 = time.perf_counter() result = func(*args, **kwargs) delta_t = time.perf_counter() - t0 calls += 1 # C arglist = [] if args: arglist.extend(['{0}'.format(repr(arg)) for arg in args]) if kwargs: kwlist = ['{0}={1}'.format(k,w) for k,w in kwargs.items() ] arglist.extend(kwlist) # print(arglist) argstr = ' ,'.join(arglist) # print(argstr) print('call# : {} - {:0.8f} - {}({}) = {}'.format(calls, delta_t, func.__name__, argstr, result)) return result return clocked La console affiche maintenant le nombre d'appels récursifs:: call# : 1 - 0.00000047 - fib(0) = 0 call# : 2 - 0.00000093 - fib(1) = 1 call# : 3 - 0.00172189 - fib(2) = 1 call# : 4 - 0.00000047 - fib(1) = 1 call# : 5 - 0.00000047 - fib(0) = 0 call# : 6 - 0.00000093 - fib(1) = 1 call# : 7 - 0.00014275 - fib(2) = 1 ... call# : 174 - 0.00189310 - fib(7) = 13 call# : 175 - 0.00340926 - fib(8) = 21 call# : 176 - 0.00504904 - fib(9) = 34 call# : 177 - 0.00961525 - fib(10) = 55 fib(10) = 55 L'inefficacité de la fonction est flagrante ! Sa complexité est en :math:`\Theta(\phi^n)` où :math:`\phi = { {\sqrt 5 + 1} \over 2}`. Il existe des algorithmes beaucoup plus performants, notamment à base de calcul matriciel, qui réduisent la complexité à :math:`\Theta(\log n)`. Nous allons utiliser ici un décorateur du module :mod:`functools` pour accélerer le calcul. Le décorateur :func:`~functools.lru_cache` ------------------------------------------ Ce décorateur implémente le stockage des résultats intermédiaires en mémoire. LRU signifie *last recently used*. Son utilisation est très simple et montre que l'on peut empiler des décorateurs:: import functools @functools.lru_cache() @clock def fib(n): if n<2: return n return fib(n-2) + fib(n-1) n=10 print(fib.__name__, "(", n, ") = ", fib(n), sep="") En supprimant les appels inutiles et en exploitant les résultats stockés dans le cache, l'exécution est maintenant plus rapide:: call# : 1 - 0.00000140 - fib(0) = 0 call# : 2 - 0.00000233 - fib(1) = 1 call# : 3 - 0.00351702 - fib(2) = 1 call# : 4 - 0.00000420 - fib(3) = 2 call# : 5 - 0.00381699 - fib(4) = 3 call# : 6 - 0.00000373 - fib(5) = 5 call# : 7 - 0.02113385 - fib(6) = 8 call# : 8 - 0.00000467 - fib(7) = 13 call# : 9 - 0.02143942 - fib(8) = 21 call# : 10 - 0.00000233 - fib(9) = 34 call# : 11 - 0.02169320 - fib(10) = 55 fib(10) = 55 .. admonition:: Exercice Les traces utilisées dans le décorateur :func:`@clock` montrent les temps d'exécution de chacune des fonctions prises séparément mais pas le temps global. Implémentez cette fonctionnalité. Utilisez les techniques de formattage pour produire un affichage permettant d'aligner les informations:: call# : 1 - 0.00000047 - fib( 0) = 0 - 0.00000047 call# : 2 - 0.00000093 - fib( 1) = 1 - 0.00000140 call# : 3 - 0.00037554 - fib( 2) = 1 - 0.00037694 call# : 4 - 0.00000187 - fib( 3) = 2 - 0.00037881 call# : 5 - 0.00057801 - fib( 4) = 3 - 0.00095681 call# : 6 - 0.00000187 - fib( 5) = 5 - 0.00095868 call# : 7 - 0.00077767 - fib( 6) = 8 - 0.00173635 call# : 8 - 0.00000187 - fib( 7) = 13 - 0.00173822 call# : 9 - 0.00099507 - fib( 8) = 21 - 0.00273328 call# : 10 - 0.00000187 - fib( 9) = 34 - 0.00273515 call# : 11 - 0.00121339 - fib( 10) = 55 - 0.00394854 .. def clock(func): calls = 0 running_time = 0 @functools.wraps(func) def clocked(*args, **kwargs): nonlocal calls, running_time t0 = time.perf_counter() result = func(*args, **kwargs) delta_t = time.perf_counter() - t0 running_time += delta_t calls += 1 arglist = [] if args: arglist.extend(['{0}'.format(repr(arg)) for arg in args]) if kwargs: kwlist = ['{0}={1}'.format(k,w) for k,w in kwargs.items() ] arglist.extend(kwlist) # print(arglist) argstr = ' ,'.join(arglist) # print(argstr) print('call# : {:3d} - {:0.8f} - {}({:>3}) = {:>3} - {:0.8f}'.format(calls, delta_t, func.__name__, argstr, result, running_time)) return result return clocked L'utilisation de ce décorateur est encouragée chaque fois que l'on a besoin d'implémenter un cache. Par exemple, pour des opérations de récupération de données sur internet.