Données Liste Implémentation

Identification

Infoforall

13 - Implémenter une Liste 2/3


Nous avons implémenter une Liste Récursive sous forme d'une Liste Chaînée utilisant en interne un tuple (tête, queue).

Aujourd'hui, une Liste Itérative sous forme d'une Liste Contiguë de cases utilisant en interne un tableau.

Principe du tableau

Prerequis : l'activité sur les Listes et la première implémentation sous forme de tuple (pour comprendre l'intérêt de celle-ci).

Documents de cours : open document ou pdf

1 - Implémentation en tableau statique

1.1 - Création d'un tableau par compréhension

La création par compréhension consiste à donner entre crochet une expression liée à une boucle et qui va permettre de remplir automatiquement les cases du nouveau tableau.

Exemple avec la création d'un tableau de 5 cases dans lequel toutes les cases contiennent 0 :

>>> t = [0 for x in range(5)] >>> t [0, 0, 0, 0, 0]

La variable de boucle x va prendre d'abord la valeur 0, puis 1, puis 2, puis 3 et finalement 4. Sa valeur n'a pas d'importance ici mais elle prend bien 5 valeurs différentes. Et pour chaque valeur, on va rajoute une case contenant 0 dans le tableau.

On lit donc une construction par compréhension de la droite vers la gauche. En mode pas à pas, cela donne quelque chose comme :

t = [0 for x in range(5)] t = [0 for x in (0, 1, 2, 3, 4)] t = [rajoute une case contenant 0 à la fin du tableau pour chaque x que tu vas lire] t = [0, 0, 0, 0, 0]

Si on veut autant de cases qu'un autre tableau, il suffit d'utiliser la fonction native len() lors de la création :

>>> a = [7, 15, 12, 25] >>> t = [0 for x in range( len(a) )] >>> t [0, 0, 0, 0]

Si on veut une case en plus par rapport à un autre tableau, il suffit d'utiliser la fonction native len() et de rajouter 1 au résultat :

>>> a = [7, 15, 12, 25] >>> t = [0 for x in range( len(a)+1 )] >>> t [0, 0, 0, 0, 0]

Si on veut une case en moins par rapport à un autre tableau, il suffit d'utiliser la fonction native len() et de soustraire 1 au résultat :

>>> a = [7, 15, 12, 25] >>> t = [0 for x in range( len(a)-1 )] >>> t [0, 0, 0]

Nous partons donc de l'idée abstraite d'une Liste itérative que nous allons implémenter sous forme d'une Liste contigüe en utilisant des tableaux statiques.

Cela va être utile si on lit plus souvent les données qu'on ne les insère ou les supprime. Pourquoi ? Simplement car lire les éléments d'un tableau se fait à coût CONSTANT : Θ(1). On considère également que le coût de len() est constant sur le type list de Python.

Nous allons réaliser un module contenant les fonctions d'interface d'une Liste.

1.2 - Les primitives d'une Liste contiguë.

Le type abstrait Liste contient des Places.

Dans le cadre d'une Liste Chaînée, ce sont des Cellules.

Dans le cadre d'une Liste Contiguë, ce sont des Cases.

S'agissant d'une implémentation sous forme de tableau, les Places seront nommées des Cases.

Si on cherche une analogie, on peut dire que :

  • La Liste est une Armoire contenant des casiers.
  • Les Cases sont les casiers numérotés et fixes dans l'Armoire.
  • Les Eléments sont les objets qu'on place dans les casiers numérotés.

Voici les opérations primitives classiques qu'on utilise pour manipuler notre structure de données Liste contiguë :

  1. listeVide() → Liste
  2. estListeVide(lst:Liste) → bool
  3. longueur(lst:Liste) → int
  4. inserer(lst:Liste, elt:Elément, i:int) → Liste
  5. supprimer(lst:Liste Non Vide, i:int) → Liste

Comme avec la liste chaînée, nous introduirons rapidement la fonction raccourci ieme() qui n'est pas une vraie primitive mais qui est bien pratique.

  1. ieme(lst:Liste Non Vide, i:int) → Element

Il reste encore les 3 fonctions usuelles d'interaction avec les Cases (rarement utilisées, à part pour créer ieme() par exemple).

  1. acces(lst:Liste Non Vide, i:int) → Case
  2. contenu(c:Case) → Elément
  3. successeur(c:Case Non Finale) → Case

Dans le cadre de cette activité, je vous fournis un module que nous allons analyser et compléter.

Voici l'ébauche de travail du module :

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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
'''Première ébauche du module Liste contiguë IMMUABLE Description des types non natifs utilisés dans les fonctions + Element : le type des éléments disponibles dans votre Liste si elle est homogène. + Case : la référence d'une case : un tuple (Liste, Indice) + Liste : la référence d'un tableau. Opérations primitives de la Liste contiguë ----------------------------------------- + nouvelleListe() -> Liste + estListeVide(lst:'Liste') -> bool + longueur(lst:'Liste') -> int + ieme(lst:'Liste Non Vide', i:int) -> 'Elément' + inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste' + supprimer(lst:'Liste Non Vide', i:int) -> 'Liste' Fonctions d'interface supplémentaires ------------------------------------- + insererTete(lst:'Liste', elt:'Element') -> 'Liste' + supprimerTete(lst:'Liste Non Vide') -> 'Liste' + representerListe(lst:'Liste') -> str ''' # Importation : aucune # Déclaration des CONSTANTES : aucune # Déclaration des fonctions d'interface fondamentales def nouvelleListe() -> 'Liste': '''Renvoie une liste vide''' return [] def estListeVide(lst:'Liste') -> bool: '''Prédicat qui renvoie True si la liste est vide''' return lst == [] def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments stockés dans lst''' return len(lst) def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie le contenu de la Case de position i VALIDE dans la liste NON VIDE lst''' return lst[i] def inserer(lst:'Liste', elt:'Elément', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en position VALIDE i''' pass def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la case i''' pass # Déclaration des fonctions d'interface supplémentaires def insererTete(lst:'Liste', elt:'Elément') -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en Tête''' nb = len(lst) + 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en plus for k in range(0, len(lst)): # 2 - pour tous les indices disponibles nouveau[k+1] = lst[k] # décalage à droite des éléments nouveau[0] = elt # 3 - elt à la position i return nouveau def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la Tête''' pass def representerListe(lst:'Liste') -> str: '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' return str(lst).replace(',',' -> ').replace('[','').replace(']','') # Instructions du programme principal if __name__ == '__main__': # Ces fonctions ne seront en mémoire qu'en lancement direct def tester_insererTete(): a = nouvelleListe() a = insererTete(a, 5) assert a == [5] a = insererTete(a, 2) assert a == [2, 5] b = insererTete(a, 20) assert a == [2, 5] assert b == [20, 2, 5] print('Test OK pour insererTete()') def tester_supprimerTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) b = supprimerTete(a) assert a == [2, 5] assert b == [5] c = supprimerTete(b) assert estListeVide(c) print('Test OK pour supprimerTete()') def tester_longueur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert longueur(a) == 0 assert longueur(b) == 1 assert longueur(c) == 2 print('Test OK pour longueur()') def tester_ieme(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert ieme(b, 0) == 5 assert ieme(c, 0) == 2 assert ieme(c, 1) == 5 print('Test OK pour lire()') def tester_inserer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) assert d == [2, 20, 5] print('Test OK pour inserer()') def tester_supprimer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) e = supprimer(d, 2) assert d == [2, 20, 5] assert e == [2, 20] print('Test OK pour supprimer()') print("Module lancé directement, il ne s'agit pas d'une importation")

