Données File Implémentation

Identification

Infoforall

20 - Implémenter une File 3/3


OPTIONNEL : uniquement pour ceux qui ont été assez rapides.

Dernière petite activité sur l'implémentation des structures linéaires. Nous allons voir comment réaliser une FILE avec simplement un ou deux tableaux statiques.

Cette activité est plutôt rapide : elle sert de conclusion à la longue séquence LISTE-PILE-FILE. Le but est plutôt de revoir le vocabulaire, d'observer l'évolution de la structure de données et de réviser pour le DS que de programmer réellement cette structure.

Prerequis : les activités sur l'implémentation liste chaînée et sur la file.

1 - Une FILE avec un (presque) tableau et un vrai tableau

Nous allons voir comment implémenter une FILE de taille limitée avec

  • Un tableau donnees de taille fixée initialement et qui va servir à stocker les valeurs qu'on place dans la FILE.
  • Un tableau file contenant 5 cases :
    • Index 0 : l'index actuel de la donnée à l'avant
    • Index 1 : l'index actuel de la donnée à l'arrière
    • Index 2 : le nombre de données réellement stockées
    • Index 3 : le nombre de données qu'on peut stocker au maximum
    • Index 4 : la référence du tableau donnees servant à stocker les données
Tableau ?

En réalité, nous ne devrions pas nommer ces structures des tableaux statiques : les "cases" ne contiennent pas toutes le même type de données.

Python gère très bien cela, ce n'est pas le cas de tous les langages ayant un type natif tableau ou array.

Nous allons travailler pour l'exemple sur une PILE ne pouvant contenir que 5 éléments avant d'être pleine.

On travaillera avec les fonctions d'interface suivante permettant de gérer une File mutable :

Version choisie des fonctions d'interface
1 2 3 4 5 6 7 8 9 10 11
nouvelleFile() -> File fileVide(f:File) -> bool enfiler(x:Elt, f:File) -> None lireAvant(f:File) -> Elt defiler(f:File) -> Elt taille(f:File) -> int

01° Suivre le déroulement théorique de ces instructions pour vous familiariser avec la structure. Observez notamment l'évolution des index qui correspondent à AVANT et ARRIERE. On vous présente à chaque fois la fonction utilisée et le contenu théorique dans notre nouvelle structure de données.

>>> file = nouvelleFile() >>> file [None, None, 0, 5, [None, None, None, None, None]] >>> enfiler(10, file) >>> file [0, 0, 1, 5, [10, None, None, None, None]] >>> enfiler(20, file) >>> file [0, 1, 2, 5, [10, 20, None, None, None]] >>> enfiler(30, file) >>> file [0, 2, 3, 5, [10, 20, 30, None, None]] >>> lireAvant(file) 10 >>> file [0, 2, 3, 5, [10, 20, 30, None, None]] >>> defiler(file) 10 >>> file [1, 2, 2, 5, [None, 20, 30, None, None]]

02° Comment évolue la valeur de l'index de l'arrière à chaque fois qu'on enfile un nouvel élément ? Comment évolue la valeur de l'index de l'avant à chaque fois qu'on défile la file ?

...CORRECTION...

On rajoute un dans un cas comme dans l'autre : on décale vers la droite dans le tableau des données.

03° Trouver le contenu de la file après ces deux utilisations de la fonction enfiler.

>>> file [1, 2, 2, 5, [None, 20, 30, None, None]] >>> enfiler(100, file) >>> file ??? >>> enfiler(200, file) >>> file ???

...CORRECTION...

>>> file [1, 2, 2, 5, [None, 20, 30, None, None]] >>> enfiler(100, file) >>> file [1, 3, 3, 5, [None, 20, 30, 100, None]] >>> enfiler(200, file) >>> file [1, 4, 4, 5, [None, 20, 30, 100, 200]]

04° On voit sur le contenu de l'index 1 de la file que l'index de l'arrière correspond à 4, le dernier index dans notre tableau de données.

[1, 4, 4, 5, [None, 20, 30, 100, 200]]

Puisqu'il reste de la place au début du tableau de données, que pourrait-on faire si on tape ceci ?

>>> file [1, 4, 4, 5, [None, 20, 30, 100, 200]] >>> enfiler(1000, file) >>> file

...CORRECTION...

On pourrait revenir au début du tableau :

>>> file [1, 4, 4, 5, [None, 20, 30, 100, 200]] >>> enfiler(1000, file) >>> file [1, 0, 5, 5, [1000, 20, 30, 100, 200]]

