Aujourd'hui je vous propose un exercice concernant la mise en cache des appels de fonctions. J'explique : quand on appelle une fonction plusieurs fois avec les mêmes arguments, on doit pouvoir retenir le résultat afin de ne pas avoir à le recalculer. Je vous propose de résoudre cela avec des décorateurs.
Pour tester si votre fonction fonctionne :
def fibo(n):
if n <= 1:
return 1
else:
return fibo(n - 1) + fibo(n - 2)
@cache
def fib(n):
if n <= 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
L'appel de fibo(32) doit durer quelques secondes, alors que l'appel de fib(32) doit être instantané.
Attention, cet exercice comporte plusieurs difficultés. Je posterai la solution que je propose d'ici quelques messages (et je ne suis qu'à moitié satisfait de ma solution à un des problèmes, donc si je trouve - seul bien sûr - d'ici là...)
Le sujet est volontairement assez vague : il ne s'agit pas d'un exercice scolaire rigide, mais d'une proposition d'entraînement. Ça veut dire aussi que vous pouvez extrapoler un peu : le but est d'avoir une discussion intéressante, pas un examen ! En particulier, le rôle des variables globales et des méthodes de classe n'est pas clairement défini. Essayez de réfléchir dessus.
edit : je suis parvenu à une solution qui me convient beaucoup mieux. Voyons les idées que vous aurez !
Voilà une solution qui marche bien en python 3. Elle est certainement perfectible (il doit y avoir un moyen de la rendre plus concise, et gérer tout un tas de cas bizarres), mais bon :
# -*- coding: utf-8 -*-
from functools import wraps # ceci est purement cosmétique
def cached(fn):
fn.cachedict = {}
@wraps(fn)
def wrapper(*args):
argskey = tuple(args)
if argskey in fn.cachedict:
print("-- Returning cached result")
ret = fn.cachedict[argskey]
else:
ret = fn.cachedict[argskey] = fn(*args)
return ret
return wrapper
@cached
def fibo(n):
if n <= 1:
return 1
else:
return fibo(n-1) + fibo(n-2)
print(fibo(50))
Le résultat dans la console, "instantané" sur un eeePc, pour fibo(50) :
-- Returning cached result
-- Returning cached result
-- Returning cached result
# ...
-- Returning cached result
-- Returning cached result
20365011074
Edit: désolé candide, j'ai répondu à cet exo avant le tien, mais celui-ci ne m'a demandé que 5 minutes…
Allez, pour soigner une bonne gueule de bois, rien ne vaut un petit exercice de programmation.
def cache(funct):
def f(*args, **kwargs):
key = funct.__name__ + '('
for arg in args:
key += '{},'.format(arg)
for k, v in kwargs.items():
key += '{}={},'.format(k, v)
key = key[:-1] + ')'
if key not in funct.__cache__:
funct.__cache__[key] = funct(*args, **kwargs)
return funct.__cache__[key]
if not hasattr(funct, '__cache__'):
funct.__cache__ = dict()
return f
def fibo(n):
if n <= 1:
return 1
else:
return fibo(n - 1) + fibo(n - 2)
@cache
def fib(n):
if n <= 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
!
Exactement le même exemple et le même problème ICI, le hasard sans doute.
Je vois pas l'intérêt de ce genre de façon de coder un truc aussi trivial que la suite de Fibonacci, je serais pas étonné que ça impacte fortement les performances et la mémoire. C'est de la déco, si je puis dire
Avec les mêmes entorses à la PEP-8 dans les appels récursifs à la fonction fib…
M'enfin peu importe, le sujet peut quand même être intéressant, je pense.
Edit : tiens d'ailleurs c'est rigolo, l'auteur de l'article préfère créer une closure pour maintenir son cache en mémoire plutôt que de tirer parti du "tout est objet" de python pour l'attacher à la fonction comme je l'ai fait…
@candide : oui enfin on peut quand même imaginer assez simplement des applications plus intéressantes de ce décorateur. Notamment sur des fonctions qui font de l'IO sur des supports coûteux en temps, comme une grosse BDD ou même directement le web…
D'ailleurs ça laisse poindre un problème sympa et une possibilité d'évolution de l'exo : dans le cas d'une fonction d'IO, le même appel ne retournera pas toujours le même résultat (si on requête une page web à 1h d'intervalle, le résultat va varier, mais probablement beaucoup moins à deux secondes ou 5 minutes d'intervalle). Ce serait donc intéressant de prévoir un mécanisme qui permette de s'affranchir honorablement de cet effet, tout en ayant quand même cette mise en cache… En gros, rajouter un timeout au-delà duquel une donnée cachée est périmée…
Avec les mêmes entorses à la PEP-8 dans les appels récursifs à la fonction fib…
La PEP8 parle de recursivité ? j'y ai même pas trouvé ce mot.
Le problème de la récursivité n'est pas le n'ombre d'appels récursifs me semble-t-il mais la taille de la pile. Pour Fibonacci(100), la profondeur de la pile est faible mais le nombre d'appels est exponentiel et c'est ça qui rend le calcul très lent voire impossible.
Je suppose que ce propose le PO avec sa déco est de ne pas recalculer ce qui l'a déjà été, bref je vois pas où tu veux en venir avec ta remarque.
Avec les mêmes entorses à la PEP-8 dans les appels récursifs à la fonction fib…
La PEP8 parle de recursivité ? j'y ai même pas trouvé ce mot.
Le problème de la récursivité n'est pas le n'ombre d'appels récursifs me semble-t-il mais la taille de la pile. Pour Fibonacci(100), la profondeur de la pile est faible mais le nombre d'appels est exponentiel et c'est ça qui rend le calcul très lent voire impossible.
Ma remarque est beaucoup plus superficielle que ça, je parlais de la coding-style : les expressions arithmétiques sont à "condenser" (écrire sans espace) dans les appels de fonctions, selon la PEP-8.
les expressions arithmétiques sont à "condenser" (écrire sans espace) dans les appels de fonctions, selon la PEP-8.
Hum, j'ai du mal à te comprendre et la remarque de forme que tu as faite nous fait dériver du sujet. Bon, tu parles bien des expressions arithmétiques dans les appels de fonctions données dans le code Python qui apparaît dans le lien que j'ai donné ICI. Bon, je ne vois pas du tout où il n'a pas respecté la PEP, par exemple ce qu'il écrit ci-dessous :
def fib(n):
if n in (0, 1):
return n
else:
return fib(n - 1) + fib(n - 2)
est parfaitement conforme, non ?
Voudrais-tu dire que l'écriture correcte serait fib(n-1) ? J'en doute assez. Par exemple, si tu demandes à Pythontidy de te reformater fib(n-1), il va ajouter des espaces dans l'appel de fonction.
J'ai changé dans ton code 50 en 2000 :
Citation : NoHaR
# -*- coding: utf-8 -*-
from functools import wraps # ceci est purement cosmétique
def cached(fn):
fn.cachedict = {}
@wraps(fn)
def wrapper(*args):
argskey = tuple(args)
if argskey in fn.cachedict:
#print("-- Returning cached result")
ret = fn.cachedict[argskey]
else:
ret = fn.cachedict[argskey] = fn(*args)
return ret
return wrapper
@cached
def fibo(n):
if n <= 1:
return 1
else:
return fibo(n-1) + fibo(n-2)
print(fibo(2000))
et tout ça pour en arriver à quoi ? à ceci :
RuntimeError: maximum recursion depth exceeded in comparison
C'est bien ce que je dis, c'est juste de la déco.
Citation : NoHaR
Edit: désolé candide, j'ai répondu à cet exo avant le tien, mais celui-ci ne m'a demandé que 5 minutes…
Candide : effectivement, ce décorateur n'a quasiment aucun intérêt pour fibonacci. De toute façon, il ne rend la complexité « que » linéaire. Je n'ai pas testé, mais d'abord je pense que l'algorithme linéaire classique est bien plus efficace, ensuite il existe un algorithme logarithmique, donc effectivement il serait idiot d'utiliser celui-ci. Il n'était là que parce qu'il s'agit d'une fonction d'exemple pour permettre aux gens de tester leurs codes. On aurait certainement pu en inventer d'autres, c'est la première qui m'est venue à l'esprit. Je n'ai pas prétendu qu'elle avait une utilité pratique.
Par contre, il m'est arrivé de me servir de ce décorateur de temps en temps. Typiquement, il aurait deux cas d'utilisation à mon avis : celui des fonctions récursives où le même appel est effectué plusieurs fois (comme fibonacci, et comme tu l'as fait remarquer il ne résout pas tous les problèmes), et celui des fonctions appelables plusieurs fois dans le code qui nécessitent un gros calcul (et qu'on ne peut pas mémoriser dans une variable, par exemple si leur paramètre dépend d'une entrée de l'utilisateur). Dans ces cas, ce décorateur permet d'éviter de refaire les calculs si on les a déjà faits une fois.
Le choix de cette fonction n'a pas de rapport avec l'article, par contre cette utilisation des décorateurs est effectivement assez classique (au moins comme exercice) et je l'avais déjà vue ailleurs (pas sur le lien que tu proposes par contre).
Pour l'instant, je suppose que les fonctions décorées respectent l'intégrité référentielle (que cette expression est moche). Si on change une variable globale qu'elles utilisent ou, si comme l'a fait remarquer NoHaR, elles font appel à une ressource extérieure qui change dans le temps, le cache ne fonctionnera pas correctement.
Pour les ressources extérieures, il peut être intéressant d'ajouter un timeout, effectivement. Pour l'environnement de la fonction, il faut récupérer toutes les variables susceptibles d'influer dessus et les rajouter comme clefs du dictionnaire. Je ne l'ai pas encore fait.
Pour résoudre le problème de la clef qui doit être non mutable, j'avais d'abord fait comme quelques solutions plus haut, avec des chaînes de caractère, mais je n'étais pas vraiment convaincu (bien que cette solution se défende tout-à-fait, elle me laissait un goût de hack un peu foireux). Finalement, j'ai tout transformé en tuple. On me dira certainement que ça revient au même, mais ça me satisfait plus.
J'ai changé dans ton code 50 en 2000 :
…
et tout ça pour en arriver à quoi ? à ceci :
RuntimeError: maximum recursion depth exceeded in comparison
C'est bien ce que je dis, c'est juste de la déco.
Certes, sur un exemple de récursion un peu violent, la mise en cache n'empêche pas la pile de sauter. Pour pallier à cela, il faudrait trouver un moyen d'optimiser les tail-recursions en python d'une part, et d'introduire proprement une évaluation paresseuse d'autre part, mais pour le coup, autant utiliser directement un autre langage que python (qui a dit haskell ?).
Ce que je dis, c'est que cela n'enlève strictement rien au principe même de mise en cache de fonctions, qui a quand même un RÉEL intérêt dans certains cas.
En insistant sur l'explosion combinatoire des appels récursifs sur cette fonction (qui est effectivement un exemple mal choisi), tu enfonces le doigts dans "le mauvais trou", parce que ce qu'un cache et sensé résoudre n'est pas une explosion de la pile, mais avant tout les problèmes de rapidité, en ciblant une fonction appelée souvent avec les mêmes paramètres, et connue pour sa lenteur.
C'est là le seul intérêt de ce topic : créer un décorateur qui permette de s'adapter simplement à toutes les fonctions de ce genre (paramètres simples, susceptible d'être appelée souvent, exécution lente), et non de déterminer une façon dégueulasse de calculer le n-ième terme de la suite de fibonacci.
Citation : candide
Citation : NoHaR
Edit: désolé candide, j'ai répondu à cet exo avant le tien, mais celui-ci ne m'a demandé que 5 minutes…
Et tu penses avoir prouvé quoi en disant ça ?
Cela veut dire simplement que cet exo, contrairement au tien, est suffisamment commun pour le résoudre en 5 minutes, parce qu'il ne pose aucun problème d'algorithmique.
Pourquoi cela devrait-il servir à prouver quoi que ce soit ?
@Orrita : le timeout n'est en fait qu'une solution pour un type de problème donné. En fait, pour faire propre, on pourrait envisager passer en paramètre de ce décorateur un objet "cache" qui gère lui-même son raffraichissement ou sa capacité d'oubli (par exemple en fonction du temps, ou bien plus simplement un cache LRU…).
Cela veut dire simplement que cet exo, comparé au tien, est suffisamment commun pour le résoudre en 5 minutes, parce qu'il ne pose aucun problème d'algorithmique.
De quel exo tu parles ? Le poker ? si c'est ça, les exercices n'ont aucun rapport et donc la comparaison n'a pas de sens. L'exercice du PO n'a rien de commun, les décorateurs sont une notion abstraites, intrinsèquement difficile, car si la fonction représente un premier niveau d'abstraction, une fonction qui prend en paramètre en fonction (et qui pire, renvoie une fonction) est un deuxième niveau d'abstraction [si tu as fait des maths et de l'analyse fonctionnelle, tu sais que c'est beaucoup plus difficile que de faire de la banale algèbre linéaire]. L'exercice en lui-même est ce que j'appelle un exercice "intello", un exo d'informaticien (informaticien != programmeur) qui sera loin de convenir à n'importe quel étudiant en informatique.
Tu as résolu l'exercice en 5 minutes ? et alors ? t'as fait des classes prépas, une écolé d'ingé (je suppose), en informatique (je suppose), tu travailles dans le développement, et en Python en plus, et depuis XX années donc ce serait même embarrassant que tu ne l'aies pas fait en 5 minutes. Maintenant, pour les avoir avec moi tous les jours ou presque je suis capable de te dire ce qu'un étudiant lambda en info est capable de comprendre au bout d'une année de Python, C et Caml : très très loin de ce genre d'exercice intello.
Hé, doucement, pourquoi tu t'enflammes ?
J'ai simplement fait cette remarque pour dire « désolé c'est vrai que j'ai pas encore participé au tien mais comme celui-ci ne me prendra que 5 minutes j'y réponds tout de suite. »
J'essaye de montrer de l'égard et de la reconnaissance envers les gens qui créent des exercices sur ce forum, en m'excusant de ne pas encore avoir trouvé le temps de participer, et tout ce que tu trouves à faire c'est de me rentrer dans la gueule pour je ne sais quel mot que tu as avalé de travers ?
PS: et non, maintenant que j'ai changé de taff je fais plutôt du Perl.
Hé candide, j'ai pas dit que cet exercice était fait pour tes étudiants de fac lambda qui ne cherchent pas à approfondir leurs cours hein. C'est un exercice de Python, et effectivement il ne risque pas d'être faisable par quelqu'un qui n'a fait du python qu'en fac.
tout ce que tu trouves à faire c'est de me rentrer dans la gueule pour je ne sais quel mot que tu as avalé de travers ?
Non, je te fais juste remarquer que tu ne peux rien dire de la difficulté de cet exercice sous prétexte que toi qui as XX années de programmation et un background solide derrière toi l'as résolu en 5 minutes. Tu ne t'en rends peut-être plus compte mais l'exercice du PO est un exercice très conceptuel. Le fait que sa solution soit courte (les 5 minutes) et qu'il ne contienne aucune algorithmique basique (à l'inverse de l'exo du Poker) ne prouve pas qu'il soit facile. Il existe énormément d'exercices difficiles (en maths par exemple) qui ne sont même pas astucieux, dont la solution tient en trois lignes mais ce sont celles qui demandent le plus de temps à être trouvées (et souvent une réponse rapide et correcte n'est que le fruit d'années d'expérience).
Quant à la valeur pédagogique des explications fournies par les différents codes de ce fil, elle est à peu près nulle, disons que des intellos s'adressent aux intellos et les zéros sont exclus (en matière de décorateur je me considère comme un zéro, je connais la définition et c'est à peu près tout)).
Effectivement, je remarque que tu n'as rien posté mais que tu as critiqué à peu près tout le monde. Tu ferais sans doute mieux d'essayer de comprendre les exemples, plutôt que t'attacher à critiquer les points sur lesquels ils n'essaient pas d'être valables.
En termes de décorateurs, j'ai déjà proposé un exercice extrêmement détaillé sur ce forum il y a plusieurs mois pour amener la notion, par la pratique, de façon progressive. Les gens qui ont eu le courage d'y répondre étaient très rares. J'en conclus que les débutants ne tiennent pas à participer à ce genre d'exos.
Ensuite, je n'ai jamais présumé de la difficulté de cet exo dans l'absolu, ni même pour un débutant. J'ai simplement précisé qu'il ne m'avait prisueq 5 minutes parce que ce genre d'application d'un décorateur, avec l'habitude, est probablement l'une des plus banales. Jusqu'à preuve du contraire, je ne parle qu'en mon nom.
candide : Tu peux arrêter de parler « d'exercices d'intello » ? Pour n'importe qui qui sait un peu utiliser Python ça ne devrait pas être insurmontable, loin de là.
De plus, il serait peut-être intéressant que tu arrêtes de rager sans raison. Si c'est parce que tu n'as pas réussi cet exercice pourtant facile pour un programmeur pas trop mauvais, ça n'est pas grave, on ne t'en veut pas.
candide : Tu peux arrêter de parler « d'exercices d'intello » ? Pour n'importe qui qui sait un peu utiliser Python ça ne devrait pas être insurmontable, loin de là.
Tu viens me donner des leçons alors que dans ce fil, tu n'as pas fait la moindre analyse, la moindre contribution ni posté le moindre ... code. Tu peux ne pas supporter les posteurs rageants et bien j'ai droit de ne pas apprécier les posteurs élitistes et qui ne s'assument pas en plus.
candide : Tu peux arrêter de parler « d'exercices d'intello » ? Pour n'importe qui qui sait un peu utiliser Python ça ne devrait pas être insurmontable, loin de là.
Je pense que les décorateurs font "intello" pour quiconque est principalement versé dans un style de programmation impératif, parce qu'étant donné que ce sont des fonctions d'ordre supérieur, ils font résonner des mécanismes qui sont plutôt courants en programmation fonctionnelle (closures, etc), mais relativement rares en dehors de ça, et ça ne me surprend pas que ça puisse paraître complètement opaque pour quelqu'un ayant pratiqué la programmation pendant des années dans des langages où ces notions n'existent juste pas, ou plus généralement pour quelqu'un d'insensible aux charmes de la programmation fonctionnelle (pourtant il faut bien avouer que c'est sexy…).
Après, il faut aussi relativiser, dans « le monde réel », celui où on code pour manger, on pousse rarement le raffinement jusqu'à proposer des API élégantes à base de décorateurs en Python, à moins de programmer ces API par goût ou par hobby.
En bref, on utilise beaucoup plus couramment les décorateurs que l'on ne les programme.
candide : Tu peux arrêter de parler « d'exercices d'intello » ? Pour n'importe qui qui sait un peu utiliser Python ça ne devrait pas être insurmontable, loin de là.
Tu viens me donner des leçons alors que dans ce fil, tu n'as pas fait la moindre analyse, la moindre contribution ni posté le moindre ... code. Tu peux ne pas supporter les posteurs rageants et bien j'ai droit de ne pas apprécier les posteurs élitistes et qui ne s'assument pas en plus.
Les seules analyses que tu as faites sont complètement à côté de la plaque : tu as commencé par critiquer l'exemple choisi sur les points qu'il ne prétendait pas résoudre, puis tu as dit qu'un étudiant n'ayant que des notions de python ne pourrait pas résoudre cet exercice (ce qui 'est un peu comme dire que proposer un exercice de C est mauvais parce que quelqu'un qui n'a jamais fait de C ne peut pas le résoudre).
xarch n'a pas fait d'analyse, mais au moins il n'a pas fait d'analyse stupide, et il ne rage pas depuis le début du topic. Et il a autant contribué et posté du code que toi.
Si c'est parce que tu n'as pas réussi cet exercice pourtant facile pour un programmeur pas trop mauvais
Pour un débutant tant que t'y es. En lui même le principe est pas trop complexe, c'est l'utilisation assez abstraite des décorateurs qui l'est, et il faut de l'expérience pour bien les comprendre.
Citation
En termes de décorateurs, j'ai déjà proposé un exercice extrêmement détaillé sur ce forum il y a plusieurs mois pour amener la notion, par la pratique, de façon progressive. Les gens qui ont eu le courage d'y répondre étaient très rares.
Normal j'ai déjà été récupérer ton post au moins une dizaine de fois, et je n'ai jamais réussi à terminer cet exercice. J'ai donc abandonné et pourtant je manipule assez correctement les bases concernant les décorateurs (enfin quand je parle de bases, c'est l'utilisation que je peux en faire à mon niveau théorique)
Et pourtant en regardant ton exercice on se dit, mais merde, c'est quand même pas compliqué ce qu'il demande, t'es nul ou quoi?
L'exo présenté ci-dessus, il est pas compliqué, il suffit d'aller sur le net on trouve les codes très optimisés, pour un utilisateur python, c'est très suffisant, maintenant pour un programmeur, rechercher par lui même c'est pas un mal.
En bref, on utilise beaucoup plus couramment les décorateurs que l'on ne les programme.
clair, je pige qu'un beignet aux décorateurs ... je ne pense pas non plus être un gros débutant ...
j'utilise @property @classmethod et @staticmethod mais j'avoue ne pas comprendre comment ça marche; et en fait je m'en fout (pour le moment).
Quelqu'un qui a déjà touché à la programmation fonctionnelle devrait avoir beaucoup moins de mal à comprendre. Fondamentalement, le principe est très simple.
Après, il faut aussi relativiser, dans « le monde réel », celui où on code pour manger, on pousse rarement le raffinement jusqu'à proposer des API élégantes à base de décorateurs en Python, à moins de programmer ces API par goût ou par hobby.
Et pour compléter ce point, cf. cet avis d'un spécialiste de Python :
Citation : Kent S Johnson
Real-world examples
Good beginner examples of real-world decorators are hard to come by. Decorators tend to be either very simple, in which case they don't add much to the examples above, or significantly more complex and difficult to understand. Also real-world decorators are often composed from other decorators and don't stand alone.
Ça résume parfaitement la situation et l'ambivalence des décorateurs, ce que certains ont visiblement du mal à comprendre :
Citation : xarch
fred1599 > Boarf, les décorateurs c'est juste des fonctions qui renvoient des fonctions, c'est pas si compliqué que ça…
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.