Probleme – La structure complète, du contrat au coût mesuré

1. La structure. L'invariant est écrit une fois, au-dessus du type, et toutes les fonctions le préservent.

/* INVARIANT DE STRUCTURE :
     - taille >= 1 et 1 <= classes <= taille ;
     - pour tout x, 0 <= parent[x] < taille ;
     - en suivant parent on atteint une racine (parent[r] == r) : pas de cycle ;
     - pour toute RACINE r, tout arbre de rang r contient au moins 2^rang[r]
       elements (le rang des non-racines est une trace perimee, jamais lue). */
struct uf_s { int* parent; int* rang; int taille; int classes; };
typedef struct uf_s uf;

/* Renvoie une structure a n classes singletons, ou NULL en cas d'echec.
   L'appelant devra appeler uf_detruire. Precondition : n >= 1. */
uf* uf_creer(int n) {
    assert(n >= 1);
    uf* u = malloc(sizeof(uf));
    if (u == NULL) { return NULL; }
    u->parent = malloc((size_t) n * sizeof(int));
    u->rang   = malloc((size_t) n * sizeof(int));
    if (u->parent == NULL || u->rang == NULL) {       /* echec PARTIEL */
        free(u->parent); free(u->rang); free(u); return NULL;
    }
    for (int i = 0; i < n; i = i + 1) { u->parent[i] = i; u->rang[i] = 0; }
    u->taille = n; u->classes = n;
    return u;
}

/* Representant de la classe de x, en aplatissant le chemin.
   Precondition : 0 <= x < u->taille. Cout amorti : quasi constant. */
int uf_trouver(uf* u, int x) {
    assert(u != NULL && 0 <= x && x < u->taille);
    if (u->parent[x] != x) { u->parent[x] = uf_trouver(u, u->parent[x]); }
    return u->parent[x];
}

/* Fusionne les classes de x et y. Renvoie true SI ET SEULEMENT SI une fusion
   a eu lieu -- c'est ce booleen qui permet de tenir le compteur, et c'est lui
   dont Kruskal se sert pour detecter un cycle. */
bool uf_unir(uf* u, int x, int y) {
    int a = uf_trouver(u, x), b = uf_trouver(u, y);
    if (a == b) { return false; }
    if (u->rang[a] < u->rang[b]) { int t = a; a = b; b = t; }  /* a le plus haut */
    u->parent[b] = a;
    if (u->rang[a] == u->rang[b]) { u->rang[a] = u->rang[a] + 1; }
    u->classes = u->classes - 1;
    return true;
}

bool uf_meme_classe(uf* u, int x, int y) {
    return uf_trouver(u, x) == uf_trouver(u, y);
}
int  uf_classes(const uf* u) { assert(u != NULL); return u->classes; }
void uf_detruire(uf* u) {
    if (u != NULL) { free(u->parent); free(u->rang); free(u); }
}

Deux points méritent d'être signalés. La ligne des trois free en cas d'échec partiel rend tout ce qui a déjà été pris — c'est la faute de fuite du chapitre chap:langage-c, à un endroit où l'on ne la cherche pas —, et free(NULL) étant légal, aucun test préalable n'est nécessaire. Ensuite, uf_trouver prend un pointeur non const bien qu'elle soit un accesseur : la compression écrit dans la structure. C'est un accesseur logique qui n'est pas un accesseur physique, et le type le dit honnêtement.

2. Le jeu de tests. La structure représente une relation d'équivalence : le jeu de tests éprouve les trois propriétés, plus le compteur.

void tester_uf(void) {
    uf* u = uf_creer(6);
    assert(uf_classes(u) == 6);
    for (int i = 0; i < 6; i = i + 1) { assert(uf_meme_classe(u, i, i)); } /* reflexivite */
    assert(!uf_meme_classe(u, 0, 1));

    assert(uf_unir(u, 0, 1) == true);
    assert(uf_unir(u, 0, 1) == false);       /* idempotence : deja unis */
    assert(uf_classes(u) == 5);              /* le compteur n'a bouge QU'UNE fois */
    assert(uf_meme_classe(u, 1, 0));         /* symetrie */

    uf_unir(u, 2, 3);
    uf_unir(u, 1, 3);
    assert(uf_meme_classe(u, 0, 2));         /* transitivite : 0 1, 1 3, 3 2 */
    assert(uf_classes(u) == 3);
    assert(!uf_meme_classe(u, 0, 4));        /* et rien de plus n'a fusionne */
    uf_detruire(u);
    printf("structure : tous les tests passent\n");
}

Le test le plus instructif est uf_unir(u, 0, 1) == false suivi de uf_classes(u) == 5 : il éprouve à la fois la valeur de retour et le fait que le compteur ne bouge pas sur une union sans effet. C'est exactement la faute qu'un compteur décrémenté sans condition produirait, et aucun test « nominal » ne la révèle.

3. Les mesures. Sur $400000$ opérations tirées au hasard (moitié unions, moitié recherches) parmi $n=100000$ éléments, en comptant les sauts de pointeur :

Ce que la mesure dit, et qu'un raisonnement asymptotique ne dirait pas. Les trois variantes ont des comportements asymptotiques différents ($O(\log n)$, $O(\log n)$ amorti, $O(\alpha (n))$ amorti), mais sur une entrée réelle l'écart est d'un facteur $3$, pas d'un facteur $\log n=17$. La raison est que $17$ est la hauteur du pire cas, et qu'un tirage uniforme n'y ressemble pas. Le rang seul suffit presque : c'est la compression sans rang qui est mauvaise, parce qu'elle laisse d'abord la forêt dégénérer avant de l'aplatir.

Sans aucune des deux, enfin, une simple suite d'unions en chaîne sur $n=20000$ produit un peigne de profondeur mesurée $19999$ : les deux optimisations ne sont pas des raffinements, elles sont la structure.