Compresser sans récursion

La version en deux passes — une pour trouver la racine, une pour raccrocher :

(* Racine de x, en aplatissant le chemin parcouru. Espace de pile : O(1).
   Precondition : p est une foret (p.(r) = r pour toute racine r). *)
let trouver p x =
  let r = ref x in
  while p.(!r) <> !r do r := p.(!r) done;          (* passe 1 : la racine *)
  let c = ref x in
  while p.(!c) <> !c do
    let suivant = p.(!c) in
    p.(!c) <- !r;                                  (* passe 2 : on raccroche *)
    c := suivant                                   (* RETENIR avant d'ecraser *)
  done;
  !r

Terminaison : variant de la passe 1, la distance de !r à la racine, qui décroît de $1$ ; même variant pour la passe 2. Correction : à la fin de la passe 2, tout nœud du chemin pointe vers !r. La ligne let suivant = p.(!c) est le piège habituel — c'est celui du renversement de liste du chapitre chap:langage-c : retenir avant d'écraser.

Sur un peigne de $10$ éléments, un trouver(9) donne pour les deux versions la même forêt, mesurée :

[| 0; 0; 0; 0; 0; 0; 0; 0; 0; 0 |]

La version en une passe (division de chemin) : au lieu d'aplatir complètement, on fait pointer chaque nœud vers son grand-père.

let trouver p x =
  let c = ref x in
  while p.(!c) <> !c do
    p.(!c) <- p.(p.(!c));      (* on saute un noeud sur deux *)
    c := p.(!c)
  done;
  !c

Sur le même peigne, elle laisse [| 0; 0; 1; 1; 3; 3; 5; 5; 7; 7 |] : le chemin est divisé par deux, pas aplati.

La mesure tranche. Sur $400000$ opérations tirées au hasard parmi $n=100000$ éléments, le nombre total de sauts de pointeur vaut :

La division de chemin gagne parce qu'elle ne parcourt le chemin qu'une fois là où l'aplatissement complet le parcourt deux fois — et elle offre la même garantie asymptotique. C'est elle qu'emploient les bibliothèques.

Et la dernière ligne du tableau est la vraie leçon : la compression seule, sans union par rang, est trois fois plus chère que le rang seul. Les deux optimisations ne s'additionnent pas, elles se complètent.