Les tableaux

Lire la millionième valeur d'un tableau prend une étape, mais placer une nouvelle valeur au début de ce même tableau déplace un million de valeurs.

Ce qu'est une structure de données

Un programme qui garde une liste de noms, une file de travaux d'impression ou un tableau de prix doit stocker ces données quelque part, et il doit répondre à des questions à leur sujet : quel est le troisième élément, ce nom est-il dans la liste, quel travail passe ensuite ? Une structure de données est une façon de stocker des données avec les méthodes qui répondent à ces questions. Le cours 6.006 du MIT sépare ici deux idées. L'interface indique quelles opérations on peut demander, comme « obtenir l'élément à la position i » ou « ajouter un élément à la fin ». La structure de données est la façon dont ces opérations sont réellement effectuées en mémoire. Une même interface peut cacher plusieurs structures de données, dont la rapidité peut être très différente.

Ce cours compte les étapes, comme le cours d'algorithmique, pour pouvoir comparer deux structures sans chronomètre. Dans cette unité, une étape est la lecture ou l'écriture d'une case de mémoire. Le labo ci-dessous les compte pour toi.

Un bloc de cases, côte à côte

Un tableau stocke ses valeurs dans un seul bloc de mémoire continu, chaque valeur dans une case de même taille, numérotée à partir de 0. C'est cette disposition qui rend la lecture rapide. Si le bloc commence à l'adresse s et que chaque case occupe c octets, alors a[i] se trouve à l'adresse s + i × c. L'ordinateur calcule cela avec une multiplication et une addition et y va directement, que i vaille 3 ou 3 000 000. Les notes du MIT indiquent que « get at(i) » et « set at(i, x) » sont en Θ(1) pour un tableau, ce qui signifie que le coût n'augmente pas avec la longueur.

Cette même disposition rend lentes les modifications au milieu. Supposons que le tableau contienne 7, 3, 9, 4, 6 et que tu veuilles mettre 1 au début. Il n'y a pas de place devant 7 : chaque valeur doit d'abord se décaler d'une case vers la droite, en commençant par la dernière pour ne rien écraser. Cela fait 5 déplacements et 1 écriture : 6 étapes. Retirer la première valeur est l'opération inverse : on la lit, puis on décale les 4 autres valeurs d'une case vers la gauche. Insérer à la position i dans un tableau de n valeurs coûte n − i déplacements plus une écriture : le début est donc le pire endroit et la fin le meilleur.

Quand le bloc est plein

Un bloc de mémoire a une taille fixe : que se passe-t-il quand on ajoute une valeur alors que toutes les cases sont prises ? Le tableau doit demander un nouveau bloc plus grand et y recopier chaque valeur avant de pouvoir écrire la nouvelle. Dans le labo, un push sur le bloc plein de 5 coûte 5 copies et 1 écriture. Si le tableau ne grandissait que d'une case à chaque fois, chaque push recopierait tout, et n push coûteraient environ n²/2 copies.

La solution décrite dans les notes du MIT consiste à grandir beaucoup d'un coup, par exemple en doublant. En partant d'une capacité de 1, les copies ont lieu quand le tableau contient 1, 2, 4, 8 et 16 valeurs : 17 push coûtent donc 1 + 2 + 4 + 8 + 16 = 31 copies au total, moins de 2 par push. Un push isolé peut encore être lent, mais toute longue série de push revient en moyenne à un coût constant par push. On parle de temps Θ(1) amorti. Vu de l'extérieur, un tableau JavaScript se comporte ainsi : MDN décrit les tableaux comme redimensionnables, et push et pop agissent à la fin, qui est le côté bon marché.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, une étape
a.push(8);              // bon marché : la fin
a.unshift(1);           // chaque valeur se décale d'une case vers la droite
console.log(a.join(" ")); // 1 7 3 9 4 6 8