Données Liste Implémentation

Identification

Infoforall

12 - Implémenter une Liste 1/3


En informatique, l'implémentation est le passage de l'abstraction théorique à la programmation concrète.

Vous avez déjà implémenté des algorithmes en programmes Python ou Javascript.

Vous allez maintenant implémenter un type abstrait LISTE en structure de données réelles en machine.

Serpent Tête et Queue
Image libre de droit

Python possède déjà un certain nombres de structures de données qui permettent l'implémentation des types abstraits.

  • On gère le type abstrait booléen en utilisant le type natif bool.
  • On gère le type abstrait integer en utilisant le type natif int.
  • On gère le type abstrait nombre à virgule flottante en utilisant le type natif float.
  • On gère le type abstrait tableau statique (array en anglais) en utilisant le type natif ... list.
  • On gère le type abstrait tableau dynamique (vector en anglais) en utilisant le type natif list.
  • On gère le type abstrait tableau associatif en utilisant le type natif dict.
  • On gère le type abstrait p-uplet nommé en utilisant le type natif dict.
  • On gère le type abstrait p-uplet en utilisant le type natif tuple.

Prerequis : l'activité sur les Listes.

1 - Tuple (Tête, Queue)

Nous allons réaliser une implémentation qui permet d'obtenir l'interface du type abstrait Liste suivante :

Principe de l'interface LISP entre l'utilisateur et les données

De façon à obtenir une structure non mutable, nous décidons de partir sur la manipulation de tuples.

Nous allons voir que chaque implémentation possède des avantages et des désavantages en fonction de la façon dont on désire utiliser la liste.

L'avantage ici va porter sur la facilité d'extraction de la tête ou de la queue.

Le type-python tuple (structure de données)

Les tuples sont déclarés en utilisant les parenthèses.

On peut les lire à l'aide des boucles for.

Les tuples sont non-mutables : on ne peut pas modifier leurs contenus après création.

Quelques commandes Shells pour vous permettre de réactiver vos connaissances sur les tuples :

Tuple vide

>>> a = () >>> type(a) <class 'tuple'> >>> a ()

Tuple ne contenant qu'un seul élement (n'oubliez pas la virgule !). Le premier cas ne crée pas un tuple mais juste un integer, les parenthèses n'ayant que le rôle de ... parenthèses.

>>> a = (5) >>> type(a) <class 'int'> >>> a 5
>>> a = (5,) >>> type(a) <class 'tuple'> >>> a (5,)

Tuple de deux éléments : la tête est un integer, la queue est un tuple aussi.

>>> a = (5, (8,())) >>> type(a) <class 'tuple'> >>> a[0] 5 >>> a[1] (8, ())

Voici le début d'une proposition d'implémentation de liste sous forme de tuple qui encoderont la tête et la queue sous cette forme : (tete, queue).

Voici d'abord les descriptions des fonctions d'interface avec ce qu'elles doivent faire, quelque soit l'implémentation réelle :

nouvelleListe() -> Liste : on crée une nouvelle liste vide ().

listeA = nouvelleListe()
Le contenu de listeA est alors ().

estVide(lst:Liste) -> bool : renvoie un booléen qui vaut True si la liste lst transmise est une liste vide.

listeA = nouvelleListe()
estVide(listeA)

Et voici l'implémentation proposée pour notre liste :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
'''Implémentation de type abstrait Liste en utilisant des tuples (tete, queue)''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tuple vide () ''' return () def estVide(lst) : '''Renvoie True si la liste est vide :: param lst(Liste) :: une liste à tester :: return (bool) :: True si la liste est un tuple vide () ''' if lst == () : return True return False

On notera qu'il est plus "propre" pour des élèves en informatique de faire ceci pour la réponse de la fonction estVide 'sans la documentation ici)' :

18 19
def estVide(lst) : return lst == ()

01° Que vont renvoyer ces instructions ?

>>> a = () >>> estVide(a) ??? >>> b = None >>> estVide(b) ??? >>> c = "C" >>> estVide(c) ??? >>> d = nouvelleListe() >>> estVide(d) ???

Question subsidiaire : quelle est la seule proposition qui respecte l'interface imposée par le créateur de cette implémentation ?

...CORRECTION...

