Vecteurs

Un vecteur est un tableau à une seule dimension. L'avantage d'un vecteur par rapport à une liste est qu'il permet un accès direct ($O(1)$) à ses éléments. De plus, le surcoût d'un vecteur (à savoir le gaspillage d'espace par élément) est bien inférieur à celui d'une liste. Il faut compter entre 2 et 4 mots de surcoût pour la liste et un seul mot pour le vecteur. Parfois, le surcoût du vecteur peut même être nul si l'objet peut être stocké directement dans le vecteur sans passer par un pointeur. C'est le cas des fixnums, octets, bits, caractères, etc.

Par contre, le vecteur est moins flexible que la liste. Avec une liste, en maintenant un pointeur sur une cellule quelconque, il est possible d'insérer une cellule après ce pointeur en $O(1)$. Ce n'est pas le cas avec un vecteur (mais voir section 23.3.4 pour une solution probabiliste de ce problème).

Le vecteur a un autre inconvénient par rapport à la liste : sa taille est limitée. C'est un problème relativement facile à corriger si l'on fait attention à la complexité. L'idée de base est d'allouer un nouveau vecteur plus grand à chaque fois que le vecteur courant est plein et de déplacer les éléments de l'ancien vers le nouveau. Ce n'est pas forcément coûteux. Supposons par exemple, que l'on décide de doubler la taille du vecteur à chaque fois qu'il est plein et que l'on commence par un vecteur de taille 1 (il est souvent plus raisonnable de commencer avec une taille de 5 minimum, voire plus selon l'application). Le coût principal de la réallocation sera le déplacement des objets. Ce coût va doubler à chaque réallocation et va donc correspondre à une série géométrique.

Pour une suite de $n = 2^k$ insertions, on obtient un vecteur de taille $n$, et la suite des coûts de déplacement est $1, 2, 4, \ldots, n/4, n/2$, soit

$$2^0, 2^1, 2^2, \ldots, 2^{k-2}, 2^{k-1}.$$

La somme de cette suite est $2^k - 1$, soit environ $n$. Le coût de l'insertion de $n$ objets est donc en $O(n)$ pour l'insertion elle-même plus un surcoût de déplacement en $O(n)$ ce qui donne un coût total en $O(n)$.

Il n'est pas nécessaire de doubler la taille du vecteur à chaque fois. On peut maintenir la complexité asymptotique avec n'importe quel facteur d'agrandissement. On peut par exemple commencer avec une taille de 5 éléments et augmenter la taille de 40% à chaque fois. Avec un facteur 2, la taille de la mémoire requise peut aller jusqu'à deux fois la taille du vecteur (ce qui est toujours inférieur au surcoût en espace d'une liste), alors qu'avec un facteur de 1.4, le gaspillage est nettement plus faible. La complexité asymptotique augmente avec la constante multiplicative. Le temps d'exécution augmente donc si l'on diminue le facteur d'agrandissement. Comme toujours, le choix sera un compromis qui dépendra des performances requises par l'application : facteur $\ge 2$ pour des applications ayant besoin de rapidité mais dont la consommation de mémoire n'est pas importante et facteur $\le 2$ dans le cas contraire.

Il est important que l'agrandissement soit fait par un facteur et non par une taille fixe. La série des coûts des déplacements ne sera plus géométrique mais arithmétique donnant un surcoût total en $O(n^2)$.

Le surcoût indiqué ci-dessus est calculé à partir d'une suite d'insertions d'éléments et il diminue considérablement lorsque il peut y avoir des suppressions d'éléments. Dans ce cas, il faut faire attention à la consommation de mémoire. Il est souvent prudent de diminuer la taille du vecteur si le taux de remplissage tombe en-dessous d'un seuil donné. Ce seuil ne doit pas être choisi trop élevé. Si, par exemple, il est fixé à 50% pour un facteur d'agrandissement de 2, on peut trouver une suite d'insertions et de suppressions très coûteuse. Dans un vecteur plein, la suite $i,s,s,i,i,s,s,i,i,\ldots$ provoque un agrandissement une fois sur quatre et une compression une fois sur quatre.

Les valeurs suivantes sont souvent raisonnables pour un grand nombre d'applications :

facteur d'agrandissement	2
facteur de compression	2
seuil de compression	25%

Les tableaux ajustables de Common Lisp (voir Section 9.1.3) permettent de programmer cela de manière relativement simple :

vecadjust.lisp

À noter dans ce code :

• l'utilisation de paramètres &key (passage d'arguments par mot-clé),
• l'utilisation de valeurs par défaut des paramètres,
• l'utilisation d'un paramètre dont la valeur est un type (en réalité un symbole ou une liste représentant un type),
• l'utilisation de l'accesseur fill-pointer avec incf et decf,
• la dernière expression des fonctions vector-insert et vector-delete est le vecteur passé en paramètre, afin de renvoyer une valeur utile,
• quand un élément est supprimé, on met nil à la place même si ce n'est pas strictement nécessaire, afin d'éviter qu'un objet supprimé ne soit maintenu vivant par le ramasse-miettes,
• l'utilisation de floor avec deux arguments pour diviser et tronquer simultanément.

Voici comment se servir de ces fonctions :

* (defparameter *v* (make-resizable-vector))

*V*
* (values *v* (length *v*) (array-total-size *v*))

#()
0
8
* (dotimes (i 8) (vector-insert i *v*))

NIL
* (values *v* (length *v*) (array-total-size *v*))

#(0 1 2 3 4 5 6 7)
8
8
* (vector-insert 8 *v*)

#(0 1 2 3 4 5 6 7 8)
* (values *v* (length *v*) (array-total-size *v*))

#(0 1 2 3 4 5 6 7 8)
9
16
* (dotimes (i 4) (vector-delete *v*))

NIL
* (values *v* (length *v*) (array-total-size *v*))

#(0 1 2 3 4)
5
16
* (vector-delete *v*)

#(0 1 2 3)
* (values *v* (length *v*) (array-total-size *v*))

#(0 1 2 3)
4
8
*

On remarque que la fonction length tient compte du fill-pointer alors que array-total-size ne le fait pas.

La technique d'agrandissement automatique doit être employée à chaque fois que le nombre d'éléments n'est pas borné a priori, ou quand le nombre maximal d'éléments est très grand par rapport au nombre moyen d'éléments.

Dans certaines situations, il vaut mieux prévoir un agrandissement automatique, même si cela parait excessif au départ. Un exemple typique est celui des noms de fichiers d'un système d'exploitation. Ces noms ont une taille bornée (définie dans un fichier d'inclusion C pour Unix) et on pourrait penser qu'on peut sans risque utiliser des chaînes de caractères de taille fixe. Pourtant, déjà plusieurs fois par le passé, il s'est produit qu'une nouvelle version d'un système autorise des noms de fichiers plus longs que les versions précédentes. Si on a utilisé un vecteur de taille fixe, une telle situation entraine un travail d'adaptation parfois difficile à chaque changement du système. Pire, le système continue souvent à fonctionner pendant un certain temps, jusqu'à la première fois où quelqu'un utilise un nom de fichier dépassant l'ancienne limitation.