Les fonctions déjà correctement implémentées sont :

  • nouvelleListe(),
  • estListeVide(),
  • longueur(),
  • ieme(),
  • insererTete() et
  • representerListe().

Vous allez devoir réaliser les fonctions supprimerTete(), inserer() et supprimer().

Commençons par les 4 opérations primitives les plus simples :

  • nouvelleListe(),
  • estListeVide(),
  • longueur() et
  • ieme() (qui comme premier() n'est pas une vraie primitive puisqu'on peut la créer en combinant contenu() et acces().

01° Mémoriser ces fonctions. Observer les 4 fonctions. Répondre ensuite à ces questions :

  1. comment se nomme dans Python le type de la structure de données qui nous sert à construire la notre ?
  2. Si on veut utiliser uniquement des tableaux statiques, va-t-on avoir le droit d'utiliser toutes les méthodes qu'offre Python sur ce type ?
  3. L'utilisateur aura-t-il le droit d'utliser directement des expressions comme liste[i] pour lire le contenu de ses données ?
  4. Connaissant les instructions de ces fonctions, que peut-on dire que leurs coûts ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
def nouvelleListe() -> 'Liste': '''Renvoie une liste vide''' return [] def estListeVide(lst:'Liste') -> bool: '''Prédicat qui renvoie True si la liste est vide''' return lst == [] def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments stockés dans lst''' return len(lst) def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie le contenu de la Case de position i VALIDE dans la liste NON VIDE lst''' return lst[i]

...CORRECTION...

  1. Nous utilisons le type natif list.
  2. Néanmoins, nous allons l'utiliser comme un simple tableau statique :
    • déclaration d'un tableau de taille fixe,
    • lecture et modification à coût constant,
    • décalage à coût linéaire).
  3. Non, l'utilisateur devra se limiter à utiliser nos fonctions d'interface. L'un des intêret de l'interface est qu'elle est indépendant des modifications futures du moteur interne.
  4. Puisqu'elles ne contiennent que des instructions à coût constant, elles sont toutes à coût constant.

Comment va-t-on gérer les insertions dans notre liste implémentée sous forme de tableau ?

Le choix a été fait de créer des listes immuables : il va donc falloir créer un deuxième tableau avec une case en plus et y décaler les éléments vers la droite.

Exemple : on veut insérer l'élément 23 en tête dans la liste intiale (5, 10, 15, 25, 30, 35) Principe de l'insertion dans une liste sur une implémentation tableau

On voit donc que la Liste après insertion est un tableau qui :

  1. doit posséder une case en plus
  2. contient les éléments de la première liste mais avec un décalage de 1 vers la droite : new[i+1] = old[i]
  3. possède le nouvel élément en indice 0

