Disjunktni-set (struktura podataka)

MakeSet creates 8 singletons.

After some operations of Union, some sets are grouped together.

Disjunktni-set je struktura podataka koja prati skup elemenata podeljena u veliki broj disjunktnih (nepreklapajućih) podskupova. Algoritam za pronalaženje skupova je algoritam koji obavlja dve korisne operacije na takve strukture podataka:

Pronađi: Određuje u kom se podskupu nalazi neki element. Ovo može da se koristi za određivanje da li su dva elementa u istom podskupu.
Unija: Spaja dva podskupa u jedan podskup.

Još jedna bitna operacija je NapraviSkup, koja pravi skup koji se sastoji od zadajućeg elementa, drugačije nazvan „singlton“. U cilju preciznije definisati ove operacije, potreban je neki način predstavljanja. Jedan uobičajen pristup je da izaberete fiksni element svakog skupa, koji će biti predstavnik tog skupa, da predstavlja skup kao celinu. Zatim, Pronađi(k) vraća predstavnika skupa u kom se nalazi k, a Unija uzima predstavnike dva skupa kao svoje argumente.

Istorija

Dok su ideje koje su se koristile u disjunktivnim-set šumama dugo bili poznate, Robert Tarjan je bio prvi koji je dokazao gornje granice (i ograničena verziju donje granice) u smislu inverznosti Ackermann function, 1975.^[1] Do toda, najbolja granica za vreme po operaciji, dokazano od strane Hopcroft i Ullman,^[2] bio je dokaz O(log^* n) , iterativni algoritam od n, još jedna sporo rastuća funkcija(ali ne spora koliko i inverzna Ackermann function).

Tarjan i Van Leeuwen su takođe razvili jedan Nađi algoritam koji je efikasniji u praksi ali zadržava nagoru kompleksnost.^[3]

Godine 2007, Sylvain Conchon i Jean-Christophe Filliâtre su razvili upornu strukturu podataka persistent verzija strukture podataka disjunktnih-set šuma, omogućavajući prethodnu verziju strukture da se efikasno zadrže, formalizovaju njegovu ispravnost koristeći dokaz proof assistant Coq.^[4]

Disjunktni-set u povezanim listama

Jednostavan pristup kreiranju Disjunktni-set strukturi je da se stvori povezana lista za svaki skup. Element na čelu svake liste je izabran za svog predstavnika. NapraviSkup kreira listu jednog elementa. Unija spaja dve liste. Nedostatak ovoga je da je operacija Pronađi zahteva linearno vreme, prolazi listu unazad od datog elementa na vrhu liste. Ovo se može izbeći, uključujući u svakom čvoru povezane liste pokazivač na početak (čelo) liste. Onda je operaciji Pronađi potrebno konstantno vreme, jer ovaj pokazivač pokazuje direktno na predstavnika skupa. Međutim, Unija sada mora da ažurira svaki element u listi i sada je njoj potrebno linearno vreme.

Disjunktni-set šume

Ovo su strukture podataka gde je svaki skup predstavljen drvetom (strukurom podataka) u kojoj svaki čvor drži referencu na svog roditelja. Njih su prvi put opisali Bernard A. Gali i Mičael J. Fisčer 1964. godine. Predstavnik svakog seta je koren stabla tog skupa je. Operacija Nađi sledi roditeljske čvorove dok ne stigne do korena. Unija kombinuje dva stabla u jedno priključivanjem korena jednog korenu drugog stabla. Jedan od načina implementacije može biti sledeći:

function MakeSet(x)

     x.parent := x

 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

U ovom naivnom obliku, ovaj pristup nije ništa bolji od pristupa povezanih lista, jer drvo može da bude veoma neuravnoteženo; međutim, može se poboljšati na dva načina. Prvi način koji se zove unija po rankovima je da se uvek manje drvo nadovezuje na koren većeg drveta. U kontekstu ovog algoritma, termin rank se koristi umesto dubine. Drveća sa jednim elementom su definisana da im je rank 0 i kada god se dva drveta koja imaju isti rank „r“ spoje, rezultat ranka je „r+1". Samo primenom ove tehnike najgore vreme izvršavanja je O(log n) za bilo koju od 3 navedene operacije (NapraviSkup, Unija ili Pronađi). Pseudokod:

