Problème — Mutable ou persistant : une pile qu'on peut annuler — exercice corrigé d'informatique (MP2I/MPI) (chapitre 6)

1. La pile persistante. Elle est déjà écrite : c'est la liste immuable.


module PilePers = struct
  type 'a t = 'a list
  let vide = []
  let empiler x p = x :: p
  let depiler = function [] -> None | x :: r -> Some (x, r)
end

Mesuré, après trois empilages successifs, les quatre versions coexistent :


v0 = []      v1 = [1]      v2 = [2;1]      v3 = [3;2;1]

« Annuler deux fois » consiste à reprendre v1. C'est une opération en $O (1)$ qui ne recalcule rien.

2. Le coût de $k$ versions, mesuré. On construit $100$ versions d'une pile de $1000$ éléments, une fois par partage et une fois par copie complète, et l'on compte les octets alloués :


100 versions par partage (k :: base) :       3 384 octets
100 copies completes                  :  2 405 784 octets

Un maillon occupe trois mots, soit $24$ octets. Les $100$ maillons neufs font $2400$ octets, le tableau qui les tient en fait un millier de plus : le compte est exact. Les copies, elles, allouent $100 \times 1001 \times 24 = 2402400$ octets, à l'octet près.

Le rapport est de $711$ , et la raison tient en une phrase : les $100$ versions partagent la même queue de $1000$ maillons, et ce partage est sûr parce que rien n'est modifiable. Chaque version ne paye que ce qui la distingue de la précédente. C'est ce que l'on appelle la persistance, et l'immuabilité en est la condition.

3. Ce que chacune sait faire.

La persistante sait	La mutable sait
garder toutes les versions, donc annuler et refaire en $O (1)$	modifier en place, sans allouer un maillon
être partagée entre plusieurs calculs sans copie ni verrou	être passée à une fonction qui la remplit, l'appelant voyant le résultat
servir de clé, de valeur de retour, d'argument, sans copie défensive	être vidée sans laisser de trace en mémoire

La bibliothèque standard offre la seconde sous le nom Stack : create, is_empty, push, pop, et l'exception Stack.Empty — vérifié, un pop de trop lève bien Stack.Empty. Après un pop, l'état antérieur n'existe plus : rien ne le retient.

Le critère de choix n'est donc pas une question de goût. Si l'application a besoin d'un « annuler » — un éditeur, un moteur de jeu qui explore des coups, un analyseur qui revient en arrière —, la structure persistante est la réponse, et elle est bon marché. Sinon, la mutable évite les allocations. Le chapitre chap:jeux rencontrera le premier cas, le chapitre chap:parcours le second.

Problème — Mutable ou persistant : une pile qu'on peut annuler

Énoncé

Corrigé

Exercices semblables