Re: Structures non mutables performantes

En moyenne chaque copie du graph coûte O(log(n)) en mémoire, ce qui est négligeable et permet de conserver une grande quantité d'étape d'undo/redo. On peut même les sauvegarder avec le fichier. C'est gratuit à faire avec des structures persistantes, modulo qu'en C++ je dois me balader avec des shared_ptr de partout, mais cela fonctionne.

Ton exemple me rappelle un commentaire que j'avais écrit sur une dépêche C++. Freem se demandait à quoi pouvait bien servir les shared_ptr, et de ce que j'en avais compris je lui avais soumis comme idée une structure de tableaux persistants. J'avais bien compris le fonctionnement des shared_ptr ? 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.

Le bouquin est bien fait, toute la seconde partie est consacrée aux structures de données : modifiables ou persistantes avec analyse de la complexité. Une structure que je trouve particulièrement élégante est le zipper de Gérard Huet pour se déplacer facilement à l'intérieur d'un type inductif (listes, arbres...). Le zipper sur les listes a pour type :

type 'a zipper = { left : 'a list ; right : 'a list }

c'est l'exemple des Queues que Okasaki¹ étudie dans la troisième partie de sa thèse. Gérard Huet en propose une version plus détaillée dans la présentation de The Zen Computational Linguistics Toolkit, voir la troisième partie : Top-down structures vs bottom-up structures.

Pour ce qui est du coût mémoire, qui reste acceptable, même avec des structures impératives on peut difficilement faire sans dès que l'on veut pouvoir annuler des opérations. Prenons un exemple idiot et sans grand intérêt : un pointeur sur un int. Si une opération de modification consiste à lui ajouter un int quelconque, il faudra bien conserver cette valeur quelque part au cas où on voudrait annuler l'addition avec une soustraction : la valeur finale contenue dans le pointeur ne contenant aucune information sur la quantité qui lui a été ajoutée. Autant encapsuler toute cette mécanique dans une structure persistante : cela simplifie son usage et le risque de bugs dans le code client de la structure.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.