02° Observer la fonction insererTete() (c'est une version simplifiée de la primitive inserer() que vous aurez à concevoir plus loin) :

1 2 3 4 5 6 7 8 9 10
def insererTete(lst:'Liste', elt:'Elément') -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en Tête''' nb = len(lst) + 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en plus for k in range(0, len(lst)): # 2 - pour tous les indices disponibles nouveau[k+1] = lst[k] # --> décalage à droite des éléments nouveau[0] = elt # 3 - elt à la position i return nouveau

Questions

  1. Cette fonction modifie-t-elle la liste en place ou crée-t-elle une copie qu'elle renvoie ?
  2. Pourquoi le tableau nouveau (créé par compréhension ligne 5 ci-dessus) est-il créé avec une case supplémentaire par rapport au paramètre lst ?
  3. Comment est-on parvenu à décaler les bonnes valeurs dans le second tableau ? (attention : à savoir expliquer et refaire)

...CORRECTION...

  1. Pas d'effet de bord : on crée un tableau ayant une case en plus, on le remplit puis on le renvoie.
  2. On insère une nouvelle valeur, il vaut bien une case en plus non ?
  3. Voir Lignes 4-7 : pour chaque case du tableau d'origine, on place la valeur de la case i dans la case i+1 du nouveau tableau.

On sait maintenant créer des listes vides, lire les éléments et insérer des têtes. Reste à savoir supprimer les têtes.

Principe de la suppression dans une liste sur une implémentation tableau

03° Quelques questions :

  1. Combien de cases va devoir avoir le nouveau tableau contenant la liste modifiée ?
  2. Va-t-on devoir décaler les cases vers la gauche (on diminue l'indice) ou vers la droite (on augmente l'indice) ?
  3. Doit-on décaler tous les indices du tableau initial ou y-a-t-il un indice à ne pas décaler ?

...CORRECTION...

  1. Une case en moins, puisqu'on supprime.
  2. On voit bien qu'on va devoir décaler vers la gauche, en diminuant les indices des éléments qu'on va déplacer.
  3. On ne doit pas décaler l'indice 0 du tableau initial puisqu'on veut le faire disparaître.

04° Compléter la fonction supprimerTete() dont on vous donne le prototype et la documentation. C'est également juste une version simplifiée de la vraie primitive supprimer() qu'il faudra réaliser plus loin dans l'activité.

PRECONDITION : la liste fournie est NON VIDE.

Prototype

1
def supprimerTete(lst:'Liste Non Vide') -> 'Liste':

Déclaration à modifer

1 2 3
def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la Tête''' pass

Vous pouvez utiliser la fonction tester_supprimerTete() pour tester votre proposition.

...CORRECTION...

1 2 3 4 5 6 7 8 9
def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la Tête''' nb = len(lst) - 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en moins for k in range(1, len(lst)): # 2 - décalage à gauche des éléments d'indice 1 et plus nouveau[k-1] = lst[k] return nouveau

Pour l'instant, on ne parvient à agir sur les têtes mais on commence à voir que cela ressemble bien à une liste.

05° Enregister le module exactement sous le nom liste_contigue_statique.py. Enregistrer au même endroit ce programme :

1 2 3 4 5 6 7 8 9 10 11 12 13
from liste_contigue_statique import nouvelleListe as new from liste_contigue_statique import insererTete as mettreDevant from liste_contigue_statique import representerListe as visuel from random import randint NBR = randint(4, 10) a = new() for _ in range(NBR): a = mettreDevant(a, randint(0, 20)) print(visuel(a))

Questions

  1. L'utilisateur n'utilisant que la fonction d'interface autorisée representerListe() (renmmée ici visuel()) pourra-t-il se rendre compte qu'on implémente notre structure de données dans un tableau ?
  2. L'utilisateur décidé à accéder directement à la mémoire (en tapant le nom de la variable) pourra-t-il se rendre compte qu'on implémente notre structure de données Liste comme un tableau ?

...CORRECTION...

20 -> 3 -> 8 -> 18 -> 2 -> 14 -> 16 -> 11 -> 2 >>> a [20, 3, 8, 18, 2, 14, 16, 11, 2]

Comme on peut le voir sur les exemples, l'utilisateur ne voit que la représentation de la liste comme une séquence ordonnée. Il ne peut donc pas savoir sous quelle forme elle est réellement implémentée. Sauf à demander directement l'accès à la variable, mais dans ce cas, il décide de passer au dessus de l'interface.

Je vous ai montré comment supprimer la tête et insérer une tête. Il vous reste à le faire à n'importe quelle position.

Commençons par l'insertion. Un exemple d'insertion d'un élément valant 23 sur l'indice 2 dans une Liste contiguë a :

>>> inserer(a, 23, 2)
Principe de l'insertion dans une liste sur une implémentation tableau

06-A° Répondre aux question ci-dessous :

  1. Pour insérer en indice 2, quels sont les indices des cases qui ne seront pas décalées ?
  2. Pour insérer en indice 2, quels sont les indices des cases qui seront décalées ?
  3. Pour insérer en indice i, quels sont les indices des cases qui ne seront pas décalées ?
  4. Pour insérer en indice i, quels sont les indices des cases qui seront décalées ?

...CORRECTION...

  1. On ne décale pas les cases de 0 à 1.
  2. On décale vers la droite les cases 2 et plus
  3. On ne décale pas les cases de 0 à (i-1).
  4. On décale vers la droite les cases i et plus

06-B° Compléter la fonction inserer() dont on vous donne le prototype et la documentation dans le module. N'utilisez la fonction insererTete() à l'interne : on veut réaliser une fonction indépendante. Par contre, vous pourrez vous inspirer de insererTete().

Préconditions : i doit être un indice VALIDE. Fournir un indice correspondant au nombre d'éléments de la liste de base veut donc dire d'insérer en fin de liste.

Prototype

1
def inserer(lst:'Liste', elt:'Elément', i:int) -> 'Liste':

Vous pouvez utiliser la fonction tester_inserer() pour tester votre implémentation.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12
def inserer(lst:'Liste', elt:'Elément', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en position VALIDE i''' nb = len(lst) + 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en plus for k in range(0, i): # 2 - copie les éléments des indices 0 à i-1 sans décalage nouveau[k] = lst[k] for k in range(i, len(lst)): # 3 - décalage à droite des éléments d'indice i et plus nouveau[k+1] = lst[k] nouveau[i] = elt # 4 - elt à la position i return nouveau

Passons à la suppression n'importe où.

Principe de la suppression dans une liste sur une implémentation tableau

07-A° Répondre aux question ci-dessous :

  1. Pour supprimer l'élément en indice 2, quels sont les indices des cases qui ne seront pas décalées ?
  2. Pour supprimer l'élément en indice 2, quels sont les indices des cases qui seront décalées ?
  3. Pour supprimer l'élément en indice i, quels sont les indices des cases qui ne seront pas décalées ?
  4. Pour supprimer l'élément en indice i, quels sont les indices des cases qui seront décalées ?

...CORRECTION...

  1. On ne décale pas les cases de 0 à 1.
  2. On décale vers la gauche les cases 3 et plus
  3. On ne décale pas les cases de 0 à (i-1).
  4. On décale vers la gauche les cases i+1 et plus

07-B° Compléter la fonction supprimer() dont on vous donne le prototype et la documentation dans le module. N'utilisez la fonction supprimerTete() à l'interne : il faut faire une fonction indépendante. Par contre, vous pourrez vous inspirer de supprimerTete().

Préconditions : l'indice i doit encore être VALIDE, ce que veut dire également que la Liste doit être NON VIDE.

Prototype

1
def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste':

Vous pouvez utiliser la fonction tester_supprimer() pour tester votre implémentation.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la case i''' nb = len(lst) - 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en moins for k in range(0, i): # 2 - copie les éléments des indices 0 à i-1 sans décalage nouveau[k] = lst[k] for k in range(i+1, len(lst)): # 3 - décalage à gauche des éléments d'indice i+1 et plus nouveau[k-1] = lst[k] return nouveau

08° Estimer les coûts des quatre fonctions inserer(), supprimer(), insererTete() et supprimerTete() pour l'implémentation en tableau statique.

Y-a-t-il un meilleur des cas et un pire des cas ?

En déduire la complexité des fonctions.

...CORRECTION...

On doit toujours copier toutes les cases une à une (ou presque : on ne copie pas le contenu qu'on veut supprimer).

Il n'y a donc pas de pire des cas ou de meilleur des cas.

Le coût est LINEAIRE.

La complexité peut donc s'écrire 𝞗(n).

Nous avons maintenant tout ce qu'il faut pour parvenir à gérer correctemment notre Liste, même si les insertions et les suppressions ne seront clairement pas de bonne qualité puisqu'on a un coût linéaire partout.

Nous n'avons pas réellement besoin des 3 primitives acces(), successeur() et contenu() puisqu'on peut gérer tout cela à la main en utilisant l'indice de la case.

Par contre, si on désire dire rigoureusement que notre Liste contiguë est une Liste, il faut disposer de ces 3 fonctions.

Gestion des cases dans notre Liste contiguë

Problématique

On pourrait croire qu'en donnant juste l'indice i de la Case, on peut trouver le successeur (la Case i+1) et son contenu (l'élément présent sur cet indice i). Mais non, l'indice n'est pas la Case.

Le prototype de contenu() montre clairement qu'en envoyant simplement la Case, on doit récupérer l'élément.

contenu(c:Case) → Elément

Or, pour faire cela, il faut pouvoir demander a[i], deux informations à connaître :

  1. La Liste a dans laquelle se trouve la case
  2. L'indice i de la case

Réponse possible

Nous faisons le choix de faire des cases de simple tuples contenant la référence de la liste sur l'indice 0 et le numéro de la case suivante sur l'indice 1.

Case = (Liste-conteneur, Indice du Successeur)

1 2 3
def acces(lst:'Liste Non Vide', i:int) -> 'Case': '''Renvoie la référence de la case d'indice i dans la liste lst NON VIDE''' return (lst, i) # on crée un tuple-case (quelle liste ?, quel indice ?)

Puisqu'une case contient bien les informations "Quelle Liste ?" et "Quel numéro ?", on peut facilement réaliser les deux autres fonctions :

1 2 3 4 5 6 7 8 9 10 11 12
def contenu(c:'Case') -> 'Elément': '''Renvoie le contenu de la case valide fournie''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return lst[i] # on renvoie l'élément stocké à cet endroit def successeur(c:'Case Non Finale') -> 'Case': '''Renvoie le case qui succède à la case fournie (qui ne doit pas être la dernière)''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return (lst, i+1) # on crée un tuple-case correspond à la case suivante

09° Lire les 3 fonctions ci-dessous gérant les Cases.

Estimer leurs coûts.

Créer ensuite la fonction precedent() qui doit renvoyer la case précédente. PRECONDITION : la case ne doit pas être la Tête de liste.

1 2 3
def precedent(c:'Case Non Tête') -> 'Case': '''Renvoie le case qui précéde la case fournie (qui ne doit pas être la première)''' return c # fausse réponse (du bon type) du prototype

...CORRECTION...

Les coûts sont contants puisqu'on ne fait que lire deux cases de tuple ou créer un tuple à deux cases à l'aide d'opérations à coûts constant en nombre ne dépendant pas du nombre d'éléments dans la liste.

1 2 3 4 5
def precedent(c:'Case Non Tête') -> 'Case': '''Renvoie le case qui précéde la case fournie (qui ne doit pas être la première)''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return (lst, i-1) # on crée un tuple-case correspond à la case précédente
Coût des primitives

Contrairement à la première Liste Tête-Queue, les primitives de notre Liste Contiguë Immuable ne sont pas toutes des fonctions à coût constant.

  1. listeVide() → Liste  Coût CONSTANT
  2. estListeVide(lst:Liste) → bool  Coût CONSTANT
  3. longueur(lst:Liste) → int  Coût CONSTANT
  4. inserer(lst:Liste, elt:Elément, i:int) → Liste  Coût LINEAIRE en θ(n)
  5. supprimer(lst:Liste Non Vide, i:int) → Liste  Coût LINEAIRE en θ(n)
  6. acces(lst:Liste Non Vide, i:int) → Case  Coût CONSTANT
  7. contenu(c:Case) → Elément  Coût CONSTANT
  8. successeur(c:Case Non Finale) → Case  Coût CONSTANT
  9. ieme(lst:Liste Non Vide, i:int) → Element  Coût CONSTANT

C'est à partir de ces primitives que nous pourront construire toutes les autres fonctionnalités mais sans toucher directement à la structure interne de notre Liste.

Nous n'allons pas aller au bout de ce module comme le précédent. Il va par contre falloir lire et comprendre ces fonctions. Lors du DS, je peux vous demander de recréer telle ou telle fonction.

Penchons nous sur la concaténation de deux listes statiques. Imaginons qu'on dispose des deux listes suivantes. L'une de 20 000 éléments et l'autre de 20 000 éléments également. Si on désire insérer la deuxième liste après la première liste, cela risque d'être compliqué avec des tableaux :

D'abord, il faut réserver une nouvelle place mémoire de 40 000 places :

Création d'un nouveau tableau

Ensuite, il faut déplacer un par un les 20 000 éléments du premier tableau.

Déplacement des éléments de A

Puis on déplace les 20 000 éléments du deuxième tableau.

Déplacement des éléments de B
MODULE Liste Contiguë IMMUABLE

Ce module devra être nommé liste_contigue_statique.py.

Vous remarquerez que insererTete() a bien été recrée comme une fonction utilisant les primitives plutôt qu'une fonction manipulant directement les données.

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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 400 401 402 403 404 405 406 407
'''INTERFACE d'une structure de données IMMUABLE Liste Contiguë Description des types non natifs utilisés dans les fonctions + Element : le type des éléments disponibles dans votre Liste si elle est homogène. + Case : la référence d'une case : un tuple (Liste, indice) + Liste : la référence d'un tableau Opérations primitives de la Liste contiguë ------------------------------------------ + nouvelleListe() -> Liste + estListeVide(lst:'Liste') -> bool + longueur(lst:'Liste') -> int + ieme(lst:'Liste Non Vide', i:int) -> 'Elément' + inserer(lst:'Liste', elt:'Element', i:int) -> 'Liste' + supprimer(lst:'Liste Non Vide', i:int) -> 'Liste' + acces(lst:'Liste Non Vide') -> 'Case' + contenu(c:'Case') -> 'Element' + successeur(c:'Case Non Fin') -> 'Case' + precedent(c:'Case Non Tête') -> 'Case' Fonctions d'interface supplémentaires ------------------------------------- + insererTete(lst:'Liste', elt:'Element') -> 'Liste' + supprimerTete(lst:'Liste Non Vide') -> 'Liste' + accesTete(lst:'Liste Non Vide') -> 'Case' + insererFin(lst:'Liste', elt:'Element') -> 'Liste' + supprimerFin(lst:'Liste Non Vide') -> 'Liste' + accesFin(lst:'Liste Non Vide') -> 'Case' + premier(lst:'Liste Non Vide') -> 'Element' + dernier(lst:'Liste Non Vide') -> 'Element' + insererFin(lst:'Liste', elt:'Element') -> 'Liste' + supprimerFin(lst:'Liste Non Vide') -> 'Liste' + accesFin(lst:'Liste Non Vide') -> 'Case' + concatener(gauche:'Liste', droite:'Liste') -> 'Liste' + rechercher(lst1:'Liste', elt:'Element') -> int + representerListe(lst:'Liste') -> str + liste(x:'list|tuple|int|float|str') -> 'Liste' + copier(lst:'Liste') -> 'Liste' ''' # Importation : aucune # Déclaration des CONSTANTES : aucune # Déclaration des opérations primitives def nouvelleListe() -> 'Liste': '''Renvoie une liste vide''' return [] def estListeVide(lst:'Liste') -> bool: '''Prédicat qui renvoie True si la liste est vide''' return lst == [] def longueur(lst:'Liste') -> int: '''Renvoie le nombre d'éléments stockés dans lst''' return len(lst) def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie le contenu de la Case de position i VALIDE dans la liste NON VIDE lst''' return lst[i] def inserer(lst:'Liste', elt:'Elément', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en position VALIDE i''' nb = len(lst) + 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en plus for k in range(0, i): # 2 - copie les éléments des indices 0 à i-1 sans décalage nouveau[k] = lst[k] for k in range(i, len(lst)): # 3 - décalage à droite des éléments d'indice i et plus nouveau[k+1] = lst[k] nouveau[i] = elt # 4 - elt à la position i return nouveau def supprimer(lst:'Liste Non Vide', i:int) -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la case i''' nb = len(lst) - 1 nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec une case en moins for k in range(0, i): # 2 - copie les éléments des indices 0 à i-1 sans décalage nouveau[k] = lst[k] for k in range(i+1, len(lst)): # 3 - décalage à gauche des éléments d'indice i+1 et plus nouveau[k-1] = lst[k] return nouveau def acces(lst:'Liste Non Vide', i:int) -> 'Case': '''Renvoie la référence de la case d'indice i dans la liste lst NON VIDE''' return (lst, i) # on crée un tuple-case (quelle liste ?, quel indice ?) def contenu(c:'Case') -> 'Elément': '''Renvoie le contenu de la case valide fournie''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return lst[i] # on renvoie l'élément stocké à cet endroit def successeur(c:'Case Non Finale') -> 'Case': '''Renvoie le case qui succède à la case fournie (qui ne doit pas être la dernière)''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return (lst, i+1) # on crée un tuple-case correspond à la case suivante def precedent(c:'Case Non Tête') -> 'Case': '''Renvoie le case qui précéde la case fournie (qui ne doit pas être la première)''' lst = c[0] # on récupère la liste contenant notre case i = c[1] # on récupère l'indice de notre case return (lst, i-1) # on crée un tuple-case correspond à la case précédente # Déclaration des fonctions d'interface supplémentaires def insererTete(lst:'Liste', elt:'Elément') -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en Tête''' return inserer(lst, elt, 0) def supprimerTete(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la Tête''' return supprimer(lst, 0) def accesTete(lst:'Liste Non Vide') -> 'Case': '''Renvoie la référence de la case de tête dans lst NON VIDE''' return acces(lst, 0) def insererFin(lst:'Liste', elt:'Elément') -> 'Liste': '''Renvoie une Liste basée sur lst où elt est en Fin''' return inserer(lst, elt, longueur(lst)) def supprimerFin(lst:'Liste Non Vide') -> 'Liste': '''Renvoie une Liste basée sur lst NON VIDE en supprimant la fin''' return supprimer(lst, longueur(lst) - 1) def accesFin(lst:'Liste Non Vide') -> 'Case': '''Renvoie la référence de la case de fin dans lst NON VIDE''' return acces(lst, longueur(lst) - 1) def premier(lst:'Liste Non Vide') -> 'Element': '''Renvoie la valeur de tête de lst NON VIDE''' return ieme(lst, 0) def dernier(lst:'Liste Non Vide') -> 'Element': '''Renvoie la valeur de fin de lst NON VIDE''' return ieme(lst, longueur(lst) - 1) def representerListe(lst:'Liste') -> str: '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' return str(lst).replace(',',' -> ').replace('[','').replace(']','') def concatener(gauche:'Liste', droite:'Liste') -> 'Liste': '''Renvoie une nouvelle liste commençant par la tête de gauche vers la fin de droite''' nouveau = nouvelleListe() # 1 - nouvelle liste pour la concaténation ng = longueur(gauche) for i in range(ng): # 2 - on copie les éléments de gauche nouveau = inserer(nouveau, ieme(gauche, i), i) nd = longueur(droite) for i in range(nd): # 3 - on copie les éléments de droite nouveau = inserer(nouveau, ieme(droite, i), ng + i) return nouveau def concatener_version_primitive(gauche:'Liste', droite:'Liste') -> 'Liste': '''Renvoie une nouvelle liste commençant par la tête de gauche vers la fin de droite''' nb = len(gauche) + len(droite) nouveau = [None for _ in range(nb)] # 1 - nouveau tableau avec autant de cases que les deux autres for i in range(0, len(gauche)): # 2 - on copie les éléments de gauche nouveau[i] = gauche[i] ng = len(gauche) # on récupère le nb d'élémnets à gauche for i in range(0, len(droite)): # 3 - on copie les éléments de droite nouveau[ng+i] = droite[i] return nouveau def rechercher(lst:'Liste', elt:'Element') -> int: '''Renvoie la position éventuelle de elt dans lst, -1 si non trouvé''' for i in range(longueur(lst)): # Pour chaque indice valide de la liste lst if ieme(lst, i) == elt: # si la case i contient l'élément cherché return i # répondre en renvoyant l'indice de la case return -1 # si on arrive ici, c'est qu'on a pas trouvé def liste(x) -> 'Liste': '''Renvoie une liste générée à partir de x''' nouvelle = nouvelleListe() if type(x) == list or type(x) == tuple: for i in range(len(x)-1, -1, -1): nouvelle = [v for v in x] elif type(x) == dict: for couple in dict.items(): nouvelle = insererTete(nouvelle, couple) elif type(x) == int or type(x) == float or type(x) == str or type(x) == bool: nouvelle = insererTete(nouvelle, x) return nouvelle def copie(lst:'Liste') -> 'Liste': '''Renvoie une copie peu profonde de la liste lst envoyée''' return [v for v in lst] # Instructions du programme principal if __name__ == '__main__': # Ces fonctions ne seront en mémoire qu'en lancement direct def tester_insererTete(): a = nouvelleListe() a = insererTete(a, 5) assert a == [5] a = insererTete(a, 2) assert a == [2, 5] b = insererTete(a, 20) assert a == [2, 5] assert b == [20, 2, 5] print('Test OK pour insererTete()') def tester_supprimerTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) b = supprimerTete(a) assert a == [2, 5] assert b == [5] c = supprimerTete(b) assert estListeVide(c) print('Test OK pour supprimerTete()') def tester_accesTete(): a = nouvelleListe() a = insererTete(a, 5) a = insererTete(a, 2) assert accesTete(a) == ([2, 5], 0) print('Test OK pour accesTete()') def tester_contenu(): a = nouvelleListe() a = insererTete(a, 5) b = insererTete(a, 2) assert contenu(accesTete(a)) == 5 assert contenu(accesTete(b)) == 2 print('Test OK pour contenu()') def tester_successeur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = insererTete(c, 20) assert successeur(accesTete(d)) == ([20, 2, 5], 1) assert successeur(accesTete(c)) == ([2, 5], 1) print('Test OK pour successeur()') def tester_longueur(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert longueur(a) == 0 assert longueur(b) == 1 assert longueur(c) == 2 print('Test OK pour longueur()') def tester_acces(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert acces(b, 0) == ([5], 0) assert acces(c, 0) == ([2, 5], 0) assert acces(c, 1) == ([2, 5], 1) print('Test OK pour acces()') def tester_ieme(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) assert ieme(b, 0) == 5 assert ieme(c, 0) == 2 assert ieme(c, 1) == 5 print('Test OK pour lire()') def tester_inserer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) assert d == [2, 20, 5] print('Test OK pour inserer()') def tester_supprimer(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) e = supprimer(d, 2) assert d == [2, 20, 5] assert e == [2, 20] print('Test OK pour supprimer()') def tester_concatener(): a = nouvelleListe() b1 = insererTete(a, 5) b2 = insererTete(b1, 2) b3 = insererTete(b2, 50) c1 = insererTete(a, 20) c2 = insererTete(c1, 200) d = concatener(b3, c2) assert d == [50, 2, 5, 200, 20] print('Test OK pour concatener()') def tester_rechercher(): a = nouvelleListe() b = insererTete(a, 5) c = insererTete(b, 2) d = inserer(c, 20, 1) assert rechercher(d, 30) == -1 assert rechercher(d, 20) == 1 assert rechercher(d, 2) == 0 assert rechercher(d, 5) == 2 print('Test OK pour rechercher()') def tester(): # Tous les tests tester_insererTete() tester_supprimerTete() tester_accesTete() tester_contenu() tester_successeur() tester_longueur() tester_acces() tester_ieme() tester_inserer() tester_supprimer() tester_concatener() tester_rechercher() print("Module lancé directement, il ne s'agit pas d'une importation") tester()

10° Lire et comprendre les fonctions non encore vues pour cette implémentation.

Estimer le coût pour chacune d'entre elles.

  • Coût de premier() ?
  • Coût de dernier() ?
  • Coût de concatener() en fonction de ng et nd ?
  • Coût de rechercher() ?

Un peu d'aide ?

Il faut se souvenir de la formule d'Euler :

Formule de la série

Ou encore :

Formule de la série formule 1'

Une somme d'opérations de ce type mène donc à un coût quadratique.

...CORRECTION...

  • Coût de premier() ? Constant.
  • Coût de dernier() ? Constant.
  • Coût de concatener() en fonction de ng et nd ? On doit faire la somme de 1 + 2 + 3 +.... (ng+nd) opérations. Le coût est donc quadratique !
  • Coût de rechercher() ? Linéaire, en 𝞞(n)

11° Observer la fonction concatener_version_primitive() qui manipule directement le type list de Python.

Quel est son coût ?

Quel est l'avantage de cette version ?

Quel est le désavantage de cette version ?

...CORRECTION...

  • Cette fois, on voit que le coût est linéaire et la complexité en θ(ng+nd)
  • Avantage : linéaire, c'est beaucoup mieux que quadratique
  • Désavantage : si on change la gesion interne, il faut modifier cette fonction ci également, sinon toutes les fonctions qui en dépendent ne fonctionneront plus !.
CONCLUSION

L'implémentation d'une liste immuable via un tableau est strictement identique pour l'utilisateur qu'une implémentation immuable Tête-Queue.

Par contre, on peut se douter de l'implémentation utilisée en interne à travers les performances de notre liste.

  • l'implémentation tableau aura en moyenne de meilleures performances en lecture que l'implémentation tuple (tête, queue).
  • l'implémentation tableau aura en moyenne de moins bonnes performances en suppression/insertion que l'implémentation tuple (tête, queue).

Nous avons également vu que manipuler les données à travers les primitives à de gros avantages en termes de solidité, mais qu'il est parfois nécessaire de créer de nouvelles primitives si on parvient à prouver que la manipulation directe aura de meilleures performances que la manipulation des primitives. Mais on ne fait jamais cela sans réflechir sur la nécessité absolue de le faire.

12° Utiliser les fonctions d'interface proposées pour créer dans la console une liste qui contiendra une tête de 5 suivi des éléments 10 puis 20.

Observer alors votre liste avec la fonction representerListe().

Un utilisateur observant sa liste avec representerListe() peut-il savoir qu'on travaille avec une implémentation tableau statique ?

...CORRECTION...

Non, un utilisateur ne pourra pas depuis l'extérieur savoir comment notre implémentation est réalisée. L'intérêt pour lui étant que son programme n'aura pas à être modifié même si l'implémentation change mais que les fonctions d'interface restent inchangées.

2 - Implémentation en utilisant directement list de Python

L'implémentation est inutile : nous verrons que chaque fonction d'interface utilise juste une méthode déjà présente pour le type list de Python.

Le but de cette activité est donc de vous permettre d'avoir du recul sur ce type natif et de comprendre son comportement en terme de liste.

Le tableau dynamique de Python (hors programme mais utile)

Le type list de Python

Le tableau statique n'est pas une très bonne implémentation de liste contiguë : la moindre insertion/suppresion est à coût linéaire quelque soit l'endroit d'intervention, avec une complexité θ(n).

Nous allons maintenant voir ce qu'est réellement le type list de Python : un tableau mutable dynamique. C'est un tableau mais :

  • On peut insérer à coût constant à la fin
  • On peut supprimer à coût constant à la fin

Le principe du tableau dynamique

Voici comment on parvient à agir à coût constant dans un tableau : on crée un tableau possèdant plus de cases que nécessaires.

Imaginons qu'on veuille initialement créer un tableau de 5 cases :

>>> t = [1, 3, 4, 1, 2]

Python réserve en réalité plus de cases que nécessaires : il vous en faut 5, l'interpréteur va générer un tableau de 10 cases. Mais les indices 05 à 09 sont juste vides. Si vous demandez la taille du tableau, on vous répondra bien 5 car le dernier indice utilisé est 4.

>>> len(t) 5

Rajouter un élément est donc facile : il suffit de le placer sur l'indice 5 qui existe déjà et de décaler la valeur du dernier indice réellement utilisé.

>>> t.append(3)

En mémoire, on a juste décaler de 1 la valeur maximale de l'indice possible et on place le 3 dans cette case finale. L'opération se fait donc à temps constant.

Si on continue à rajouter des choses, nous allons aboutir à un tableau totalement rempli.

>>> t.append(1) >>> t.append(9) >>> t.append(18) >>> t.append(8)

Notre tableau dynamique est plein !

Pourtant, on peut continuer à rajouter des éléments... Comment est-ce que cela est possible ?

>>> t.append(7)

Le rajout se fait en deux temps.

ETAPE 1 : Python crée un nouveau tableau deux fois plus grand (on passe de 10 à 20 cases sur notre exemple).

ETAPE 2 : Python copie le contenu, case par case puis rajoute la nouvelle valeur dans la nouvelle valeur maximale d'indice !

Cette fois, l'insertion a été faite à coût linéaire, puisqu'il a fallu recopier les valeurs avant de parvenir à mettre le 7 en fin de tableau.

Par contre, insérer encore un élément se fera à nouveau à coût constant : il suffit de décaler l'indice maximum et d'y placer le nouvel élément.

>>> t.append(5)

CONCLUSION : l'insertion n'est pas exactement constant puisqu'une fois de temps à autre, l'insertion sera à coût linéaire. Mais, en moyenne, c'est quasiment linéaire.

Pour la suppression, c'est encore plus simple : il suffit de décaler l'indice maximum d'une valeur vers la gauche. Même pas besoin de supprimer le contenu de la case, on la rend juste inaccessible pour l'utilisateur.

>>> t.pop() 5

L'essentiel

On peut insérer en fin de list Python à coût constant avec append().

On peut supprimer en fin de list Python à coût constant avec pop().

Maintenant vous savez vraiment pourquoi.

Coûts de certaines méthodes de list

Vous avez maintenant compris que :

  • append() possède un coût amorti constant.
  • pop() possède un coût constant, si on l'utilise pour supprimer la fin.

Il reste à voir deux utilisations qui ont l'air "magique", mais qui ont un coût non constant...

Insertion de nouveaux éléments avec la méthode insert()

La méthode append() permet de rajouter EN PLACE un nouvel élément à d'une list-Python.

Mais il existe également une méthode nommée insert() qui permet de faire la même chose MAIS en choississant la position de l'insertion via un indice, comme notre fonction inserer().

Dans ce cas, il faut faire 3 choses :

  1. On augmente de 1 l'indice maximum.
  2. On décale à droite n-i valeurs : celles d'indice i à n-1, qu'on place dans les cases d'indice i+1 à n.
  3. On place la valeur à insérer dans la case i.

Coût de l'insertion en i

L'insertion est donc linéaire et la complexité en θ(n-i). On a donc du 𝞞(n).

1 2 3
def inserer(lst:'Liste', x:'Elément', i:int) -> None: '''Modifie en place la liste en insérant l'élément elt à l'indice i fourni''' lst.insert(i, x)

Ici, on obtient une liste mutable, dont les données ont été modifiées directement en mémoire. Votre fonction n'a donc pas besion de renvoyer une nouvelle référence.

Suppression d'un élément via la méthode pop()

La méthode nommée pop() qui permet de supprimer une position et de renvoyer l'élément correspondant.

La suppression de l'élément en position i se fait en plusieurs étapes :

  1. On décale à gauche n-i valeurs : celles d'indice i+1 à n-1, qu'on place dans les cases d'indice i à n-2.
  2. On diminue de 1 la valeur de l'indice maximum.

Coût de la suppression en i

La suppression est donc linéaire et la complexité en θ(n-i). On a donc du 𝞞(n).

Pour supprimer ET récupérer l'ancien élément d'indice 0 :

1
valeur_extraite = t.pop(0)

Pour juste supprimer l'ancien élément d'indice 0 sans le mémoriser :

1
t.pop(0)

Voici donc notre nouvelle fonction d'interface supprimer() :

1 2 3
def supprimer(lst:'Liste Non Vide', i:int) -> 'Elément': '''Renvoie l'élément supprimé à l'indice i VALIDE dans lst NON VIDE''' return lst.pop(i)

Si on résume :

  • append(elt)) : un coût amorti constant pour l'insertion en fin.
  • pop() : un coût constant pour la suppression en fin.
  • insert(i, elt) : un coût linéaire pour l'insertion, le pire des cas étant en 0.
  • pop(i) : un coût linéaire pour la suppression, le pire des cas étant en 0.

