Tableaux statiques et dynamiques

Identification

Infoforall

15 - Tableau statique et dynamique


Vous allez aujourd'hui pourquoi on peut accéder en temps constant à n'importe quelle case d'un tableau, même s'il comporte 6 milliards de case.

En nous allons découvrir un peu plus de choses sur le type list de Python. Notamment qu'il s'agit en réalité d'un tableau dynamique et non pas d'un tableau purement statique.

Documents de cours PDF : .PDF

Sources latex : .TEX et entete.tex et licence.tex

1 - Tableaux statiques

(Rappel) 1.1 TABLEAU STATIQUE : définition

Un tableau statique est un tableau comportant un nombre de cases fixé à la création.

Un tableau est un conteneur formant une collection ordonnée d'éléments ayant tous le même type. On peut donc avoir un tableau statique d'integers, ou un tableau statique de floats par exemple.

Les cases sont identifiées par un numéro nommé indice (index en anglais).

Voici deux exemples de tableaux :

Un tableau de caractères de 3 cases (indices 0-1-2) 

Indice 0 1 2
Elément 'A' 'B' 'C'

Un tableau de flottants de 4 cases (indices 0-1-2-3) :

Indice 0 1 2 3
Elément 5.89 12.56 15.89 5.0
flowchart LR D([Variable]) --> M([conteneur-tableau]) M -- indice 0 --> A([élément 0]) M -- indice 1 --> B([élément 1]) M -- indice 2 --> C([élément 2])

Notez bien que la première case est la case d'indice 0, pas celle d'indice 1. Si un tableau possède 20 cases, les indices disponibles vont de 0 à 19.

1.2 RAM

Mémoire vive

La mémoire est un ensemble de bits pouvant contenir 0 ou 1 et regroupés en octets.

La mémoire vive est la zone dans laquelle on place les programmes en cours d'exécution et les données sur lesquelles ils travaillent.

RAM

RAM est l'acronyme de Random Access Memory, "mémoire à accès aléatoire" ?

"Accès aléatoire" est à comprendre comme en opposition à "accès séquentiel" : en accès séquentiel, on doit parcourir les cases 0, 1, 2, 3, ... 98, 99 pour atteindre la case 100.

L'accès aléatoire veut donc dire qu'on peut atteindre à coût constante une case mémoire pourvu qu'on connaisse son adresse.

Exemple visuel

Voici une petit partie des zones-mémoires d'un ordinateur. Accèder à la case 239 ne prend pas plus de temps qu'accèder à la case 200

Contenu de la mémoire
Un petit apercu de la mémoire

Chaque case représente un octet dont le contenu est donnée comme un entier non signé. On préfère noter 45 plutôt que 00101101.

01° Que vaut l'octet stocké à l'adresse 216 ?

Contenu de la mémoire

...CORRECTION...

On voit qu'on y a stocké un octet correspont à N = 72 10

02° Peut-on savoir ce qui est stocké en mémoire si on ne connait pas l'encodage qui a été utilisé ?

...CORRECTION...

Non. On ne peut pas le savoir.

Il s'agit peut-être effectivement d'un contenu mémoire stocké uniquement sur un octet.

S'il s'agit d'un entier, il s'agit bien de 72.

S'il s'agit d'un caractère, 72 correspond à la lettre H majuscule en ASCII.

>>> chr(72) 'H'

Mais il est probable également qu'il s'agisse d'un octet faisant partie d'un encodage sur plusieurs octets : un grand nombre entier, un flottant ou même une image. Dans ce cas, il est impossible de savoir ce que nous sommes en train de visualiser : si on ne sait pas comment un contenu a été encodé (transformer en octet), il est presque impossible de le décoder.

1.3 Principe d'un tableau

Espace des noms

L'espace des noms fait le lien à coût constant entre le nom d'une variable (t ci-dessous) et une adresse-mémoire (500 ci-dessous).

Propriétés générales d'organisation

