Files

Le type abstrait file

Principe

Le jeu Décades Flush ( d'après A. Busser )

Le but du jeu est de ranger les nombres de la liste de gauche ci-dessous dans l'ordre croissant, en n'utilisant que deux opérations élémentaires possibles :

placer le dernier nombre de la liste de gauche en début d'une des 3 suites de nombres.
extraire le nombre en fin d'une des suites, et le placer en première place dans la liste de droite qui doit donc être triée.


🂢🂤🂡🂣🂥🂦🂩🂧🂨🂪

Conclusion

La structure utilisée dans le jeu ci-dessus s'appelle une file.

En informatique, une file (queue en anglais ) est une structure de données basée sur le principe «Premier entré,premier sorti», en anglais FIFO (First In, First Out), ce qui veut dire que les premiers éléments ajoutés à la file seront les premiers à être récupérés.

Dans cette structure, on n'a donc accès qu'aux "extrémités" de la file, l'une où l'on "enfile" les éléments ( que l'on appelle souvent la "queue" ), l'autre où on les "défile" ( la "tête" ).

Le fonctionnement ressemble à une file d'attente : les premières personnes à arriver sont les premières personnes à sortir de la file.

Voici quelques exemples d'usage courant d'une file :

En général, on utilise des files pour mémoriser temporairement des transactions qui doivent attendre pour être traitées. Par exemple, un serveur web qui reçoit plusieurs demandes de connexion, va les mettre dans une file, puis les traitera dans l'ordre de leur arrivée. Cela permet de ne pas "bloquer" le serveur lors d'une demande de connexion : le traitement se fera pendant les temps où aucune demande ne se fait, tout en laissant la possibilité à une nouvelle connexion de s'établir ( le serveur reste "à l'écoute" ).
Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente.
Dans un système d'exploitation multi-taches, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune, les différents programmes sont mis dans une file d'attente en attendant qu'arrive leur tour d'être exécutés.

Une file est utile dans tous les cas où des informations doivent être traitées par ordre de priorité, l'information placée en début de file étant la plus prioritaire.

Primitives

Il n'y a pas besoin là non plus de grand chose pour faire fonctionner une file :

création d'une file vide
"enfiler" un élément en queue de file
"défiler" l'élément en tête de la file
savoir si la file est vide ou non ( en effet, on ne peut pas défiler un élément d'une file vide. )

On peut également stocker dans une file des éléments de tout type : entier, chaînes de caractères, listes,..., mais aussi des objets.

Implémentations

Le TAD file n'est pas disponible non plus nativement en Python, il va falloir nous-mêmes l'implémenter.

Pour illustrer le concept de "plusieurs implémentations possibles pour le même TAD", vous allez implémenter le type file de trois manières différentes :

une version où la file sera un tableau de taille fixe
une version où la file sera un tableau dynamique
une version ou la file sera implémentée avec deux piles

Dans les trois cas, vous utiliserez le paradigme de programmation objet.

Version tableau de taille fixe

Comme dans le cas de la pile, vous utiliserez un tableau dont la taille ne changera jamais.

On utilisera deux attributs self.tete et self.queue pour repérer les éléments en tête et en queue de file; attention alors à la manière de modifier ces deux "pointeurs" pour que la file fonctionne correctement ( il faudra bien entendu la tester...)

Écrire une classe FileStatique qui utilise un tableau de taille fixe ( disons 20 éléments ) pour gérer une structure de données de type file.

Voila l'interface de la classe :

class FileStatique: def __init__(self): """ Instancie une file vide de 20 élements ( initialisés à None ) """ pass def enfiler(self, element): """ Enfile ( si la file n'est pas pleine ! ) un élément en queue de file """ pass def defiler(self): """ Défile ( si la file n'est pas vide ! ) un élément en tête de file, et le renvoie """ def est_vide(): """ Renvoie True si la file est vide, False sinon """ pass def est_pleine(self): """ Renvoie True si la file est pleine, False sinon """ pass

Quel est le principal avantage de cette implémentation ? Et bien sûr, son, principal inconvénient ?

SOLUTION

Version tableau dynamique

Écrire une classe FileDynamique qui implémente le TAD file à l'aide d'un tableau dynamique.
L'interface de cette classe sera exactement la même que la précédente :
class FileDynamique: def __init__(self): """ Instancie une file vide """ pass def enfiler(self, element): """ Enfile un élément en queue de file """ pass def defiler(self): """ Défile ( si la file n'est pas vide ! ) un élément en tête de file, et le renvoie """ def est_vide(): """ Renvoie True si la file est vide, False sinon """ pass
Voila les méthodes à votre disposition pour manipuler un tableau dynamique en Python :
- element = tableau.pop(i) : retire et renvoie l'élément à l'index i du tableau; si i n'est pas précisé, c'est le dernier élément qui est retiré
- tableau.append(element) : ajoute un élément à la fin du tableau
- tableau.insert(i, element) : insère un élément dans le tableau avant celui situé à l'index i; si i = 0, l'insertion se fait au début du tableau
Là aussi, vous avez le choix de mettre la tête de la file en début ou en fin de tableau, à vous de choisir : y a-t-il une meilleure solution qu'une autre ?
testez votre classe en instanciant un objet FileDynamique, puis en appelant ses méthodes pour quelques éléments.
Que vous ayez choisi de mettre la tête de la file au début ou en fin de tableau, quel est, à votre avis, l'inconvénient, du point de vue complexité, de cette implémentation ?

SOLUTION

Version deux piles

Bizarre cette idée...

Principe

On utilise donc deux piles : la première dont le sommet correspondra à la queue de la file ( appelons-la pile_queue ), le sommet de la deuxième à sa tête ( pile_tete ).

Enfiler un élément : on place simplement l'élément au sommet de pile_queue
Défiler la tête : deux cas peuvent se présenter.
- si pile_tete est vide : on va se servir du fait que, si on inverse une pile, son élément le plus en bas se retrouve au sommet. La tête de liste étant "tout en bas" de pile_queue, on va donc dépiler cette dernière entièrement dans pile_tete; on dépile alors simplement le sommet de pile_tete.
- si pile_tete n'est pas vide : on dépile simplement son sommet.

Vérification sur un exemple

Sur le schéma ci-dessous, donnez la trace des opérations suivantes en dessinant, après les étapes 1,2, 3, 4, 5 et 6 le contenu des deux piles.

On crée une file vide.
On enfile les éléments a,b et c.
On défile un élément.
On enfile les éléments d et e.
On défile deux éléments.
On défile un élément.

SOLUTION

Intérêt de cette implémentation

Wow...c'est bien compliqué, pourquoi se casser la tête ? Et bien, cette façon de faire est beaucoup plus efficace que la précédente :

Attention, explication hors programme mais intéressante tout de même...

La très grande majorité du temps, les opérations de défilage, aussi bien que celles d'enfilage, basées ici sur des opérations de dépilage qui ne font appel elles-mêmes qu'à des méthodes en O(1) ( cf. chapitre précédent ), sont donc alors très efficaces.

Il n' y a que lorsque que l'on veut défiler et que pile_tete est vide, que l'on doit dépiler entièrement pile_queue vers pile_tete, ce qui est beaucoup plus couteux en temps ( opération en O(n) ). Mais comme cela se produit peu fréquemment, "on a le temps" de faire n "petites" opérations en O(1) avant de faire une "grosse" opération en O(n).

Prenons un exemple :

supposons qu'une opération en O(1)( pour 1 élément ) dure 1 µs; une opération en O(n) durera donc 100 µs pour n = 100 éléments ( les valeurs sont bidons...).
entre 2 opérations en O(n), on a donc le temps de faire 100 opérations en O(1); la durée totale des 100+1 opérations est 100 + 100 x 1µs = 200 µs
ramenée à une seule opération, la durée "lissée" est donc en moyenne de : 200 / 101 = 2 µs, soit seulement le double d'une opération en O(1) !

Dans ce type d'implémentation, on fait le choix d'utiliser le plus souvent des opérations rapides, quitte à de temps en temps faire appel à une opération plus coûteuse en temps mais dont le coût sera "amorti" sur l'ensemble des opérations.

( Avec l'implémentation précédente, les opérations d'enfilage se faisait TOUJOURS en O(n)...)

Il fallait y penser...cela vous montre que l'implémentation "naïve" ( au sens de "naturelle", "évidente" ) d'un TAD ( mais également de tout algorithme ) n'est pas toujours la plus efficace : il faut souvent se creuser un peu plus la tête !!

Implémentation

Vous allez écrire une classe File implémentant le TAD file à l'aide de deux piles, et, pour bien illustrer l’intérêt de la réutilisation de classes déjà écrites, vous allez reprendre le code de la classe Pile que vous avez codée au chapitre précédent ( copiez simplement son code dans votre nouveau script ).

Vous allez donc "imbriquer" des objets ( deux instances de Pile ) dans un autre objet ( une instance de File )...pas de problème, ça marche très bien, et le gros plus c'est que vous n'avez pas à refaire le code pour gérer les deux piles, tout est déjà écrit !

from pile import * # pensez à charger le module 'pile.py' class File: def __init__(self): self.pile_tete = Pile() # pile statique ou pile dynamique, au choix self.pile_queue = Pile() def enfiler(element): pass def defiler(self): pass def est_vide(self): pass

Attention à l'appel des méthodes des "objets dans l'objet".

Par exemple : j'ai besoin pour gérer ma file, de dépiler une des piles ; mais la file n'a pas de méthode depiler() !


	>>> file.depiler()
	Traceback (most recent call last):
	  File "", line 1, in 
	AttributeError: 'File' object has no attribute 'depiler'

	>>>

Pour bien "cibler" la méthode, il faut "enchaîner" les notations '.', en "descendant" progressivement dans la hiérarchie des objets :


	file.pile_tete.depiler() # on accède bien à : depiler() > méthode de pile_tete > attribut de file.

Vous testerez là-aussi le bon fonctionnement de votre classe.

SOLUTION

Conclusion

Trois manières différentes de coder la file...mais, vous aurez remarqué que son interface n'a pas changé; quelqu'un qui voudrait utiliser notre structure de données ne sera pas du tout géné par le fait que l'on change d'une implémentation à l'autre !

A noter que Python propose la classe deque dans le module collections qui est optimisée pour la manipulation de files; son implémentation se fait avec une structure appelée liste doublement chaînée ( encore une autre implémentation différente ! )

Applications

File circulaire

Voila une optimisation de la file linéaire qui ne présente pas ses inconvénients.

les deux pointeurs tete et queue sont initialisés à -1; ces deux pointeurs seront incrémentés pour adresser les éléments du tableau correspondant à la tête et à la queue de la file, et vont donc se "déplacer" de la gauche vers la droite du tableau ( on pourrait aussi faire l'inverse bien sûr ), mais en "revenant" au début du tableau quand nécessaire.
La file "balaie" ainsi de manière "circulaire" tout le tableau, en "effaçant" les données qui s'y trouvaient éventuellement mais qui ne font alors plus partie de la file.

Il faudra bien entendu vérifier quand nécessaire si la file est vide ou pleine !

-	-	-	-	-	-	-	-	-	-

Les éléments appartenant à la file sont en rouge.

Pour enfiler un élément, c'est assez simple :

on vérifie si la file n'est pas pleine
on vérifie ensuite si la queue de la file n'a pas atteint le dernier élément du tableau ( indice N - 1 ) : si c'est le cas, on le "fait revenir" au début du tableau en lui donnant l'indice 0; sinon, on incrémente simplement le pointeur queue.
on stocke alors l'élément à l'indice queue tu tableau.

pour défiler, il faut faire un peu plus attention :

on commence bien entendu par vérifier que la file n'est pas vide.
on vérifie ensuite si la file ne contient plus qu'un seul élément : dans ce cas, on renvoie l'élément en tête de file, puis on réinitialise tete et queue à -1 pour signaler que la file est alors vide.
on vérifie ensuite si la tete de la file n'a pas atteint le dernier élément du tableau ( indice 19 ) : si c'est le cas, on le "fait revenir" au début du tableau en lui donnant l'indice 0; sinon, on incrémente simplement le pointeur tete.
on renvoie la tete de la file, c'est à dire l'élément du tableau à l'indice tete.

d'après le principe énoncé précédemment, quelle condition sur les pointeurs tete et queue est vérifiée quand la file est vide ?
à l'aide de l'animation, déterminer les deux situations correspondant à une file pleine; en déduire les conditions à vérifier sur les valeurs des pointeurs tete et queue pour déterminer si la file est pleine.
coder alors une classe FileStatiqueBis qui implémente une file circulaire à l'aide d'un tableau de taille fixe; l'interface sera exactement la même que celle de la file statique traitée en début de cours.
Instancier et tester le bon fonctionnement de votre classe !

class FileCirculaire: def __init__(self): self.tete = self.queue = -1 def enfiler(self, elt): pass def defiler(self): pass def est_vide(self): pass

SOLUTION

Application des files : simulation d'une file d'attente aux caisses d'un supermarché

Dans un supermarché, il y a 5 caisses et une file d’attente commune.

Dès qu’une caisse est libre, le client en tête de file y est envoyé. Le temps de passage d'un client en caisse est aléatoirement compris entre 3 et 10 minutes.

Un nouveau client entre dans la queue de la file toutes les 1 min.

Réaliser une simulation de leurs passages en caisses et afficher en combien de minutes 10 clients sont passés.
Refaire quelques essais avec un temps d'attente aux caisses plus élevé.

Indications :

La simulation sera une boucle, dont chaque "tour" correspondra à une durée simulée de 1 min.

Pour modéliser la file d'attente, vous utiliserez....une file ( version quelconque ), chaque élément de la file correspondant à un client ( repéré par exemple par un numéro indiquant son ordre d'arrivée dans la file ).

Pour les caisses, vous utiliserez une liste : chaque élément de cette liste représente le temps d'attente à la caisse ( premier élément temps caisse 1, puis temps caisse 2, etc... ces temps variant au cours de la simulation dans les limites indiquées ci-dessus.).

Prolongements possibles :

Afficher la liste des clients passés aux caisses, avec leurs numéros dans l'ordre de leur sortie.

# Votre code ici

SOLUTION