Qu'est-ce qu'un tableau ?

Une application météo qui affiche les températures de la semaine a besoin de sept nombres. Elle pourrait utiliser sept variables séparées, monday, tuesday et ainsi de suite, mais alors aucune boucle ne pourrait les parcourir, et ajouter un huitième jour obligerait à écrire du nouveau code. Un tableau range les sept nombres sous un seul nom, temperatures, dans des cases numérotées de 0 à 6.

Comment fonctionne un tableau

Un tableau garde ses éléments côte à côte dans un seul bloc de mémoire, et chaque élément occupe le même nombre d'octets. Cette disposition permet à l'ordinateur de trouver n'importe quel élément avec un seul calcul :

address of element i = start address + i × element size

Supposons qu'un tableau d'entiers de 32 bits (4 octets chacun) commence à l'adresse mémoire 1000. L'élément 0 est à 1000, l'élément 1 à 1004, l'élément 2 à 1008 et l'élément 3 à 1012. Atteindre l'élément 3 ou l'élément 3 000 000 prend la même étape unique, c'est pourquoi la lecture d'un tableau par indice est dite en temps constant, noté O(1).

Le module array de Python stocke des nombres bruts de cette façon, tu peux donc vérifier le calcul :

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

Cette formule explique aussi pourquoi la plupart des langages comptent à partir de 0. L'indice est un décalage : le nombre d'éléments à sauter depuis le début. Le premier élément est à 0 élément du début, donc son indice est 0, et le dernier élément d'un tableau de longueur n a l'indice n − 1. Quelques langages, comme Lua, MATLAB, R et Fortran, commencent à 1.

Utiliser un tableau en Python

La plupart du code Python utilise la list intégrée comme tableau. Tu la crées avec des crochets, tu lis et modifies les éléments par indice, et tu obtiens sa longueur avec len() :

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

Un indice négatif compte à partir de la fin, donc temperatures[-1] est le dernier élément. Ce raccourci est propre à Python ; C et Java n'ont pas d'indices négatifs.

Ce que coûtent les opérations sur un tableau

La disposition continue rend certaines opérations rapides et d'autres lentes. Le coût augmente avec n, le nombre d'éléments :

Insérer au début est lent parce que chaque élément doit se déplacer d'une case pour faire de la place. Chercher dans un tableau non trié demande une recherche linéaire qui passe par chaque élément tour à tour, alors qu'un tableau trié permet une recherche dichotomique, qui divise par deux l'intervalle restant à chaque étape.

Parcourir un tableau avec une boucle

Tableaux et boucles vont ensemble : une boucle visite chaque élément tour à tour, ce qu'on appelle l'itération. Les mêmes quelques lignes traitent un tableau de 5 éléments ou de 5 millions.

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

Les tableaux dans d'autres langages

En C, un tableau a une taille fixe définie à sa déclaration, et il contient des valeurs brutes d'un seul type. sizeof donne sa taille en octets :

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Les tableaux Java ont aussi une longueur fixe, et les nouveaux éléments démarrent avec une valeur par défaut, comme 0 pour les nombres. Quand tu as besoin d'un tableau Java qui grandit, tu utilises ArrayList :

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

Les tableaux JavaScript grandissent et rétrécissent librement et peuvent mélanger les types, comme dans [1, "two", true].

Les tableaux qui grandissent, comme la list de Python, l'ArrayList de Java et le std::vector de C++, s'appellent des tableaux dynamiques. Ils réservent de la place supplémentaire à la fin. Quand cette place est épuisée, ils allouent un bloc plus grand, y copient chaque élément et continuent. Ces copies sont assez rares pour que l'ajout reste rapide en moyenne.

Un tableau peut aussi contenir d'autres tableaux. grid[row][col] lit une case d'un tableau à deux dimensions, la disposition utilisée pour les plateaux de jeu, les feuilles de calcul et les images. Le guide C des tableaux multidimensionnels montre comment ils sont rangés en mémoire.

Erreurs courantes

Le décalage d'une unité (off by one). Un tableau de 3 éléments a les indices 0, 1 et 2, donc l'indice 3 dépasse la fin. Python s'arrête avec une erreur :

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java lève une ArrayIndexOutOfBoundsException, et JavaScript renvoie discrètement undefined. C ne fait aucune vérification : lire au-delà de la fin est un comportement indéfini, qui peut renvoyer n'importe quoi ou faire planter le programme avec une erreur de segmentation.

Copier par affectation. En Python, Java et JavaScript, b = a ne copie pas un tableau ; les deux noms désignent le même, donc modifier b modifie a. Utilise a.copy() en Python ou [...a] en JavaScript pour une vraie copie. La page sur les variables explique pourquoi.

Pour aller plus loin

Un tableau n'est vraiment utile qu'avec une boucle pour le parcourir, alors lis ensuite ce qu'est l'itération, et ce qu'est un octet pour l'unité derrière les tailles d'éléments ci-dessus. Le guide des listes Python couvre le découpage, le tri et les méthodes de liste, et la visualisation de la liste chaînée montre la structure qui échange l'accès rapide par indice contre des insertions rapides.