Aller au contenu

TNSI : TD Files⚓︎

Qu'est qu'une File?⚓︎

Représentation Verticale

Enfile / Enqueue /
Ajout File

listeVvaleursV14...2745indicesVTête / Premier Queue / DerniervaleursV:queue->indicesV:queuevaleursV:tete->indicesV:tete

Représentation Horizontale

listevaleurs5472...14indicesTête Queuevaleurs:queue->indices:queuevaleurs:tete->indices:tete

Enfile / Enqueue /
Ajout File
Défile / Dequeue /
Retrait File

Def

Une File 🇫🇷 ou Queue 🇬🇧🇫🇷 est une Structure de Données, dite linéaire, qui modélise la méthode FIFO (First In First Out) 🇬🇧, ou Premier Arrivé Premier Sorti 🇫🇷. Intuitivement, on pourra penser à une file d'attente, ou à une queue dans un magasin.

Interface d'une File⚓︎

Pte

L'interface (c'est-à-dire les opérations disponibles) d'une File contient a minima :

  • la création d'une file vide
  • l'ajout d'un élément en queue de file (qui sera celui du dessous pour une représentation verticale, ou celui de droite pour une représentation horizontale). On dira qu'on enfile 🇫🇷 ou enqueue 🇬🇧, idéalement en temps constant
  • le retrait d'un élément en tête de file (qui sera celui du dessus pour une représentation verticale, ou celui de gauche pour une représentation horizontale) et le renvoi de sa valeur. On dira qu'on défile 🇫🇷 ou dequeue 🇬🇧, idéalement en temps constant.

Ex

On considère l'enchaînement d'opérations ci-dessous. Écrire à chaque étape l'état de la file f et la valeur éventuellement renvoyée.

Bien comprendre que la classe File() et ses méthodes n'ont pas encore été Implémentées (c'est-à-dire n'ont pas été concrètement écrites). Nous utilisons simplement son Interface.

# On suppose que la classe File est déjà implémentée :
f = File()
f.enfile(3)       # ou f.enqueue(3)
f.enfile(5)
f.est_vide()
f.enfile(1)
f.defile()        # ou f.dequeue()
f.defile() 
f.enfile(9)
f.defile() 
f.defile()  
f.est_vide()

# On suppose que la classe Pile existe déjà :
f = File()
f.enfile(3)       # f = 3
f.enfile(5)       # f  = 3 5
f.est_vide()      # False
f.enfile(1)       # f  = 3 5 1
f.defile()        # val renvoyée : 3 , f =  5 1
f.defile()        # val renvoyée : 5 , f =  1 
f.enfile(9)       # f = 1 9
f.defile()        # val renvoyée : 1 , f =  9 
f.defile()        # val renvoyée : 9 , f =  None
f.est_vide()      # True

Implémentation d'une File par un Tableau⚓︎

Dans cette partie, un Tableau sera implémenté par le type de données list de Python

