Est-il possible de représenter efficacement la mutation du graphe objet avec des états immuables?

Je m'entraîne à utiliser des objets immuables en C ++. Mon objectif personnel est de représenter un graphe d'objet générique (en tas) avec une séquence de graphes immuables.

Construire le graphique multi-version lui-même n'est pas si difficile. Le problème est la performance. Le contrôle de version à force brute nécessite une copie complète du graphique, ce qui n'était pas acceptable.

J'ai essayé de partager des nœuds inchangés. Mais dans ce cas, j'ai eu un nouveau problème; les références. La référence à un autre objet doit être mise à jour dans tout le graphique. Cela nécessite de visiter tous les nœuds pour chaque fois que je dérive une nouvelle version du graphique. Et cela mute les nœuds avec des références, ils doivent donc également être dérivés (par copie). Les performances ne seront pas meilleures que la copie par force brute.

Autant que je puisse imaginer, il n'y a pas de moyen vraiment efficace de représenter la mutation du graphe d'objet avec des états immuables. Je demande donc une idée à ce sujet.

Est-il possible de représenter efficacement une mutation du graphe objet avec un état immuable?

Ce que vous recherchez s'appelle une structure de données persistante . La ressource canonique pour les structures de données persistantes est le livre Purely Functional Data Structures de Chris Okasaki . Les structures de données persistantes ont suscité un intérêt ces derniers temps en raison de leur vulgarisation à Clojure et Scala.

Cependant, pour une raison étrange, les graphiques persistants semblent être pour la plupart ignorés. Nous avons des listes, des dizaines de différents types d'arbres, des tableaux, des files d'attente prioritaires, des cartes, mais pas de graphiques.

Je n'ai vraiment trouvé qu'un seul article: Graphiques entièrement persistants - lequel choisir?

Si vous ne considérez pas les connexions entre les objets comme faisant partie de votre ressource versionnée (et vous pourriez - dans ce cas, ce qui suit n'aide probablement pas beaucoup), vous pourriez envisager de diviser vos objets en une partie qui représente la partie connectivité de l'objet et une partie qui représente l'état immuable.

Ensuite, vous pouvez avoir chacun des sous-objets de connectivité contenant un vecteur des états versionnés. De cette façon, vous pouvez utiliser un numéro de version de graphique pour accéder à l'état immuable approprié.

Afin d'éviter d'avoir à parcourir l'intégralité du graphique chaque fois qu'il y a une mise à jour vers un nœud spécifique, vous pouvez faire en sorte que si un nœud est accédé avec un numéro de version supérieur à celui de la version actuelle du nœud, la version actuelle est utilisée . Si le nœud est ensuite mis à jour, vous remplissez toutes les versions intermédiaires avec la version précédente - vous permettant ainsi de faire des mises à jour paresseuses du graphique d'objet.

Si la connectivité entre les objets fait partie de votre état versionné, alors ce qui précède ne fonctionne pas. Mais vous pouvez peut-être l'étendre comme suit:

Pour chaque objet du graphique, créez un "objet de poignée". L'objet handle contient la liste des états immuables versionnés. Plutôt que de stocker des références d'objet dans l'un des objets du graphique, vous stockeriez une référence à l'objet de poignée. Ensuite, chaque référence aux objets serait dé-référencée via le handle à l'aide du handle et du numéro de version de la vue du graphique objet qui était en cours de traitement. Cela retournerait l'état immuable correct pour l'objet. Les états immuables utilisent les poignées pour faire référence à d'autres objets dans le graphique, de sorte que vous obtenez toujours la date cohérente pour la version du graphique que vous souhaitez traiter.

La même logique décrite ci-dessus s'applique à la mise à jour des versions dans les poignées - ce qui permet des mises à jour paresseuses et localisées.

Il existe une solution publiée à ce problème avec une très bonne complexité de temps amorti, mais difficile à trouver lorsque vous ne savez pas exactement quoi rechercher. Vous pouvez trouver un bon résumé dans ces notes de cours (consultez la section 2.2.3) ou lire le document original Making Data Structures Persistent . Si votre graphique d'objet a une connectivité limitée (par exemple, des structures arborescentes), vous pouvez même atteindre la complexité O (1) amortie pour la lecture et la mise à jour du graphique immuable, ce qui est impressionnant.

L'idée est que chaque objet, en plus de stocker son état immuable actuel, réserve de l'espace pour enregistrer les changements. Lorsque vous souhaitez créer un nouveau graphique immuable à partir d'un graphique existant en appliquant des modifications, vous devez considérer deux cas:

• L'objet que vous souhaitez modifier a encore de l'espace pour les modifications. Vous pouvez stocker les modifications directement dans l'objet.

• L'objet n'a plus d'espace pour les modifications. Vous créez une nouvelle instance en fonction des valeurs actuelles et des enregistrements de modification vides. Vous devez maintenant mettre à jour récursivement tous les objets référençant l'ancien objet pour référencer le nouvel objet.

  Si l'objet de référence lui-même a encore de l'espace pour les modifications, vous pouvez stocker directement la modification dans la référence, sinon elle se répercute récursivement.

Bien que ce schéma prenne en charge la création efficace de nouvelles générations de graphiques d'objets immuables, il complique la lecture de celui-ci, car vous devez maintenant spécifier la "version" à laquelle vous souhaitez accéder lors de la lecture des données d'un objet immuable. Cela est dû au fait que l'objet immuable peut avoir des informations pour plusieurs versions en raison des enregistrements de modification stockés, vous devez donc spécifier la version que vous souhaitez consulter.

Lors de l'implémentation, j'essaie de masquer cette complexité dans l'API. Lorsque je référence quelque chose dans le graphique immuable de l'extérieur, j'utilise des talons générés au lieu de références directes, donc les appelants n'ont pas besoin de continuer à transmettre manuellement la version souhaitée. Cela rend les références un peu plus chères qu'un pointeur direct, mais je trouve que ça vaut le coup.