Structure de données 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 ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures.

Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée. S'il existe une opération permettant la fusion de deux versions antérieures, la structure est dite confluente. Les structures qui ne sont pas persistantes sont dites éphémères.

Ce type de structures de données est particulièrement courant en programmation logique et fonctionnelle. Dans un programme purement fonctionnel, où toute donnée est immuable, les structures de données sont automatiquement totalement persistantes. Les structures persistantes peuvent aussi être obtenues en utilisant des modifications en place des données et peuvent alors être parfois plus efficaces, en temps ou en espace, que leurs contreparties purement fonctionnelles.

Bien que la persistance peut être obtenue par une simple copie, c'est en général une solution inefficace en temps et en espace, car la plupart des opérations n'effectuent que peu de changements dans une structure de données. Une meilleure solution consiste à exploiter les similarités entre les anciennes versions et la nouvelle, telles que des sous-arbres communs dans un certain nombre de structures d'arbre. Parce qu'il devient rapidement difficile de déterminer quelles sont les parties de la structure effectivement partagées entre plusieurs versions, et parce qu'il est souvent souhaitable de supprimer des versions devenues inutiles, la présence d'un ramasse-miettes s'impose naturellement.

La structure de données persistante la plus simple est sans doute celle de liste simplement chaînée, où chaque élément contient une référence vers l'élément suivant dans la liste. Une telle structure est persistante si les opérations se limitent à extraire un suffixe d'une liste, c'est-à-dire les k derniers éléments pour un certain k, et à y ajouter de nouveaux éléments en tête. Le suffixe peut alors être partagé entre l'ancienne liste et la nouvelle, au lieu d'être dupliqué. Tant que les éléments sont immuables, ce partage reste invisible.

De nombreuses structures de données, telles que les arbres bicolores ou les files, peuvent facilement être adaptées pour être persistantes. Une version persistante de la structure de tableau est la structure de VList introduite en 2002 par Phil Bagwell.

Sommaire

Notes et références

Annexes

Articles connexes

Liens externes

Bibliographie


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Structure de données persistante 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

  • 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 …   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

  • Java Framework de persistence — Persistance (informatique) Pour les articles homonymes, voir persistance. En programmation, la gestion de persistance des données (en anglais : persistence) et éventuellement des états de programme se réfère au mécanisme responsable de la… …   Wikipédia en Français

  • Java Frameworks de persistence — Persistance (informatique) Pour les articles homonymes, voir persistance. En programmation, la gestion de persistance des données (en anglais : persistence) et éventuellement des états de programme se réfère au mécanisme responsable de la… …   Wikipédia en Français

  • Persistance (informatique) — Pour les articles homonymes, voir persistance. En programmation, la gestion de persistance des données (en anglais : persistence) et éventuellement des états de programme se réfère au mécanisme responsable de la sauvegarde et la restauration …   Wikipédia en Français

  • Purement fonctionnel — En informatique, l adjectif purement fonctionnel désigne un algorithme, une structure de données ou un langage de programmation qui exclut les modifications destructives. Par conséquent, les variables en sont exclues et les identificateurs… …   Wikipédia en Français

  • Transparence referentielle — Transparence référentielle La transparence référentielle est une propriété des langages de programmation qui fait que chaque expression peut être remplacée par son résultat sans changer le comportement du programme. Sommaire 1 Définition 2… …   Wikipédia en Français

  • Transparence référentielle — La transparence référentielle est une propriété des expressions d un langage de programmation qui fait qu une expression peut être remplacée par son résultat sans changer le comportement du programme. Sommaire 1 Définition 2 Exemples et contre… …   Wikipédia en Français

  • Business Intelligence — Informatique décisionnelle Pour les articles homonymes, voir DSS et BI. L’informatique décisionnelle (Management du système d information, en anglais : DSS pour Decision Support System ou encore BI pour Business Intelligence) désigne les… …   Wikipédia en Français

Share the article and excerpts

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