Structure de données persistante : Brève description, Notes et références, Annexes Wikipédia, l'encyclopédie libre

Structure de données persistante

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 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.

Brève description

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 puisse ê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.