Tableaux, listes et structures de données
Partie 3 sur 3
6Les mêmes idées dans les autres langages
Écrire ses propres listes en C est instructif, mais, dans la pratique, les langages modernes fournissent des structures prêtes à l’emploi, qui cachent la mémoire et vérifient les limites.
6.1C++ : std::array et std::vector
Le C++ garde les tableaux du C, mais propose dans sa bibliothèque standard deux outils plus sûrs : std::array, un tableau de taille fixe qui connaît sa taille, et std::vector, un tableau extensible qui réserve la mémoire, la rend automatiquement et grandit quand on ajoute des éléments :
#include <vector>
std::vector<int> notes = {12, 15, 9};
notes.push_back(14); /* ajoute à la fin */
int n = notes.size(); /* 4 */
int x = notes.at(10); /* lève une erreur claire au lieu de déborder */
Quand le vecteur est plein, il alloue un tableau plus grand (souvent deux fois) et y recopie ses éléments ; cette recopie, rare, est rentabilisée par les nombreux ajouts suivants, d’où un coût « O(1) en moyenne ». En C++, les structures sont identiques à celles du C, à ceci près que l’obligation d’écrire struct disparaît.
6.2Python : la liste et le dictionnaire
En Python (voir le langage Python), le mot « liste » désigne en réalité un tableau extensible, qui accepte des éléments de types mélangés :
notes = [12, 15, 9]
notes.append(14) # ajoute à la fin
notes[0] # 12 ; l'indice commence à 0 comme en C
notes[-1] # 14 ; l'indice négatif compte depuis la fin
age = {"Paul": 16, "André": 22} # dictionnaire : clé -> valeur
age["Pierre"] = 12
Accéder à une case hors limites provoque une erreur explicite (IndexError) et non une corruption silencieuse.
6.3JavaScript : l’objet Array et les tableaux « associatifs »
En JavaScript (voir le langage JavaScript), un tableau est un objet Array. Il existe plusieurs façons de le créer :
const a = ["donnée 1", "donnée 2", "donnée 3"]; /* forme usuelle */
const b = new Array("x", "y"); /* forme équivalente, moins employée */
const c = []; /* tableau vide */
Pour accéder à un élément, on écrit le nom suivi de l’indice entre crochets (a[3] est le quatrième). La propriété length donne le nombre d’éléments. Voici les méthodes de l’objet Array, avec leur description corrigée :
| Méthode | Effet |
|---|---|
concat(t2) | renvoie un nouveau tableau, concaténation (mise bout à bout) des tableaux |
join(sép) | renvoie une chaîne contenant tous les éléments, séparés par sép |
push(v1, v2…) | ajoute des éléments à la fin |
pop() | supprime le dernier élément et renvoie sa valeur |
unshift(v1…) | ajoute des éléments au début |
shift() | supprime le premier élément et renvoie sa valeur |
slice(début, fin) | renvoie une copie d’une partie (extraction), sans modifier le tableau |
splice(pos, n, v…) | retire et/ou ajoute des éléments à une position donnée, en modifiant le tableau |
reverse() | inverse l’ordre des éléments |
sort() | trie les éléments |
valueOf() | renvoie la valeur du tableau lui-même |
toString() | renvoie les éléments sous forme d’une chaîne séparée par des virgules |
Des corrections utiles. On voit parfois unshift décrit à tort comme renvoyant « le code source qui a permis de créer l’objet Array » (description qui appartient à une méthode ancienne, toSource, jamais standard) ; en réalité, il ajoute des éléments au début. On liste aussi les propriétés constructor (le constructeur de l’objet) et prototype (qui permet d’ajouter ses propres propriétés à tous les tableaux, pratique déconseillée), ainsi qu’une propriété input qui ne concerne en fait que les résultats d’une recherche par expression régulière, et non les tableaux ordinaires. On écrit parfois des appels de la forme pop(tableau) alors que ces méthodes s’appellent sur le tableau (tableau.pop()). Enfin, sort() trie par défaut comme du texte : [10, 9, 1].sort() donne [1, 10, 9]. Pour trier des nombres, on fournit une fonction de comparaison : tableau.sort((x, y) => x - y).
On parle aussi de tableaux associatifs, où l’on utilise « une chaîne ou un nombre spécifique » comme indice, par exemple MonTableau["Pierre"] = 12. Cela marche parce qu’en JavaScript un tableau est un objet, mais c’est une mauvaise pratique : ces valeurs n’entrent pas dans length et les méthodes comme push ou sort les ignorent. La bonne pratique est d’employer un objet ({"Pierre": 12}) ou, mieux, un objet Map, conçu pour cela. Les tableaux à plusieurs dimensions s’écrivent aujourd’hui comme des tableaux de tableaux : [[1, 2], [3, 4]].
Afficher le résultat avec document.write est déconseillé aujourd’hui, car cela peut effacer toute la page. On écrit plutôt dans un élément de la page ou, pour tester, dans la console du navigateur avec console.log.
6.4Le dictionnaire, ou tableau associatif
Un dictionnaire associe une clé (un nom) à une valeur. Contrairement au tableau, où l’on retrouve une valeur par son numéro, on la retrouve par son nom : age["Pierre"]. Presque tous les langages le proposent sous des noms différents (dict en Python, Map ou objet en JavaScript, std::unordered_map en C++). Il est le plus souvent réalisé avec une table de hachage : une fonction transforme la clé en un numéro de case dans un tableau interne (voir le hachage), ce qui permet de retrouver la valeur en un temps presque constant, quelle que soit la taille du dictionnaire.
Pour s’exercer
Exercice 6 : choisir
Pour chacun des besoins suivants, quelle structure : (a) les 1 000 notes d’une classe lues par numéro d’élève ; (b) retrouver le numéro de téléphone d’un contact par son nom ; (c) une file d’attente où l’on retire toujours le premier et ajoute toujours à la fin, avec des millions d’éléments.
Voir la réponse
(a) un tableau (accès par position en O(1)). (b) un dictionnaire (recherche par clé en O(1) en moyenne). (c) une structure faite pour cela, une file, réalisée avec une liste chaînée ayant un pointeur de tête et un pointeur de fin, ou un tampon circulaire ; un simple tableau où l’on retire le premier élément coûterait O(n) à chaque retrait.
Exercice 7 : le tri en JavaScript
Que donne [25, 100, 3].sort() en JavaScript ? Comment obtenir un tri croissant des nombres ?
Voir la réponse
Par défaut, sort compare les éléments comme du texte : "100" avant "25" avant "3", donc le résultat est [100, 25, 3]. Pour trier des nombres, on passe une fonction de comparaison : [25, 100, 3].sort((x, y) => x - y) donne [3, 25, 100].
7Quelle structure choisir ?
Le bon choix dépend des opérations que le programme fait le plus souvent. La figure 3 compare les structures selon leur coût. On l’exprime avec la notation O (« grand O »), qui indique comment le temps d’une opération grandit avec le nombre n d’éléments : O(1) veut dire que le temps ne dépend pas de n (constant), O(n) qu’il est proportionnel à n (dix fois plus d’éléments, environ dix fois plus de temps).
7.1La règle pratique
- Si vous lisez souvent par position et ajoutez surtout à la fin, un tableau extensible (
vector, liste Python,ArrayJavaScript) est presque toujours le meilleur choix. - Si vous cherchez souvent par un nom, un identifiant ou une clé, un dictionnaire.
- Si vous insérez et supprimez sans cesse au milieu d’une très grande suite, sans accès par position, la liste chaînée peut convenir ; mais voyez le point suivant.
- Si vous avez des données de natures différentes qui forment un tout (une personne, un produit), une structure (ou une classe, ou un objet), éventuellement stockée dans un tableau.
7.2Pourquoi le tableau gagne souvent contre la liste
Sur le papier, la liste chaînée gagne l’insertion au milieu. En pratique, les tableaux gagnent beaucoup plus souvent qu’on ne le croit, à cause du matériel : un processeur charge la mémoire par blocs, et le tableau, dont les cases sont voisines, profite pleinement de ce chargement ; les maillons d’une liste, dispersés, obligent à de multiples accès lents à la mémoire. Pour des centaines ou des milliers d’éléments, le tableau est souvent plus rapide même pour l’insertion. Ne choisissez la liste que si la mesure le justifie.
7.3Mesurer plutôt que deviner
Un principe vaut pour toutes ces structures : n’optimisez pas sans avoir mesuré. Un programme qui manipule cent éléments se moque du coût en O(n) ; un programme qui en manipule dix millions s’en soucie. Les mesures (le temps réel avec un chronomètre ou un outil d’analyse de performance) doivent trancher.