05° Qu'est-ce qui permettrait de savoir à partir de là que le tableau des données est plein sans aller voir directement dans le tableau des données lui-même ?

...CORRECTION...

Il suffit de comparer le nombre de données (dans l'index 2 de file). Ici, on trouve qu'il y a 5 données effectivement stockées.

[1, 0, 5, 5, [1000, 20, 30, 100, 200]]

Et on compare ce nombre au nombre de places maximales disponibles, visible dans l'index 3.

[1, 0, 5, 5, [1000, 20, 30, 100, 200]]

Ici, on voit qu'on a 5 données stockées pour 5 données au maximum : on ne peut donc plus rien stocker avant de défiler.

06° Regarder ce code théorique. Donner le contenu attendu sur la dernière ligne.

>>> file [1, 0, 5, 5, [1000, 20, 30, 100, 200]] >>> defiler(file) 20 >>> file [2, 0, 4, 5, [1000, None, 30, 100, 200]] >>> defiler(file) 30 >>> file [3, 0, 3, 5, [1000, None, None, 100, 200]] >>> defiler(file) 100 >>> file ???

...CORRECTION...

[4, 0, 2, 5, [1000, None, None, None, 200]]

07° Pourquoi la valeur d'index de l'avant est-elle passée de 4 à 0 ?

>>> file [4, 0, 2, 5, [1000, None, None, None, 200]] >>> defiler(file) 200 >>> file [0, 0, 1, 5, [1000, None, None, None, None]]

...CORRECTION...

Nous étions arrivés au maximum : 4.

En rajoutant encore 1, il faut revenir à 0 plutôt que d'atteindre un index 5 qui n'existe pas : les index disponibles ici sont 0-1-2-3-4 puisqu'on a 5 valeurs possibles.

Il est temps de joueur un peu avec cette implémentation.

Pour gérer le retour à 0, elle utilise l'opérateur % utilisé comme modulo.

>>> 3 % 5 3 >>> 4 % 5 4 >>> 5 % 5 0

08° Donner le résultat qui devrait s'aficher.

>>> 8 % 10 ??? >>> 9 % 10 ??? >>> 10 % 10 ???

...CORRECTION...

>>> 8 % 10 8 >>> 9 % 10 9 >>> 10 % 10 10

09° Utiliser maintenant le code de cette implémentation pour vérifier qu'elle fonctionne correctement.

Questions

  1. a-t-on en réalité le droit en tant qu'utilisateur d'afficher le contenu de la pile en tapant pile dans la console ?
  2. un utilisateur a-t-il alors la possibilité de connaître la structure de données utilisée pour réaliser l'implémentation du type abstrait FILE ?
  3. Comment se nomme l'ensemble des 5 fonctions nouvelleFile, fileVide, enfiler, defiler et lireAvant ?
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
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 statiques''' def nouvelleFile(taille_max:int=5) -> File: donnees = [None for x in range(taille_max)] return [None, None, 0, taille_max, donnees] # [avant, arriere, taille, taille_max, donnees] def fileVide(f:File) -> bool: assert len(f) == 5 # On vérifie que la taille du tableau est compatible avec nos files assert type(f[2]) == int # On vérifie que l'index 3 contient bien un integer assert type(f[4]) == list # On vérifie que l'index 4 fait bien référence à un tableau return len(f) == 5 and f[2] == 0 def filePleine(f:File) -> bool: assert len(f) == 5 # On vérifie que la taille du tableau est compatible avec nos files assert type(f[2]) == int # On vérifie que l'index 3 contient bien un integer assert type(f[4]) == list # On vérifie que l'index 4 fait bien référence à un tableau return f[2] >= f[3] # Normalement, ça ne peut être que égal, pas supérieur def enfiler(elt:Elt, f:File) -> None : if not filePleine(f) : # On gére les valeurs d'index de l'arrière if fileVide(f) : f[0] = 0 # On gère aussi l'avant car c'est la première valeur placée f[1] = 0 # On définit l'index où inserer la première donnée f[2] = 1 else : f[1] = f[1] + 1 # On incrémente l'index de l'arrière f[1] = f[1] % f[3] # On revient à l'index 0 si on a dépassé l'index max des données f[2] = f[2] + 1 # On augmente la taille # On place la valeur dans les données index_arriere = f[1] # On récupère la valeur d'index où placer l'arrière f[4][index_arriere] = elt # On place la valeur dans les données def defiler(f:File) -> Elt: if not fileVide(f) : index_avant = f[0] # On cherche l'index de l'avant reponse = f[4][index_avant] # On lit et stocke l'avant f[4][index_avant] = None # Optionnel : on supprime vraiment le contenu de la case f[0] = f[0] + 1 # On incrémente l'index de l'avant f[0] = f[0] % f[3] # On revient à l'index 0 si on a dépassé l'index max des données f[2] = f[2] - 1 # On diminue la taille if fileVide(f) : f[0] = None f[1] = None return reponse # On renvoie l'ancienne valeur à l'avant def lireAvant(f:File) -> Elt: if not fileVide(f) : index_avant = f[0] # On cherche l'index de l'avant return f[4][index_avant] # On lit et renvoie l'avant

...CORRECTION...

  1. Non, un utilisateur ne devra pas visualiser ainsi la file. Pour deux raisons : la première est simple : cette instruction ne fait pas partie de l'interface autorisée. Deuxième raison : s'il a besoin de voir l'intérieur de la file, c'est peut-être qu'il s'est trompé de type. Normalement, on ne peut visualiser que l'AVANT d'une FILE. S'il a vraiment besoin de savoir ce que contient sa FILE, c'est qu'il veut en réalité utiliser une LISTE, non ?
  2. L'utilisateur ne pourra donc pas savoir qu'il manipule une structure composée d'un "tableau" dans lequel on a placé le tableau de données.
  3. L'ensemble de ces fonctions se nomme l'INTERFACE. Et les fonctions se nomment les FONCTIONS D'INTERFACE.

10° Estimer le coût de l'enfilement et du défilement dans cette structure.

...CORRECTION...

Si on regarde les codes de ces fonctions, on voit qu'elles ne contiennent pas de boucles, d'appels recursifs ou d'utilisation à des méthodes particulières du type list de Python (comme un pop(0)).

Nous retrouvons un coût CONSTANT pour enfiler et défiler puiqu'on le nombre d'instructions à réaliser ne dépend pas du nombre de données dans la structure.

Par contre, c'est un peu bizarre comme structure : nous avons tendance à ne parler de "tableau" qui si les données contenues sont homogènes. Ce n'est pas rigoureusement le cas ici. Comment faire alors ?

2 - Une File avec un dictionnaire et un tableau

Une manière de faire pourrait être de contourner le problème et d'utiliser par exemple un dictionnaire pour contenir les informations sur la file et de n'utiliser un tableau que pour les données.

Voici un exemple d'utilisation (avec toujours l'observation du contenu de structure uniquement pour que comprendre comment ça fonctionne)

>>> file = nouvelleFile() >>> file {'avant': None, 'arriere': None, 'taille': 0, 'max': 5, 'data': [None, None, None, None, None]} >>> enfiler(10, file) >>> file {'avant': 0, 'arriere': 0, 'taille': 1, 'max': 5, 'data': [10, None, None, None, None]} >>> enfiler(20, file) >>> enfiler(30, file) >>> enfiler(100, file) >>> file {'avant': 0, 'arriere': 3, 'taille': 4, 'max': 5, 'data': [10, 20, 30, 100, None]} >>> defiler(file) 10 >>> file {'avant': 1, 'arriere': 3, 'taille': 3, 'max': 5, 'data': [None, 20, 30, 100, None]}

11° Observer l'implémentation ci-dessous. L'interface obtenue est-elle différente de l'interface habituelle ? A-t-on toujours une file mutable ou a-t-on une file non mutable / immuable ? Peut-on avoir plusieurs implémentations pour une même interface ?

Donner un moyen de distinguer si deux implémentations sont potentiellement différentes en n'utilisant pourtant que les fonctions d'interface lors des interactions avec les données ?

...CORRECTION...

C'est la même interface que précédemment : nous avons les mêmes fonctions dont les prototypes sont exactement les mêmes. Le fait que le code interne change n'a aucune influence sur l'extérieur.

Il s'agit toujours d'une implémentation d'une structure sous-jacante mutable puisque la fonction enfiler ne renvoie rien : elle modifie les données par effet de bord.

On peut bien entendu implémenter un type abstrait via plusieurs structures de données différentes qui donneront pourtant les mêmes choses si les fonctions d'interface restent les mêmes.

Pour voir si deux implémentations sont potentiellement différentes, il faut évaluer le temps d'exécution de certaines opérations et voir comment cela évolue lorsque la taille des données augmente par exemple.

Voici l'implémentation totalement modifié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 41 42 43 44 45 46 47 48 49 50 51 52
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 un dictionnaire et un tableau statique''' def nouvelleFile(taille_max:int=5) -> File: donnees = [None for x in range(taille_max)] return {'avant':None, 'arriere':None, 'taille':0, 'max':taille_max, 'data':donnees} def fileVide(f:File) -> bool: assert type(f) == dict # On vérifie au moins que f est un dictionnaire return f['taille'] == 0 def filePleine(f:File) -> bool: assert type(f) == dict # On vérifie au moins que f est un dictionnaire return f['taille'] >= f['max'] # Normalement, ça ne peut être que égal, pas supérieur def enfiler(elt:Elt, f:File) -> None : if not filePleine(f) : # On gére les valeurs d'index de l'arrière if fileVide(f) : f['avant'] = 0 # On gère aussi l'avant car c'est la première valeur placée f['arriere'] = 0 # On définit l'index où inserer la première donnée f['taille'] = 1 else : f['arriere'] = f['arriere'] + 1 # On incrémente l'index de l'arrière f['arriere'] = f['arriere'] % f['max'] # On revient à l'index 0 si on a dépassé l'index max des données f['taille'] = f['taille'] + 1 # On augmente la taille # On place la valeur dans les données index_arriere = f['arriere'] # On récupère la valeur d'index où placer l'arrière f['data'][index_arriere] = elt # On place la valeur dans les données def defiler(f:File) -> Elt: if not fileVide(f) : index_avant = f['avant'] # On cherche l'index de l'avant reponse = f['data'][index_avant] # On lit et stocke l'avant f['data'][index_avant] = None # Optionnel : on supprime vraiment le contenu de la case f['avant'] = f['avant'] + 1 # On incrémente l'index de l'avant f['avant'] = f['avant'] % f['max'] # On revient à l'index 0 si on a dépassé l'index max des données f['taille'] = f['taille'] - 1 # On diminue la taille if fileVide(f) : f['avant'] = None f['arriere'] = None return reponse # On renvoie l'ancienne valeur à l'avant def lireAvant(f:File) -> Elt: if not fileVide(f) : index_avant = f['avant'] # On cherche l'index de l'avant return f['data'][index_avant] # On lit et renvoie l'avant

12° Observer la nouvelle fonction nouvelleFile. Si on désire partir du code de l'implémentation précédente (celle avec notre tableau qui contient des informations et un tableau de données), par quoi faut-il remplacer les codes suivants pour les rendre compatibles avec notre nouvelle structure de données ?

  • f[0] qui contient l'index de l'avant ?
  • f[1] qui contient l'index de l'arrière ?
  • f[2] qui contient le nombre de valeurs stockées ?
  • f[3] qui contient le nombre maximum d'éléments stockables ?
  • f[4] qui contient le tableau des données stockées ?

...CORRECTION...

Il suffit de remplacer le numéro d'index de la case du tableau par la clé correspondante dans le dictionnaire.

  • f[0] devient f["avant"]
  • f[1] devient f["arriere"]
  • f[2] devient f["taille"]
  • f[3] devient f["max"]
  • f[4] devient f["data"]

3 - Plus condensé encore ?

On pourrait même décider de partir sur un 'tableau' unique qui contiendrait les informations sur la file et les données stockées dans la file.

En réalité, vous pouvez réaliser l'implémentation que vous voulez TANT qu'elle est efficace : l'utilisateur n'y verra que du feu puisqu'il n'a accès qu'à l'interface.

Imaginons la situation suivante : on profite du type list de Python qui permet de gérer des tableaux (dynamiques) non homogènes.

On crée un tableau possèdant x + 4 cases.

  • Index 0 : l'index de l'avant
  • Index 1 : l'index de l'arrière
  • Index 2 : le nombre de données stockées
  • Index 3 : le nombre maximum de données stockées
  • Index 4 : la première donnée stockée (ancien index 0 du tableau de données)
  • Index 5 : la deuxième donnée (ancien index 1...)
  • ...
  • Index x+3 : la dernière case de données. L'ancien index x-1 du tableau de données.

Cela donnera cela (n'oubliez pas que l'utilisateur n'aurait pas la possibilité de voir le contenu de toute la file)

>>> file = nouvelleFile() >>> file [None, None, 0, 5, None, None, None, None, None] >>> file = enfiler(100, f) >>> file = enfiler(100, file) >>> file [4, 4, 1, 5, 100, None, None, None, None] >>> file = enfiler(200, file) >>> file = enfiler(300, file) >>> file [4, 6, 3, 5, 100, 200, 300, None, None] >>> file = defiler(file) >>> file [5, 6, 2, 5, None, 200, 300, None, None] >>> file = defiler(file) >>> file [6, 6, 1, 5, None, None, 300, None, None] >>> file = enfiler(400, file) >>> file = enfiler(500, file) >>> file [6, 8, 3, 5, None, None, 300, 400, 500] >>> file = enfiler(600, file) >>> file [6, 4, 4, 5, 600, None, 300, 400, 500] >>> file = defiler(file) >>> file [7, 4, 3, 5, 600, None, None, 400, 500]

13° Dire s'il s'agit d'une structure de données mutable/muable ou non mutable/immuable. Justifiez votre réponse à partir des instructions visibles ci-dessus.

...CORRECTION...

Dans la mesure où nous sommes obligés à chaque fois d'utiliser une nouvelle affectation pour stocker le résultat renvoyé par les fonctions d'interface, on peut comprendre sans problème qu'il s'agit à priori d'une version non mutable.

14° Dire (et justifier à l'aide des répondes visibles) s'il s'agit d'une structure respectant l'idée générale FIFO ou LIFO.

...CORRECTION...

On voit qu'on supprime toujours d'abord l'élément le plus ancien de la séquence.

Il s'agit donc de FIFO : First In First Out.

15° Regarder le code implémentant cette proposition. Comment se fait-il qu'il s'agisse d'une version non mutable ? Peut-on la transformer facilement en version mutable ?

...CORRECTION...

On voit que les fonctions d'enfilement et défilement créent une copie de file de base, modifie la copie et renvoie la copie.

Dans la mesure où le type list est mutable en Python, on pourrait très facilement revenir à une version mutable : il suffit de travailler directement sur le tableau recu en paramètre. Plus besoin de le renvoyer dans ce cas : le tableau est directement modifié par effet de bord.

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
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 un "tableau" unique''' def nouvelleFile(taille_max:int=5) -> File: file = [None for x in range(taille_max+4)] file[2] = 0 file[3] = taille_max return file def fileVide(f:File) -> bool: return f[2] == 0 def filePleine(f:File) -> bool: return f[2] >= f[3] # Normalement, ça ne peut être que égal, pas supérieur def enfiler(elt:Elt, fo:File) -> File : if not filePleine(fo) : f = [valeur for valeur in fo] # On crée une copie # On gére les valeurs d'index de l'arrière if fileVide(f) : f[0] = 4 # On gère aussi l'avant car c'est la première valeur placée f[1] = 4 # On définit l'index où inserer la première donnée f[2] = 1 else : f[1] = f[1] + 1 # On incrémente l'index de l'arrière f[1] = (f[1]-4) % f[3] + 4 # On revient à l'index 0 si on a dépassé l'index max des données f[2] = f[2] + 1 # On augmente la taille # On place la valeur dans les données index_arriere = f[1] # On récupère la valeur d'index où placer l'arrière f[index_arriere] = elt # On place la valeur dans les données return f def defiler(fo:File) -> File: if not fileVide(fo) : f = [valeur for valeur in fo] # création d'une copie index_avant = f[0] # On cherche l'index de l'avant f[index_avant] = None # Optionnel : on supprime vraiment le contenu de la case f[0] = f[0] + 1 # On incrémente l'index de l'avant f[0] = (f[0]-4) % f[3] + 4 # On revient à l'index 0 si on a dépassé l'index max des données f[2] = f[2] - 1 # On diminue la taille if fileVide(f) : f[0] = None f[1] = None return f # On renvoie le nouveau tableau def lireAvant(f:File) -> Elt: if not fileVide(f) : index_avant = f[0] # On cherche l'index de l'avant return f[index_avant] # On lit et renvoie l'avant

16° Regarder le code implémentant cette proposition. Que pouvez-vous dire de sa clarté par rapport aux versions précédentes (en mettant de côté l'histoire des copies de tableau) ?

...CORRECTION...

La structure simple n'a pas nécessairement créer un code simple et plus clair que les structures précédentes. Cette version à priori plus simple demande en réalité plus de travail de compréhension lors de la lecture du code.

4 - FAQ

Rien pour l'instant

C'est la fin de la partie sur les données linéaires et ordonnées.

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