VList

En algorithmique, une VList est une structure de données persistante (conçue par Phil Bagwell en 2002), qui combine l'accès rapide aux éléments (comme dans les tableaux) avec la souplesse d'extension des listes simplement chaînées.

Performances

Les VLists permettent un accès en temps constant (en moyenne). De plus elles sont très compactes puisque seulement O(log n) pointeurs sont utilisés en interne en plus des éléments eux-mêmes ; ils peuvent donc également profiter des propriétés de localité des données.

Les opérations sur les VLists sont :

• Accès au k^e élément : O(1) en moyenne, O(log n) dans le pire des cas.
• Ajout d'un élément en début de liste : O(1) en moyenne, plus parfois une allocation de mémoire.
• Obtention de la liste commençant au 2^e élément d'une liste existante : O(1)
• Calcul de la longueur de la liste : O(log n) .

Avantages

Les VLists, contrairement aux tableaux, ont la propriété que différentes versions mises à jour de la VList partagent automatiquement leur structure. Comme elles sont immuables, elles sont utiles en programmation fonctionnelle : leurs performances permettent une implémentation purement fonctionnelle de structures qui requièrent d'habitude des tableaux classiques, comme les tables de hachage.

Inconvénients

• L’immuabilité a son revers: il est coûteux de modifier des éléments au milieu de la liste (sauf dans le cas des dequeues à base de VLists (VDLists), implémentées de façon non immuable, qui conservent un accès en temps constant aux éléments).
• L'accès aux éléments de la fin de la liste coûte O(log n). C'est mieux qu'avec une liste chaînée, mais évidemment moins performant qu'avec un tableau à accès direct.
• L'espace inutilisé dans le dernier bloc alloué est en 0(n), soit, en espérance, la moitié de la taille de ce bloc. Et lorsque la VList est utilisée en mode totalement persistant, le gâchis est encore plus grand, à tel point que la structure peut se révéler inadéquate : il faut alors adapter le facteur de croissance géométrique de la taille du prochain bloc à allouer.

Structure

La VList (2,3,4,5,6)

La structure interne d'une VList est une liste simplement chaînées de tableaux (blocs), dont la taille croît géométriquement. Avec un facteur de croissance de deux, le dernier bloc alloué contient la moitié des éléments de la liste, le suivant la moitié du reste, etc. Le facteur de croissance reste un paramètre que l'on peut ajuster.

Chaque bloc stocke des informations telles que sa taille, et le pointeur vers le bloc suivant (i.e. précédemment alloué).

L'accès se fait en temps constant en espérance : étant donné un index valide, on parcourt les blocs en regardant leur taille (homogène à un nombre d'éléments), jusqu'à avoir atteint le bon bloc. Or, il y a 1 chance sur 2 que l'élément recherché appartienne au premier bloc parcouru, 1 chance sur 4 pour qu'il appartienne au deuxième, etc. L'espérance du nombre moyen de pointeurs à suivre est donc :

$\sum _{i=1}^{\lceil log_{2}n\rceil }{\frac {i-1}{2^{i}}}<\sum _{i=1}^{\infty }{\frac {i-1}{2^{i}}}=1.$

Toute référence à une VList est en fait une paire <base, offset>, dont l’offset indique la position du premier élément à considérer dans le bloc.

Retirer le premier élément de la liste consiste donc simplement à incrémenter l’offset de 1, sauf en fin de bloc, auquel cas on passe au bloc suivant et on remet l’offset à zéro. Si une référence est la dernière à délaisser un bloc, celui-ci doit être soit explicitement libéré, soit pris en charge par un ramasse-miettes.

Comme la liste est construite de façon incrémentale, le premier bloc parcouru dans la liste chaînée des blocs peut ne pas contenir deux fois plus de valeurs que le suivant. Cela influence très peu les performances. L'espace mémoire est néanmoins alloué, et ajouter un élément en début de liste revient donc à remplir une case du tableau et à mettre à jour les compteurs. Lorsque le bloc est plein, on en crée un nouveau deux fois (ou de n'importe quelle valeur du facteur de croissance) plus grand, qui pointe vers l'ancien.

Extensions

Il est possible de construire de nombreuses structures de données performantes à l'aide des VLists, comme des tampons (buffers) circulaires, des dequeues (immuables ou non), des listes de types variables ou non, ou des tableaux à taille variable et des piles.

La paire <base, offset> est en pratique sous-optimale à manier (deux indirections coûteuses). Bagwell décrit une implémentation avec des blocs pouvant comporter jusqu'à $2^{23}$ éléments sur des machines avec une largeur de bus d'adressage de 32 bits, et n'utilisant qu'un seul pointeur pour référencer la Vlist, tout en conservant les autres attraits de sa structure de données (types d'éléments variables (jusqu'à 16), ramasse-miettes, dequeues, etc.)

On peut facilement étendre les VList pour leur conférer la facilité d'utilisation des listes doublement chaînées. Il peut être souhaitable de leur intégrer un verrou (mutex) pour rendre leur utilisation sans risque avec des processus légers (thread-safe).

Lien externe

• Le papier de Phil Bagwell[PDF] - à l'EPFL