data-structures
Struttura dei dati di reperimento dell'unione

introduzione

Teoria

Le strutture di dati di ricerca dell'Unione forniscono le seguenti operazioni:

• make_sets(n) inizializza una struttura dati di ricerca unione con n singleton
• find(i) restituisce un rappresentante per il set di elementi i
• union(i,j) unisce i set contenenti i e j

Noi rappresentiamo la nostra partizione degli elementi 0 a n - 1 per la memorizzazione di un elemento padre parent[i] per ogni elemento i che alla fine porta ad un rappresentante del set contenente i .
Se un elemento stesso è un rappresentante, è il suo genitore, cioè parent[i] == i .

Quindi, se iniziamo con le serie singleton, ogni elemento è il suo rappresentante:

Possiamo trovare il rappresentante per un determinato set semplicemente seguendo questi indicatori parent.

Vediamo ora come possiamo unire i set:
Se vogliamo unire gli elementi 0 e 1 e gli elementi 2 e 3, possiamo farlo impostando il genitore da 0 a 1 e impostando il genitore da 2 a 3:

In questo caso semplice, solo il puntatore genitore degli elementi stesso deve essere modificato.
Se tuttavia vogliamo unire insiemi più grandi, dobbiamo sempre cambiare il puntatore genitore del rappresentante del set che deve essere unito in un altro insieme: Dopo l' unione (0,3) , abbiamo impostato il genitore del rappresentante del set contenente 0 al rappresentante del set contenente 3

Per rendere l'esempio un po 'più interessante, ora uniamo anche (4,5), (5,6) e (3,4) :

L'ultima nozione che voglio introdurre è la compressione del percorso :
Se vogliamo trovare il rappresentante di un set, potremmo dover seguire diversi indicatori parentali prima di raggiungere il rappresentante. Potremmo semplificare questo compito memorizzando il rappresentante per ciascun set direttamente nel nodo principale. Perdiamo l'ordine in cui abbiamo unito gli elementi, ma possiamo potenzialmente avere un grande guadagno in runtime. Nel nostro caso, i soli percorsi che non sono compressi sono i percorsi da 0, 4 e 5 a 3:

Implementazione di base

L'implementazione più elementare di una struttura dati di ricerca unione è costituita da un array parent memorizza l'elemento genitore per ogni elemento della struttura. Seguendo questi 'puntatori' genitore per un elemento i ci conduce al rappresentante j = find(i) dell'insieme contenente i , dove parent[j] = j tiene.

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

Miglioramenti: compressione del percorso

Se eseguiamo molte operazioni di merge in una struttura dati di ricerca unione, i percorsi rappresentati dai puntatori parent potrebbero essere piuttosto lunghi. La compressione del percorso , come già descritto nella parte teorica, è un modo semplice per mitigare questo problema.

Potremmo cercare di fare la compressione percorso su tutta la struttura dei dati dopo ogni k -esimo operazione di unione o qualcosa di simile, ma una simile operazione potrebbe avere una abbastanza grande runtime.

Pertanto, la compressione del percorso viene principalmente utilizzata solo su una piccola parte della struttura, in particolare il percorso che percorriamo per trovare il rappresentante di un set. Questo può essere fatto memorizzando il risultato dell'operazione di find dopo ogni chiamata secondaria ricorsiva:

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
}

Miglioramenti: Unione per dimensione

Nella nostra attuale implementazione di merge , scegliamo sempre il set di sinistra per essere il figlio del set giusto, senza prendere in considerazione la dimensione dei set. Senza questa restrizione, i percorsi (senza compressione del percorso ) da un elemento al suo rappresentante potrebbero essere piuttosto lunghi, portando così a grandi runtime nelle chiamate di find .

Un altro miglioramento comune è quindi l' unione per euristica delle dimensioni , che fa esattamente quello che dice: quando uniamo due set, impostiamo sempre il set più grande come genitore del set più piccolo, portando così a una lunghezza del percorso al massimo passaggi:

Archiviamo un membro aggiuntivo std::vector<size_t> size nella nostra classe che viene inizializzato a 1 per ogni elemento. Quando si uniscono due set, il set più grande diventa il padre del set più piccolo e si sommano le due dimensioni:

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
    }

Miglioramenti: Unione per grado

Un altro euristico comunemente usato al posto dell'unione per dimensione è l' unione per grado euristico

L'idea di base è che non abbiamo realmente bisogno di memorizzare la dimensione esatta dei set, è sufficiente un'approssimazione della dimensione (in questo caso: approssimativamente il logaritmo della dimensione dell'insieme) per ottenere la stessa velocità dell'unione per dimensione.

Per questo, introduciamo la nozione di rango di un insieme, che viene data come segue:

• I singleton hanno il grado 0
• Se vengono uniti due set con un rank non uguale, l'insieme con rank più grande diventa il genitore mentre il rank rimane invariato.
• Se si uniscono due insiemi di rango uguale, uno di essi diventa il genitore dell'altro (la scelta può essere arbitraria), il suo rango viene incrementato.

Un vantaggio dell'unione per rango è l'uso dello spazio: dato che il grado massimo aumenta all'incirca come , per tutte le dimensioni di input realistiche, il rank può essere memorizzato in un singolo byte (poiché n < 2^255 ).

Una semplice implementazione dell'unione per grado potrebbe apparire come questa:

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

Miglioramento finale: Unione per rank con memoria fuori dai limiti

Mentre in combinazione con la compressione del percorso, l'unione per grado raggiunge quasi le operazioni a tempo costante su strutture di dati union-find, c'è un trucco finale che ci permette di sbarazzarci dell'archiviazione del rank memorizzando il rango in voci fuori campo di l'array parent . Si basa sulle seguenti osservazioni:

• In realtà, abbiamo solo bisogno di memorizzare il rango per i rappresentanti , non per altri elementi. Per questi rappresentanti, non è necessario memorizzare un parent .
• Finora, il parent[i] è al massimo delle size - 1 , cioè i valori più grandi non sono usati.
• Tutti i ranghi sono al massimo .

Questo ci porta al seguente approccio:

• Invece della condizione parent[i] == i , ora identifichiamo i rappresentanti di
  parent[i] >= size
• Usiamo questi valori fuori limite per archiviare i ranghi del set, cioè l'insieme con il rappresentante i ha il parent[i] - size rango parent[i] - size
• Quindi inizializziamo l'array genitore con parent[i] = size invece di parent[i] = i , cioè ogni insieme è il suo rappresentante con il grado 0.

Dal momento che abbiamo solo compensato i valori di rango per size , possiamo semplicemente sostituire il vettore di rank con il vettore parent nell'implementazione di merge e solo bisogno di scambiare la condizione identificando i rappresentanti nella find :

Implementazione terminata usando union per rank e path compression:

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