8. Les fonctions
En Python, tout est objet et les fonctions n’échappent pas à la règle.
8.1. 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
Avertissement
Cette fonction est recréée ici à titre d’exemple. Le module math dispose d’une fonction 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 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 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 dir():
>>> for i in dir(fact):
... print("{:>18} : {}".format( i, eval("fact."+i)))
...
__annotations__ : {}
__call__ : <method-wrapper '__call__' of function object at 0x0000000000663E18>
__class__ : <class 'function'>
__closure__ : None
__code__ : <code object fact at 0x0000000000792B70, file "<stdin>", line 1>
......
__repr__ : <method-wrapper '__repr__' of function object at 0x0000000000663E18>
__setattr__ : <method-wrapper '__setattr__' of function object at 0x0000000000663E18>
__sizeof__ : <built-in method __sizeof__ of function object at 0x0000000000663E18>
__str__ : <method-wrapper '__str__' of function object at 0x0000000000663E18>
__subclasshook__ : <built-in method __subclasshook__ of type object at 0x000000005D0F1C60>
On peut faire un peu d’introspection sur l’attribut 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
'<stdin>'
>>> 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 dis() du module 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 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)
<Signature (n)>
>>> inspect.signature(fact).parameters
mappingproxy(OrderedDict([('n', <Parameter "n">)]))
8.2. 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 (
list,tuple,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 create_adder() prend un seul argument qui sert pour la construction de la fonction interne adder(). C’est cette dernière qui est retournée. Ici la fonction add_5() est construite avec un appel à 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 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.
8.3. 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 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.
8.3.1. 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 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 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]
[]
Astuce
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 format(). **kwargs fait référence aux arguments nommés que nous abordons ci dessous.
8.4. 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
8.4.1. 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 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 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
8.5. 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}
Astuce
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.
8.6. 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 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 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 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
8.7. 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 filter(), map() et 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')]
>>>
8.8. 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 decorate() acceptant une fonction en paramètre et retournant une autre fonction (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 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 f() a bien été remplacée par la fonction inner():
entering function : f
running f()
exiting function : f
f = <function decorate.<locals>.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 = <function g at 0x000001F4C36CCD08>
8.8.1. 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 clock() (le décorateur) prenant en argument la fonction à décorer func() et retournant la fonction décorée clocked().
La signature de 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 functools est utilisé pour copier les attributs __name__ et __doc__ de func() vers 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 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.
8.8.2. 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 print_hello() à partir de print_msg() (A) puis on exécute 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 print_hello(), la fonction 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 print_hello(). C’est le concept de closure:
Hello
Plus étonnant encore, on peut détruire 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 __closure__ de la fonction:
>>> print_hello.__closure__
(<cell at 0x00000268BB33BCD8: str object at 0x00000268BB38AA08>,)
>>> print_hello.__closure__[0].cell_contents
'Hello'
Pour notre décorateur, le concept de closure est utilisé de la façon suivante. La variable calls est définie en dehors de la fonction clocked() (A). C’est une variable libre (free variable) pour clocked(). Cette variable est accessible à l’intérieur de clocked() avec le mot clé 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 \(\Theta(\phi^n)\) où \(\phi = { {\sqrt 5 + 1} \over 2}\). Il existe des algorithmes beaucoup plus performants, notamment à base de calcul matriciel, qui réduisent la complexité à \(\Theta(\log n)\). Nous allons utiliser ici un décorateur du module functools pour accélerer le calcul.
8.8.3. Le décorateur 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
Exercice
Les traces utilisées dans le décorateur @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
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.