Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Structure de données persistante
Résumé
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.