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.
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ë :
- listeVide() → Liste
- estListeVide(lst:Liste) → bool
- longueur(lst:Liste) → int
- inserer(lst:Liste, elt:Elément, i:int) → Liste
- 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.
- 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).
- acces(lst:Liste Non Vide, i:int) → Case
- contenu(c:Case) → Elément
- 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 | |
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 :
- comment se nomme dans Python le type de la structure de données qui nous sert à construire la notre ?
- 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 ?
- L'utilisateur aura-t-il le droit d'utliser directement des expressions comme liste[i] pour lire le contenu de ses données ?
- 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 | |
...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).
- 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.
- 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)
On voit donc que la Liste après insertion est un tableau qui :
- 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 : new[i+1] = old[i]
- 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 | |
Questions
- Cette fonction modifie-t-elle la liste en place ou crée-t-elle une copie qu'elle renvoie ?
- 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 ?
- Comment est-on parvenu à décaler les bonnes valeurs dans le second tableau ? (attention : à savoir expliquer et refaire)
...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 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.
03° Quelques questions :
- Combien de cases va devoir avoir le nouveau tableau contenant la liste modifiée ?
- Va-t-on devoir décaler les cases vers la gauche (on diminue l'indice) ou vers la droite (on augmente l'indice) ?
- Doit-on décaler tous les indices du tableau initial ou y-a-t-il un indice à ne pas décaler ?
...CORRECTION...
- Une case en moins, puisqu'on supprime.
- On voit bien qu'on va devoir décaler vers la gauche, en diminuant les indices des éléments qu'on va déplacer.
- 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 | |
Déclaration à modifer
1
2
3 | |
Vous pouvez utiliser la fonction tester_supprimerTete() pour tester votre proposition.
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
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 | |
Questions
- 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 ?
- 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)
06-A° Répondre aux question ci-dessous :
- Pour insérer en indice 2, quels sont les indices des cases qui ne seront pas décalées ?
- Pour insérer en indice 2, quels sont les indices des cases qui seront décalées ?
- Pour insérer en indice i, quels sont les indices des cases qui ne seront pas décalées ?
- Pour insérer en indice i, quels sont les indices des cases qui seront décalées ?
...CORRECTION...
- On ne décale pas les cases de 0 à 1.
- On décale vers la droite les cases 2 et plus
- On ne décale pas les cases de 0 à (i-1).
- 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 | |
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 | |
Passons à la suppression n'importe où.
07-A° Répondre aux question ci-dessous :
- Pour supprimer l'élément en indice 2, quels sont les indices des cases qui ne seront pas décalées ?
- Pour supprimer l'élément en indice 2, quels sont les indices des cases qui seront décalées ?
- Pour supprimer l'élément en indice i, quels sont les indices des cases qui ne seront pas décalées ?
- Pour supprimer l'élément en indice i, quels sont les indices des cases qui seront décalées ?
...CORRECTION...
- On ne décale pas les cases de 0 à 1.
- On décale vers la gauche les cases 3 et plus
- On ne décale pas les cases de 0 à (i-1).
- 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 | |
Vous pouvez utiliser la fonction tester_supprimer() pour tester votre implémentation.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11 | |
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 :
- La Liste a dans laquelle se trouve la case
- 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 | |
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 | |
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 | |
...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 | |
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.
- listeVide() → Liste Coût CONSTANT
- estListeVide(lst:Liste) → bool Coût CONSTANT
- longueur(lst:Liste) → int Coût CONSTANT
- inserer(lst:Liste, elt:Elément, i:int) → Liste Coût LINEAIRE en θ(n)
- supprimer(lst:Liste Non Vide, i:int) → Liste Coût LINEAIRE en θ(n)
- acces(lst:Liste Non Vide, i:int) → Case Coût CONSTANT
- contenu(c:Case) → Elément Coût CONSTANT
- successeur(c:Case Non Finale) → Case Coût CONSTANT
- 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 :
Ensuite, il faut déplacer un par un les 20 000 éléments du premier tableau.
Puis on déplace les 20 000 éléments du deuxième tableau.
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 | |
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 :
Ou encore :
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 :
- On augmente de 1 l'indice maximum.
- On décale à droite n-i valeurs : celles d'indice i à n-1, qu'on place dans les cases d'indice i+1 à n.
- 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 | |
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 :
- 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.
- 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 | |
Pour juste supprimer l'ancien élément d'indice 0 sans le mémoriser :
1 | |
Voici donc notre nouvelle fonction d'interface supprimer() :
1
2
3 | |
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 | |
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 | |
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 | |
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 :
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]]
Activité publiée le 14 10 2020
Dernière modification : 23 10 2020
Auteur : ows. h.