Tableaux statiques et dynamiques

Identification

Infoforall

14 - 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 est un conteneur formant une collection ordonnée d'éléments ayant tous le même type. On peut donc avoir un tableau d'integers, ou un tableau statique de floats par exemple.

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

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

Voici par exemple un tableau de caractères de 3 cases :

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

3 cases donc des indices valant 0, 1 et 2.

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
Hiérarchie des mémoire

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

Vous devez être capable de distinguer ces trois types de mémoire :

  1. Les registres : très petite capacité, mais très grande rapidité d'accès ;
  2. La mémoire vive (RAM) : capacité moyenne, vitesse moyenne ;
  3. La mémoire de masse (DD, clé USB...) : grande capacité, mais accès lent.
RAM
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.

En effet, cette mémoire est asssez grande pour contenir tout cela (contrairement aux registres) et est assez rapide pour que l'exécution ne soit pas trop lente.

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

"Accès aléatoire" est à comprendre 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.
  • en accès aléatoire, on peut atteindre à coût constant une case mémoire pourvu qu'on connaisse son adresse-mémoire.
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 ? Donner son contenu sous forme binaire.

Contenu de la mémoire

...CORRECTION...

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

Pour écrire 72, on a besoin de 64. Il restera (72-64) = 8.

Pour écrire 8, on a besoin de 8. Il restera (8-8) = 0.

On a donc N = 72 10= 0100 1000 2

⚙ 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 est une table permettant de faire le lien (à coût constant) entre le nom d'une variable (t ci-dessous) et une adresse-mémoire (500 ci-dessous).

Important : une variable (t par exemple) ne "contient" pas le contenu du tableau, juste l'adresse de ce contenu.
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.
  • Chaque case encode le même type de données, et comporte C octets.
  • Si on désigne par n le nombre de cases du tableau, il occupe une place-mémoire de L = n*C octets.

Exemple : considérons un tableau ne comportant que 3 integers uniquement (on prendra 4 octets par entier, pour représenter de grandes valeurs, supérieures à 255). Ci-dessous, il s'agit donc des zones en orange, bleu et vert :

    Principe du tableau dans l'espace des noms
  • Le premier octet du tableau est stocké à l'adresse A = 500.
  • Chaque case contient C = 4 octets.
  • Le tableau occupe donc L = 3 * 4 = 12 octets consécutifs :
    • L'adresse du premier octet est 500 à l'adresse ;
    • L'adresse du dernier octet est 511 : 500 + (12 - 1).
    • Les 4 octets d'adresse 500-501-502-503 (oranges) représentent collectivement le premier entier.