13° Placer cette nouvelle implémentation en mémoire : cette fois, elle utilise directement les méthodes du type list de Python pour créer une LISTE MUABLE.

Réalisation à faire : utiliser des instructions en console pour créer une liste dont la tête est 200 et les éléments suivants 100 et 10. Attention : la liste est muable et les fonctions d'interface ne s'utilisent pas de la même façon en MUTABLE et en IMMUABLE.

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
'''Implémentation d'une LISTE MUABLE en utilisant un tableau dynamique list-Python Description des primitives ------------------------------------ 1 ::: nouvelleListe() -> 'Liste' Coût CST 2 ::: estListeVide(lst:'Liste') -> bool Coût CST 3 ::: longueur(lst:'Liste') -> int Coût CST 4 ::: ieme(lst:'Liste Non Vide', i:int) -> 'Elément' Coût CST 5 ::: insererFin(lst:'Liste', elt:'Elément') -> None Coût CST 6 ::: supprimerFin(lst:'Liste Non Vide') -> 'Elément' Coût CST 6 ::: inserer(lst:'Liste', elt:'Elément', i:int) -> None Coût LIN en θ(n-i) 7 ::: supprimer(lst:'Liste Non Vide', i:int) -> 'Elément' Coût' LIN en θ(n-i) Description d'autres fonctions' ------------------------------ 8 ::: representerListe(lst:'Liste') -> str ''' def nouvelleListe() -> 'Liste': '''Renvoie une liste vide''' return [] def estListeVide(lst:'Liste') -> bool: '''Renvoie True si la liste est vide''' return lst == [] def longueur(lst:'Liste') -> int: '''Renvoie le nombre de cases utilisées dans le tableau''' return len(lst) def ieme(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie la valeur stockée à l'indice VALIDE voulu de lst NON VIDE''' return lst[i] def insererFin(lst:'Liste', elt:'Elément') -> None: '''Modifie en place la liste en insérant l'élément en fin de liste''' lst.append(elt) def supprimerFin(lst:'Liste Non Vide') -> 'Element': '''Renvoie l'élément de fin supprimé dans lst NON VIDE''' return lst.pop() def inserer(lst:'Liste', elt:'Elément', i:int) -> None: '''Modifie en place la liste en insérant l'élément à l'indice fourni''' lst.insert(i, elt) def supprimer(lst:'Liste Non Vide', i:int) -> 'Element': '''Renvoie l'élément supprimé à l'indice VALIDE dans lst NON VIDE''' return lst.pop(i) def representerListe(lst:'Liste'): '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête''' return str(lst).replace(',',' -> ').replace('[','').replace(']','')

14° Utiliser representerListe() pour observer le contenu de votre liste muable. L'utilisateur peut savoir que la liste est muable puisqu'il a dû l'utiliser. Peut-il savoir que les données de la liste sont stockées sous forme d'un tableau dynamique ?

...CORRECTION...

Non, un utilisateur ne pourra toujours pas savoir comment notre implémentation est réalisée. Normalement, à ce stade des activités d'implémentation, vous devriez avoir compris :o)

Remarquez bien que certaines fonctions permettent de voir la nature muable de cette implémentation. Notamment inserer() qui renvoie None.

15° Réaliser la fonction concatener() qui devra renvoyer une nouvelle liste. Ni la liste gauche, ni la liste gauche ne devront avoir été donc modifiées.

Prototype

def concatener(gauche:'Liste', droite:'Liste') -> 'Liste':

Votre fonction devra avoir un coût linéaire par rapport au nombre d'éléments de gauche et de droite et devra uniquement manipuler les primitives et pas le type list directement.

...CORRECTION...

1 2 3 4 5 6 7
def concatener(gauche:'Liste', droite:'Liste') -> 'Liste': nouveau = nouvelleListe() for i in range(longueur(gauche)): nouveau.insererFin(ieme(gauche, i)) for i in range(longueur(droite)): nouveau.insererFin(ieme(droite, i)) return nouveau

16° Même question mais en manipulant directement le type list. Vous devriez obtenir le même coût.

Prototype

def concatener(gauche:'Liste', droite:'Liste') -> 'Liste':

Votre fonction devra avoir un coût linéaire par rapport au nombre d'éléments de gauche et de droite et devra uniquement manipuler les primitives et pas le type list directement.

...CORRECTION...

1 2 3 4 5 6 7
def concatener_primitive(gauche:'Liste', droite:'Liste') -> 'Liste': nouveau = [] for i in range(len(gauche)): nouveau.append(gauche[i]) for i in range(len(droite)): nouveau.append(droite[i]) return nouveau
CONCLUSION sur le type list Python

Chaque fonction ne possède qu'une seule instruction. Comme vous le voyez, il est plutôt inutile de vouloir créer une liste contiguë muable en utilisant le type list de Python : pourquoi recréer des fonctions d'interface alors que le créateur de Python a justement créer le type list avec cette idée en tête. De plus, beaucoup d'opérations disponibles sur le type list de Python sont optimisées (tri, concaténation...)

Néanmoins, vous en savez maintenant beaucoup plus sur cette structure de données native de Python.

3 - FAQ

On peut avoir le module déjà réalisé ?

Vous pouvez maintenant directement télécharger ce module :

MODULE LISTE CONTIGUE IMMUABLE TABLEAU STATIQUE

MODULE LISTE CONTIGUE MUABLE

On m'a dit de faire attention aux copies de tableaux. C'est vrai ?

Oui. Si vous voulez obtenir une copie d'un tableau, ne faites surtout pas cela :

>>> a = [2, 40, 3] >>> b = a >>> b [2, 40, 3]

Pourquoi ? Ca a l'air de marcher !

Oui mais non. La variable a ne contient pas les DONNEES du tableau mais son ADRESSE-MEMOIRE (ou son équivalent en Python). Et donc b contient aussi en réalité cette adresse.

>>> id(a) 50505050 >>> id(b) 50505050 >>> id(a)

Du coup, a et b sont des alias des mêmes données. Si vous modifiez a, vous modifiez b.

>>> a [2, 40, 3] >>> b [2, 40, 3] >>> a[0] = 1000 >>> b [1000, 40, 3]

Comment faire alors ?

Si votre tableau ne contient que des données immuables, vous pouvez recréer un tableau par compréhension :

>>> a = [2, 40, 3] >>> b = [valeur for valeur in a] >>> b [2, 40, 3] >>> a[0] = 1000 >>> a [1000, 40, 3] >>> b [2, 40, 3]

Si votre tableau contient des données muables, le mieux est encore d'utiliser le module copy et sa fonction deepcopy() de copie profonde.

Exemple avec a qui est un tableau contenant des tableaux

>>> import copy >>> a = [[4,2,0], [40,20,0], [3,4,8]] >>> b = copy.deepcopy(a) >>> b [[4,2,0], [40,20,0], [3,4,8]] >>> a[0][2] = 1000 >>> a [[4, 2, 1000], [40, 20, 0], [3, 4, 8]] >>> b [[4, 2, 0], [40, 20, 0], [3, 4, 8]]

Nous venons donc de voir clairement qu'un utilisateur ne peut pas savoir comment est implémenté une structure de données dont on lui fournit juste l'interface.

Par contre, chaque implémentation va avoir des avantages et des défauts.

  • Version 1 Tuple (tête, queue) : bien si on désire souvent manipuler uniquement les têtes, mais coûts linéaires en lecture, insertion et suppression ailleurs.
  • Version 2 tableaux : coût constant en lecture n'importe où mais coût linéaire en insertion et suppression.
  • Version 3 list Python : comme au dessus mais les insertions et suppressions en fin de liste sont à coût constant.

La fois prochaine, nous verrons une dernière implémentation du type abstrait LISTE : la liste chaînée muable en version programmation objet.

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