En informatique, un tableau désigne un conteneur de données qui a les propriétés suivantes :

  • Les octets sont consécutifs en mémoire à partir d'une première adresse A.
  • Le tableau occupe une largeur de L octets.
  • Chaque case encode le même type de données, et comporte C octets.

Exemple : considérons un tableau de 1000 integers (on prendra 4 octets par entier).

    Principe du tableau dans l'espace des noms
  • Ici le premier octet du tableau est stocké à l'adresse A = 500 dans la mémoire.
  • Chaque case contient C = 4 octets.
  • Le tableau occupe donc L = 1000 * 4 = 4000 octets consécutifs allant de l'adresse 500 à l'adresse 4499.
  • Les 4 octets d'adresse 500-501-502-503 (oranges) représentent collectivement le premier entier.
Indice des cases
  • On identifie chaque case par un simple numéro qu'on appelle indice.
  • t[0] veut donc dire d'aller décoder le contenu DES CASES qui correspondent à l'indice 0 : les cases 500 - 501 - 502 - 503 ici.
  • t[1] veut donc dire d'aller décoder le contenu DES CASES qui correspondent à l'indice 1 : les cases 504 - 505 - 506 - 507 ici.
Principe des octets consécutifs
Exemple visuel

Sur cet autre exemple, les données, stockées à partir de l'adresse 200, ont toutes une taille de 4 octets.

Mémoire avec groupement de 4 octets
Les indices correspondant aux groupements de 4 octets
1.4 Accès aux cases à coût CONSTANT

Accès à Coût CONSTANT

L'accès à n'importe quelle case du tableau se fait à coût constant.

Voyons pourquoi.

Explications

1 - Trouver l'adresse du tableau via l'espace des noms : constant

L'espace des noms fait le lien entre le nom d'un tableau et l'adresse A de son premier octet, à coût CONSTANT .

2 - Calcul de l'adresse d'une case du tableau : constant

Connaissant l'adresse A du début du tableau (500 ou 200 sur nos exemples), la largeur C des cases du tableau (4 sur les exemples), et l'indice i de la case voulue dans le tableau, on peut calculer facilement l'adresse du premier octet à lire :

Adresse du premier octet à lire = A + i * C

  • t[0] : commence à 500 + 0*4 = 500
  • t[1] : commence à 500 + 1*4 = 504
  • t[2] : commence à 500 + 2*4 = 508
  • t[3] : commence à 500 + 3*4 = 512
  • ...

3 - RAM : constant

L'accès à une case-mémoire dont on connait l'adresse est à coût CONSTANT.

4 - Lire 4 cases

4 actions à coût CONSTANT donc coût CONSTANT au total.

5 - Conclusion : obtenir la valeur stockée dans une case

On obtient donc un coût CONSTANT pour une action de type t[i] en Python.

03° Soit un tableau d'integers sur 4 octets, il commence à l'adresse 200. Quelle est l'adresse de l'élément d'indice 100 ?

...CORRECTION...

Il suffit de calculer 200 + 4*100 = 600.

04° Soit un tableau de flottants sur 8 octets, il commence à l'adresse 10000. Quelle est l'adresse de l'élément d'indice 10 ?

...CORRECTION...

Il suffit de calculer 10000 + 8*10 = 10080.

Nous verrons plus tard d'autres structures de données ayant d'autres avantages et d'autres inconvénients. Comme toujours, il faudra étudier le problème et choisir ensuite la structure la plus adaptée à sa résolution.

Pour l'instant, nous nous limiterons aux tableaux.

05° En Python, quelle est la correspondance que permet de réaliser l'espace des noms ?

  1. Nom de variable - Contenu mémoire
  2. Nom de variable - Longueur de la zone mémoire
  3. Nom de variable - Adresse mémoire
  4. Adresse mémoire - Contenu mémoire

...CORRECTION...

C : l'espace des noms permet de faire une liaison entre le nom d'une variable et une adresse mémoire.