Indice des cases
Lien entre indice et adresse-mémoire
  • On identifie chaque case de 4 octets par un numéro qu'on appelle indice.
  • t[0] représente donc le contenu des cases 500 - 501 - 502 - 503.
  • t[1] représente donc le contenu des cases 504 - 505 - 506 - 507.
  • 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 : coût constant

    L'espace des noms fait le lien entre le nom d'un tableau et l'adresse A de son premier octet.

    2 - Calcul de l'adresse de la case d'indice i : coût constant

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

    A désigne l'adresse du tableau et C la largeur en octets de ses cases.

    Si on prend A = 500 et C = 4 :

    • 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 : coût constant

    L'accès à un octet dont on connait l'adresse est à coût CONSTANT par définition même de la RAM.

    4 - Lire 4 cases : coût constant

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

    5 - Conclusion : obtenir la valeur t[i] : coût CONSTANT

    ⚙ 03° Soit un tableau d'integers où chaque integer occupe 4 octets (on peut ainsi stocker plus que 255), 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.

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

    1. C'est un lien entre Nom de variable - Contenu mémoire
    2. C'est un lien entre Nom de variable - Longueur de la zone mémoire
    3. C'est un lien entre Nom de variable - Adresse mémoire
    4. C'est un lien 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.

    Bien entendu, connaissant l'adresse mémoire, on peut ensuite trouver le contenu mémoire.

    ⚙ 06° Donner le contenu du tableau Python t représenté ci-dessous (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.

    En efet, un type list référence un tableau d'adresses (8 octets sur les systèmes 64 bits).

    Chaque case du tableau contient donc l'adresse du contenu qu'on veut mettre à cette position i et pas directement le contenu.

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

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

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

    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
    Un tableau statique est un tableau ayant ces trois propriétés :

    1. toutes les cases sont consécutives en mémoire ;
    2. toutes les cases contiennent le même type de données ;
    3. 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. Ce type Python accepte d'ailleurs des contenus non-homogènes.

    Type list : tableau dynamique
    Un tableau dynamique est un tableau ayant ces trois propriétés :

    1. toutes les cases sont consécutives en mémoire ;
    2. toutes les cases contiennent le même type de données ;
    3. le nombre de cases est variable : après création, on peut en supprimer ou en rajouter.

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

    tdyn = [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 :

    nom_du_tableau.append(contenu_de_la_nouvelle_case)

    Cette insertion en fin est à 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

    il ne faut jamais réaliser une affectation sur la réponse d'un append() :

    >>> 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. Pourquoi 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...

    1. On commence par 0 et on cherche un par un les multiples de 7 : les nombres dont le reste est 0 lorsqu'on réalise une division par 7. Si c'est le cas, on rajoute ce nombre à la fin du tableau.
    2. On devrait donc obtenir [0, 7, 14, 21].

    3. Lancer le programme pour vérifier : ok
    4. Coût linéaire en fonction du nombre de cas à traiter.
    5. Regardons la création par compréhension suivante :
    6. >>> tab = [x for x in range(1000000) if x % 7 == 0]

      On dit bien "Pour chaque x de 0 à 999999, si x est un multiple de 7, alors rajoute ce x dans le nouveau tableau".

    ⚙ 10-A° 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 n 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 n 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 n fois les lignes 5-6 (actions à coût constant), le coût est donc LINEAIRE par rapport à nd :

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

    ⚙ 10-B° Modifier le programme pour utiliser plutôt un parcours par valeur : on ne modifie pas les deux tableaux initiaux, autant prendre l'autre façon de parcourir.

    ...CORRECTION...

    1 2 3 4 5 6 7
    animaux = ["Chat", "Chien", "Poisson"] animaux_sauvages = ["Lion", "Tigre", "Éléphant"] for animal in animaux_sauvages): # Pour chaque animal du tableau animaux_sauvages animaux.append(animal) # Ajoute cet animal aux autres animaux print(animaux)
    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()

    La suppression en fin de list est à 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° 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.

    ⚙ 12° 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)

    La suppression sur une position i quelconque est à 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

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

    1. L3 : nc correspond au nombre de cases du tableau t qu'on va créer en ligne 5. Quel est le plus nombre de cases 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.

    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)

    La suppression d'un élément quelconque est à 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.

    Les actions à évakuer :

    • Localiser l'indice de la première occurrence de l'élément cherché dans le tableau ;
    • Placer cet indique dans une variable i

    • Faire appel à pop(i) pour supprimer cette case.

    ...CORRECTION...

    Nous avons déjà vu (voir la partie Algorithmique) que localiser l'indice d'un élément recherché est à coût LINEAIRE puisqu'on doit chercher dans les cases une à une.

    L'affectation est à coût CONSTANTE.

    pop(i) est à coût LINEAIRE.

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

    ⚙ 15-A° 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 occurrences 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 occurrences 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)

    ⚙ 15-B° Quel est le coût de la fonction précédente dans le pire des cas ?

    ...CORRECTION...

    Dans le pire des cas, on va devoir supprimer les n éléments.

    On va donc réaliser n fois une action à coût linéaire.

    On obtient donc O(n*n) = O(n2).

    Il s'agit donc d'un coût quadratique.

    3 - Récapitulatif des coûts

    Bilan des actions sur les tableaux
    Actions à coût CONSTANT (indépendant du nombre n de cases)
    • Création d'un tableau vide : coût CONSTANT
    • t = [] ou t = list()

    • Accès en lecture ou en modification d'une case : coût CONSTANT
    • t[i] ou t[i] = ...

    • Récupérer le nombre de cases : coût CONSTANT
    • len(t)

    • Ajouter une case à la fin : coût CONSTANT
    • t.append(5)

    • Supprimer la case de fin : coût CONSTANT
    • v = t.pop(0)

    • Créer un alias d'un tableau : coût CONSTANT
    • alias = t

    Actions à coût LINEAIRE (par rapport au nombre n de cases)
    • Supprimer la première case : coût LINEAIRE en n
    • v = t.pop(0)

    • Supprimer la case i : coût LINEAIRE en (n-i)
    • v = t.pop(i)

    • Supprimer la première case où apparaît v : coût LINEAIRE en n
    • t.remove(v)

    • Créer une copie d'un tableau : coût LINEAIRE
    • copie = [v for v in t] ou copie = list(t)

    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 03 2025
    Auteur : ows. h.