Discussion :

[KiLVaiDeN]

Salut,

Je viens de penser à quelque chose, dites moi ce que vous en pensez.

Les algorithmes fréquemment utilisés en matière d'insertion et de suppression d'elements, que ce soient des caractères dans une chaine, ou d'objets dans une liste, sont du type "instantanné". Je peux me tromper et avoir une vision simpliste de la chose sur ce sujet.

Par instantanné, je veux dire que la modification est immediatement faite.

En faisant un parallèle avec ce qui peut être fait avec les bases de données, je me suis demandé pourquoi est-ce qu'on ne pourrait pas avoir une sorte de "queue" des opérations, qui viendraient s'ajouter à "l'objet" conteneur, et lorsqu'on a besoin d'utiliser le contenu de la liste ou de la chaine, on pourrait la "reconstruire" à partir de cette queue ?

Ainsi, une opération de concaténation par exemple lors de la création d'un fichier texte, ne ferait que des ajouts dans la queue, et une étape finale ferait l'écriture; ça pourrait grandement insérer les traitements non ?

C'est une idée simpliste, je ne suis pas sûr des algorithmes utilisées dans ces cas, mais j'ai l'impression que ça pourrait être faisable ?

Merci de me donner votre opinion et A+

[FrancisSourd]

C'est une bonne idée. J'ai déjà entendu parler de cela sous le nom de "lazy data structure". Mais je ne connais pas de texte introductif sur le sujet.

Evidemment, c'est particulièrement utile quand mettre à jour la structure de données après k modifications est aussi coûteux que la mettre à jour après une seule modifications.

[DrTopos]

Il me semble que ce que propose KiLVaiDeN n'est qu'un cas particulier d'évaluation paresseuse (lazy evaluation), en particulier dans les langages fonctionnels où programmes et données sont de même nature. En théorie, il n'y a pas de différence fondamentale entre données (listes, tableaux, etc...) et fonctions. Il y a seulement le fait que ce sont des données de types différents.

On va donc fatalement tomber sur les mêmes problèmes que ceux que pose l'évaluation paresseuse, à savoir, une certaine inflation dans la représentation des données, car il faut représenter des données non encore calculées, et le problème de la maîtrise des ordres d'évaluation, qu'un langage comme Haskell (l'un des très rares à pratiquer l'évaluation paresseuse), traite avec des monades.

Toutefois, il faut noter que dans la mesure où les évaluations sont déterministes (exemptes d'effet de bord), l'ordre n'a pas d'importance (ce qui pourrait bien être le cas pour les exemples cités par Kil). Dans ce cas, le bénéfice de l'évaluation paresseuse est seulement la possibilité de ne pas avoir à calculer quelque chose qui ne servira jamais.

Bien entendu, l'évaluation paresseuse est tentante. On sait en particulier, que dans le cas du calcul de fonctions récursives partielles, c'est la méthode qui a le plus de chances de terminer (théorème de Cadiou), c'est-à-dire en pratique, le moins de risque de lancer une exception.

[KiLVaiDeN]

Merci pour ces informations, je vais me renseigner plus en détail sur le sujet de la "lazy evaluation" ( je préfère les termes anglais en l'occurrence ! )

A+