Le principe consisté à conserver toutes les opérations de transformations effectuées sur une structure modifiables à la manière d'un gestionnaire de version. C'est ce que tu fais aussi avec tes graphes ? D'ailleurs l'exemple des tableaux persistants est tiré du livre de mon commentaire précédent.
J'ai regardé ton exemple, et si je comprend bien, tu maintient une liste de diff, mais dans le sens inverse. C'est à dire que reroot applique l'ensemble des diff sur le tableau, et modifie les références vers les anciens tableaux pour remplacer ceux-ci par un diff. Ce qui veut dire que si tu accèdes alternativement à un ancienne et une nouvelle version du tableau, tu passes ton temps à faire de la cuisine interne de pointeur pour que le tableau réellement stocké soit à un moment l'ancien et à un moment le nouveau ? Si tu pensais que les shared_ptr était un moyen d'obtenir un pointeur sur un pointeur et de pouvoir modifier le pointeur interne, ce n'est pas le cas. Sinon je ne vois pas trop comment utiliser des shared_ptr dans ton implémentation.
Un shared_ptr n'est rien d'autre qu'un pointeur qui est responsable de la durée de vie de ce qui est pointé. Quand le shared_ptr est copié, le compteur de référence est incrémenté (atomiquement). Quand il est détruit, le compteur de référence est décrémenté, et si il atteint 0, la valeur pointée est aussi détruite. C'est un garbage collector à comptage de référence. Il y a quelques subtilités en plus car le shared_ptr peut pointer sur un objet et maintenir la durée de vie d'un autre objet, c'est pratique si tu veux pointer directement sur les éléments d'une grosse structure et que tu veux garder la grosse structure en vie tant qu'il existe un pointeur sur l'un de ses enfants. C'est un truc inutile dans un contexte avec un garbage collector, puisque c'est le garbage collector qui fait ce travail. Mais en C++, c'est le développeur qui est responsable de la durée de vie de ses éléments alloués sur le tas, et la mode est de plus en plus à l'usage de unique_ptr et shared_ptr pour simplifier ce travail. Les shared_ptr sont un peu l'équivalent du GC de Haskell / OCaml et les unique_ptr sont un peu l'équivalent de la gestion de ressources sur des types linéaires (Grosse simplification, on vas un jour me ressortir cela en entretien et j'aurais honte ;)
Ce que je fais avec mes graph, ils sont non mutables. Quand j'en veux un nouveau, j'en crée une copie intégrale en réutilisant un maximum l'ancien graph. Dans le pire des cas, c'est en O(n) avec n la profondeur maximum du graph. Et je met ce nouveau graph dans ma liste d'opérations effectuée.
En gros, j'ai une liste [graph0, edition (graph0), edition' (edition (graph 0))], mais en pratique l'utilisation mémoire n'est pas équivalente à 3 graph. Après il suffit de bouger le "pointeur" (qui peut être un zipper) sur cette liste pour annuler / refaire. La seule subtilité c'est ce qui se passe quand une nouvelle édition arrive alors que on est pas en queue de liste. Soit on détruit les états suivants (le plus classique). Example, si on annule et que on fait edition'', la liste sera [graph0, edition (graph0), edition'' (edition (graph 0)]. Mais on peut aussi crée un arbre, tel que :
Mais c'est dur à conceptualiser pour les utilisateurs, soit on peut considérer que l'annulation EST une opérations, et donc obtenir la liste suivante : [graph0, edition (graph0), edition' (edition (graph0)), edition (graph0), edition'' (edition (graph0))]. Ce qui est amusant c'est que chaque étape ne coûte rien en mémoire.
Dans ce contexte, j'utilise des shared_ptr pour les pointeurs vers chaque noeuds du graph. Quand je réutilise un nœud dans le graph suivant (ce qui arrive très souvent), alors le shared ptr est incrémenté. En gros cela me gère gratuitement la durée de vie des noeuds de tous les états de mon arbre.
Quand il est tant de faire un peu de ménage, je peux par exemple supprimer les éléments les plus vieux de mon historique. Soit ceux-ci sont encore utilisés par un graph plus récent, et ils sont conservé, soit ils ne le sont pas, le compteur du shared ptr tombe à zéro, et l'élément est supprimé et récursivement le même mécanisme est appliqué à tous ses enfants.
Ce qui est beau avec cette approche c'est qu'il n'est pas nécessaire de stocker la liste des opérations et il n'est pas nécessaire de réfléchir à comment inverser une opération, le code est assez trivial puisque il consiste en une gestion d'une pile d'opération, et chaque nouvelle opération crée une copie modifié du graph et ajoute celle ci dans la pile.
Merci pour la référence bibliographique, je lirais cela dans le train ;)
[^] # Re: Structures non mutables performantes
Posté par Guillaum (site web personnel) . En réponse à la dépêche Sortie de GHC 8.2.1. Évalué à 2.
J'ai regardé ton exemple, et si je comprend bien, tu maintient une liste de diff, mais dans le sens inverse. C'est à dire que
rerootapplique l'ensemble des diff sur le tableau, et modifie les références vers les anciens tableaux pour remplacer ceux-ci par un diff. Ce qui veut dire que si tu accèdes alternativement à un ancienne et une nouvelle version du tableau, tu passes ton temps à faire de la cuisine interne de pointeur pour que le tableau réellement stocké soit à un moment l'ancien et à un moment le nouveau ? Si tu pensais que les shared_ptr était un moyen d'obtenir un pointeur sur un pointeur et de pouvoir modifier le pointeur interne, ce n'est pas le cas. Sinon je ne vois pas trop comment utiliser des shared_ptr dans ton implémentation.Un
shared_ptrn'est rien d'autre qu'un pointeur qui est responsable de la durée de vie de ce qui est pointé. Quand leshared_ptrest copié, le compteur de référence est incrémenté (atomiquement). Quand il est détruit, le compteur de référence est décrémenté, et si il atteint 0, la valeur pointée est aussi détruite. C'est un garbage collector à comptage de référence. Il y a quelques subtilités en plus car leshared_ptrpeut pointer sur un objet et maintenir la durée de vie d'un autre objet, c'est pratique si tu veux pointer directement sur les éléments d'une grosse structure et que tu veux garder la grosse structure en vie tant qu'il existe un pointeur sur l'un de ses enfants. C'est un truc inutile dans un contexte avec un garbage collector, puisque c'est le garbage collector qui fait ce travail. Mais en C++, c'est le développeur qui est responsable de la durée de vie de ses éléments alloués sur le tas, et la mode est de plus en plus à l'usage deunique_ptretshared_ptrpour simplifier ce travail. Lesshared_ptrsont un peu l'équivalent du GC de Haskell / OCaml et lesunique_ptrsont un peu l'équivalent de la gestion de ressources sur des types linéaires (Grosse simplification, on vas un jour me ressortir cela en entretien et j'aurais honte ;)Ce que je fais avec mes graph, ils sont non mutables. Quand j'en veux un nouveau, j'en crée une copie intégrale en réutilisant un maximum l'ancien graph. Dans le pire des cas, c'est en
O(n)avecnla profondeur maximum du graph. Et je met ce nouveau graph dans ma liste d'opérations effectuée.En gros, j'ai une liste
[graph0, edition (graph0), edition' (edition (graph 0))], mais en pratique l'utilisation mémoire n'est pas équivalente à 3 graph. Après il suffit de bouger le "pointeur" (qui peut être un zipper) sur cette liste pour annuler / refaire. La seule subtilité c'est ce qui se passe quand une nouvelle édition arrive alors que on est pas en queue de liste. Soit on détruit les états suivants (le plus classique). Example, si on annule et que on faitedition'', la liste sera[graph0, edition (graph0), edition'' (edition (graph 0)]. Mais on peut aussi crée un arbre, tel que :Mais c'est dur à conceptualiser pour les utilisateurs, soit on peut considérer que l'annulation EST une opérations, et donc obtenir la liste suivante :
[graph0, edition (graph0), edition' (edition (graph0)), edition (graph0), edition'' (edition (graph0))]. Ce qui est amusant c'est que chaque étape ne coûte rien en mémoire.Dans ce contexte, j'utilise des
shared_ptrpour les pointeurs vers chaque noeuds du graph. Quand je réutilise un nœud dans le graph suivant (ce qui arrive très souvent), alors le shared ptr est incrémenté. En gros cela me gère gratuitement la durée de vie des noeuds de tous les états de mon arbre.Quand il est tant de faire un peu de ménage, je peux par exemple supprimer les éléments les plus vieux de mon historique. Soit ceux-ci sont encore utilisés par un graph plus récent, et ils sont conservé, soit ils ne le sont pas, le compteur du shared ptr tombe à zéro, et l'élément est supprimé et récursivement le même mécanisme est appliqué à tous ses enfants.
Ce qui est beau avec cette approche c'est qu'il n'est pas nécessaire de stocker la liste des opérations et il n'est pas nécessaire de réfléchir à comment inverser une opération, le code est assez trivial puisque il consiste en une gestion d'une pile d'opération, et chaque nouvelle opération crée une copie modifié du graph et ajoute celle ci dans la pile.
Merci pour la référence bibliographique, je lirais cela dans le train ;)