From c4bf6a75c7378e2b2735353ecf4f135c5ab33512 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 6 Dec 2011 23:28:35 +0100 Subject: [PATCH] Prepsana cast o Union-Find Dukaz odhadu pres log* prepsan, uz je snad citelnejsi. Nepravdiva poznamka o worst-case slozitosti nahrazena spravnym dolnim odhadem vcetne odkazu. --- 9-decomp/9-decomp.tex | 127 ++++++++++++++++++++++++++++++------------ ga.bib | 20 +++++++ 2 files changed, 110 insertions(+), 37 deletions(-) diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index e769400..08ce770 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -36,33 +36,72 @@ nebo jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla: \itemize\ibull -\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Na~poèátku -jsou v¹echny ranky nulové. Pokud spojujeme +\:{\I Union dle ranku:} ka¾dý koøen $v$ si bude pamatuje svùj rank $r(v)$, co¾ je nìjaké +pøirozené èíslo. Na~poèátku jsou v¹echny ranky nulové. Pokud spojujeme dva stromy s~koøeny $v$, $w$ a $r(v)), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li, rovnou pod koøen. \endlist -\s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude -mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací -bude omezena $\O(\log n)$ v~nejhor¹ím pøípadì.% -\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila. \cite{tarjan84setunion}} +Pro úèely analýzy struktury budeme uva¾ovat také ranky ostatních vrcholù -- ka¾dý vrchol +si ponese svùj rank z~doby, kdy byl naposledy koøenem. Struktura se ov¹em +podle rankù vnitøních vrcholù nijak neøídí a nemusí si je ani pamatovat. +Stromu s~koøenem ranku~$r$ budeme zkrácenì øíkat {\I strom ranku~$r$.} + +\s{Invariant~C:} Na ka¾dé cestì z~vrcholu do~koøene pøíslu¹ného stromu ranky +ostøe rostou. Jinými slovy rank vrcholu, který není koøen, je men¹í, ne¾ je rank +jeho otce. + +\proof +Na poèátku (pro jednovrcholové stromy) tvrzení jistì platí. +Nech» provedeme Union, který pøipojí vrchol~$v$ pod~$w$. Cesty do~koøene z~vrcholù, +které le¾ely pod~$w$, zùstanou zachovány, pouze se vrcholu~$w$ pøípadnì +zvý¹í rank. Cesty z~vrcholù pod~$v$ se roz¹íøí o~hranu~$vw$, na které rank +v~ka¾dém pøípadì roste. +Komprese cest nahrazuje otce vrcholu jeho vzdálenìj¹ím pøedkem, tak¾e se rank +otce mù¾e jedinì zvý¹it. +\qed + +\s{Invariant~R:} Strom ranku~$r$ obsahuje alespoò $2^r$ vrcholù. + +\proof +Indukcí podle èasu. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí. +Nech» pøipojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v) a \. + +K~tomu nám ov¹em staèilo samotné pravidlo Union podle ranku, o~kompresi cest +jsme zatím dokázali pouze to, ¾e slo¾itost v~nejhor¹ím pøípadì nezhor¹uje.% +\foot{Mimochodem, Komprese cest samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila \cite{tarjan84setunion}.} +Kombinace obou metod se ve~skuteènosti chová mnohem lépe: -Amortizovanì se ale popsaná struktura chová daleko lépe: +\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) +Posloupnost $m$~operací \ a \ provedená na~prázdné struktuøe s~$n$ vrcholy +trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.% +\foot{Je známo \cite{fredman:cellprobe}, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout, +a~to ani v~modelu silnìj¹ím ne¾ RAM. Námi uvádìný algoritmus si témìø vystaèí +s~Pointer Machine, jen porovnávání rankù z~tohoto modelu vyboèuje. Slo¾itost +operací v~nejhor¹ím pøípadì je obecnì hor¹í, je znám dolní odhad $\Omega(\log n/\log\log n)$; +více viz Alstrup \cite{alstrup:worstuf}.} -\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované -slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.% -\foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím -pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.} +Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný. Místo toho podobnou +metodou uká¾eme trochu slab¹í výsledek s~iterovaným logaritmem: -Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný, ale naznaèíme alespoò, -¾e amortizovaná èasová slo¾itost je omezena iterovaným logaritmem, konkrétnì ¾e -ve~struktuøe s~$n$ prvky trvá provedení $\ell$~operací Union a Find $\O((n+\ell)\cdot\log^* n)$. +\s{Vìta':} Ve~struktuøe s~$n$ prvky trvá provedení posloupnosti $m$~operací +\ a \ $\O((n+m)\cdot\log^* n)$. \def\up{\mathop{\uparrow}} @@ -72,32 +111,47 @@ $2\up (k+1)=2^{2\up k}$. Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce k~této funkci inverzní. -Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù (vrchol, který ji¾ není -koøenem, si pamatuje svùj poslední rank z~doby, kdy je¹tì koøenem byl): +Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù: $k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té -skupinì, vyu¾ívajíce toho, ¾e vrcholù s~rankem~$r$ je nejvý¹e~$n/2^r$: +skupinì. + +\s{Invariant~S:} V~$k$-té skupinì le¾í nejvý¹e $n/(2\up k)$ vrcholù. + +\proof +Nejprve uká¾eme, ¾e vrcholù s~rankem~$r$ je nejvý¹e $n/2^r$. Kdybychom nekomprimovali +cesty, snadno to plyne z~invariantù~C a~R: ka¾dému vrcholu ranku~$r$ pøiøadíme v¹ech +jeho alespoò $2^r$ potomkù. Jeliko¾ ranky na cestách smìrem ke~koøeni rostou, ¾ádného +potomka jsme nemohli pøiøadit více vrcholùm. Komprese cest ov¹em nemù¾e invariant +poru¹it, proto¾e nemìní ranky ani rozhodnutí, jak probìhne který \. + +Teï u¾ staèí odhad $n/2^r$ seèíst pøes v¹echny ranky ve~skupinì: $$ {n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le {n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} = {n \over 2^{2\up(k-1)}} \cdot 1 = {n \over 2\up k}. $$ +\qed -Operace Union a Find potøebují nekonstantní èas pouze na~vystoupání ze~zadaného vrcholu~$v$ do~koøene stromu -a tento èas je pøímo úmìrný poètu hran na~cestì z~$v$ do~koøene. Tato cesta je následnì rozpojena a v¹echny -vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu. Hrany cesty, které spojují vrcholy z~rùzných -skupin (takových je jistì $\O(\log^* n)$), naúètujeme právì provádìné operaci, tak¾e -jimi celkem strávíme èas $\O(\ell\log^*n)$. Zbylé hrany budeme poèítat pøes celou dobu bìhu -algoritmu a úètovat je vrcholùm. - -Uva¾me vrchol~$v$ v~$k$-té skupinì, který ji¾ není koøenem stromu. Hrana z~$v$ do~jeho rodièe -bude úètována vrcholu~$v$ pouze tehdy, le¾í-li rodiè také v~$k$-té skupinì. Jen¾e -ranky vrcholù na~cestì z~libovolného vrcholu do~koøene ostøe rostou, tak¾e pøi ka¾dém pøepojení -rank rodièe vrcholu~$v$ vzroste, a~proto po~$2\up k$ pøepojeních bude rodiè vrcholu~$v$ v~$(k+1)$-ní -nebo vy¹¹í skupinì. Ka¾dému vrcholu v~$k$-té skupinì tedy úètujeme nejvý¹e $2\up k$ pøepojení -a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù, naúètujeme -celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$. +\>{\sl Dùkaz vìty:} +Operace \ a \ potøebují nekonstantní èas pouze na~vystoupání +po~cestì ze~zadaného vrcholu~$v$ do~koøene stromu. Èas strávený na~této cestì +je pøímo úmìrný poètu hran cesty. Celá cesta je pøitom rozpojena a v¹echny +vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu. + +Hrany cesty, které spojují vrcholy z~rùzných skupin (takových je $\O(\log^* n)$), +naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(\ell\log^*n)$. +Zbylé hrany budeme poèítat pøes celou dobu bìhu algoritmu a úètovat je vrcholùm. + +Uva¾me vrchol~$v$ v~$k$-té skupinì, jeho¾ rodiè le¾í také v~$k$-té skupinì. +Jeliko¾ hrany na cestách do~koøene ostøe rostou, ka¾dým pøepojením vrcholu~$v$ rank jeho +rodièe vzroste. Proto po nejvý¹e $2\up k$ pøepojeních se bude rodiè vrcholu~$v$ nacházet +v~nìkteré z~vy¹¹ích skupin. Jeliko¾ rank vrcholu~$v$ se u¾ nikdy nezmìní, bude hrana z~$v$ +do~jeho otce ji¾ nav¾dy hranou mezi skupinami. Ka¾dému vrcholu v~$k$-té skupinì tedy naúètujeme +nejvý¹e $2\up k$ pøepojení a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù, +naúètujeme celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$. +\qed \h{Union-Find s~pøedem známými Uniony} @@ -112,8 +166,7 @@ dva vrcholy v~t Popí¹eme algoritmus, který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \ i \ v~amortizovanì -konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem v~\cite{alstrup97optimal} -a \cite{alstrup98marked}. +konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}. \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech definujeme: @@ -133,7 +186,7 @@ Vnit vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty. -\s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøepokladu, +\s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøedpokladu, ¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì, hrany komprimovaných cest tuènì. @@ -162,7 +215,7 @@ d Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$ amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas. -\s{Cestová komprese:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem +\s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami: \>$\(x,y)$: diff --git a/ga.bib b/ga.bib index 97419fb..157daa2 100644 --- a/ga.bib +++ b/ga.bib @@ -718,3 +718,23 @@ year={2010}, publisher={Springer} } + +@inproceedings{ fredman:cellprobe, + author = {M. Fredman and M. Saks}, + title = {The cell probe complexity of dynamic data structures}, + booktitle = {STOC '89: Proceedings of the 21st annual ACM Symposium on Theory of Computing}, + year = {1989}, + isbn = {0-89791-307-8}, + pages = {345--354}, + location = {Seattle, Washington, United States}, + doi = {http://doi.acm.org/10.1145/73007.73040}, +} + +@inproceedings{ alstrup:worstuf, + title={Worst-case and amortised optimality in union-find}, + author={Alstrup, S. and Ben-Amram, A.M. and Rauhe, T.}, + booktitle={Proceedings of the 31st annual ACM symposium on Theory of computing}, + pages={499--506}, + year={1999}, + organization={ACM} +} -- 2.39.2