Données File Implémentation

Identification

Infoforall

19 - Implémenter une File 2/3


Dans l'activité précédente, nous avons vu deux façons d'implémenter les files :

  • Avec un tableau dynamique Python : peu concluant car si l'insertion à l'arrière est à temps (presque) constant avec append(), la suppression de l'avant avec pop(0) est elle à coût linéaire : il faut décaler le 1 vers le 0, le 2 vers le 1...
  • Avec deux piles : c'est mieux. L'insertion à l'Arrière est à coût constant et la suppression de l'Avant aussi parfois. Pourquoi parfois ? Car si la pile de sortie est vide, il faut déverser l'intégralité de la pile d'entrée dans la pile de sortie. Nous sommes donc à coût constant la plupart du temps et à coût linéaire parfois.

Nous allons voir plusieurs implémentations plus efficaces car à coût constant à l'insertion et à la suppression.

  1. des implémentations avec une liste chaînée (ici même)
    • sous forme d'objets
    • sous de tableaux
  2. une implémentation avec deux tableaux (dans l'activité suivante)
  3. une implémentation en tableau unique (dans l'activité suivante)

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

1 - File implémentée par une Liste Chaînée de type objet

Nous avions déjà réalisé une implémentation de liste chaînée en utilisant deux classes :

  • Une classe Cellule qui permet de stocker la valeur ainsi que la référence de la Cellule suivante dans la liste
  • Une classe Liste qui permet de stocker la référence de la tete de la liste et la référence de la derniere cellule

Le code était assez complexe car nous voulions pouvoir insérer, supprimer et lire n'importe où et pouvoir concaténer deux listes.

Avec une FILE, le problème est beaucoup plus simple :

  1. On ne peut enfiler/insérer qu'à l'ARRIERE (la dernière Cellule de la structure)
  2. On ne peut lire que l'AVANT (la première Cellule, la tête pour une liste)
  3. On ne peut défiler/supprimer que l'AVANT

Du coup, nous obtenons un code d'implémentation beaucoup beaucoup plus simple que celui de la Liste en version liste chaînée : il y a moins de cas à gérer.

Voici les prototypes des fonctions d'interface :

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° En regardant simplement les prototypes, donner la proposition correcte parmi les deux propositions ci-dessous :

Pour modifier le contenu d'une file nommée donnees, il faut :

  1. Utiliser donnees = enfiler(42, donnees) car on utilise visiblement un type non mutable ou immuable
  2. Utiliser enfiler(42, donnees) car on utilise visiblement un type mutable ou muable

...CORRECTION...

Nous voyons que la fonction enfiler ne renvoie pas une nouvelle File. Notre structure de donnée est donc de type mutable.

Il suffit donc d'utiliser enfiler(42, donnees).

Regardons maintenant le code de l'implémentation proposée. Commençons par la classe Cellule. Il s'agit d'un objet assez simple qui possède :

  • Un attribut v permettant de stocker la valeur
  • Un attribut s permetant de stocker la référence de la cellule suivante
  • Une méthode récursive renvoyerCelluleFinale qui permet de trouver la cellule finale d'une série de cellules.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
'''Implémentation de la file sous forme d'une liste chaînée''' # Déclaration des Classes Cellule et File class Elt : '''Juste pour pouvoir noter Elt dans les déclarations des fonctions''' class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale()

Notre FILE va être constituée d'un objet encore plus simple :

21 22 23 24 25 26 27
class File : '''Classe implémentant une Liste sous forme Liste chaînée ''' def __init__(self) : self.avant = None self.arriere = None self.nombre = 0

Comme vous pouvez le voir, les instances de cette classe ne possèdent que 3 attributs

  • Un attribut avant qui va contenir la référence de la cellule caractérisant l'avant de la file
  • Un attribut arriere qui va contenir la référence de la cellule caractérisant l'arrière de la file
  • Un attribut nombre qui va contenir le nombre de cellules composant notre FILE (peut être utile dans certaines applications où on veut limiter le nombre d'entités dans la FILE)

Passons à l'étude des 5 fonctions d'interface. Comme à chaque fois, regardons d'abord comment créer une file vide et tester si une file est vide.

41 42 43 44 45 46 47
# Fonctions d'interface de la FILE def nouvelleFile() -> File : return File() def fileVide(f:File) -> bool : return f.avant == None

02° Qu'est-ce qui caractérise une FILE vide dans cette implémentation ?

...CORRECTION...

Une FILE est considérée comme vide si il s'agit d'une instance de File dont l'attribut avant ne renvoie vers rien.

Etudions le coût de l'insertion d'une valeur à l'arrière de la file. On envoie la valeur à insérer ainsi que la référence de la File. La fonction enfiler va simplement devoir créer une nouvelle instance de Cellule et la définir comme nouvelle cellule arrière.

Deux cas de figures apparaissent :

  • Si on enfile une nouvelle Cellule dans une FILE vide : AVANT et ARRIERE doivent faire référence à la même Cellule
  • Insertion dans une file vide : Arriere et Avant pointe la même Cellule
  • Si on enfile une nouvelle Cellule dans une FILE non vide : il suffit de changer la référence de créer la nouvelle Cellule et d'y mener l'ancienne Cellule Arrière vers celle-ci. Il faudra bien entendu modifier l'attribut arriere de la file pour qu'elle désigne bien la nouvelle Cellule Arrière.
  • Par exemple : on enfile maintenant 10 :

    Insertion de 10 dans la file contenant 42

    Si on enfile maintenant 50 :

    Insertion de 50 dans la file contenant 10 à l'arrière

03° Dans la fonction enfiler proposée,

  1. sur quelles lignes gère-t-on le cas de l'insertion dans une file vide ;?
  2. sur quelle ligne crée-t-on la nouvelle liaison entre la nouvelle Cellule Arrière et l'ancienne Cellule Arrière ?
  3. sur quelle ligne définit-on la nouvelle Cellule comme étant l'arrière de notre file ?
  4. Quel est le coût d'un enfilement dans cette implémentation ?
49 50 51 52 53 54 55 56 57 58 59 60
def enfiler(x:Elt, f:File) -> None : '''On insére la nouvelle valeur à l'arrière''' if fileVide(f) : # C'est vide : Avant et Arrière sont la même Cellule cellule = Cellule(x, None) f.avant = cellule f.arriere = cellule f.nombre = 1 else : # Il y a déja une cellule Arrière : on lui rajoute une suite cellule = Cellule(x, None) f.arriere.s = cellule # on rajoute la cellule à la suite de l'actuelle arrière f.arriere = cellule # on déclare la nouvelle cellule comme l'arrière f.nombre = f.nombre + 1

...CORRECTION...

On gère la file vide sur les lignes 52 à 55.

On rajoute la liaison entre l'ancienne Arrière et la nouvelle sur la ligne 58.

On modifie ensuite ligne 59 la référence vers laquelle pointe l'arrière de la file.

Quelque soit le nombre de Cellules déjà présentes dans la file, le rajout d'une nouvelle Cellule à l'arrière consiste juste à créer une nouvelle Cellule et à modifier un attribut s et l'attribut arriere : le coût est donc CONSTANT.

La fonction defiler est alos assez facile à réaliser : il suffit de récupérer la cellule située à l'avant et de faire pointer l'attribut avant de la liste vers le suivant.

Défiler la liste chaînée

On voit donc que c'est encore plus simple que l'enfilement : il suffit de faire pointer l'attribut avant vers la cellule suivante. On notera que dans la version proposée, on a décidé de renvoyer la valeur "supprimée" (42 ici).

04° Dans la fonction defiler proposée,

  1. sur quelle ligne mémorise-t-on la valeur de la cellule qu'on va supprimer ;?
  2. sur quelle ligne renvoie-t-on cette valeur ?
  3. sur quelle ligne modifie-t-on l'attribut avant de notre liste ?
  4. Quel est le coût d'un défilement dans cette implémentation ?
66 67 68 69 70 71 72 73
def defiler(f:File) -> Elt : if not fileVide(f) : reponse = f.avant.v # on mémorise l'ancienne valeur à l'avant f.avant = f.avant.s # la nouvelle Cellule avant est le successeur de la précédente if f.avant == None : # si l'avant n'existe pas en réalité f.arriere = None f.nombre = f.nombre - 1 return reponse # on renvoie la valeur supprimée

...CORRECTION...

On mémorise la valeur supprimée sur la ligne 68 en allant voir la valeur de l'attribut v de l'avant actuel.

On la renvoie en ligne 73 si la file n'était pas vide. Sinon, on renvoie donc None.

Ligne 69, on va lire la référence de la Cellule qui suit l'avant. On la définit alors comme la nouvelle Cellule Avant.

Aucune boucle ou appel récursif à priori. Le coût de cette opération est donc bien un coût CONSTANT.

05° Quelqu'un trouve que c'est bizarre de travailler dans ce sens : il trouve qu'il serait plus logique que l'Avant soit la Cellule de fin, comme dans une vraie file d'attente.

Insertion de 50 dans la file contenant 10 à l'arrière

Quel serait le coût de l'insertion d'une Cellule Arrière (enfilement) dans ce cas ?

Quel serait le coût de la suppression d'une Cellule Avant (défilement) dans ce cas ?

Conclusion : est-il pertinent de tenter d'implémenter un type abstrait en suivant au plus près l'idée naturelle qu'on s'en fait en tant qu'humain ?

...CORRECTION...

L'enfilement ne posera pas de probème : on peut facilement trouver la référence de la Cellule Arrière. Il suffit de créer une nouvelle Cellule et de la faire pointer vers l'ancienne Arrière. On modifie ensuite l'attribut arriere de la liste.

On aura toujours un coût CONSTANT.

Le problème vient de la suppresion de l'AVANT : il faudrait juste faire pointer l'attribut avant vers la Cellule qui se situe juste devant le 42.

Le problème ? Elle n'est pas stockée et on ne peut pas remonter en arrière dans une liste simplement chaînée !

Il va donc falloir partir de Arrière et remonter la file de Cellule en Cellule.

Bref, l'enfilement va avoir un coût LINEAIRE.

Moralité : il faut bien réfléchir avant d'utiliser une implémentation plutôt qu'une autre : alors que les deux façons de faire peuvent paraître identiques, elles peuvent se révéler différentes en termes de coûts.

Au final, il ne reste qu'à voir la fonction lireAvant et la fonction optionnelle taille qui permet de récupérer le nombre d'éléments présents dans la File.

Rien de complexe :

62 63 64
def lireAvant(f:File) -> Elt : if not fileVide(f) : return f.avant.v
75 76
def taille(f:File) -> int : return f.nombre

Passons à son utilisation. Vous trouverez le code total sous la question 06.

Il intègre les 6 fonctions d'interface et une fonction hors interface permettant d'obtenir une représentation de la File sous forme d'un tuple (pourquoi pas ?):

1 2 3 4 5 6 7 8
nouvelleFile() -> File fileVide(f:File) -> bool enfiler(x:Elt, f:File) -> None lireAvant(f:File) -> Elt defiler(f:File) -> Elt taille(f:File) -> int afficherFile(f:File) -> tuple

06° Placer le code ci-dessous en mémoire pour utiliser la console interactive pour les utiliser. Par exemple :

>>> f = nouvelleFile() >>> enfiler("Bonjour", f) >>> afficherFile(f) ('Bonjour',) >>> enfiler("à", f) >>> enfiler("tous", f) >>>enfiler("!", f) >>> afficherFile(f) ('Bonjour', 'à', 'tous', '!') >>> taille(f) 4 >>> defiler(f) 'Bonjour' >>> afficherFile(f) ('à', 'tous', '!') >>> lireAvant(f) 'à' >>> afficherFile(f) ('à', 'tous', '!') >>> taille(f) 3

Le code de l'implémentation :

Implémentation du type FILE sous forme d'une liste chaînée implémentée comme un objet
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 70 71 72 73 74 75 76
'''Implémentation de la file sous forme d'une liste chaînée''' # Déclaration des Classes Cellule et File class Elt : '''Juste pour pouvoir noter Elt dans les déclarations des fonctions''' class Cellule : '''Classe permettant de créer des cellules-maillons basiques''' def __init__(self, valeur, suivant) : assert isinstance(suivant, Cellule) or suivant == None self.v = valeur self.s = suivant def renvoyerCelluleFinale(self) : if self.s == None : return self else : return self.s.renvoyerCelluleFinale() class File : '''Classe implémentant une Liste sous forme Liste chaînée ''' def __init__(self) : self.avant = None self.arriere = None self.nombre = 0 # Fonction d'observation qui n'a rien à faire dans l'interface d'une File ! def afficherFile(f) : '''Fonction debug, ce n'est pas une fonction d'interface. Affiche Avant -> Arrière''' tableau = recupererValeur(f.avant) return tuple(tableau) def recupererValeur(cellule) : if cellule.s == None : return [cellule.v] else : return [cellule.v] + recupererValeur(cellule.s) # Fonctions d'interface de la FILE def nouvelleFile() -> File : return File() def fileVide(f:File) -> bool : return f.avant == None def enfiler(x:Elt, f:File) -> None : '''On insére la nouvelle valeur à l'arrière''' if fileVide(f) : # C'est vide : Avant et Arrière sont la même Cellule cellule = Cellule(x, None) f.avant = cellule f.arriere = cellule f.nombre = 1 else : # Il y a déja une cellule Arrière : on lui rajoute une suite cellule = Cellule(x, None) f.arriere.s = cellule # on rajoute la cellule à la suite de l'actuelle arrière f.arriere = cellule # on déclare la nouvelle cellule comme l'arrière f.nombre = f.nombre + 1 def lireAvant(f:File) -> Elt : if not fileVide(f) : return f.avant.v def defiler(f:File) -> Elt : if not fileVide(f) : reponse = f.avant.v # on mémorise l'ancienne valeur à l'avant f.avant = f.avant.s # la nouvelle Cellule avant est le successeur de la précédente if f.avant == None : # si l'avant n'existe pas en réalité f.arriere = None f.nombre = f.nombre - 1 return reponse # on renvoie la valeur supprimée def taille(f:File) -> int : return f.nombre

2 - Implémentation en liste chaînée de tableaux

Question : est-on obligé d'utiliser des objets pour faire des listes chaînées ?

Réponse : non.

Voilà, c'est fini :o)

Si cette réponse lapidaire ne vous suffit pas, voyons comment on peut faire.

Il suffit de garder le même esprit (à savoir stocker la référence du suivant) mais d'utilser de simples tableaux.

Un Cellule pourrait ainsi être un tableau de 2 cases stockant la valeur et la référence de la Cellule-tableau suivante : [valeur, suivante]

Notre Liste est elle un tableau contenant 3 cases qui contiennent l'adresse du tableau avant, l'adresse du tableau arriere et le nombre des valeurs dans notre File. [avant, arriere, nombre]

On retrouve donc exactement la même chose qu'avec les objets !

Commençons par les deux fonctions nouvelleFile et fileVide.

1 2 3 4 5
def nouvelleFile() -> File : return [None, None, 0] # [avant, arriere, nombre] def fileVide(f:File) -> bool : return f == [None, None, 0] # [avant, arriere, nombre]

Comme vous le voyez, il suffit d'envoyer ou de tester le tableau correspondant à une file vide, à savoir : pas d'avant, ni d'arrière et une taille de 0.

Voici maintenant le code qui est en réalité un copier/coller de celui sur les objets (à part les deux fonctions précédentes). Vous allez devoir modifier les fonctions pour les rendre compatibles avec notre nouvelle implémentation. L'utilisateur lui n'y verra que du feu.

07° Copier/coller l'intégralité du code ci-dessous dans votre éditeur de code. Modifier ensuite les deux fonctions lireAvant et taille pour qu'elles fonctionnent avec notre nouvelle implémentation qui utilise un tableau pour la Liste et un tableau pour la Cellule, plutôt que des instances de Classe.

...CORRECTION...

1 2 3 4 5 6
def lireAvant(f:File) -> Elt : if not fileVide(f) : return f[0][0] def taille(f:File) -> int : return f[2]
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
'''Implémentation de la file sous forme d'une liste chaînée''' # Déclaration des Classes Cellule et File class Elt : '''Juste pour pouvoir noter Elt dans les déclarations des fonctions''' class Cellule : '''Un tableau de 2 cases : juste pour pouvoir noter Cellule dans les déclarations des fonctions''' class File : '''Un tableau de 3 cases : juste pour pouvoir noter File dans les déclarations des fonctions''' # Fonction d'observation qui n'a rien à faire dans l'interface d'une File ! def afficherFile(f) : '''Fonction debug, ce n'est pas une fonction d'interface. Affiche Avant -> Arrière''' tableau = recupererValeur(f[0]) return tuple(tableau) def recupererValeur(cellule) : if cellule[1] == None : return [cellule[0]] else : return [cellule[0]] + recupererValeur(cellule[1]) # Fonctions d'interface de la FILE def nouvelleFile() -> File : return [None, None, 0] # [avant, arriere, nombre] def fileVide(f:File) -> bool : return f == [None, None, 0] # [avant, arriere, nombre] def enfiler(x:Elt, f:File) -> None : # A MODIFIER '''On insére la nouvelle valeur à l'arrière''' if fileVide(f) : # C'est vide : Avant et Arrière sont la même Cellule cellule = Cellule(x, None) f.avant = cellule f.arriere = cellule f.nombre = 1 else : # Il y a déja une cellule Arrière : on lui rajoute une suite cellule = Cellule(x, None) f.arriere.s = cellule # on rajoute la cellule à la suite de l'actuelle arrière f.arriere = cellule # on déclare la nouvelle cellule comme l'arrière f.nombre = f.nombre + 1 def lireAvant(f:File) -> Elt : # A MODIFIER if not fileVide(f) : return f.avant.v def defiler(f:File) -> Elt : # A MODIFER if not fileVide(f) : reponse = f.avant.v # on mémorise l'ancienne valeur à l'avant f.avant = f.avant.s # la nouvelle Cellule avant est le successeur de la précédente if f.avant == None : # si l'avant n'existe pas en réalité f.arriere = None f.nombre = f.nombre - 1 return reponse # on renvoie la valeur supprimée def taille(f:File) -> int : # A MODIFIER return f.nombre

Comme vous le voyez, il suffit d'adapter le code est de "traduire" le sens des instructions précédentes sur la version Objet en fournissant les bons indices dans les tableaux imbriqués.

08° Modifier les autres fonctions d'interface pour obtenir au final une version totalement fonctionnelle.

Si vous bloquez, la solution complète se trouve ci-dessous.

Module Typing

Depuis Python 3.8 (je crois), on peut utiliser un module nommé typing qui permet de typer les paramètres et le retour sans passer par de "fausses" classes.

Si vous voulez en savoir plus, allez voir dals la documentation de Python. Dans le cadre de ces cours, son utilisation est purement cosmétique de toutes façons.

Voici la version finalisée de notre nouvelle implémentation de liste chaînée. Comme vous le voyez, nous sommes parvenus au final à récréer de la POO sans passer par les objets. Même dans les langages qui ne possèdent pas de structures de données CLASSE, on peut parvenir à implémenter des objets. C'est juste long... Et l'avantage de la POO est la syntaxe particulière objet.attribut ou objet.methdoe qui permet de créer des codes plus clairs que celui-ci avec des indices de partout !

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
'''Implémentation de la file sous forme d'une liste chaînée''' # Déclaration des Classes Cellule et File class Elt : '''Juste pour pouvoir noter Elt dans les déclarations des fonctions''' class Cellule : '''Un tableau de 2 cases : juste pour pouvoir noter Cellule dans les déclarations des fonctions''' class File : '''Un tableau de 3 cases : juste pour pouvoir noter File dans les déclarations des fonctions''' # Fonction d'observation qui n'a rien à faire dans l'interface d'une File ! def afficherFile(f) : '''Fonction debug, ce n'est pas une fonction d'interface. Affiche Avant -> Arrière''' tableau = recupererValeur(f[0]) return tuple(tableau) def recupererValeur(cellule) : if cellule[1] == None : return [cellule[0]] else : return [cellule[0]] + recupererValeur(cellule[1]) # Fonctions d'interface de la FILE def nouvelleFile() -> File : return [None, None, 0] # [avant, arriere, nombre] def fileVide(f:File) -> bool : return f == [None, None, 0] # [avant, arriere, nombre] def enfiler(x:Elt, f:File) -> None : '''On insére la nouvelle valeur à l'arrière''' if fileVide(f) : # C'est vide : Avant et Arrière sont la même Cellule cellule = [x, None] # une cellule est [valeur, suivant] f[0] = cellule f[1] = cellule f[2] = 1 else : # Il y a déja une cellule Arrière : on lui rajoute une suite cellule = [x, None] # une cellule est [valeur, suivant] f[1][1] = cellule # on rajoute la cellule à la suite de l'actuelle arrière f[1] = cellule # on déclare la nouvelle cellule comme l'arrière f[2] = f[2] + 1 def lireAvant(f:File) -> Elt : if not fileVide(f) : return f[0][0] def defiler(f:File) -> Elt : if not fileVide(f) : reponse = f[0][0] # on mémorise l'ancienne valeur à l'avant f[0] = f[0][1] # la nouvelle Cellule avant est le successeur de la précédente if f[0] == None : # si l'avant n'existe pas en réalité f[1] = None f[2] = f[2] - 1 return reponse # on renvoie la valeur supprimée def taille(f:File) -> int : return f[2]

09° Placer le code ci-dessus en mémoire pour utiliser la console interactive pour les utiliser. Par exemple :

>>> f = nouvelleFile() >>> enfiler("Bonjour", f) >>> afficherFile(f) ('Bonjour',) >>> enfiler("à", f) >>> enfiler("tous", f) >>>enfiler("!", f) >>> afficherFile(f) ('Bonjour', 'à', 'tous', '!') >>> taille(f) 4 >>> defiler(f) 'Bonjour' >>> afficherFile(f) ('à', 'tous', '!') >>> lireAvant(f) 'à' >>> afficherFile(f) ('à', 'tous', '!') >>> taille(f) 3

Conclusion : un utilisateur limité aux fonctions d'interface peut-il connaître l'implémentation réelles du type de données qu'il pense utiliser ?

10° Quel est le coût d'un enfilement dans le pire des cas ? Quel est le coût d'un défilement dans le pire des cas ?

Du coup, comment pourrait-on quand même avoir une petite idée de l'implémentation interne d'un type abstrait ? Par exemple : comment pourrait-on distinguer une implémentation en liste chaînée et une implémentation via un simple tableau avec un beau pop(0) supposé linéaire ?

...CORRECTION...

On garde un temps CONSTANT en enfilement et en défilement puisqu'on effectue un nombre d'actions qui ne dépendent pas de la taille de la file.

Il faut comparer le temps qu'on met pour défiler par exemple dans une file de 50 éléments et dans une file de 500 000 éléments.

Si on trouve des durées sensiblement égales, nous avons un défilement constant. Donc pourquoi pas une implémentation en listes chaînées.

Si le temps d'exécution est multiplié par 10000 (500000/50), nous n'avons à priori pas une liste chaînée sous le capot.

3 - Comparaison expérimentale

A titre d'exemple, voici un programme permettant de comparer le défilement d'une petite file et d'une grande file.

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
if __name__ == '__main__' : # Importation des modules import time import random t1 = 0 t2 = 0 for etape in range(100) : print(f"Calculs pour étape valant {etape}") # Création de grandes files nombres = [random.randint(1,100) for x in range(100000)] file1 = nouvelleFile() for valeur in nombres : enfiler(valeur, file1) t0 = time.time() defiler(file1) t1 = t1 + time.time() - t0 nombres = [random.randint(1,100) for x in range(1000)] # Création des petites files file2 = nouvelleFile() for valeur in nombres : enfiler(valeur, file2) t0 = time.time() defiler(file2) t2 = t2 + time.time() - t0 print(f"Temps moyen de défilement sur la grande file : {t1/100}") print(f"Temps moyen de défilement sur la petite file : {t2/100}")

Voici un exemple de réponses avec l'implémentation liste chaînée (via des tableaux) :

Temps moyen de défilement sur la grande file : 4.682540893554688e-06 Temps moyen de défilement sur la petite file : 2.5415420532226563e-06

On voit qu'en multipliant les données par 100, on obtient deux fois plus de temps. Nous sommes bien en quasi-linéaire.

Voici un exemple de réponses avec l'implémentation liste chaînée (via des objets) :

Temps moyen de défilement sur la grande file : 6.518363952636719e-06 Temps moyen de défilement sur la petite file : 3.4737586975097657e-06

Idem.

Voici la version de la File composé de deux files avec un lecture unique (et donc le dépilement de la pile d'entrée dans la pile de sortie)

Temps moyen de défilement sur la grande file : 0.11710217475891113 Temps moyen de défilement sur la petite file : 0.001174468994140625

Ici, on voit très bien le facteur 100.

Regardons ce que donne cette implémentation sur la deuxième lecture (sans nécessité de dépiler la pile d'entrée dans la pile de sortie)

Temps moyen de défilement sur la grande file : 5.934238433837891e-06 Temps moyen de défilement sur la petite file : 3.3259391784667967e-06

Et enfin, la version "naïve", celle dans un simple tableau avec un pop(0) servant à défiler :

Temps moyen de défilement sur la grande file : 6.56437873840332e-05 Temps moyen de défilement sur la petite file : 1.6617774963378906e-06

On trouve un facteur 40. Presque 100. Cela vient du fait que les lists-Python optimisent pas mal les choses. Néanmoins, nous ne sommes clairement pas à coîu constant.

4 - FAQ

Rien pour l'instant

La dernière activité vous montrera qu'on peut réaliser également une implémentation correcte (c'est à dire à coût constant en enfilement et défilement) de la FILE en utilisant un ou deux tableaux.

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