Mise à niveau : TD / TP 2

Comme il a été dit, vous aurez toutes les solutions d'hier et d'aujourd'hui, mais pas tout de suite, car je veux que vous réfléchissez un peu, aussi off-line...


"Mémoïsation"

Exercice 1. On constate parfois que quelques fonctions sont appelées plusieurs fois avec les mêmes arguments. Si l'exécution est onéreuse, c'est une perte de temps ; il serait utile de pouvoir sauvegarder le résultat, et de le re-utiliser plus tard. Parfois une telle optimisation peut économiser un temps considérable !, même changer la classe de complexité d'un algoritme (passer de milliards d'années, à quelques secondes...).

Un exemple assez académique (peu pratique, mais significatif) est l'algorithme récursif qui calcule la suite de Fibonacci. Nous avons : \(f_0=0; f_1=1; \ldots f_n = f_{n-2} + f_{n-1}\).

Ceci engendre : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... etc. Si on code cette fonction selon la description ci-dessus :

def fibo(n):
    if n==0:return 0
    if n==1:return 1
    return fibo(n-1)+fibo(n-2)
les appels pour n<25 donnent des résultats assez vite. Pour n=35 il faut attendre plusieurs secondes, pour n=40 ceci devient insoutenable (la valeur : 102334155, plusieurs minutes), et très vite le temps de calcul dépasse l'âge de l'Univers...

Python nous donne des moyens pour automatiser ce processus de sauvegarde des "arguments vus". Nous pouvons coder un dictionnaire, dont les clés sont les arguments (potentiels) de la fonction, et les valeurs – les valeurs retournées. Bien sûr, cela ne marchera pas toujours, uniquement aux données (arguments) "non-mutables", comme nombres, chaînes ou tuples, qui peuvent être utilisés comme clés.

Si la fonction "découvre" que l'argument a déjà été utilisé, on le récupère depuis ce dictionnaire. Si non, alors la valeur est calculée, et ensuite la paire (argument, résultat) est insérée dans le dictionnaire. La technique orientée-objet peut s'avérer utile. Si un objet, disons, x, l'instance d'une classe utilisateur dispose de la méthode :

   def __call__(self,arg1, arg2,...,argN):
	 ...

alors l'expression x(a1,a2,...,aN) est le synonyme de x.__call__(a1,a2,...aN). Ainsi les objets Python peuvent "simuler" les procédures.

Écrire une classe Fib(object), dont l' __init__ n'a pas de paramètres, sauf self, qui pendant l'initialisation instaure, en tant que champ local, un dictionnaire, dont la valeur serait {0:0, 1:1}. Ensuite définissez la méthode __call__(self,n), qui vérifie si n est déjà une clé dans ce dictionnaire local, si oui, on retourne immédiatemment la valeur, sinon on lance la clause récursive r=self(n-1)+self(n-2) et on stocke le résultat (avec la clé) dans le dictionnaire. Ce résultat est aussi retourné.

Exercice 2.

(Uniquement pour ceux qui ont trop de temps libre, et veulent creuser le problème)

Notez que pour chaque fonction "mémoisable", il faudrait répéter la même manipulation, ce qui est assez pénible. Écrire une classe Memo(object) dont les instances sont formées par : p = Memo(fun), où fun est le nom d'une fonction (procédure Python). L'initialiseur la stocke comme un champ interne, contrairement à l'exercice précédent. Pour simplifier, fun sera toujours fonction d'un seul argument. Les appels : p(xx) seront équivalents à fun(xx), mais l'objet p possédera un dictionnaire interne, et mémorisera la valeur retournée (avant le retour, bien sûr) sous la clé xx. Un deuxième appel p(xx) avec le même xx, n'appelera plus la fonction fun, mais accédera au dictionnaire et récupérera la valeur.

Afin de vérifier qu'un dictionnaire dispose d'une clé concrète, utiliser par ex. if cle in dict ... ou if cle not in dict ...

Problème : si la fonction (extérieure) est récursive, la mémoïsation primitive risque de marcher mal... (Les appels récursifs internes appelleront la fonction originale, non pas le mémo-objet, car la fonction ne sait même pas que la mémoïsation existe !). Si vous arrivez à résoudre ce dilemme, OK, sinon, demandez de l'aide. L'idée consiste à re-affecter le NOM de la fonction, afin que les appels internes lancent le mémo-objet. Ce problème est très tordu, car les fonctions ne savent pas comment elles s'appellent en général, même si dans les cas simples : si, par ex. sin.__name__ $\to$ 'sin'.


Exercice 3.

En suivant la définition de la classe Verb du cours, écrire une classe Single (très simple, les détails quelconques, comme dans Verb), qui permet de créer une seule instance. Elle est sauvegardée aussi comme une variable de classe, et ensuite, si elle est là, toute tentative de créer une autre, retourne la vieille, déjà existante.


Itérateurs et générateurs

Nous avons vu en cours des "séquences virtuelles", des objets équipés avec la méthode __next__() [parfois cachée, comme dans le cas de range(...)], qui permettent d'itérer, de coopérer correctement avec la boucle for. Nous avons également vu les générateurs, la façon commode : lisible et compacte de faire des itérateurs. (En fait, les générateurs sont considérablement plus universels et utiles ; ils peuvent agir comme des coroutines, et servir pour la simulation du parallélisme en Python)

Exercice 4.

Construire le générateur "powerset", selon le cours. Il s'agit d'engendrer l'ensemble de tous les sous-ensembles d'une collection. Par exemple [1,2,3] doit engendrer [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. On parcourt la liste-source, et pour chaque élément de la liste-source, soit on le prend dans le résultat, soit non. Ensuite on retourne par yield cette solution. Conceptuellement est très facile, le seul problème est d'implémenter cela dans Python de manière rationnelle...

Une solution est récursive. Si on construit un flot (ou une liste) de [a,b,c], on la garde, et ensuite, pour [a,b,c,d] (ou [d,a,b,c]) pour chaque item de la précédente, on engendre deux éléments nouveaux, avec, et sans d.


Exercice 5.

Écrire une fonction/générateur ousinon(g1,g2) qui prend deux générateurs, g1, et g2, et si le premier est effectif (au moins un item disponible), le résultat se réduit à lui. Si, par contre, le premier échoue tout de suite, le résultat est équivalent au second générateur.

Pensez à vérifier le premier élément dans try ..., mais ne pas oublier sa valeur, il sera retourné (par yield) de notre fonction génératrice avant la boucle for qui engendre les autres. Dans ce cas l'autre générateur n'est pas touché.



Retour