Implémenter une File par un Tableau

  1. Implémenter une classe File, disposant des méthodes suivantes :

    • File() : crée une file vide, et initialise le constructeur __init__() avec un attribut data = [] initialisé à un objet Python vide, de type list
    • est_vide() : indique si la file est vide.
    • enfile(x:int)->None ou enqueue(x:int)->None : insère un élément en bas (ou à droite) de la file, en temps constant
    • defile() ou dequeue() : renvoie la valeur de l'élément en haut (ou à gauche) de la file ET le supprime de la file.
    • get_tete() : renvoie la valeur de la tete, sans la supprimer de la File

    • une méthode magique __repr__() : permet d'afficher la file sous forme agréable lorsque :

      • l'on tape >>> f ou >>> print(f) dans un Interpréteur Python
      • l'on utilise l'instruction print(f) dans un Script Python (Exemple d'affichage : |•|3|6|2|5|⟂| où 3 est la tête/premier arrivé/premier à sortir, et 5 est la queue/dernier arrivé/dernier à sortir, de la file

    • Modifier le constructeur __init__() de sorte que l'on puisse maintenant instancier la classe File en lui passant en argument un objet de type list de Python:

      # Créer une File `f` initialisée par la liste Python [1,2,3], 
# qui sera représentée dans un Terminal par `|•|1|2|3|⟂|`
f = File([1,2,3])

    • vider() : vide la File. Syntaxe : f.vider() vide f

    • copy() renvoie une copie profonde de la File (la modification de l'une n'entraine pas la modification de l'autre). Syntaxe : f1 = f.copy()
    • renverse() renverse la File. Syntaxe : f.renverse() renverse f
    • concatene() : concatène deux Files. Syntaxe : f1.concatene(f2) concatène f2 à la queue/au dessous/à droite de f1, et f2 est vidée

2.

Quelle est la complexité en temps des opérations enfile()/enqueue() et defile()/dequeue() ?
Conclusion : Le type list de Python est-il parfaitement adapté pour implémenter une File?

  • l'insertion enfile() / enqueue() n'est PAS en temps constant
  • le retrait defile() / dequeue() se fait en temps constant Cette implémentation, très simple, ne remplit donc pas toutes les conditions en termes de complexité en temps (à cause de l'insertion qui n'est pas en temps constant).

3.

Précisément, quelle méthode dans notre classe File est le facteur limitant, c'est-à-dire ralentit nos opérations? et pourquoi ?

Notre implémentation répond parfaitement à l'interface qui était demandée. Mais si le cahier des charges obligeait à ce que les opérations enfile() et defile() aient lieu en temps constant, en \(O(1)\), notre implémentation ne conviendrait pas. En cause : notre méthode defile() agit en temps linéaire (\(O(n)\)) et non pas en temps constant. L'utilisation de la structure de liste de Python (les tableaux dynamiques) provoque, lors de l'instruction self.data.pop(0) un redimensionnement de la liste, qui voit disparaître son premier élément. Chaque élément doit être recopié dans la case qui précède, avant de supprimer la dernière case. Ceci nous coûte un temps linéaire.

Implémentation d'une File par une Liste Chaînée Double⚓︎

On dispose de la Classe Cellule qui permet de modéliser une Cellule d'une File :

class Cellule :
    def __init__(self, valeur, suivante):
        self.valeur = valeur
        self.suivante = suivante

Ex

  1. À l'aide cette classe Cellule, implémenter une classe File par une Liste Chaînée Double:

    • disposant exactement de la même interface que dans l'implémentation par Tableau, mais augmentée d'une méthode retirer_queue():
      • est_vide()
      • enfile(x:int)->None / enqueue(x:int)->None
      • defile() / dequeue()
      • get_tete() : renvoie la valeur de la tete, sans la supprimer de la File
      • une méthode magique __repr__() : permet d'afficher la file sous forme agréable lorsque :
        • l'on tape >>> f ou >>> print(f) dans un Interpréteur Python
        • l'on utilise l'instruction print(f) dans un Script Python (Exemple d'affichage : |•|3|6|2|5|⟂| où 3 est la tête/premier arrivé/premier à sortir, et 5 est la queue/dernier arrivé/dernier à sortir, de la file
      • Modifier le constructeur __init__() de sorte que l'on puisse maintenant instancier la classe File en lui passant en argument un objet de type list de Python: 
        # Créer une File `f` initialisée par la liste Python [1,2,3], 
# qui sera représentée dans un Terminal par `|•|1|2|3|⟂|`
f = File([1,2,3])
      • vider() : vide la File. Syntaxe : f.vider() vide f
      • copy() renvoie une copie profonde de la File (la modification de l'une n'entraine pas la modification de l'autre). Syntaxe : f1 = f.copy()
      • retirer_queue() renvoie la valeur de la queue, ET supprime la queue de la File. On pourra dans cette question, utiliser les méthodes get_valeur(), get_suivante() et set_suivante() de la classe Cellule, que nous avions développées dans le TD sur les Listes Chaînées (Simples, ou Doubles).
      • renverse() renverse la File. Syntaxe : f.renverse() renverse f
      • concatene() : concatène deux Files. Syntaxe : f1.concatene(f2) concatène f2 à la queue/au dessous/à droite de f1, et f2 est vidée
    • et des deux attributs (publics) suivants (=Liste Chaînée Double)
      • le premier élément, tete, de la File
      • le dernier élément, queue, de la File La classe File doit donc pouvoir être utilisée par exemple comme suit:
        f = File()
f.enfile(5)     # ou f.enqueue(5)
f.enfile(8)
f.defile()      # ou f.dequeue()

Étudier la complexité des opérations d'ajout enfile() / enqueue(), et defile() / dequeue()
Conclusion : Une Liste Chaînée Double est-elle parfaitement adaptée pour implémenter une File?

La donnée des deux extrémités, permet de réaliser un retrait en tête de liste defile() / dequeue(), ET un ajout en fin de liste enfile() / enqueue() en temps constant dans les deux cas. Une Liste Chaînée Double est donc parfaitement adaptée pour implémenter une File.

Remarque

Il est important de de noter que la manière d'utiliser la file (son interface) est indépendante des deux implémentations. Il est fréquent de commencer la programmation avec une implémentation améliorable d'une structure de données. Puis, par la suite, la structure de données pourra être améliorée sans que le code principal n'ait besoin d'être retouché.

Implémentation d'une File avec deux Piles⚓︎

Il est possible d'implémenter une File avec 2 Piles, l'idée est la suivante : on crée une Pile d'Entrée et une Pile de Sortie.

  • quand on veut enfiler, on empile sur la pile d'entrée.
  • quand on veut défiler, on dépile sur la pile de sortie.
  • Lorsque la pile de sortie est vide, on dépile entièrement la pile d'entrée dans la pile de sortie.

Dans l'exercice suivant, on suppose connue et on reprend la structure de Pile du TD précédent sur les Piles, implémentée (par exemple) avec les Listes Chaînées Simples par deux classes Cellule et Pile

Ex

  1. Implémenter une classe File avec deux Piles, disposant exactement de la même interface que dans l'implémentation par Tableau, (pas besoin d'implémenter la méthode retirer_queue()) :
    • le constructeur __init__() définit une Pile d'Entrée, et une Pile de Sortie
    • disposant des méthodes suivantes :
      • est_vide()->bool
      • enfile(x:int)->None ou enqueue(x:int)->None
      • defile() ou dequeue()
      • get_tete() : renvoie la valeur de la tete, sans la supprimer de la File
      • une méthode magique __repr__() : permet d'afficher la file sous forme agréable lorsque :
        • l'on tape >>> f ou >>> print(f) dans un Interpréteur Python
        • l'on utilise l'instruction print(f) dans un Script Python (Exemple d'affichage : |•|3|6|2|5|⟂| où 3 est la tête/premier arrivé/premier à sortir, et 5 est la queue/dernier arrivé/dernier à sortir, de la file
      • Modifier le constructeur __init__() de sorte que l'on puisse maintenant instancier la classe File en lui passant en argument un objet de type list de Python: 
        # Créer une File `f` initialisée par la liste Python [1,2,3], 
# qui sera représentée dans un Terminal par `|•|1|2|3|⟂|`
f = File([1,2,3])
      • vider() : vide la File. Syntaxe : f.vider() vide la file f
      • copy() renvoie une copie profonde de la File (la modification de l'une n'entraine pas la modification de l'autre). Syntaxe : f1 = f.copy()
      • renverse() renverse la File. Syntaxe : f.renverse() renverse f.
      • concatene() : concatène deux Files. Syntaxe : f1.concatene(f2) concatène f2 au dessous/à droite de f1, et f2 est vidée
    • la Classe File doit pouvoir être utilisée par exemple comme suit: 
      f = File()
f.enfile(5)     # ou f.enqueue(5)
f.enfile(8)
f.defile()      # ou f.dequeue()
  2. Quelle est la complexité des méthodes enfile() et defile() Conclusion : Une Double Pile est-elle parfaitement adaptée pour implémenter une File?

Le module collections.deque⚓︎

Page de Référence sur le site python.org : Module collections.deque

Nous avons présenté 3 implémentations de la structure de file, qui ne peuvent pas être implémentées correctement par une simple liste python, contrairement à la structure de pile.

La bibliothèque standard possède toutefois un module nommé collections qui contient quelques structures de données supplémentaires, dont le type deque, qui est une implémentation de file : 

from collections import deque
f = deque()
f.append("Premier Arrivé")
f.append("Deuxième")
print(f.popleft())
f.append("Troisième")
while f:
  print(f.popleft())

produit la sortie suivante :

Premier Arrivé
Deuxième
Troisième

⚠ Avec le type deque, les opérations d'ajout et de suppression dans la file sont toutes deux réalisées en temps constant.

ATTENTION Ne pas confondre le type deque dont nous venons de parler, et qui signifie Double Ended Queue 🇬🇧, avec le verbe dequeue / défiler

Exemples d'Utilisation des Files⚓︎

Ex

1.

Chercher sur internet des exemples d'utilisation des Files en informatique.

  • Gérer la File des impressions en attente (spooler) d'un système d'impression
  • Mémoriser la File des transactions en attente accédant à une base de données
  • Gérer la File d'attente des processus d'un système d'exploitation
  • Parcours en largeur d'un Graphe
  1. Citer/Étudier la complexité dans chaque exemple