data-structures
Structure de données de recherche d'union

Introduction

Théorie

Les structures de données de recherche d'union fournissent les opérations suivantes:

• make_sets(n) initialise une structure de données de recherche d'union avec n singletons
• find(i) renvoie un représentant pour l'ensemble de l'élément i
• union(i,j) fusionne les ensembles contenant i et j

Nous représentons notre partition des éléments 0 à n - 1 en stockant un élément parent parent[i] pour chaque élément i qui conduit finalement à un représentant de l'ensemble contenant i .
Si un élément lui-même est un représentant, c'est son propre parent, c.-à-d. parent[i] == i .

Ainsi, si nous commençons avec les ensembles singleton, chaque élément est son propre représentant:

Nous pouvons trouver le représentant pour un ensemble donné en suivant simplement ces pointeurs parents.

Voyons maintenant comment nous pouvons fusionner les ensembles:
Si nous voulons fusionner les éléments 0 et 1 et les éléments 2 et 3, nous pouvons le faire en définissant le parent de 0 à 1 et en définissant le parent de 2 à 3:

Dans ce cas simple, seul le pointeur parent des éléments doit être modifié.
Si nous voulons cependant fusionner des ensembles plus grands, nous devons toujours changer le pointeur parent du représentant de l'ensemble à fusionner dans un autre ensemble: Après la fusion (0,3) , nous avons défini le parent du représentant de l'ensemble. contenant 0 au représentant de l'ensemble contenant 3

Pour rendre l'exemple un peu plus intéressant, fusionnons maintenant (4,5), (5,6) et (3,4) :

La dernière notion que je veux introduire est la compression de chemin :
Si nous voulons trouver le représentant d'un ensemble, il se peut que nous devions suivre plusieurs pointeurs parent avant d'atteindre le représentant. Nous pouvons faciliter cela en stockant le représentant pour chaque ensemble directement dans son nœud parent. Nous perdons l’ordre dans lequel nous avons fusionné les éléments, mais nous pouvons potentiellement avoir un gain d’exécution important. Dans notre cas, les seuls chemins non compressés sont les chemins de 0, 4 et 5 à 3:

Implémentation de base

L'implémentation la plus élémentaire d'une structure de données union-find consiste en un parent tableau stockant l'élément parent pour chaque élément de la structure. Suivre ces «pointeurs» parentaux pour un élément i nous conduit au représentant j = find(i) de l'ensemble contenant i , où parent[j] = j tient.

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi != pj) {        // If the elements are not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

Améliorations: Compression de chemin

Si nous effectuons de nombreuses opérations de merge sur une structure de données union-find, les chemins représentés par les pointeurs parent peuvent être assez longs. La compression de chemin , déjà décrite dans la partie théorique, est un moyen simple d’atténuer ce problème.

Nous pourrions essayer de compresser les chemins sur toute la structure de données après chaque opération de fusion k -th ou quelque chose de similaire, mais une telle opération pourrait avoir un temps d'exécution assez important.

Ainsi, la compression de trajectoire est principalement utilisée uniquement sur une petite partie de la structure, en particulier le chemin que nous empruntons pour trouver le représentant d'un ensemble. Cela peut être fait en stockant le résultat de l’opération de find après chaque sous-ensemble récursif:

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

Améliorations: Union par taille

Dans notre implémentation actuelle de la merge , nous choisissons toujours le jeu de gauche comme étant l’enfant du jeu correct, sans tenir compte de la taille des jeux. Sans cette restriction, les chemins d'accès (sans compression de chemin ) d'un élément à son représentant pourraient être assez longs, ce qui entraînerait des temps d'exécution importants sur les appels de find .

Une autre amélioration courante est l'heuristique union by size , qui fait exactement ce qu'elle dit: lors de la fusion de deux ensembles, nous définissons toujours le plus grand ensemble comme étant le parent du plus petit ensemble, conduisant ainsi à une longueur de chemin d'au plus pas:

Nous stockons un membre supplémentaire std::vector<size_t> size dans notre classe qui est initialisé à 1 pour chaque élément. Lors de la fusion de deux ensembles, le plus grand ensemble devient le parent du plus petit ensemble et nous résumons les deux tailles:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }

Améliorations: Union par rang

Une autre heuristique couramment utilisée à la place de l'union par la taille est l'heuristique union par rang

Son idée de base est que nous n'avons pas besoin de stocker la taille exacte des ensembles, une approximation de la taille (dans ce cas: approximativement le logarithme de la taille de l'ensemble) suffit pour atteindre la même vitesse que l'union par taille.

Pour cela, nous introduisons la notion de rang d'un ensemble, qui est donnée comme suit:

• Singletons ont le rang 0
• Si deux ensembles de rangs inégaux sont fusionnés, l'ensemble ayant le plus grand rang devient le parent tandis que le rang reste inchangé.
• Si deux ensembles de même rang sont fusionnés, l'un d'eux devient le parent de l'autre (le choix peut être arbitraire), son rang est incrémenté.

L'un des avantages de l' union par rang est l'utilisation de l'espace: à mesure que le rang maximal augmente , pour toutes les tailles d'entrée réalistes, le classement peut être stocké dans un seul octet (puisque n < 2^255 ).

Une simple implémentation de l'union par rang pourrait ressembler à ceci:

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }

Amélioration finale: Union par rang avec stockage hors limites

En combinaison avec la compression de chemin, l'union par rang réalise presque des opérations à temps constant sur des structures de données de recherche d'union, mais il existe une dernière astuce qui nous permet de supprimer le rank en stockant les entrées le tableau parent . Il est basé sur les observations suivantes:

• En fait, il suffit de stocker le classement pour les représentants , pas pour les autres éléments. Pour ces représentants, nous n'avons pas besoin de stocker un parent .
• Jusqu'à présent, le parent[i] est au maximum de la size - 1 , c.-à-d.
• Tous les grades sont au plus .

Cela nous amène à l'approche suivante:

• Au lieu de la condition parent[i] == i , nous identifions maintenant les représentants par
  parent[i] >= size
• Nous utilisons ces valeurs hors limites pour stocker les rangs de l’ensemble, c’est-à-dire l’ensemble avec représentant que i rangé parent[i] - size
• Ainsi, nous initialisons le tableau parent avec parent[i] = size au lieu de parent[i] = i , c'est-à-dire que chaque ensemble est son propre représentant avec le rang 0.

Comme nous ne compensons que les valeurs de classement par size , nous pouvons simplement remplacer le vecteur de rank par le vecteur parent dans l’implémentation de la merge et seulement échanger la condition identifiant les représentants dans find :

Implémentation terminée en utilisant l'union par rang et la compression de chemin:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};