Glisser un retardataire parmi 2 000 inscrits
Un tableau est une suite de cases rangées côte à côte dans la mémoire, et une liste Python s’appuie sur ce rangement. Savoir comment une liste est stockée explique pourquoi lire une case est immédiat et pourquoi insérer au milieu coûte cher.
Une université garde la liste triée de ses 2 000 inscrits à un partiel. Un retardataire s’inscrit tard. Il faut le placer à sa bonne place sans casser l’ordre.
À la fin de cette leçon
Remarque
Je peux expliquer comment une liste est stockée en mémoire et ce que coûte une insertion.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Tableau | une suite de cases côte à côte en mémoire | |
| Indice | le numéro d’une case, qui part de 0 | notes[2] |
| Insertion | ajouter une valeur à une place précise | |
| Décalage | déplacer une valeur d’une case | |
| Capacité | le nombre de cases réservées | |
| Coût | le nombre d’étapes qu’une opération demande |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un tableau range ses cases côte à côte
Les cases d’un tableau se suivent en mémoire, sans trou. Toutes ont la même taille, par exemple 4 octets pour un entier.
Pour lire la case numéro 5, l’ordinateur ne parcourt rien. Il calcule son adresse : début du tableau + indice × taille d’une case. Ce calcul prend une seule étape, que le tableau ait 10 ou 10 millions de cases.
Exemple travaillé : les adresses d’un tableau
| Indice | Calcul | Adresse |
|---|---|---|
| 0 | 1000 + 0 × 4 | 1000 |
| 1 | 1000 + 1 × 4 | 1004 |
| 2 | 1000 + 2 × 4 | 1008 |
| 5 | 1000 + 5 × 4 | 1020 |
| 100 | 1000 + 100 × 4 | 1400 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un programme C mesure l’écart entre deux cases
Un petit programme en C le prouve. Il range quatre entiers dans un tableau, puis affiche la taille totale et l’écart en octets entre la case 0 et la case 1.
Les trois commandes écrivent le programme, le compilent avec gcc, puis le lancent. Les deux premières n’affichent rien.
Écrire le programme C
printf '%s\n' '#include <stdio.h>' 'int main(void) {' ' int t[4] = {10, 20, 30, 40};' ' printf("taille %d octets, écart %d octets\n", (int)sizeof t, (int)((char *)&t[1] - (char *)&t[0]));' ' return 0;' '}' > /tmp/tableau.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Compiler avec gcc
gcc -o /tmp/tableau /tmp/tableau.cAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Lancer le programme
/tmp/tableauAffichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Insérer au milieu oblige à décaler
Pour insérer une valeur au milieu d’un tableau, il faut d’abord lui faire de la place. Chaque valeur à droite de la place choisie recule d’une case. C’est un décalage.
On commence par la dernière valeur, pour n’écraser personne. Insérer au début décale tout le tableau. Insérer à la fin ne décale rien.
Exemple travaillé : insérer 10 dans une liste triée
| Étape | Action | Cases du tableau |
|---|---|---|
| Départ | Une case libre au bout | 3, 8, 12, 20, 25, libre |
| 1 | Reculer 25 d’une case | 3, 8, 12, 20, libre, 25 |
| 2 | Reculer 20 | 3, 8, 12, libre, 20, 25 |
| 3 | Reculer 12 | 3, 8, libre, 12, 20, 25 |
| 4 | Écrire 10 dans la case libre | 3, 8, 10, 12, 20, 25 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter les décalages
# Une liste triée de numéros d’étudiants, un numéro par case.
numeros = [3, 8, 12, 20, 25]
nouveau = 10
# On cherche la place du nouveau numéro.
place = 0
while place < len(numeros) and numeros[place] < nouveau:
place = place + 1
# Tout ce qui est à droite de la place doit reculer d’une case.
decalages = len(numeros) - place
numeros.insert(place, nouveau)
print(numeros)
print("valeurs décalées :", decalages)
# Remplacez nouveau par 1, puis par 30, et comparez les décalages.
Python fait le décalage à votre place
En Python, insert(0, valeur) fait tout ce décalage sans que vous le voyiez. La commande suivante insère 5 au début d’une liste de quatre valeurs, puis l’affiche. Les quatre autres valeurs ont reculé d’une case.
Insérer 5 au début d’une liste
python3 -c "liste = [10, 20, 30, 40]; liste.insert(0, 5); print(liste)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Quand le tableau est plein, on le recopie
Un tableau a une capacité fixe. Quand elle est atteinte, il faut réserver un espace plus grand et y recopier toutes les valeurs.
Une liste Python agrandit son espace par paliers, souvent en le doublant. Cela n’arrive que de temps en temps. Ajouter à la fin reste donc rapide en moyenne.
Exemple travaillé : une capacité qui double
| Ajouts | Capacité avant | Recopie | Capacité après |
|---|---|---|---|
| 1 à 4 | 4 | Non | 4 |
| 5 | 4 | Oui, 4 valeurs | 8 |
| 6 à 8 | 8 | Non | 8 |
| 9 | 8 | Oui, 8 valeurs | 16 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Ce que coûte chaque opération (n valeurs)
| Opération | Étapes | Pourquoi |
|---|---|---|
| Lire par indice | 1 | Un calcul d’adresse |
| Ajouter à la fin | 1 le plus souvent | Sauf quand il faut recopier |
| Insérer au début | n | Toutes les valeurs reculent |
| Supprimer au début | n | Toutes les valeurs avancent |
| Chercher dans une liste non triée | n | On regarde case par case |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Erreur fréquente
Attention
Beaucoup d’étudiants pensent qu’insérer au début d’une liste coûte autant qu’ajouter à la fin, puisque les deux sont une seule ligne de Python. Ce n’est pas vrai. insert(0, x) décale toutes les valeurs, append(x) n’en décale aucune. Sur un million de valeurs, l’écart se compte en millions d’étapes.
Pour aller plus loin
Une liste triée de 1 000 numéros reçoit 500 retardataires, un par un, chacun à sa place. Estimez le nombre total de décalages. Dites ce que vous trouvez trop lent.
Cherchez ensuite une autre méthode : ajouter les 500 numéros à la fin, puis trier la liste une seule fois.