06° Donner le contenu du tableau Python t en utilisant la représentation de principe ci-desous (on peut voir qu'on considère que la largeur des cases du tableau est de 8 octets) :

Image de la mémoire
Espace des noms et Espace mémoire

...CORRECTION...

On parvient à voir que la case 0 référence l'adresse mémoire 22352 qui référence le contenu 5.

L'indice 1 référence l'adresse 26608 qui référence elle-même le contenu 'a'.

L'indice 2 référence l'adresse 08848 qui référence elle-même le contenu "Hello".

On en déduit que le tableau équivalent contient [5, 'a', "Hello"] et n'est donc pas homogène en apparence.

07° Les tableaux Python n'ont pas à être homogènes. Pourquoi à votre avis ?

  1. Les cases peuvent être de tailles différentes
  2. Ils sont homogènes : ce sont des tableaux d'adresses : chaque case contient en réalité l'adresse du contenu de cet indice.
  3. Ce sont en réalité des dictionnaires
  4. La taille de chaque case est fixée à 10000 octets, et Python remplit au besoin avec des octets "vides".

...CORRECTION...

A : Impossible, sinon on ne pourrait pas calculer à coût constant l'adresse de la case voulue en fonction de son indice.

B : c'est bien cela. Chaque case contient en réalité la référence d'une zone-mêmoire (stockée sur 4 octets (sur les machines 32 bits) ou 8 octets (sur les machines 64 bits).

Il s'agit donc d'un mécanisme en 3 temps.

Lorsqu'on tape t[3], Python

  1. chercher l'adresse du tableau t en utilisant l'espace des noms,
  2. calcule l'adresse de la case en considèrant des cases de largeur 4 ou 8 octets selon le système, y trouve ...une adresse puis
  3. va lire le contenu qu'on peut trouver à cette nouvelle adresse.

C : vous ne pouvez pas le savoir pour le moment, mais c'est même plutôt l'inverse : les dictionnaires sont en réalité implémentés sous forme de tableaux assez particuliers. Vous verrez comment en terminale NSI.

D : pourquoi pas mais... Si on veut stocker un tableau de caractères ne nécessitant qu'un octet par caractère, on aurait alors besoin de 50000 octets pour un tableau de 5 caractères qui n'en nécessite que 5. Pas très optimal.

1.9 Type list : un tableau non homogène

Le type natif list de Python permet de créer des tableaux dont le contenu est en apparence non-homogène.

Comment est-ce possible ?

En réalité, un type list référence un tableau d'adresses (8 octets sur les systèmes 64 bits). Dans les cases, on stocke donc l'adresse du contenu qu'on veut mettre à cette position et pas directement le contenu.

Grace à cette stratégie, on obtient des tableaux qui semblent ne pas avoir exactement le même type dans chaque case.

Image de la mémoire
Espace des noms et Espace mémoire

Vous savez maintenant pourquoi les tableaux statiques sont homogènes et pourquoi Python permet d'implémenter des tableaux non-homogènes.

Nous allons maintenant voir que le type list de Python est en réalité un tableau dynamique, et pas simplement un tableau statique.

2 - Tableaux dynamiques

2.1 TABLEAU DYNAMIQUE : présentation rapide

Tableau statique avec le type list

Dans un tableau statique :

  1. toutes les cases contiennent le même type de données et
  2. le nombre de cases est constant : après création, on ne peut pas en supprimer ou en rajouter.

Les tableaux statiques s'implémentent en Python à l'aide du type list. D'ailleurs Python accepte des contenus de types différents dans les différentes cases contrairement à un tableau statique standard.

Type list : tableau dynamique

Le list Python est encore plus flexible que cela : il s'agit d'un tableau dynamique (on peut ajouter ou supprimer des cases).

On pourrait donc créer une list Python contenant trois cases comme ceci :

exemple = [1, 2, 5]

Et plus tard dans le programme, le tableau pourrait faire référence à 6 cases :

[1, 2, 5, 10, 20, -10]

Ou même simplement 1 case :

[5]

2.2 TABLEAU DYNAMIQUE : list.append()

Principe et syntaxe

La méthode append() ajoute une case contenant la valeur voulue à la fin du tableau. Toujours à la fin.

La syntaxe est la suivante :

nom_du_tableau.append(contenu_de_la_nouvelle_case)

Insertion en fin : coût CONSTANT, c'est donc une opération efficace qu'on peut utiliser sans dégrader les performances du programme.

Exemple
>>> tab = [] >>> tab.append(10) >>> tab [10] >>> tab.append(20) >>> tab [10, 20] >>> tab.append(30) >>> tab [10, 20, 30] >>> tab.append(0) >>> tab [10, 20, 30, 0]

L'élément est toujours ajouté à la fin du tableau.

Modifie en place, aucune réponse renvoyée

La méthode ne renvoie aucune réponse : elle modifie en place le tableau sur lequel elle doit agir.

Une erreur très courante, qu'il ne faut donc jamais faire : réaliser une affectation de ce type :

>>> tab = [10, 20, 30] >>> tab = tab.append(100) >>> tab

Ici, on place dans tab le résultat renvoyé par append(), à savoir... rien. On a donc involontairement "vidé" tab. Cela ne provoque pas d'interruption du programme : c'est une erreur sémantique.

⚙ 08° Réaliser ceci :

  1. Exécuter mentalement ce programme suivant puis donner l'affichage provoqué.
  2. 1 2 3 4 5 6 7 8 9
    couleurs = [] couleurs.append("red") couleurs.append("green") couleurs.append("blue") couleurs.append("yellow") couleurs.append("cyan") couleurs.append("magenta") print(couleurs)
  3. Lancer le programme pour vérifier.

...CORRECTION...

Ligne 1 : couleurs = [] Ligne 2 : couleurs = ['red'] Ligne 3 : couleurs = ['red', 'green'] Ligne 4 : couleurs = ['red', 'green', 'blue'] Ligne 5 : couleurs = ['red', 'green', 'blue', 'yellow'] ...

On agit ainsi en rajoutant toujours le nouvel élément à la fin du tableau.

⚙ 09° Réaliser ceci :

  1. Déterminer quelles sont les 4 premières valeurs qui seront intégrées au tableau multiples7, vide initialement en ligne 1.
  2. 1 2 3 4 5 6 7
    multiples7 = [] for x in range(1000000): if x % 7 == 0: multiples7.append(x) print(multiples7)
  3. Lancer le programme pour vérifier.
  4. Que peut-on dire du coût de cette création en fonction du nombre n de nombres à tester ? Coût constant, logarithmique, linéaire ou quadratique ?
  5. Vérifier que ce programme permet d'expliquer comment réaliser cette création par compréhension :
  6. >>> tab = [x for x in range(1000000) if x % 7 == 0]

...CORRECTION...

⚙ 10° Réaliser ceci :

  1. Compléter ce programme pour qu'il parvienne à concaténer ces deux tableaux (créer un nouveau tableau qui contient les éléments du tableau A puis les éléments du tableau B).
  2. 1 2 3 4 5 6 7 8
    animaux = ["Chat", "Chien", "Poisson"] animaux_sauvages = ["Lion", "Tigre", "Éléphant"] for i in ... : # Pour chaque indice possible du tableau animaux_sauvages nouveau = ... # Récupère ce nouvel animal ... # Ajoute cet animal aux autres animaux print(animaux)
  3. Que peut-on dire du coût du rajout en fonction du nombre d'éléments ns d'animaux sauvages ? Coût constant, logarithmique, linéaire ou quadratique ?
  4. Vérifier que ce programme permet d'expliquer comment Python réaliser ceci :
  5. 1 2 3 4
    animaux = ["Chat", "Chien", "Poisson"] animaux_sauvages = ["Lion", "Tigre", "Éléphant"] animaux = animaux + animaux_sauvages

...CORRECTION...

1 2 3 4 5 6 7 8
animaux = ["Chat", "Chien", "Poisson"] animaux_sauvages = ["Lion", "Tigre", "Éléphant"] for i in range(len(animaux_sauvages)): # Pour chaque indice possible du tableau animaux_sauvages nouveau = animaux_sauvages[i] # Récupère ce nouvel animal animaux.append(nouveau) # Ajoute cet animal aux autres animaux print(animaux)

Le rajout n'intervient que sur les lignes 4-5-6.

L4 : nous allons réaliser la boucle ns fois : autant de fois que d'animaux sauvages.

Pendant la boucle :

  • L5 : accès à une case de tableau donc CONSTANT
  • L6 : ajout en fin de tableau donc CONSTANT

On réalise ns fois des actions à coût constant, le coût est donc LINEAIRE par rapport à nd :

𝓞(nd*(1+1)) = 𝓞(2*nd) = 𝓞(nd).

2.3 TABLEAU DYNAMIQUE : list.pop() sans argument

Principe et syntaxe, version sans argument

La méthode pop() supprime la dernière case d'un tableau ET renvoie la valeur supprimée : cela permet de la stocker si on le désire.

La syntaxe est la suivante :

nom_du_tableau.pop()

Suppression en fin (list) : coût CONSTANT, c'est donc une opération efficace qu'on peut utiliser sans dégrader les performances du programme.

Exemple
>>> tab = [10, 20, 30] >>> tab.pop() # supprimer sans mémoriser >>> tab [10, 20] >>> a = tab.pop() # on stocke le 20 qu'on va supprimer >>> tab [10] >>> tab.pop() # supprimer sans mémoriser >>> tab [] >>> a 20 >>> tab.pop() # supprimer une case d'un tableau vide ? IndexError: pop from empty list
Gérer le cas problématique

Attention : vouloir supprimer une case d'un tableau vide lève une exception.

Si vous n'êtes pas certain qu'il reste une case à supprimer, il faut donc tester avant d'agir :

>>> tab = [10] >>> tab.pop() # supprimer la case de fin >>> tab [] >>> if tab: tab.pop() # si tab n'est pas vide >>> if len(tab) > 0: tab.pop() # si tab n'est pas vide

Il n'y aura d'activation de la méthode que si le tableau contient un élément au moins.

Modifie en place et renvoie la valeur supprimée

La méthode renvoie la valeur supprimée. C'est le développeur qui décidera ce qu'il veut en faire. Ne pas réaliser d'affectation permet donc de simplement supprimer la valeur définitivement.

⚙ 11-A° On veut supprimer et afficher un par un les éléments en fin de tableau.

  1. Compléter ce programme pour qu'il réalise cela, jusqu'à ce qu'il soit entièrement vidé.
  2. 1 2 3 4 5 6 7 8
    memoire1 = ["Alice", "Bob", "Charlie", "Dana" ,"Elodie", "Fabien"] while len(...) > ...: # Tant que memoire1 n'est pas vide prenom = ... # Supprime et mémorise le dernier prénom de memoire1 ... # Affiche l'élément supprimé print(memoire1)
  3. Que peut-on dire du coût de cette suppression ? Coût constant, logarithmique, linéaire ou quadratique ?

...CORRECTION...

1 2 3 4 5 6 7 8
memoire1 = ["Alice", "Bob", "Charlie", "Dana" ,"Elodie", "Fabien"] while len(memoire1) > 0: # Tant que memoire1 n'est pas vide prenom = memoire1.pop() # Supprime et mémorise le dernier prénom de memoire1 print(prenom) # Affiche l'élément supprimé print(memoire1)

La suppression n'intervient que sur les lignes 4-5.

On réalise la boucle n fois si n est le nombre d'éléments dans le tableau.

La ligne 5 est une action à coôt CONSTANT.

Le coût est donc LINEAIRE par rapport à n :

𝓞(n*1) = 𝓞(n).

On remarquera que le print() est une action qui demande beaucoup de temps. On évitera de placer des print() dans des boucles si le but est d'aller vite.

⚙ 11-B° On veut maintenant supprimer un à un les éléments de fin d'un tableau et les placer à la fin d'un deuxième tableau.

  1. Compléter ce programme pour qu'il parvienne à supprimer une par une les dernières cases du tableau jusqu'à ce qu'il soit entièrement vidé.
  2. 1 2 3 4 5 6 7 8 9
    memoire1 = ["Alice", "Bob", "Charlie", "Dana" ,"Elodie", "Fabien"] memoire2 = [] while len(...) > ...: # Tant que memoire1 n'est pas vide prenom = ... # Supprime et mémorise le dernier prénom de memoire1 ... # Place ce prénom en fin de memoire2 print(memoire1) print(memoire2)
  3. Quelle est la propriété liée à l'ordre que possède le deuxième tableau par rapport au premiert ?
  4. Que peut-on dire du coût de cette action ? Coût constant, logarithmique, linéaire ou quadratique ?
  5. Au vu du programme réalisé, de son action et de son coût, que pouvez-vous dire du coût de la méthode reverse() qu'on présente ici mais qui n'est pas à connaître ou à utiliser en NSI :
  6. >>> tab = [10, 20, 30, 40, 50] >>> tab.reverse() >>> tab [50, 40, 30, 20, 10]

...CORRECTION...

1 2 3 4 5 6 7 8 9
memoire1 = ["Alice", "Bob", "Charlie", "Dana" ,"Elodie", "Fabien"] memoire2 = [] while len(memoire1) > 0: # Tant que memoire1 n'est pas vide prenom = memoire1.pop() # Supprime et mémorise le dernier prénom de memoire1 memoire2.append(prenom) # Place ce prénom en fin de memoire2 print(memoire1) print(memoire2)

On voit que memoire2 contient les prénoms mais dans l'ordre inverse.

L'inversion intervient sur les lignes 4-5-6.

L4 : nous allons réaliser la boucle n fois : autant de fois que de prénoms dans la mémoire 1.

Pendant la boucle :

  • L5 : suppression d'une case de fin : CONSTANT
  • L6 : ajout en fin : CONSTANT

On réalise n fois des actions à coût constant, le coût est donc LINEAIRE par rapport à n :

𝓞(n*(1+1)) = 𝓞(2*n) = 𝓞(n).

On peut donc supposer que la méthode reverse() agit également à coût linéaire.

2.4 TABLEAU DYNAMIQUE : list.pop(i) avec argument

Principe et syntaxe, version avec argument

La méthode pop(i) supprime la case d'indice i du tableau ET renvoie la valeur supprimée : cela permet de la stocker si on le désire.

La syntaxe est la suivante :

nom_du_tableau.pop(i)

Suppression sur une position quelconque : coût LINEAIRE, c'est donc une opération à utiliser avec précaution car elle peut dégrader les performances du programme si le tableau possède beaucoup de cases.

Exemple
>>> tab = [10, 20, 30] >>> tab.pop(1) # supprimer la case 1 sans mémoriser >>> tab [10, 30] >>> a = tab.pop(0) # on stocke le 10 qu'on va supprimer >>> tab [30] >>> a 10

⚙ 12° On désire supprimer systématiquement l'élément du mileu d'un tableau totalement aléatoire.

  1. L3 : Quel est le plus petit nombre de cases nc possible ? Le plus grand nombre ?
  2. L5 : Expliquer cette création par compréhension.
  3. L10-L12 : Compléter le programme pour qu'il parvienne bien à supprimer et afficher l'élément central.
  4. L12 : Quel est le coût de cette ligne qui supprime une case au milieu ?
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    import random nc = random.randint(10, 50) t = [random.randint(10, 99) for _ in range(nc)] print(t) g = 0 # indice de gauche d = len(t) - 1 # indice de droite m = ... # indice du milieu valeur = ... # supprime et récupère la valeur du milieu print(valeur) # affiche cette valeur print(t)

...CORRECTION...

L3 : il y aura entre 10 et 50 cases dans le tableau.

L5 : Crée un tableau t par comphénsion où, pour nc cases, la case contient une valeur aléatoire entre 10 et 99.

1 2 3 4 5 6 7 8 9 10 11 12 13 14
import random nc = random.randint(10, 50) t = [random.randint(10, 99) for _ in range(nc)] print(t) g = 0 # indice de gauche d = len(t) - 1 # indice de droite m = (g+d) // 2 # indice du milieu valeur = t.pop(m) # supprime et récupère la valeur du milieu print(valeur) # affiche cette valeur print(t)

La ligne 12 supprime la case avec t.pop(m). Cette action est à coût linéaire.

⚙ 13° Nous allons expliquer pour l'utilisation de pop(i) est linéairé en i.

  1. L3 : quel est l'indice le plus grand du tableau t au départ ?
  2. Si on veut supprimer l'indice 2 référençant 1000, quels seront les indices des cases à supprimer et mémoriser avec pop() (suppression du dernier élément) de façon à ce que l'indice i soit le dernier indice du tableau t ?
  3. t = [10, 20, 1000, 50, 70, 90]

  4. L28 : Que contient sur les données de l'exemple nb_a_memoriser ? Quel est le lien avec les contenus des indices qu'il faudrait supprimer et mémoriser ailleurs ?
  5. L29-31 : Expliquer ce que va contenir le tableau recup après exécution de la boucle. Que constate-t-on vis à vis de l'ordre des éléments lorsqu'on utilise pop() sur un tableau et append() sur l'autre ?
  6. L38 : Quel est l'indice dans le tableau initial de l'élément qu'on vient de supprimer ?
  7. L45-47 : Expliquer ce que va contenir le tableau t après exécution de la boucle.
  8. Justifier à l'aide de ce programme que supprimer la case d'indice i est à coût linéaire.
  9. 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
    # Variables globales utilisables par les fonctions t = [10, 20, 1000, 50, 70, 90] # Le tableau qu'on veut modifier m = [] # Un tableau servant de mémoire # Définition des fonctions def affichage(message:str) -> None: """Affiche le message et les tableaux t et memoire""" print(message) print("t référence ", t) print("m référence ", m) print() # Programme principal i = 2 # L'indice où on veut supprimer i_fin = len(t) - 1 # L'indice final dans le tableau t initial affichage("Situation initiale") # Phase 1 : supprime de t et mémorise vers memoire nb_a_memoriser = i_fin - i # On calcule le nombre de cases à mémoriser avant la i for _ in range(nb_a_memoriser): # Réalise ceci nb_a_memoriser fois v = t.pop() # Supprime et mémorise le dernier élément de t m.append(v) # Place le à la fin de m affichage("Après la phase 1") # Phase 2 : supprimer l'élément d'indice i voulu t.pop() # Supprimer un élément de t (il s'agit de l'élément i) affichage("Après la phase 2") # Phase 1 : supprime de memoire et mémorise vers t for _ in range(nb_a_memoriser): # Réalise ceci nb_a_memoriser fois v = m.pop() # Supprime et mémorise le dernier élément de m t.append(v) # Place le à la fin de t affichage("Après la phase 3")

...CORRECTION...

2.5 TABLEAU DYNAMIQUE : list.remove(x)

Principe et syntaxe

La méthode remove(x) supprime la première case contenant x dans le tableau. Attention, elle ne renvoie rien.

La syntaxe est la suivante :

nom_du_tableau.remove(valeur_a_supprimer)

Suppression d'un élément quelconque : coût LINEAIRE, c'est donc une opération à utiliser avec précaution car elle peut dégrader les performances du programme si le tableau possède beaucoup de cases.

Exemple
>>> tab = [10, 20, 30, 10, 40] >>> tab.remove(20) # supprimer la case qui référence 20 >>> tab [10, 30, 10, 40] >>> tab.remove(10) # supprimer la 1er case qui référence 10 >>> tab [30, 10, 40] >>> tab.remove(10) # supprimer la case qui référence 10 >>> tab [30, 40] >>> tab.remove(10) # supprimer une case qui référence 10 ? ValueError: list.remove(x): x not in list
Gérer le cas problématique

Attention, tenter de supprimer une valeur qui n'existe pas lève une exception.

Si vous n'êtes pas certain qu'un élément que vous voulez supprimer est présent, il faut donc tester avant d'agir :

>>> tab = [10, 20, 30, 10, 40] >>> tab.remove(20) # supprimer la case qui référence 20 >>> tab [10, 30, 10, 40] >>> if 50 in tab: tab.remove(50)

Il n'y aura pas d'activation de la méthode puisque 50 n'est pas dans le tableau. Et donc pas d'erreur.

Modifie en place, aucune réponse renvoyée

La méthode ne renvoie aucune réponse : elle modifie en place le tableau sur lequel elle doit agir.

Une erreur très courante, qu'il ne faut donc jamais faire : réaliser une affectation de ce type :

>>> tab = [10, 20, 30] >>> tab = tab.remove(20) >>> tab

Ici, on place dans tab le résultat renvoyé par remove(), à savoir... rien. On a donc involontairement vidé tab de tout contenu. Notez que cela ne provoque pas d'erreur, c'est une erreur de sémantique.

⚙ 14° Nous allons retrouver le coût linéaire de la méthode remove() simplement en analysant ce qu'elle doit faire en théorie : pour chacune des actions ci-dessous, donner le coût estimé de cette action en théorie. En déduire le coût total de la méthode.

  • Localiser l'indice de la première occurence de l'élément cherché dans le tableau et placer sa valeur dans une variable i
  • Faire appel à pop(i) pour supprimer cette case.

...CORRECTION...

Nous avons déjà vu (notamment dans "Alice déménage") que localiser un contenu et donc son indice est à coût LINEAIRE puisqu'on doit chercher dans les cases une à une. L'affectation est à coût CONSTANTE. Au total, cette étape est donc à coût LINEAIRE.

Nous venons de montrer dans la question précédente que pop(i) est à coût LINEAIRE.

On en déduit que la méthode remove(x) est à coût LINEAIRE.

⚙ 15° Compléter la fonction supprimer() pour qu'elle supprime toutes les valeurs x qui se trouveraient dans le tableau t.

1 2 3 4 5 6 7 8 9 10
def supprimer(x:int, t:list[int]) -> None: """Supprime toutes les occurences de x dans le tableau t""" while ... # Tant qu'on trouve un x dans le tableau t ... # Supprime ce x du tableau t = [10, 20, 10, 30, 10, 40, 10, 50] print(t) supprimer(10, t) print(t)

...CORRECTION...

1 2 3 4 5 6 7 8 9 10
def supprimer(x:int, t:list[int]) -> None: """Supprime toutes les occurences de x dans le tableau t""" while x in t: # Tant qu'on trouve un x dans le tableau t t.remove(x) # supprime ce x du tableau t t = [10, 20, 10, 30, 10, 40, 10, 50] print(t) supprimer(10, t) print(t)

3 - Récapitulatif des coûts

A faire.

4 - FAQ

Rien pour le moment

-

Maintenant que vous savez ajouter et supprimer à coût constant des données dans une structure de données, vous allez pouvoir réaliser un premier jeu vidéo avec des ennemis et des tirs, qui apparaissent et disparaissent.

Activité publiée le 20 07 2024
Dernière modification : 20 07 2024
Auteur : ows. h.