Implémenter une Liste avec des tableaux
Nous avons implémenter une liste sous forme d'une structure de données composée d'un tuple (tête, queue).
Nous allons faire la même chose avec un tableau aujourd'hui.
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).
1 - Implémentation en tableau
Nous allons réaliser une autre implémentation, l'implémentation du type abstrait Liste en utilisant un tableau.
C'est très utile si on lit plus souvent les données qu'on ne les insère ou les supprime.
Pourquoi ? Simplement car on lit les éléments d'un tableau en un temps constant : Θ(1)
Nous allons encore une fois réaliser ceci :
Dans le cadre de cette activité, je vous fournis l'interface de base que nous allons analyser. Ensuite, vous devrez créer l'interface souple.
Commençons par les 3 fonctions d'interface les plus simples : nouvelleListe, estVide et lireTete.
01° Mémoriser ces fonctions. Observer les 3 fonctions. Répondre ensuite à ces questions :
- comment se nomme dans Python le type (pas abstrait du coup) de la structure de données utilisée ici pour implémenter notre Liste abstraite ?
- Va-t-on avoir le droit d'utiliser toutes les méthodes qu'offre Python sur ce type ?
- L'utilisateur aura-t-il le droit d'utliser directement [index] pour lire le contenu de nos données ?
...CORRECTION...
Nous utilisons le type natif list.
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).
L'utilisateur devra se limiter à utiliser nos fonctions d'interface. D'ailleurs, notre fonction lireTete intégre une vérification de la taille du tableau. Cela permettra d'éviter certaines erreurs de tentative de lecture de l'index 0 sur un tableau vide ! C'est l'un des intêret de l'interface, elle est censée éviter un certain nombre de problèmes en vérifiant la validité des changements par exemple.
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 | |
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 non-mutables : il va donc falloir créer un deuxième tableau et de décaler les éléments vers la droite.
Exemple : on veut insérer l'élément 23 dans la liste intiale (5, 10, 15, 25, 30, 35)
On voit donc que le tableau implémentant la liste après insertion
- doit posséder une case en plus
- contient les éléments de la première liste mais avec un décalage de 1 vers la droite : les index sont plus grands de 1
- possède un nouvel élément à l'index 0
02° Rajouter maintenant la fonction insererTete :
1
2
3
4
5
6
7
8
9
10
11
12
13 | |
- cette fonction modifie-t-elle la liste en place ou crée-t-elle une copie qu'elle renvoie ?
- pourquoi le tableau reponse (créé par compréhension ligne 9 ci-dessus) est-il créé avec une case supplémentaire par rapport au tableau reçu en paramètre ?
- comment est-on parvenu à décaler les bonnes valeurs dans le second tableau ? (attention : à savoir expliquer et refaire)
- Programmation interne : le développeur va-t-on avoir le droit d'utiliser toutes les méthodes qu'offre Python sur ce type list qu'on utilise pour nos tableaux ?
- Interface externe : l'utilisateur aura-t-il le droit d'utiliser directement [index] pour lire le contenu de nos données du coup ?
...CORRECTION...
- Pas d'effet de bord : on crée un tableau ayant une case en plus, on le remplit puis on le renvoie.
- On insère une nouvelle valeur, il vaut bien une case en plus non ?
- Voir Lignes 10-11 : à l'aide d'une boucle sur les index de la liste-tableau d'origine, on crée les cases de la copie en décalant de 1 vers la droite les valeurs. On rajoute donc 1 à l'index.
- Non, la personne qui code ces fonctions ne pourra pas utiliser toutes la panoplie des méthodes du type list-python. Si on décide d'utiliser des tableaux statiques, on ne devra pas par exemple utiliser append. Si on décide d'utiliser des tableaux dynamiques, on pourra cette fois rajouter et supprimer directement des cases. Le tout est de savoir comment on veut implémenter nos listes.
- Non, l'utilisateur n'en a pas le droit : cette utilisation ne figure pas explicitement dans l'interface fournie. Dans la description de l'interface, on aurait très bien pu remplacer
lireTeteparliste[0], mais on ne l'a pas fait. On respecte le travail et les choix de celui qui a conçu l'interface. Si ça tombe, il a une très bonne raison d'avoir sélectionné la première façon de faire.
On sait maintenant créer des listes, lire la tête et insérer des têtes.
Reste à savoir supprimer les têtes.
03° Combien de cases va devoir avoir le tableau contenant la liste modifiée ? Va-t-on devoir décaler les cases vers la gauche (on diminue l'index) ou vers la droite (on augmente l'index) ?
...CORRECTION...
Une case en moins, puisqu'on supprime.
On voit bien qu'on va devoir décaler vers la gauche, en diminuant les index des éléments qu'on va déplacer.
04° Compléter le code de la fonction supprimerTete dont on vous donne le prototype et la documentation.
Attention, pensez d'abord à gérer le cas de la liste vide (on renvoie alors une liste vide) avant de commencer à déplacer les éléments.
Prototype
1 | |
Code à compléter
1
2
3
4
5
6
7
8 | |
Remarque : on remarquera que Python ne connait pas notre type "Liste". Le module typing permet par contre de le faire et donc ensuite de vérifier les préconditions avec des assertions si on veut.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | |
Voilà. Nous sommes parvenus à implémenter nos listes sous forme interne de tableaux.
Voici le code final de notre implémentation du type abstrait LISTE en utilisant des tableaux et en fournissant l'interface de base d'accès uniquement à la tête.
Notre interface possède les 5 fonctions de base plus une fonction optionnelle d'affichage globale de la liste.
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 | |
05° Mettre les fonctions en mémoire. Utiliser l'interface pour créer une liste, rajouter des têtes, observer la liste, supprimer la tête et observer à nouveau la liste.
L'utilisateur n'utilisant que les fonctions d'interface pourra-t-il se rendre compte de l'implémentation interne réalisée sur le type abstrait Liste ?
...CORRECTION...
>>> a = nouvelleListe()
>>> afficherListe(a)
'()'
>>> a
[]
>>> a = insererTete(5, a)
>>> afficherListe(a)
'(5,)'
>>> a
[5]
>>> a = insererTete(15, a)
>>> afficherListe(a)
'(15, 5)'
>>> a
[15, 5]
>>> a = supprimerTete(a)
>>> afficherListe(a)
'(5,)'
>>> a
[5]
Comme on peut le voir sur les exemples, l'utilisateur ne peut utiliser normalement que la fonction afficherListe et ne voit donc 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.
Nous avons réalisé l'interface basique ne gèrant que la tête. Passons à l'interface plus souple, bien pratique pour gérer véritablement des listes comme on le désire.
06° Compléter le code de la fonction lireElement dont on vous donne le prototype et la documentation.
On veut pouvoir accéder directement à la valeur d'un élément. Il faudra bien entendu utiliser la lecture directe du tableau dans le code interne : c'est l'avantage majeur d'un tableau : l'accès à coût constant aux éléments.
Prototype
1 | |
Code à compléter
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
Un peu plus dur : l'insertion. Un exemple d'insertion d'un élément valant 23 sur l'index 2 dans une liste stockée dans la variable a :
>>> insererElement(23, a, 2)
07° Compléter le code de la fonction insererElement dont on vous donne le prototype et la documentation.
Demandez-vous ce qu'on ne doit pas bouger, ce qu'on doit insérer et ce qu'on doit déplacer.
vous pourrez vous inspirer du code de insererTete.
Prototype
1 | |
Code à compléter
1
2
3
4
5
6
7
8
9
10 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | |
Dernière fonctionnalité : la suppression.
08° Compléter le code de la fonction supprimerPosition dont on vous donne le prototype et la documentation.
Attention, pensez d'abord à gérer le cas de la liste vide (on renvoie alors une liste vide) avant de commencer à déplacer les éléments.
Prototype
1 | |
Code à compléter
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | |
09° Estimer les coûts (complexité) dans le pire des cas de nos quatre fonctions lecture-modification-insertion-suppression en considérant que l'implémentation Python du type natif list correspond à un tableau dynamique.
...CORRECTION...
Lecture : coût constant (on va directement en mémoire, sans passer par la lecture des autres valeurs)
Insertion : coût linéaire, il faut déplacer l'intégralité des données une par une.
Suppression : coût linéaire pour les mêmes raisons.
Coût de l'implémentation en tableau
On notera donc que dans le pire des cas :
- La lecture d'une valeur est à coût constant (Θ(1))
- L'insertion et la suppression est à coût linéaire (Θ(n))
Rappel : 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))
Notre nouvelle implémentation en tableau est donc strictement identique pour l'utilisateur vis à vis de l'interface (il ne peut pas savoir laquelle il utilise). Par contre, l'implémentation tableau aura de meilleurs performances en lecture.
La totalité du code pour mémoire :
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 | |
2 - Implémentation en utilisant directement list de Python
Si le type natif list se nomme ainsi, c'est bien qu'il permet l'implémentation de Liste. Par contre, en interne, il s'agit d'une tableau dynamique qui possède plus de fonctions d'interface que celle du type abstrait TABLEAU DYNAMIQUE. La structure de données nommée list est donc un savant mélange de fonctionnalités des tableaux et des listes.
Voici comment on pourrait créer notre interface en utilsant les Pythonneries associées à ce type natif.
Insertion de nouveaux éléments via les outils présents dans Python
Vous connaissez déja la méthode append qui permet de rajouter un nouvel élément à la fin de nos objets de type natif list-Python.
Attention, append modifie la variable sur laquelle on agit MAIS elle ne renvoie rien : il faudra donc l'utiliser sur une copie du tableau et renvoyer cette copie ensuite.
Votre fonction devra toujours renvoyer la copie modifiée.
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.
1
2
3
4
5
6
7
8
9
10
11
12 | |
ERREUR COURANTE
Ne faites donc jamais ceci : insert étant une fonction-procédure, comme append, vous allez renvoyer ... None.
1
2 | |
Suppression d'un élément via les outils présents dans Python
De la même façon, il existe une méthode nommée pop qui permet d'extraire un élément (la méthode renvoie l'élément) et modifie le tableau en place.
On peut donc l'utiliser pour juste modifier le tableau, sans mémoriser la valeur extraite.
1
2
3
4
5
6
7
8
9
10
11 | |
Erreur courante
Nous aurions pu faire cela, même si on ne désire pas stocker la valeur extraite :
1
2
3 | |
Mais, il ne faut pas faire ceci :
1
2 | |
Avec ce code, vous allez renvoyer l'élément supprimé et pas le nouveau tableau !
Au final, nous allons obtenir le même effet pour l'utilisateur, si ce n'est que le code utilise les fonctionnalités de Python et que nous ne connaissons pas les coûts de ces fonctions. A priori, elles sont performantes mais il faudrait aller voir le code interne de Python pour le savoir.
On notera qu'il est pénible de devoir fournir la position lorsqu'on veut placer ou supprimer le dernier élément. Comment faire pour simplifier la démarche de l'utilisateur ? Utiliser des valeurs par défaut pour ce paramètre.
Index -1 avec Python
Le code ci-dessous profite d'une Pythonnerie que vous n'avez pas à connaître : un index de -1 est normalement impossible. En Python, il sera compris comme voulant dire : le dernier élément.
L'index -2 correspond donc à l'avant-dernier élément, ect ...
10° Placer cette nouvelle implémentation ci-dessous en mémoire. Utilisez alors les fonctions pour vous convaincre qu'un utilisateur ne peut pas savoir quel code interne implémente le type abstrait Liste.
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 | |
3 - FAQ
On m'a dit de faire attention aux copies de tableaux. C'est vrai ?
Oui.
Activité publiée le 20 09 2022
Dernière modification : 21 09 2022
Modification : Andjekel
Source : ows. h.