TD11. Files et piles
Le sujet de ce TD est disponible au format pdf ici.
Les objectifs de ce TD sont les suivants :
- continuer à manipuler des références ;
- maîtriser les piles ;
- maîtriser les files.
Exercice 1 : les derniers seront les premiers
Vous êtes contactés par l'association NiEmacsNiVim pour réaliser un petit projet logiciel pour eux.
Cette association développe un éditeur de texte révolutionnaire dans lequel il suffit de taper contrôle + s
pour sauvegarder un fichier et de taper contrôle + z
pour annuler la dernière action.
Afin justement de pouvoir annuler un grand nombre d'actions, NiEmacsNiVim nous demande de leur fournir un module Python permettant de :
- créer un historique d'actions initialement vide ;
- ajouter une action à un historique ;
- récupérer la dernière action ajoutée en levant une exception si il n'y a plus d'action dans l'historique ;
- connaître la taille de l'historique.
Question 1
Ce cahier des charges correspond il à une structure de données (SDD) ou à un type abstrait (TA) ?
Correction question 1
Cliquez ici pour révéler la correction.
C'est un TA car seule une spécification est donnée.
Question 2
Avez vous déjà rencontré quelque chose de similaire, et si oui sous quelle dénomination ?
Correction question 2
Cliquez ici pour révéler la correction.
C'est une pile, une stack en anglais, et c'est du Last In First Out (LIFO).
Question 3
Proposez un squelette de votre module pour qu'il puisse être validé par NiEmacsNiVim avant que vous ne commenciez le développement. Vous fournirez une nouvelle classe permettant de représenter une pile. Pour rappel, dans le cadre de BPI nous utilisons les classes uniquement comme un agrégat de données. Les opérations que vous fournirez seront donc des fonctions et non pas des méthodes.
Correction question 3
Cliquez ici pour révéler la correction.
Voici le squelette de code que nous proposons :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
Question 4
Implémentez votre module sans utiliser de list
Python.
Correction question 4
Cliquez ici pour révéler la correction.
Voici l'implémentation basée sur une liste chaînée :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
Question 5
Dessinez la mémoire d'une pile contenant du haut vers le bas "partez"
, 3.0
, (1, 2)
.
C'est à dire une pile dans laquelle nous avons empilé (1, 2)
puis 3.0
puis "partez"
.
Correction question 5
Cliquez ici pour révéler la correction.
Voici le dessin des instances en mémoire :
Question 6
Justifiez vos choix auprès de NiEmacsNiVim.
Correction question 6
Cliquez ici pour révéler la correction.
Bonjour NiEmacsNiVim,
Concernant le nom des fonctions, nous avons utilisé une terminologie communément admise.
En effet, les deux opérations d'une pile sont en général appelées empile
et depile
en français (push
et pop
en anglais).
Concernant les performances, pour avoir une implémentation efficace, c'est-à-dire avec des coûts constants, on peut :
- utiliser une liste simplement chaînée avec un pointeur vers la tête et
empile(v)
==ajoute_en_tete(v)
etdepile()
==supprime_en_tete()
; c'est ce que nous avons fait dans le code que nous vous fournissons ; - utiliser une liste doublement chaînée avec un pointeur vers la fin et
empile(v)
==ajoute_en_fin(v)
etdepile()
==supprime_en_fin()
; mais c'était plus compliqué que la liste simplement chaînée.
Question 7
Sans écrire de code, comment feriez-vous pour implémenter votre module avec une list
Python ?
Quels seraient les avantages et les inconvénients par rapport à votre implémentation précédente ?
Correction question 7
Cliquez ici pour révéler la correction.
Pour avoir des coûts constant avec un tableau dynamique, donc une list
en Python, il faut empiler et dépiler à la fin du tableau dynamique.
Donc il faut :
empile(v)
==append(v)
;depile()
==pop()
.
Voici ce que ça donne si on implémente notre Pile
avec ça :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
En pratique, dans du code Python professionnel on utiliserait cette solution avec une list
car :
- c'est beaucoup plus facile et rapide à écrire ;
- performant car la liste est implémentée directement en C et non en Python ;
- et il n'y a aucun désavantage.
Voici le dessin des instances en mémoire d'une pile avec list
contenant les mêmes éléments que dans la question 5 :
Correction vidéo pour l'ensemble de l'exercice :
Exercice 2 : première arrivée, première servie
Question 1
Analysez le module Python ci-dessous et notez toutes les remarques (positives et négatives) et questions que vous pouvez avoir.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
Correction question 1
Cliquez ici pour révéler la correction.
Il y a beaucoup de choses intéressantes à dire sur ce petit programme. Les voici de la plus importante à la moins importante dans le contexte de ce TD :
- bien qu'aucune classe ne soit définie, nous travaillons bien ici avec le TA file implémentée à l'aide d'un tableau dynamique, donc une
list
en Python ; - faire
pop(0)
sur unelist
Python, donc un tableau dynamique, ça coûte cher comme il faut bouger tout le monde vers la gauche ; - comment faire pour avoir un coût constant : avec une liste simplement chaînée avec pointeur de tête et pointeur de fin et
enqueue(v) = ajoute_en_fin(v)
etdequeue() = supprime_en_tete()
; - une assertion est techniquement une exception en Python, de type
AssertionError
. On peut donc l'attraper comme n'importe quelle exception ; - néanmoins, ici il ne faut pas utiliser une assertion mais une exception, sûrement
IndexError
, voir le point suivant pour comprendre pourquoi ; - différence donc entre assertion et exception : une assertion est utilisée pour informer que quelque chose de logiquement impossible ne dépendant pas des entrées du programme a eu lieu. Autrement dit, si une assertion nous saute à la figure, c'est parce que nous, programmeur avons loupé quelque chose. Au contraire, une exception est levée dans le cas d'une erreur pendant l'exécution qui était anticipable (par exemple
FileNotFoundError
pour la fonctionopen()
). Citation "Python’s assert statement is a debugging aid, not a mechanism for handling run-time errors. The goal of using assertions is to let developers find the likely root cause of a bug more quickly. An assertion error should never be raised unless there’s a bug in your program." Les assertions peuvent être ignorées par l'interpréteur avec-O
. Comme ici on fournit un module, et que nous souhaitons gérer une erreur pendant l'exécution anticipable et non un bug de nous programmeur, il ne faut pas utiliser d'assertion maisIndexError
; - il manque le teste
if __name__ == "__main__"
qui est crucial ici car nous sommes dans le cadre d'un module ; - le choix des noms des deux fonctions est tout pourri. En français le "bon" choix semble être
defiler
etenfiler
; - le module standard
datetime
permet de savoir quel jour et quelle heure il est ; - le module standard
time
permet de dormir un peu.
Enfin, n'hésitez pas aller (re)voir le mémo concernant les TA et SDD disponible ici pour replacer les files, les piles et leur implémentation au bon endroit dans le contexte des TA et SDD que nous avons déjà vus.
Correction vidéo :
Exercice 3 : il y a des piles et des files partout (pour aller plus loin)
Question 1
Listez toutes les utilisations de le TA pile au sein d'un ordinateur que vous avez déjà rencontrées.
Correction question 1
Cliquez ici pour révéler la correction.
Plusieurs idées :
- la pile des frames Python quand on appelle des fonctions ;
- cette pile d'appels de fonction est également présente dans tous les autres langages ;
- la pile matériel du processeur qui fournit une instruction
push
et une instructionpop
pour justement faciliter la réalisation de la pile d'appels des langages ; - pour vérifier qu'un parenthésage est correct :
([]{{}}[])
est ok mais pas([)(])
. On empile dès qu'on a une parenthèse ouvrante, et on dépile et on vérifie que ça correspond dès qu'on a une parenthèse fermante.
Question 2
Même question pour le TA file.
Correction question 2
Cliquez ici pour révéler la correction.
Plusieurs idées :
- la file des jobs en attente dans l'imprimante du premier étage du bâtiment E ;
- la file des paquets à envoyer/recevoir sur le réseau ;
- la file des requêtes vers le disque dur.
Question 3
Faites un dessin/schéma pour illustrer le plus simplement et clairement possible selon vous les notions de pile et de file. L'objectif est d'expliquer ces concepts à vos collègues absents aujourd'hui.
Correction question 3
Cliquez ici pour révéler la correction.