>>> a = () >>> estVide(a) True >>> b = None >>> estVide(b) False >>> c = "C" >>> estVide(c) False >>> d = nouvelleListe() >>> estVide(d) True

Seule cette dernière création avec d respecte l'interface : a crée une liste sans passer par la fonction d'interface nouvelleListe.

02° Créer maintenant la fonction d'interface suivante :

insererTete(x:Elt, lst:Liste) -> Liste : on renvoie une nouvelle liste où la tête est maintenant l'élément x et la queue la liste précédente lst.

Historiquement, dans LISP cette fonction se nomme cons (comme _cons_truct) lorsqu'elle insère bien le nouvelle élément en tant que nouvelle tête.

AIDE : il suffit de renvoyer un nouveau tuple dont la tête est notre x et la queue l'ancien tuple !

Voici un exemple d'utilisation :

>>> a = nouvelleListe() >>> a = insererTete(5, a) >>> a (5, ()) >>> a = insererTete(2, a) >>> a (2, (5, ()))
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
'''Implémentation de type abstrait Liste en utilisant des tuples (tete, queue)''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tuple vide () ''' return () def estVide(lst) : '''Renvoie True si la liste est vide :: return (bool) :: True si la liste est un tuple vide () ''' return lst == () def insererTete(x,lst) : '''Renvoie une nouvelle liste où x est la tête et liste la queue :: param x(Elt) :: un élément compatible avec votre liste qui devient la tête :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' pass

...CORRECTION...

1 2 3 4 5 6 7 8 9
def insererTete(x,lst) : '''Renvoie une nouvelle liste où x est la tête et liste la queue :: param x(Elt) :: un élément compatible avec votre liste qui devient la tête :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' return (x, lst)

On remarquera que le fait de taper a pour visualiser le contenu ne fait pas partie de l'interface : un utilisateur ne devrait donc pas utiliser ce moyen de visualiser le contenu.

03° Réaliser la fonction d'interface permettant de lire la tête :

lireTete(lst:Liste) -> Elt : on renvoie la tête de la liste lst.

Précondition : lst est une liste (ici () ou (tete,queue)), queue étant une liste.

Attention, on ne modifie pas la liste ! Dans LISP, cette fonction se nomme car (pour contents of address register)

Attention : pensez à vérifier que la liste n'est pas vide avant de chercher à lire l'index 0 (la tête).

Exemple d'utilisation

>>> a = insererTete(5, nouvelleListe() ) >>> a = insererTete(15, a) >>> lireTete(a) 15 >>> b = nouvelleListe() >>> lireTete(b) >>>

...CORRECTION...

1 2 3 4 5 6 7 8 9
def lireTete(lst) : '''Renvoie la tête de la liste, sans toucher à la liste elle-même :: param lst(Liste) :: la liste dont on désire lire la tête :: return (Elt) :: la tête voulue, None si la tête est vide ''' if not estVide(lst) : return lst[0]

04° Dernière fonction d'interface, supprimer la tête :

supprimerTete(lst:Liste) -> Liste : on renvoie une nouvelle liste où la tête est maintenant le deuxième élément (la tête de la queue précédente !). Techniquement, cela revient bien à supprimer l'ancienne tête si on enregistre cette nouvelle version dans une variable. Notez bien qu'on aurait pu nommer cette fonction recupererQueue puisque c'est ce qu'elle fait.

Précondition : lst est une liste (ici () ou (tete,queue)), queue étant une liste.

Imaginons la liste suivante :

5823

Votre fonction doit renvoyer ceci :

823

AIDE : la tête est l'index 0 de la liste et la queue est son index 1.

AIDE 2 : pensez à gérer

  1. le cas particulier de la liste vide () : pas de nouvelle tête puisque pas de queue. Il faudra renvoyer une liste vide.
  2. le cas général où la queue dans votre liste est une liste non vide.
  3. Voici un exemple d'utilisation pour chacun des cas précédents :

    >>> a = nouvelleListe() >>> b = supprimerTete(a) >>> b ()
    >>> a = insererTete(5, nouvelleListe()) >>> b = supprimerTete(a) >>> b ()
    >>> a (20, (15, (5, ()))) >>> b = supprimerTete(a) >>> b (15, (5, ())) >>> c = supprimerTete(b) >>> c (5, ())

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def supprimerTete(lst) : '''Renvoie une nouvelle liste où on a supprimé la tête de l'ancienne :: param lst(Liste) :: la liste dont on supprime la tête :: return (Liste) :: la nouvelle liste ''' if estVide(lst) : # la liste envoyée est () return nouvelleListe() else : return lst[1]

