La file

Cours/Algorithmie/Structure de pile et file/La file

La file est la structure de donnée idéale pour gérer un flux de donnée dont on doit conserver l'ordre. On appelle également cette structure FIFO pour first in, first out : on rend toujours la donnée la plus anciennement stockée. La structure d'une file d'entiers sera alors :

structure Pile<T>:
    longueur: entier
    capacité: entier
        
    #  autres attributs

méthode (f: File<T>) enfile(donnée: T) → ∅  # push
méthode (f: File<T>) défile() → T           # pop

La taille de la file doit être déterminée à la création. Comme la pile, son implémentation nécessitera d'autres attributs.

À retenir

Une file est un buffer permettant de découpler l'arrivée du traitement de données temporelles.

Implémentation

On va utiliser 2 indices pour parcourir le tableau de stockage des données :

un indice fin permettant de savoir où ajouter le prochain élément
un indice début permettant de savoir quel prochain élément rendre

Ces deux indices coïncidaient avec la longueur pour la pile.

structure File<T>:
    longueur: entier
    capacité: entier

    (données: [T]) ← [T]{longueur: capacité}
    début: entier ← capacité - 1
    fin: entier ← 0

méthode (f: File<T>) enfile(donnée: T) → ∅:
    f.données[f.fin] ← donnée
    f.fin ← (f.fin + 1) % f.capacité

    f.longueur ← f.longueur + 1

méthode (f: File<T>) défile() → T:
    f.longueur ← f.longueur - 1
    f.début ← (f.début + 1) % f.capacité
    rendre f.données[f.début]

On voit facilement que :

Proposition

Les complexités de toutes les méthodes de la structure File sont en $\mathcal{O}(1)$.

Utiliser une file peut se voire comme une opération élémentaire.

Prenons un exemple de file d'entiers pour comprendre comment cette implémentation fonctionne :

Départ :

          fin
          |  début
          v  v  
données : 0123

Ajout d'un élément 1 :

           fin
           | début
           v v  
données : 0123
          1

Ajout d'un élément 2 :

            fin
            |début
            vv  
données : 0123
          12

On défile un élément (1) :

            fin
      début |
          v v  
données : 0123
          12

Notez que l'élément dépilé n'est pas effacé, on ne peut juste plus l'atteindre. Cette implémentation permet une gestion circulaire des données.

Prolongez l'exemple précédent en enfilant successivement 3, 4, et 5 puis en défilant tous les élément de la file. Quel est l'état des indices après ces opérations ?

corrigé

Pour comprendre le fonctionnement, on va visuellement supprimer les éléments de la file et ne représenter que les données effectivement conserver (ce n'est pas le cas dans l'implémentation réelle)

État initial :

            fin
      début |
          v v  
données : 0123
           2

Enfile 3 :

             fin
      début  |
          v  v  
données : 0123
           23

Enfile 4 :

        fin
      début  
          v    
données : 0123
           234

Enfile 5 :

         fin
      début| 
          vv   
données : 0123
          5234

Défile (2) :

         fin
       début 
           v   
données : 0123
          5 34

Défile (3) :

         fin
           |début 
           vv   
données : 0123
          5  4

Défile (4) :

         fin
           | début 
           v v   
données : 0123
          5

Défile (5) :

         fin
      début|  
          vv    
données : 0123

Début et fin sont décalé de 1 par rapport à la construction de la structure.

Exemples

Exemple : un buffer

Cet exemple montre l'usage classique d'une file. On traite de façon différée les entrées et les sorties dans l'ordre d'arrivée en stockant les données dans une file.

(buffer := File<entier>) ← File<entier>{capacité: n}

fonction écrire(donnée: entier) → ∅:
    buffer.enfile(donnée)

fonction lire() → entier:
    rendre buffer.défile()

Ceci ce passe constamment lorsque l'on lit une vidéo, télécharge un fichier, etc.

La principale problématique est alors, quelle taille de file choisir pour ne pas perdre des données ?

Si la fréquence de lecture est inférieure à la fréquence d'écriture, pas de soucis. La taille de la file peut être de 1 entier : entre 2 écritures, on aura au moins une lecture.

Mais si la fréquence d'écriture est supérieure à la fréquence de lecture, il faut calculer la profondeur de file permettant de stocker la différence entre le temps d'écriture (qui remplit la file) et de lecture (qui la vide).

Ainsi si :

$f_e$ est la fréquence d'écriture
$f_l$ est la fréquence de lecture
$K$ est le nombre d'entiers à transférer

On aura écrit les $K$ entiers en $K/f_e$ secondes. Pendant ce temps à on aura uniquement lu $K/f_e \cdot f_l$ données. La taille $F$ de la file minimale est donc de la différence :

$$ F = K - K\cdot \frac{f_l}{f_e} = K(1-\frac{f_l}{f_e}) $$

Dans les cas réels, les données sont envoyés par burst continu de $K$ entiers, puis des pauses permettant de lire la fin des données et de vider la file. Ceci permet d'avoir des tailles de buffer raisonnable même si la différence de lecture et d'écriture est grande.

Taille de la file selon le problème de transfert

Exemple : création des entiers binaires

On peut aussi utiliser la file comme outil d'énumération. Par exemple pour faire un compteur :

algorithme compteur(n: entier) → ∅:
    F ← File<chaîne> {capacité: K}
    F.enfile("1")
    (i:= entier) ← 1

    c := chaîne 
    répéter n fois:
        c ← F.défile()
        afficher à l'écran c
        si i < n:               # limite la taille de la file
            F.enfile(c + "0")
            F.enfile(c + "1")
            i ← i + 2

L'algorithme va afficher les $n$ premiers entiers sous forme binaire. Il dépend d'une file de taille $K$.

Montrer que pour l'algorithme précédent fonctionne, il faut une file de taille au moins $\frac{n}{2}$.

corrigé

Lorsque l'on crée le $n$ème élément que l'on place dans la file, on le crée avec la chaîne de caractères $n_0\dots n_k$ que l'on vient de sortir de la file.

Le $n$ nombre est alors de la forme $n_0\dots n_k0$ ou $n_0\dots n_k1$. Supposons sans perte de généralité que c'est $n_0\dots,n_k0$.

Comme on vient de sortir $n_0\dots n_k = n/2$ de la file et qu'on y a placé $n_0\dots n_k0 = n$, il y a bien $n/2$ élément dans la file.