Qu’est-ce qu’un tableau ?
Contexte :
Les programmes tirent profit de la vitesse de calcul de la machine et les types de données nous permettent de préciser la nature de l’information à l’ordinateur. Pour aller encore plus loin, nous aimerions pouvoir manipuler plus facilement de nombreuses données.
Les tableaux vont nous permettre de regrouper dans la mémoire des informations qui peuvent être traitées par lot. L’ordinateur pourra donc lancer les calculs sur une série de données sans avoir besoin d’intervention extérieure. Les tableaux constituent un atout majeur lorsqu’il s’agit de faire réaliser énormément d’opérations à la machine en écrivant le moins d’instructions possible.
Manipuler les données par lot
Maintenant que nous connaissons les types simples, nous aimerions aller plus loin dans la gestion de nos données. Si nous voulons gérer un grand volume d’information, nous nous retrouvons limités. Nous voulons par exemple manipuler des données météorologiques relevées sur un mois, soit entre 28 et 31 valeurs. Nous pourrions définir 31 valeurs de type décimal qui serviraient à sauvegarder tous les relevés de température pris sur un mois :
D’un point de vue algorithmique, nous aurions donc une déclaration de variables assez conséquente :
Méthode :
Variable :
Jour1, jour2, … jour30 : réel
Début
…
Fin
Chaque opération statistique comme le calcul de la moyenne par exemple, nous obligerait à faire appel à chacune de ces 30 variables :
Méthode :
Variable :
Jour1, jour2, … jour30 : réel
moyenne : réel
Début
…
Moyenne = (jour1 + jour2 + … + jour30) / 30
Fin
Remarque :
C’est une solution qui marche mais qui n’est pas viable pour le développeur. Si nous pouvons le concevoir pour un mois, cela devient impossible à gérer pour une année ou pour une période encore plus longue. Le fait de déclarer autant de variables nuit également à la compréhension du programme ou de l’algorithme.
Ce petit exemple nous montre deux problèmes auxquelles nous nous heurtons.
Les différentes variables « jour » véhiculent toutes des informations sur la température, nous aimerions donc grouper ces valeurs.
Le fait qu’il n’y ait pas toujours 31 jours par mois fait que nous allons déclarer des variables qui ne seront pas forcément toutes utilisées.
Nous avons déjà parlé de la rapidité de calcul de la machine et que le but du développeur est de faire faire à l’ordinateur un maximum de traitement à partir d’un minimum d’instructions. Avec cette solution, nous ne sommes clairement pas dans cette optique.
Plusieurs valeurs dans une variable
Sortons de l’algorithmie et de la programmation quelques instants. Si nous cherchions comment représenter des relevés de température pour en calculer des indicateurs (moyenne, valeur maximum, valeur minimum), il y a de fortes chances que nous pensions à les représenter dans un tableur.
Exemple :
Un tableur est composé d’une grille de cellules et nous pouvons facilement y placer nos valeurs de température. Une fois les valeurs dans notre tableur, certaines fonctions vont nous permettre de calculer rapidement nos indicateurs :
Remarque :
À partir du moment où toutes les valeurs nécessaires à nos calculs se retrouvent dans la même colonne, nous ne les considérons plus comme des valeurs isolées mais nous voulons traiter l’ensemble de la colonne. Si nous regardons les fonctions moyenne(cellule_début : cellule_fin), min(cellule_début : cellule_fin) et max(cellule_début : cellule_fin), nous voyons que le paramètre attendu est une plage de valeurs. La plage de valeurs est définie par la cellule de début et la cellule de fin et le tableur sait qu’il va devoir traiter toutes les valeurs entre ces deux cellules.
C’est ce genre de principe que nous aimerions retrouver dans nos langages de programmation. Nous voudrions pouvoir donner une liste de valeurs à la machine et la laisser la traiter. Cette liste, c’est ce que nous allons représenter avec un tableau.
Tableau dans la mémoire
Pour une variable de type simple (entier, booléen, réel), une zone mémoire est allouée et le nom de la variable pointe directement sur cette zone pour pouvoir récupérer la valeur stockée. Dans le cas d’un tableau, nous ne nous contentons pas d’une seule valeur mais d’une liste de valeurs. Ce n’est donc pas une seule case mémoire qui sera allouée cette fois mais autant de cases qu’il y a de valeurs dans notre tableau.
Fondamental :
La représentation du tableau amène une contrainte supplémentaire. Les éléments du tableau sont stockés dans des zones contigües de la mémoire. Voici la représentation d’une variable de type tableau de réel contenant les éléments : 21.5, 19.4, 18.7, 22.4 :
La variable « température » pointe sur la première case mémoire du tableau. Les éléments du tableau se suivent physiquement dans la mémoire si bien qu’il est aisé de parcourir un tableau puisqu’il suffit de parcourir la mémoire. Parcourir un tableau est une opération qui consiste à commencer par le premier élément et à traiter les éléments successivement selon leur position dans le tableau. La difficulté est de savoir à quel moment le tableau s’arrête. Pour cela, les langages de programmation modernes incluent dans le type tableau une information sur la taille du tableau. Dans notre exemple, nous avons un tableau de 4 éléments, la taille est donc de 4. Si nous sommes sur le premier élément du tableau, sa fin se trouve 4 zones mémoires plus loin.
Remarque :
Certains langages, comme le C, s’appuient sur une autre règle pour connaître la fin d’un tableau. Au lieu de sauvegarder le nombre d’éléments, le langage C utilise un caractère spécial pour marquer la fin du tableau : « \0 ».
Il s’agit là d’un autre mécanisme mais qui fonctionne bien également. On pourra donc parcourir le tableau jusqu’à atteindre le fameux caractère « \0 » et être donc sûr d’être arrivé à la fin du tableau.
Fondamental :
La notion de fin de tableau est très importante. Sans elle, nous pourrions continuer à parcourir la mémoire de l’ordinateur sans que les valeurs que nous prenons en compte aient encore un sens pour notre calcul :
Dans cet exemple, la taille du tableau de 4 nous indique que seules les 4 premières valeurs sont à prendre en compte dans le traitement du tableau. Sans cette information, nous pourrions très bien utiliser l’âge ou la taille et le résultat de notre calcul n’aurait plus aucun sens. Nous pourrions également nous retrouver dans un emplacement mémoire utilisé par un autre programme. Il s’agit dans ce cas-là d’un débordement de la mémoire attribuée. C’est une erreur qui peut être assez compliquée à corriger. Le mieux est donc de rester vigilant sur les dimensions des tableaux que nous utilisons.
Contenu d’un tableau
Jusqu’à présent, nous avons vu qu’un tableau peut contenir plusieurs éléments et que la taille du tableau est une information importante pour pouvoir le parcourir. Nous allons nous intéresser ici au contenu du tableau. Un tableau contient toujours un seul type d’éléments en algorithmie. Nous allons donc prendre l’habitude de déclarer un tableau d’entiers, un tableau de réels ou un tableau de booléens. Plusieurs langages de programmation ont étendu la notion de tableau pour pouvoir contenir des types différents. C’est le cas des listes en Python ou des arrays en Javascript.
Fondamental :
Comme toutes les variables, les tableaux sont donc définis par un type qui correspond au type des éléments qui le composent. Encore une fois cette notion de type est importante et cela a un impact sur la représentation mémoire du tableau. Pour nous en convaincre, voici un petit descriptif des types en C++ et la taille qu’ils prennent en mémoire :
Type | Désignation | Taille en octet |
|---|---|---|
int | Entier | 2 |
Flot | Réel | 4 |
double | Réel, double précision | 8 |
char | caractère | 1 |
bool | Boolean | 1 |
Complément :
Un octet est une unité de mesure de la quantité de données. Il correspond à 8 bits. Autrement dit, un octet est une valeur numérique sur 8 positions et chaque position peut valoir 0 ou 1. Il est donc possible de coder sur un octet 28 = 256 valeurs différentes. Pour le cas d’un entier codé sur 2 octets, il est possible de représenter les nombres de 0 à (216 – 1) = 65 535. 2 est élevé à la puissance 16 car nous sommes sur deux octets (2 x 8 = 16).
Exemple :
Une variable de type double utilise deux fois plus de mémoire de stockage qu’une variable de type float. Le fait de définir un type pour le tableau permet au langage de savoir que chaque élément de la mémoire va utiliser la même taille de zone mémoire :
Le tableau « Age » est un tableau d’entiers (int). Chaque élément utilise donc deux octets en mémoire. Le tableau « Taille » est un tableau de réels (float). Chaque élément utilise donc 4 octets en mémoire. La taille mémoire utilisée par chaque élément permet de déterminer la taille mémoire occupée par le tableau en entier :
Tableau « Age » : 3 éléments de 2 octets → Tableau de 3 x 2 = 6 octets
Tableau « Taille » : 2 éléments de 4 octets → Tableau de 2 x 4 = 8 octets
Exemple :
Si vous avez déjà programmé en Python, vous avez dû vous apercevoir que le type « list » se rapproche beaucoup du tableau que nous venons de décrire. Dans une liste Python, nous pouvons cependant stocker des éléments de types différents. Le type liste de Python n’est pas à proprement dit un tableau mais nous pouvons le voir comme une extension du tableau. C’est également le cas des arrays en Javascript.
Remarque :
Cette première partie nous a permis de comprendre la structure du tableau ainsi que sa représentation en mémoire. Nous allons voir dans la partie suivante comment créer un tableau et le manipuler.