VList (structure de données)

VList (structure de données)

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.

Sommaire

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[1].

Les opérations sur les VLists sont :

  • Accès au ke é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 2e é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 à jours 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'à 223 é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).

Notes

Lien externe

Ce document provient de « VList ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article VList (structure de données) de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Structure de donnees persistante — Structure de données persistante En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu elle est modifiée ; une telle structure est observationnellement immuable, car… …   Wikipédia en Français

  • Structure de données persistante — En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu elle est modifiée ; une telle structure est observationnellement immuable, car ses opérations ne la modifient pas …   Wikipédia en Français

  • 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. Sommaire 1… …   Wikipédia en Français

  • Vlist — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Vlist, commune néerlandaise, située en Hollande Méridionale, Vlist, hameau de cette commune, Vlist, rivière néerlandaise. En informatique, la structure de …   Wikipédia en Français

  • .xml — Extensible Markup Language Extensible Markup Language Extension de fichier .xml Type MIME application/xml, text/xml Développé par World Wide Web Consortium Type de format …   Wikipédia en Français

  • Dialecte XML — Extensible Markup Language Extensible Markup Language Extension de fichier .xml Type MIME application/xml, text/xml Développé par World Wide Web Consortium Type de format …   Wikipédia en Français

  • EXtensible Markup Language — Extension de fichier .xml Type MIME application/xml, text/xml Développé par World Wide Web Consortium Type de format …   Wikipédia en Français

  • Element XML — Extensible Markup Language Extensible Markup Language Extension de fichier .xml Type MIME application/xml, text/xml Développé par World Wide Web Consortium Type de format …   Wikipédia en Français

  • Extensible Markup Language — Extension .xml Type MIME application/xml, text/xml Développé par …   Wikipédia en Français

  • Extensible markup language — Extension de fichier .xml Type MIME application/xml, text/xml Développé par World Wide Web Consortium Type de format …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”