Il nous manque encore une chose qui pourrait être pratique mais qui ne fait pas partie de l'interface obligatoire : de quoi représenter la liste sans montrer son implémentation mémoire réelle.

Nous aimerions afficher (20, 15, 5) plutôt que (20, (15, (5, ()))).

05° Regarder cette fonction afficherListe.

1 2 3 4 5 6 7 8 9 10 11 12
def afficherListe(lst) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: return (str) :: un string représentant notre liste ''' reponse = [] while not(estVide(lst)) and lireTete(lst) != None : tete = lireTete(lst) reponse.append(tete) liste = supprimerTete(lst) return str(tuple(reponse))

Elle renvoie un string représentant le contenu interne de la Liste de façon totalement arbitraire : le contenu affiché n'a rien à voir avec le contenu réel (des tuples dans des tuples).

Utiliser les instructions suivantes :

>>> a = insererTete(20, (15, (5, nouvelleListe()))) >>> afficherListe(a) '(20, 15, 5)'

Question : un utilisateur peut-il avoir une idée de l'implémentation interne de notre Liste en utilisant nos fonctions d'interface ?

...CORRECTION...

Non. C'est le principe de l'interface : quelque soit l'implémentation interne, l'utilisateur doit pouvoir utiliser les fonctions d'interface pour obtenir les mêmes effets.

Tentons maintenant de créer la deuxième interface (la plus souple) à partir de celle-ci : nous voudrions par exemple parvenir à lire n'importe quelle valeur de notre liste, pas seulement la tête.

Principe de l'interface d'une liste plus souple

L'avantage de notre implémentation par rapport au type abstrait : on colle au plus près à la structure (tête, queue).

Voyons maintenant les désavantages.

Pour rappel, voici les fonctions d'interface que nous avons créé jusqu'à présent.

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
'''Implémentation de type abstrait Liste en utilisant des tuples (tete, queue)''' def nouvelleListe() : '''Renvoie une liste vide :: return (Liste) :: renvoie une liste vide sous forme d'un tuple vide () ''' return () def estVide(lst) : '''Renvoie True si la liste est vide :: return (bool) :: True si liste peut être vu comme une liste vide ''' return lst == () def insererTete(x,lst) : '''Renvoie une nouvelle liste où x est la tête et liste la queue :: param x(Elt) :: un élément compatible avec votre liste qui devient la tête :: param lst(Liste) :: la liste qui va devenir la queue de la nouvelle :: return (Liste) :: la nouvelle liste ''' return (x, lst) def lireTete(lst) : '''Renvoie la tête de la liste, sans toucher à la liste elle-même :: param lst(Liste) :: la liste dont on désire lire la tête :: return (Elt) :: la tête voulue, None si la tête est vide ''' if not estVide(lst) : return lst[0] def supprimerTete(lst) : '''Renvoie une nouvelle liste où on a supprimé la tête de l'ancienne :: param lst(Liste) :: la liste dont on supprime la tête :: return (Liste) :: la nouvelle liste ''' if estVide(lst) : # la liste envoyée est () return nouvelleListe() else : return lst[1] def afficherListe(lst) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: return (str) :: un string représentant notre liste ''' reponse = [] while not(estVide(lst)) and lireTete(lst) != None : tete =lireTete(lst) reponse.append(tete) liste = supprimerTete(lst) return str(tuple(reponse))

06° Créer la fonction d'interface lireElement en utilisant les fonctions d'interface que nous avons déjà créé : il faudra utiliser supprimerTete jusqu'à arriver à la bonne.

  • Combien de fois doit-on utiliser supprimerTete pour atteindre l'élément d'index position ?
  • Que doit-on faire une fois qu'on a récupéré la bonne liste ?

lireElement(lst:Liste, position:int) -> Elt : on renvoie l'élément stocké en position position.

listeA = (12, 15, 18, 4)
reponse = lireElement(listeA, 1)
reponse contient alors 15.

Précondition : lst est une liste et position un index valide.

Exemple d'utilisation :