function MakeSet(x)

     x.parent := x
     x.rank   := 0

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x and y are not already in same set. Merge them.
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

Ove dve tehnike komplemetniraju jedna drugu. Prmenjuju se zajedno vreme za rad je samo $O(\alpha (n))$ , where $\alpha (n)$ is the inverse of the function $n=f(x)=A(x,x)$ , and $A$ ekstremno brzo raste Ackermann function. Pošto $\alpha (n)$ je obrnuto od ove funkcije, $\alpha (n)$ je manje od 5 za sve daljine praktične vrednosti $n$ . Dakle, vreme izvršavanja po operaciji je efikasno mala konstanta.

U stvari, ovo je asimptotski optimalan : Fredman i Saks su pokazali 1989. da <math> \ omega (\ alpha (n)) </ math> reči moraju biti pristupljene bilo kom disjunktnom-skupu struktura podataka po operaciji u proseku^[5]

Primena

Primena disjunktivnog-seta struktura podataka modela podela skupa partitioning of a set, je na primer da pratite povezane komponente (connected components) neusmerenog grafa (undirected graph). Ovaj model se zatim može koristiti za određivanje da li dve grane pripadaju istom čvoru, ili da li će dodavanje granice između njih rezultovati u ciklusom. Unija-Nađi algoritam se koristi u implementacijama visokih performansi Unification.^[6]

Reference

^ Tarjan, Robert Endre (1975). „Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215—225. doi:10.1145/321879.321884.
^ Hopcroft, J. E.; Ullman, J. D. (1973). „Set Merging Algorithms”. SIAM Journal on Computing. 2 (4): 294—303. doi:10.1137/0202024.
^ Tarjan, Robert E.; van Leeuwen, Jan (1984), „Worst-case analysis of set union algorithms”, Journal of the ACM, 31 (2): 245—281
^ Conchon, Sylvain; Filliâtre, Jean-Christophe (oktobar 2007), „A Persistent Union-Find Data Structure”, ACM SIGPLAN Workshop on ML, Freiburg, Germany
^ Fredman, M.; Saks, M. (maj 1989), „The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345—354, „Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.”
^ Knight, Kevin (1989). „Unification: A multidisciplinary survey”. ACM Computing Surveys. 21: 93—124. doi:10.1145/62029.62030.

Spoljašnje veze

C++ implementation, part of the Boost C++ libraries
A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
Java applet: A Graphical Union–Find Implementation, by Rory L. P. McGuire
Wait-free Parallel Algorithms for the Union–Find Problem Arhivirano na sajtu Wayback Machine (18. jul 2008), a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union–Find that never needs to block
Python implementation
Visual explanation and C# code

[1] Tarjan, Robert Endre (1975). „Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215—225. doi:10.1145/321879.321884.

[2] Hopcroft, J. E.; Ullman, J. D. (1973). „Set Merging Algorithms”. SIAM Journal on Computing. 2 (4): 294—303. doi:10.1137/0202024.

[3] Tarjan, Robert E.; van Leeuwen, Jan (1984), „Worst-case analysis of set union algorithms”, Journal of the ACM, 31 (2): 245—281

[4] Conchon, Sylvain; Filliâtre, Jean-Christophe (oktobar 2007), „A Persistent Union-Find Data Structure”, ACM SIGPLAN Workshop on ML, Freiburg, Germany

[5] Fredman, M.; Saks, M. (maj 1989), „The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345—354, „Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.”

[6] Knight, Kevin (1989). „Unification: A multidisciplinary survey”. ACM Computing Surveys. 21: 93—124. doi:10.1145/62029.62030.

[1]

[2]

[3]

[4]

[5]

[6]