Skip to content

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
class Pile:
    """Classe représentant une pile."""

    # TODO
    ...


def empile(pile, element):
    """On empile l'élément donné dans la pile donnée"""
    # TODO
    ...


def depile(pile):
    """On depile l'élément au sommet de la pile donnée"""
    # TODO
    ...

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
class Cellule:
    """Une cellule d'une pile.

    Possède une référence vers la valeur et
    une référence vers la cellule suivante.
    """

    def __init__(self, valeur, suivant):
        self.valeur = valeur
        self.suivant = suivant


class Pile:
    """Classe représentant une pile."""

    def __init__(self):
        """On utilise un chaînage pour représenter la pile."""
        self.sommet = None
        self.taille = 0



def empile(pile, element):
    """On empile l'élément donné dans la pile donnée"""
    pile.sommet = Cellule(element, pile.sommet)
    pile.taille += 1


def depile(pile):
    """On depile l'élément au sommet de la pile donnée"""
    # Que faire si la pile est vide ?
    # On lève une exception comme l'indique le cahier des charges.
    # On utilise IndexError car c'est l'exception
    # levée en général en Python dans ce genre de situation.
    if pile.taille == 0:
        raise IndexError("Can't pop from empty stack")
    pile.taille -= 1
    sommet = pile.sommet
    pile.sommet = pile.sommet.suivant
    return sommet

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 :

pile liste chaînée

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) et depile() == 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) et depile() == 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
class PileTableauDynamique:
    """Classe représentant une pile avec un tableau dynamique.

    La classe se nomme volontairement pas "Historique"
    car c'est une pile générique qui peut stocker
    n'importe quel type de données.
    """

    def __init__(self):
        """Construit une pile vide.

        Ici nous avons choisi d'utiliser en interne une list
        Python pour avoir le moins de choses à implémenter.
        """
        self.data = []
        self.taille = 0


def empile_tableau_dynamique(pile, element):
    """On empile l'élément donné dans la pile donnée"""
    pile.data.append(element)
    pile.taille += 1


def depile_tableau_dynamique(pile):
    """On depile l'élément au sommet de la pile donnée"""

    # Que faire si la pile est vide ?
    # On lève une exception comme l'indique le cahier des charges.
    # On utilise IndexError car c'est l'exception
    # levée par list.pop() si la liste est vide.
    #
    # Nous pourrions simplement laisser l'exception de
    # la liste remonter, mais ici ça nous permet de
    # définir notre propre message d'erreur.
    #
    if pile.taille == 0:
        raise IndexError("Can't pop from empty stack")
    pile.taille -= 1
    return pile.data.pop()

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 :

pile tableau dynamique

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
#!/usr/bin/env python3

"""Implémentation de l'ADT file en python."""

import datetime
import time

def arrive(l, b):
    l.append(b)

def premier(l):
    assert l, "file vide!"
    preums = l[0]
    l.pop(0)
    return preums

# Quelques tests
file_devant_la_poste = []
if datetime.date.today().weekday() == 5: # Samedi, c'est blindé !
    for i in range(1, 43):
        arrive(file_devant_la_poste, "client" + str(i))
else:
    arrive(file_devant_la_poste, "Micheline")
    arrive(file_devant_la_poste, "Karim")
    arrive(file_devant_la_poste, "Bao")
print(file_devant_la_poste)
try:
    while True:
        print(premier(file_devant_la_poste) + " au guichet SVP")
        time.sleep(5)
except:
    pass
print(file_devant_la_poste)

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 une list 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) et dequeue() = 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 fonction open()). 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 mais IndexError ;
  • 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 et enfiler ;
  • 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 instruction pop 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.

stack queue