>>> a = insererTete(20, (15, (5, nouvelleListe()))) >>> lireElement(a, 1) 15 >>> lireElement(a, 0) 20 >>> lireElement(a, 2) 5

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def lireElement(lst, position) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param lst(Liste) :: une liste :: param position(int) :: une valeur de position valide pour cette liste :: return (Elt) :: la valeur située à cette position ''' for x in range(position) : liste = supprimerTete(lst) return lireTete(lst)

07° Le pire des cas pour la lecture est ici le fait de vouloir lire la dernière valeur de la liste.

Question : Que vaut le coût de la lecture d'éléments pour notre implémentation :

  • A : Elle est logarithmique
  • B : Elle est linéaire
  • C : Elle est quadratique
  • D : Elle est exponentielle

...CORRECTION...

Le coût est linéaire : il va falloir supprimer autant de tête que l'index voulu et ensuite on pourra lire la valeur.

On a donc n + 1 appels à la fonction de lecture.

On voit l'index 5 : 5 têtes à supprimer avant d'atteindre la bonne.

On voit l'index 50 : 50 têtes à supprimer avant d'atteindre la bonne.

Si les données sont multipliées par 10, on a donc un temps d'exécution 10 fois plus grand.

08° Observer la fonction insererElement.

Question : Que vaut le coût de l'insertion dans le pire des cas pour notre implémentation (lorsque l'élément à rajouter est à placer en fin de liste) :

  • A : Elle est logarithmique
  • B : Elle est linéaire
  • C : Elle est quadratique
  • D : Elle est exponentielle

insererElement(x:Elt, lst:Liste, position:int) -> Liste : on renvoie une nouvelle liste où l'élément fourni x est maintenant l'élément de la liste situé en position position. On prendra ici un système de position lié à un index commençant à 0.

listeA = (12, 15, 18, 4)
listeB = inserer(5, listeA, 2)
listeB contient alors (12, 15, 5, 18, 4).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def insererElement(x, lst, position) : '''Renvoie une représentation de la Liste sous forme d'une séquence commençant par la tête :: param x(Elt) :: l'élément à insérer, compatible avec la liste :: param lst(Liste) :: une liste :: param position(int) :: une valeur d'index valide pour cette liste :: return (Liste) :: la nouvelle liste ''' les_tetes = [] for etape in range(position) : les_tetes.append(lireTete(lst)) liste = supprimerTete(lst) liste = insererTete(x, lst) for etape in range(len(les_tetes)-1,-1,-1) : liste = insererTete(les_tetes[etape], lst) return lst

Exemple d'utilisation :

>>> a = insererTete(20, (15, (5, nouvelleListe()))) >>> afficherListe(a) '(20, 15, 5)' >>> a = insererElement(12, a, 1) >>> afficherListe(a) '(20, 12, 15, 5)' >>> a = insererElement(20, a, 2) >>> afficherListe(a) '(20, 12, 20, 15, 5)'

...CORRECTION...

Si notre liste possède n éléments, on voudra le placer à l'index n-1.

On remarque qu'on a n-1 opérations de suppressions de têtes puis n-1 opérations d'insertion de têtes.

On a donc 2 * (n-1) opérations linéaires à effectuer.

On a donc 2 n - 2 opérations.

Si on néglige le -2 pour les grandes valeurs de n, on obtient 2 n opérations.

On omet le facteur multiplicateur puisqu'on ne cherche que l'évolution pour cette même structure pour deux valeurs de n différentes : on voit donc que l'insertion possède un coût en n : il s'agit d'une évolution linéaire.

Coût de l'implémentation en tuple (tête, queue)

On notera donc que dans le pire des cas :

  • La lecture est à coût linéaire (Θ(n))
  • L'insertion et la suppression est à coût linéaire (Θ(n))

Cela peut paraître correct. Mais nous allons voir qu'on peut implémenter nos listes de deux façons différentes qui vont apporter un coût constant soit à la lecture, soit à l'insertion.

  • L'implémentation en tableau pour la lecture à coût constant
  • L'implémentation en liste chaînée pour l'insertion/suppression à coût constant

2 - FAQ

Rien pour l'instant

Un coût (dans le pire des cas) linéaire en lecture et en insertion. Pas terrible. Regardons si on peut faire mieux.

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