Données File Implémentation

Identification

Infoforall

18 - Implémenter une File 1/3


Nous allons voir quelques implémentations possibles du type File.

Prerequis : l'activité sur les Piles, sur les Files, ainsi qu'au moins l'une des activités d'implémentation.

1 - Implémentation de la File sous forme d'un tableau dynamique

Type abstrait FILE - Principe FIFO

Principe général d'organisation de la FILE : FIFO

Une File est un type abstrait de données ayant les propriétés suivantes :

  • il s'agit d'une séquence finie et ordonnée de données
  • on s'impose strictement de n'agir que sur les deux extrémités. On insère d'un côté et on supprime et lit de l'autre
    • insérer un élément du côté de l'entrée (l'arrière de la file) se nomme l'enfilement
    • supprimer l'élément du côté de la sortie (l'avant de la file) se nomme le défilement

On désigne également la pile sous l'acronyme FIFO pour First In First Out (à savoir), ou en français : Premier arrivé, premier parti..

FIFO

Fonctions d'interface pour une FILE (en version non mutable ici)

Voici la description des fonctions d'interface fondamentales que les algorithmes vont pouvoir effectuer sur le type File.

Principe de l'interface d'une file
  1. nouvelleFile() -> File : on crée une nouvelle file vide. On pourra l'identifier à (). En anglais, cela pourrait donner newQueue.
  2. fileVide(f:File) -> bool : renvoie un booléen qui vaut True si la file p transmise est une file vide. On peut aussi le noter estVide. En anglais, cela pourrait donner isNil ou isNull.
  3. enfiler(elt:Elt, f:File) -> File : on renvoie une file en rajoutant l'élément elt en entrée dans f. En anglais, ça se nomme enqueue. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).
  4. defiler(f:File) -> File  : on supprime l'élément en position de sortir et renvoie la nouvelle file f. En anglais, ça se nomme dequeue. La fonction n'est définie que si la file n'est pas vide. On considère qu'une bonne implémentation réalise ceci à coût constant (θ(1)).
  5. lireAvant(p:File) -> Elt : on renvoie l'élément en sortie(sans le supprimer ici). La fonction n'est définie que si la file n'est pas vide normalement. En anglais, ça se nomme front

