Tableaux et tableaux dynamiques

Un tableau stocke des emplacements de taille fixe de manière contiguë, ce qui permet de calculer l’adresse de la position $i$ à partir d’une adresse de base et d’un pas :

$$\operatorname{address}(i)=\operatorname{base}+i\cdot\operatorname{stride}.$$

On obtient ainsi un accès indexé en temps constant et une forte localité spatiale.

Statique ou dynamique

• Un tableau statique possède une capacité fixe.
• Un tableau dynamique suit sa longueur et sa capacité. Lorsqu’il est plein, il alloue un tableau sous-jacent plus grand et copie les emplacements existants.

Une croissance géométrique de la capacité rend l’ajout en fin amorti en $O(1)$, bien qu’un redimensionnement isolé coûte $O(n)$. C’est une garantie globale, pas la promesse que chaque ajout aura une latence constante.

Coût des opérations

Opération	Coût typique
Lecture/écriture par indice	$O(1)$
Parcours séquentiel	$O(n)$
Ajout en fin	$O(1)$ amorti
Retrait en fin	$O(1)$ sans réduction ; sinon $O(1)$ amorti avec une politique adaptée
Insertion/suppression près du début ou au milieu	décalages en $O(n)$
Recherche de valeurs non triées	$O(n)$

La recherche binaire n’est en $O(\log n)$ que si l’ordre est maintenu et si l’accès aléatoire est disponible ; maintenir cet ordre peut rendre les mises à jour coûteuses.

Frontière du langage

Les tableaux typés de bas niveau stockent généralement en ligne des valeurs homogènes. Une list Python est un tableau dynamique de références d’objets : les emplacements de références sont contigus, tandis que les objets référencés peuvent résider ailleurs et avoir des types différents.

Frontière d’usage

Choisissez les tableaux pour l’accès aléatoire, l’itération compacte, le tri, les matrices et le stockage sous-jacent d’un tas. Évitez les opérations de file au début d’un tableau lorsque les décalages fréquents domineraient.

D’où viennent ces bornes ?

Le tableau compte les opérations sur des emplacements de taille fixe pour une séquence de longueur $n$, suivant Open Data Structures. Le calcul d’indice, le déplacement ou la comparaison d’un emplacement sont supposés constants ; les comparaisons coûteuses, la destruction d’objets et la latence d’allocation se comptent séparément. Dans la formule d’adresse, les indices partent de zéro et vont de $0$ à $n-1$. La capacité est le stockage alloué, la longueur le nombre d’éléments présents, avec $0 \le n \le \text{capacity}$. Les emplacements libres ne sont pas des éléments valides.

Avec une capacité initiale de 1 doublée à chaque agrandissement, huit ajouts copient successivement 1, 2 puis 4 anciens emplacements : sept copies et huit nouvelles écritures. En général, pour $m$ ajouts depuis un tableau vide, la somme géométrique des capacités copiées est inférieure à $2m$, soit un travail total en $O(m)$. Agrandir d’un seul emplacement à chaque fois copie au contraire $1+2+\cdots+(m-1)$ emplacements, un travail quadratique. Le facteur 2 illustre la preuve ; ce n’est pas le facteur de croissance spécifié par Python.

Le retrait en fin ne décale rien. Sa borne en $O(1)$ suppose l’absence de redimensionnement : une implémentation qui réduit sa capacité peut copier $O(n)$ emplacements lors d’un retrait et n’offrir qu’une borne amortie. Réduire seulement lorsque le tableau est nettement sous-rempli (par exemple, diviser la capacité par deux à un quart d’occupation) évite qu’une alternance d’ajouts et de retraits déclenche sans cesse de grandes copies.

Une insertion concrète

values = [10, 20, 30]
values.insert(1, 15)
assert values == [10, 15, 20, 30]
assert values.pop(1) == 15
assert values == [10, 20, 30]

L’insertion décale 20 et 30 vers la droite ; la suppression les décale vers la gauche. Un indice conservé peut donc désigner un autre élément après mutation. À bas niveau, une réallocation peut aussi invalider les pointeurs vers l’ancien tableau ; les références d’objets Python se distinguent de ces adresses d’emplacements. Python lève IndexError pour une lecture hors limites ou un pop() sur une liste vide.

Source

• Open Data Structures : listes fondées sur des tableaux

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.