data-structures
Union-find gegevensstructuur

Invoering

Theorie

Zoekstructuren van Union vinden de volgende bewerkingen mogelijk:

• make_sets(n) initialiseert een union-find datastructuur met n singletons
• find(i) retourneert een vertegenwoordiger voor de set van element i
• union(i,j) voegt de sets met i en j

We vertegenwoordigen onze partitie van de elementen 0 tot n - 1 door een ouderelement parent[i] op te slaan voor elk element i dat uiteindelijk leidt tot een vertegenwoordiger van de set met i .
Als een element zelf een vertegenwoordiger is, is het zijn eigen ouder, dat wil zeggen parent[i] == i .

Dus als we met singleton sets beginnen, is elk element zijn eigen vertegenwoordiger:

We kunnen de vertegenwoordiger voor een bepaalde set vinden door eenvoudigweg deze bovenliggende aanwijzingen te volgen.

Laten we nu kijken hoe we sets kunnen samenvoegen:
Als we de elementen 0 en 1 en de elementen 2 en 3 willen samenvoegen, kunnen we dit doen door de ouder van 0 op 1 in te stellen en de ouder van 2 op 3 in te stellen:

In dit eenvoudige geval moeten alleen de bovenliggende elementen van de elementen worden gewijzigd.
Als we echter grotere sets willen samenvoegen, moeten we altijd de bovenliggende aanwijzer wijzigen van de vertegenwoordiger van de set die moet worden samengevoegd in een andere set: Na samenvoegen (0,3) hebben we de bovenliggende instelling van de vertegenwoordiger van de set ingesteld met 0 voor de vertegenwoordiger van de set met 3

Om het voorbeeld een beetje interessanter te maken, laten we nu ook (4,5), (5,6) en (3,4) samenvoegen :

Het laatste idee dat ik wil introduceren is padcompressie :
Als we de vertegenwoordiger van een set willen vinden, moeten we mogelijk meerdere bovenliggende aanwijzingen volgen voordat we de vertegenwoordiger bereiken. We kunnen dit gemakkelijker maken door de vertegenwoordiger voor elke set rechtstreeks in het bovenliggende knooppunt op te slaan. We verliezen de volgorde waarin we de elementen hebben samengevoegd, maar kunnen mogelijk een grote looptijdwinst opleveren. In ons geval zijn de enige paden die niet zijn gecomprimeerd de paden van 0, 4 en 5 tot 3:

Basis implementatie

De meest eenvoudige implementatie van een uniestructuur voor het vinden van gegevens bestaat uit een array- parent die het ouder-element voor elk element van de structuur opslaat. Het volgen van deze 'pointers' voor een element i leidt ons naar de representatieve j = find(i) van de set met i , waar parent[j] = j geldt.

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
        }
    }
};

Verbeteringen: Padcompressie

Als we veel merge uitvoeren op een uniestructuur voor het vinden van gegevens, kunnen de paden die worden weergegeven door de parent aanwijzers behoorlijk lang zijn. Padcompressie , zoals al beschreven in het theoriegedeelte, is een eenvoudige manier om dit probleem te verminderen.

We kunnen proberen om padcompressie op de hele gegevensstructuur uit te voeren na elke k-de samenvoegbewerking of iets dergelijks, maar een dergelijke bewerking kan een vrij grote looptijd hebben.

Daarom wordt padcompressie meestal alleen op een klein deel van de structuur gebruikt, vooral het pad waar we langs lopen om de vertegenwoordiger van een set te vinden. Dit kan worden gedaan door na elke recursieve suboproep het resultaat van de find te slaan:

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
}

Verbeteringen: Unie op grootte

In onze huidige implementatie van merge , kiezen we altijd de linker set als het kind van de juiste set, zonder rekening te houden met de grootte van de sets. Zonder deze beperking kunnen de paden (zonder padcompressie ) van een element naar zijn vertegenwoordiger behoorlijk lang zijn, wat leidt tot grote runtimes bij find aanroepen.

Een andere veel voorkomende verbetering is dus de unie per grootte- heuristiek, die precies doet wat er staat: Wanneer we twee sets samenvoegen, stellen we altijd de grotere set in als ouder van de kleinere set, wat dus leidt tot een padlengte van maximaal stappen:

We slaan een extra lid std::vector<size_t> size in onze klasse die voor elk element wordt geïnitialiseerd op 1. Bij het samenvoegen van twee sets wordt de grotere set de ouder van de kleinere set en we sommen de twee formaten op:

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
    }

Verbeteringen: Union op rang

Een andere heuristiek die gewoonlijk wordt gebruikt in plaats van unie per grootte is de unie per rang heuristiek

Het basisidee is dat we eigenlijk niet de exacte grootte van de sets hoeven op te slaan, een benadering van de grootte (in dit geval: grofweg de logaritme van de grootte van de set) volstaat om dezelfde snelheid te bereiken als unie per grootte.

Hiervoor introduceren we de notie van de rang van een set, die als volgt wordt gegeven:

• Singletons hebben rang 0
• Als twee sets met een ongelijke rang worden samengevoegd, wordt de set met een grotere rang de ouder, terwijl de rang ongewijzigd blijft.
• Als twee sets van gelijke rang worden samengevoegd, wordt de ene de ouder van de andere (de keuze kan willekeurig zijn), wordt de rang verhoogd.

Een voordeel van unie per rang is het ruimtegebruik: omdat de maximale rang ongeveer stijgt , voor alle realistische invoerformaten, kan de rang worden opgeslagen in een enkele byte (sinds n < 2^255 ).

Een eenvoudige implementatie van union by rank kan er zo uitzien:

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];
        }
    }

Laatste verbetering: Unie op rang met out-of-bounds opslag

Hoewel in combinatie met padcompressie Union by Rank bijna constante tijdsbewerkingen op unie-vind datastructuren realiseert, is er een laatste truc waarmee we de rank volledig kunnen verwijderen door de rang op te slaan in niet-toegestane vermeldingen van de parent array. Het is gebaseerd op de volgende opmerkingen:

• We moeten eigenlijk alleen de rang opslaan voor vertegenwoordigers , niet voor andere elementen. Voor deze vertegenwoordigers hoeven we geen parent te slaan.
• Tot nu toe is parent[i] maximaal size - 1 , dat wil zeggen dat grotere waarden niet worden gebruikt.
• Alle rangen zijn hoogstens .

Dit brengt ons bij de volgende aanpak:

• In plaats van de voorwaarde parent[i] == i , identificeren we nu vertegenwoordigers door
  parent[i] >= size
• We gebruiken deze out-of-bounds-waarden om de rangen van de set op te slaan, dwz de set met representatief i heeft parent[i] - size
• Dus initialiseren we de bovenliggende array met parent[i] = size plaats van parent[i] = i , dat wil zeggen dat elke set zijn eigen vertegenwoordiger is met rang 0.

Omdat we alleen compensatie van de rang waarden door size , kunnen we gewoon de plaats van de rank vector door de parent vector in de uitvoering van de merge en hoeft alleen de voorwaarde het identificeren van vertegenwoordigers in ruil find :

Implementatie voltooid met unie door rang- en padcompressie:

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];
        }
    }
};