Quelques explications sur le contenu interne possible du tableau dynamique qui va gérer tout cela (on prendra le cas le plus naïf où on déplace tout le tableau à chaque sortie d'un élément...):

On considère ici le cas d'une interface destinée à une File non mutable.

>>> a = nouvelleFile() >>> a = enfiler(5, a)
Tableau contient 5
>>> a = enfiler(10, a)
Tableau contient 5-10
>>> a = enfiler(20, a)
Tableau contient 5-10-20
>>> a = defiler(a)
Tableau contient X-10-20

Il ne reste qu'à déplacer les valeurs vers la gauche :

Tableau contient 10-20

01°Estimer le coût des trois fonctions enfiler, defiler et lireAvant.

...CORRECTION...

Difficile de répondre sans connaître les codes des méthodes correspondantes.

Si on suppose que l'accès à la dernière case , le rajout d'une case est à coût constant, alors enfiler est à coup constant.

La lecture de l'index 0 est à coût constant. lireAvant est donc à coût constant.

Par contre, il faut déplacer tous les éléments restants dans le tableau pour defiler. Cette opération est donc ici linéaire. Ce n'est pas terrible.

Voici une implémentation utilisant le type list de Python qui est une structure de données proche du tableau dynamique. La seule subtilité du code ci-dessous vient du fait qu'on utilise méthode pop en fournissant un argument de 0 pour signaler qu'on veut "supprimer" la valeur située dans la case d'index 0.

Implémentation du type File (mutable) sous forme d'un tableau dynamique Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
class Elt : '''Juste pour pouvoir noter Elt dans les prototypes''' class File : '''Juste pour pouvoir noter File dans les prototypes''' '''Implémentation de type abstrait Pile en utilisant des tableaux dynamiques''' def nouvelleFile() -> File: return [] def fileVide(f:File) -> bool: return f == [] def enfiler(elt:Elt, f:File) -> None : f.append(elt) # rajoute l'élément à la fin du tableau (ARRIERE pour nous) def defiler(f:File) -> Elt: if not fileVide(f) : return f.pop(0) # supprime et renvoie le premier élément du tableau (AVANT pour nous) def lireAvant(f:File) -> Elt: if not fileVide(f) : return f[0] # renvoie le contenu de l'index 0, AVANT pour nous

02° Utiliser cette version et sa fonction d'affichage pour constater qu'on a bien une File et qu'à part la mutabilité, on ne peut pas savoir comment tout cela est implémenté à l'interne tant qu'on utilise uniquement les fonctions d'interface.

Notez bien le comportement de la File en FIFO contrairement à la Pile : le 40 qu'on rajoute plus tard se met bien à la suite des autres dans la File.

>>> a = nouvelleFile() >>> enfiler(5, a) >>> a [5] >>> enfiler(10, a) >>> a [5, 10] >>> enfiler(20, a) >>> a [5, 10, 20] >>> defiler(a) 5 >>> a [10, 20] >>> defiler(a) 10 >>> a [20] >>> enfiler(40, a) >>> a [20, 40] >>> defiler(a) 20 >>> defiler(a) 40

Cette implémentation est claire

  1. On rajoute les nouveaux éléments à la fin du tableau lors de l'enfilement
  2. On supprime l'élement d'index 0 lors du défilement

Mais ... le défilement est à coût linéaire dans cette implémentation simple : il faut déplacer les éléments vers la gauche pour combler le trou.

Voyons maintenant une autre implémentation qui réagit un peu mieux.

2 - Implémentation d'une File avec deux Piles

Le principe est simple :

  • Lorsqu'on veut enfiler un élément dans la File abstraite, on dépose en réalité l'élément dans une structure de données Pile d'entrée qu'on nommera PileEntree.
  • Lorsqu'on veut defiler un élément de la File abstraite, on va chercher en réalité le sommet d'une structure de données Pile de sortie qu'on nommera PileSortie.

Sur l'image ci-dessous, on a inséré les horaires d'arrivée des clients dans un magasin. Le premier est arrivé à 13h, le suivant à 13h20... Lorsqu'on enfile les heures d'arrivée, on voit bien que la dernière heure est au Sommet de pileEntree.

File avec deux piles

Le problème vient du fait que lorsqu'on va vouloir défiler ces données, on veut récupérer d'abord le 13h !

Comment faire ?

03° Réflechir à ce problème. Auriez-vous une solution ?

Comme souvent, une fois la solution trouvée cela paraît évident.

Le tout est de trouver l'idée...

Comment alors ?

L'idée globalement est d'inverser les éléments de la Pile d'entrée en les déversant dans la Pile de sortie.

Déversement qui inverse l'ordre

L'ancien Sommet (en rose ici) va bien se retrouver tout en bas de la pile de sortie. Et l'élément qui va se retrouver au Sommet de la pile de Sortie est bien le plus ancien élément qu'on avait stocké dans la pile d'Entrée.

Par contre, il ne faut le faire que lorsqu'on veut lire notre FILE et que la pile interne de sortie est vide.

Lorsqu'on veut défiler les données de la File, deux cas se présentent :

  • Si la pile de sortie pileSortie est vide
    • On dépile l'intégralité de pileEntree dans pileSortie : cela va permettre d'inverser les positions respectives du premier arrivé et du dernier arrivé dans pileEntree. On peut dire qu'on déverse la pile d'entrée dans la pile de sortie.
  • Si la pile de sortie pileSortie n'est pas vide, on dépile juste la pile de sortie.

Les étapes de l'inversion en images :

  1. La pile d'entrée a déjà reçu ceci :
  2. File avec deux piles
  3. On veut défiler mais la pile de sortie est vide. Il faut donc déverser toute la pile d'entrée dans la pile de sortie
    • On dépile le premier élément de la pile d'entrée et on l'empile dans la pile de sortie
    • File avec deux piles
    • On dépile le deuxième élément de la pile d'entrée et on l'empile dans la pile de sortie
    • File avec deux piles
    • On dépile le troisième élément de la pile d'entrée et on l'empile dans la pile de sortie
    • File avec deux piles
    • Au final, à la fin du déversement, la pile d'entrée sera vide et la pile de sortie aura de nouveaux éléments, dont le plus ancien est bien le Sommet !
    • Déversement de la pile d'entrée dans la pile de sortie
  4. On peut alors défiler et obtenir le 13h et même enfiler de nouveaux éléments qui vont alors aller dans la pile d'entrée. Tant que la pile de sortie n'est pas vide, les éléments resteront dans la pile d'entrée.
  5. File avec deux piles

Nous allons maintenant réaliser une implémentation mutable de File avec deux piles qui utilise l'implémentation Pile non mutable.

On écrira donc des codes de ce type pour les files mutables : enfiler(5, ma_file).

Par contre, comme nos Piles sont non mutables, on écrira des choses comme ceci : ma_pile = empiler(5, ma_pile).

04° Nous allons stocker nos deux piles dans un tableau que nous nommerons par exemple file, comme file.

 file = [pileEntree, pileSortie.

Voici donc un exemple d'utilisation de la file : on y enfile des éléments qui viennent s'empiler dans la pile d'entrée.

>>> file = nouvelleFile() >>> file [(), ()] >>> enfiler(5, file) >>> file [(5, ()), ()] >>> enfiler(10, file) >>> enfiler(20, file) >>> file [(20, (10, (5, ()))), ()]

Quel type de code doit-on trouver dans la fonction enfiler pour parvenir à rajouter un nouvel élément dans la pile d'entrée (celle en violet) non mutable contenue dans notre file. On considère qu'on récupère la référence de la file dans un paramètre nommé f ?

  • A :  f[0] = empiler(5, f[0]) 
  • B :  empiler(5, f[0]) 
  • C :  f[0] = enfiler(5, f[1]) 
  • D :  enfiler(5, f[0]) 

...CORRECTION...

Pour atteindre la pile d'entrée, il faut utiliser  f[0]  puisque la pile d'entrée est stockée dans l'index 0.

L'énoncé dit que les piles sont non mutables ici. On ne peut donc pas agir sur les piles simplemnet en fournissant leurs adresses : les fonctions des piles renvoient une nouvelle pile, image modifiée de la précédente. Si on veut modifier notre liste, il faut donc remplacer par affectation l'ancien contenu par le nouveau.

La réponse est donc A :  f[0] = empiler(5, f[0]) 

Si on désire lire les éléments (et donc lire d'abord le 5 normalement), il faut d'abord déverser la pile d'entrée dans la pile de sortie.

>>> file [(20, (10, (5, ()))), ()] >>> lireAvant(file) 5 >>> file [(), (5, (10, (20, ())))]

05° Que doit-on remarquer d'important dans le contenu de la pile de sortie f[1] par rapport au contenu de la pile f[0] maintenant vide ? Demandez vous notamment où se trouve maintenant le 5, qui était le premier élément qu'on a voulu stocker dans notre file.

...CORRECTION...

On remarque que le contenu de la pile est inversée. Le 5 est maintenant au sommet. Or, ce 5 était le premier arrivé lors du remplissage de la pile d'entrée.

06° On veut maintenant défiler notre file (composée de deux piles en interne).

 file = [pileEntree, pileSortie.

>>> file [(), (5, (10, (20, ())))] >>> defiler(20, file) 5 >>> file [(), (10, (20, ()))]

Quel type de code doit-on trouver dans la fonction defiler pour parvenir à supprimer le sommet de la pile de sortie (non mutable) stockée à l'intérieur de la variable f ?

  • A :  f[1] = depiler(f[1]) 
  • B :  depiler(f[1]) 
  • C :  f[1] = defiler(f[1]) 
  • D :  defiler(f[1]) 

...CORRECTION...

Pour atteindre la pile de sortie, il faut utiliser  f[1]  puisque la pile de sortie est stockée dans l'index 1.

L'énoncé dit que les piles sont non mutables ici. Si on veut modifier notre liste, il faut donc remplacer par affectation l'ancien contenu par le nouveau.

La réponse est donc A :  f[1] = depiler(f[1]) 

Vous allez maintenant devoir récréer les fonctions peu à peu.

Vous trouverez le code complet plus bas, au cas où vous auriez des problèmes.

Dans le résumé du cours, vous trouverez un autre exemple : l'implémentation deux piles en utilisant la Pile-tableau.

07° Regarder le code ci-dessous. Comment se nomment les fonctions permettant de vérifier si une pile ou une file est vide ?

Regarder la fonction nouvelleFile. Quelle est la structure qui stocke les données de la file ? Que contient cette structure ?

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
class Elt : '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile : '''Juste pour pouvoir noter Pile dans les prototypes''' class File : '''Juste pour pouvoir noter File dans les prototypes''' '''Implémentation de type abstrait Pile en utilisant des tuples (sommet, autre_pile)''' def nouvellePile() -> Pile : '''Renvoie une liste vide''' return () def pileVide(p:Pile) -> bool : '''Renvoie True si la pile est vide''' return p == () def empiler(elt:Elt, p:Pile) -> Pile : '''Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile.''' return (elt, p) def lireSommet(p:Pile) -> Elt : '''Renvoie la valeur stockée au sommet, sans la supprimer de la pile''' if not pileVide(p) : return p[0] def depiler(p:Pile) -> Pile : '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet''' if pileVide(p) : # la liste envoyée est () return nouvellePile() else : return p[1] # Fonction de l'implémentation FILE hors Interface def deverser(f:File) -> None : while not pileVide(f[0]) : element = lireSommet(f[0]) f[0] = depiler(f[0]) f[1] = empiler(element, f[1]) # Fonctions d'interface de la FILE def nouvelleFile() -> File : pileEntree = nouvellePile() # inputStack en anglais pileSortie = nouvellePile() # outputStack en anglais return [pileEntree, pileSortie] def fileVide(f:File) -> None : return pileVide(f[0]) and pileVide(f[1]) def enfiler(elt:Elt, f:File) -> None: pass def defiler(f:File) -> Elt: pass def lireAvant(f:File) -> Elt : pass

...CORRECTION...

On constate que les fonctions se nomment pileVide et fileVide.

La FILE est implémentée sous la forme d'un tableau de deux éléments : l'index 0 correspond à la pile d'entrée et l'index 1 correspond à l'index de sortie.

 file = [pileEntree, pileSortie.

08° Créer la fonction enfiler après avoir étudier le prototype pour savoir ce qu'elle doit recevoir et renvoyer. Pensez à aller revoir les QCM précédents :o)

09° Expliquer le fonctionnement de la fonction deverser.

10° Créer la fonction lireAvant. Pensez à utiliser la fonction deverser si la pile de sortie est vide.

11° Créer la fonction defiler qui devra également utiliser deverser si la pile de sortie est vide.

Voici le code final de correction.

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
class Elt : '''Juste pour pouvoir noter Elt dans les prototypes''' class Pile : '''Juste pour pouvoir noter Pile dans les prototypes''' class File : '''Juste pour pouvoir noter File dans les prototypes''' '''Implémentation de type abstrait Pile en utilisant des tuples (sommet, autre_pile)''' def nouvellePile() -> Pile : '''Renvoie une liste vide''' return () def pileVide(p:Pile) -> bool : '''Renvoie True si la pile est vide''' return p == () def empiler(elt:Elt, p:Pile) -> Pile : '''Renvoie une nouvelle pile où elt est le sommet et pile la suite de notre nouvelle pile.''' return (elt, p) def lireSommet(p:Pile) -> Elt : '''Renvoie la valeur stockée au sommet, sans la supprimer de la pile''' if not pileVide(p) : return p[0] def depiler(p:Pile) -> Pile : '''Renvoie une nouvelle pile où on a supprimé l'ancien sommet''' if pileVide(p) : # la liste envoyée est () return nouvellePile() else : return p[1] # Fonction de l'implémentation FILE hors Interface def deverser(f:File) -> None : while not pileVide(f[0]) : element = lireSommet(f[0]) f[0] = depiler(f[0]) f[1] = empiler(element, f[1]) # Fonctions d'interface de la FILE def nouvelleFile() -> File : pileEntree = nouvellePile() # inputStack en anglais pileSortie = nouvellePile() # outputStack en anglais return [pileEntree, pileSortie] def fileVide(f:File) -> None : return pileVide(f[0]) and pileVide(f[1]) def enfiler(elt:Elt, f:File) -> None: f[0] = empiler(elt, f[0]) def defiler(f:File) -> Elt: if not fileVide(f) : if pileVide(f[1]) : deverser(f) valeur = lireSommet(f[1]) f[1] = depiler(f[1]) return valeur def lireAvant(f:File) -> Elt : if not fileVide(f) : if pileVide(f[1]) : deverser(f) return lireSommet(f[1])

12° Utiliser dans instructions dans le Shell pour enfiler 5, 10, 20. Défiler (vous devriez obtenir 5). Rajouter ensuite un 40. Défiler jusqu'à bout. Vous devriez obtenir le 10, le 20 puis le 40.

3 - FAQ

Rien pour le moment

Nous venons de voir deux implémentations possibles.

L'implémentation sous forme d'un simple tableau n'est pas terrible à cause du pop(0) qui provoque un coût linéaire lors du défilement.

L'implémentation sous forme de deux piles est plus performant mais nécessite parfois d'effectuer un déversement, dont le coût est linéaire. C'est mieux que le précédent car ce n'est pas à chaque défilement.

Dans les deux activités qui suivent, nous allons voir qu'en "compliquant" un peu les choses, on peut obtenir des implémentations à coût constant à l'enfilement et au défilement.

Activité publiée le 14 10 2020
Dernière modification : 23 10 2020
Auteur : ows. h.