7 \def\pnromanp{(\nroman)}
8 \def\pnromanap{(\nroman ')}
10 % Vlozeni obrazku {obrazek}{popisek}
11 \def\nosizefigure#1#2{\bigskip\vbox{\centerline{\epsfbox{#1}}\smallskip\centerline{#2}}\bigskip}
15 \prednaska{8}{Q-Heaps \& Union-Find problem}{zapsali Cyril Strejc a Ale¹
18 Na minulém semináøi jsme si mimo jiné ukázali výpoèetní model RAM a nahlédli
19 jsme, ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat
20 vektorový poèítaè. A kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké
21 datové struktury bychom s ním mohli vytváøet. Vektor ukládáme v $\O(w)$ slovech.
23 pøedpokládat, ¾e hodnoty, které do stuktur ukládáme, jsou rùzné. Svým sna¾ením
24 smìrujeme ke strukturám, které zvládnou operace {\it Insert} a {\it Delete} v
25 kostantním èase s rozumnou konstantou.
29 \: $w$, ¹íøka slova daného stroje (RAMu)
30 \: $n$, velikost vstupu
32 Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$.
34 \h{Word-Encoded B-Tree}
35 V podstatì pùjde o obyèejný B-strom s daty v listech. Faktor stromu oznaème $B$.
36 Ukládáme $k$-bitové hodnoty a chceme aby $Bk=\O(w)$ -- tehdy se nám uzel stromu
37 vejde do vektoru a my budeme dostateènì rychle umìt operace s uzly, které do
38 B-stromu potøebujeme, t.j. dìlení, spojování, vyhledávání. Té¾ ukládáme pointry
39 na syny. Je tøeba si trochu rozmyslet, ¾e v ka¾dém uzlu se pointry na syny také
40 povede ``scucnout'' do vektoru. Jen¾e poèet prvkù ($\vert T\vert$), které se do
41 stromu vejdou je øádovì $B^h$, kde $h$ je hloubka stromu, a tudí¾ $\log\vert
42 T\vert = \O(h)$. Proto se pointry do vektoru pìknì vejdou.
46 Q-Heap je teoreticky zajímavá datová struktura, v praxi neimplementovatelná.
47 Narozdíl od Word-Encoded B-Tree není takové omezení na velikost ukládaného èísla
48 -- maximální velikost èísla odpovídá velikost slova.
53 \: $r\le k$, poèet prvkù v Q-haldì
54 \: $x_1 < \ldots < x_r$, prvky (o $w$ bitech) v Q-haldì
55 \: $\X = (x_1,\ldots,x_r)$
56 \: $c_i = \msb(x_i \oplus x_{i+1})$, nejvy¹¹í bit, na kterém se li¹í $x_i$ a
58 \: $\rank_\X(x)$, poèet prvkù mno¾iny $\X$, které jsou men¹í ne¾ $x$.
59 Samotné $x$ ov¹em nemusí být prvek mno¾iny $\X$.
62 Haldové operace budeme umìt v $\O(1)$, nicménì bude nutný preprocesing v èase
63 $\O(2^{k^4})$, co¾ ov¹em není tak hrozné, jak na prní pohled vypadá, jeliko¾
64 $k = \O(\root 4 \of {\log n})$, èili nakonec ho stihneme v lineárním èase.
66 A jak to tedy vypadá? Prvky $x_1,\ldots,x_r$ budeme ukládat do tzv. trie.
67 {\it Trie} je binární strom s prvky (daty) v listech, v na¹em pøípadì s
68 hodnotami $x_1,\ldots,x_r$. Popí¹u konstrukci trie. Oznaèím $c = \max(c_i)$.
69 Mno¾inu $\X$ rozdìlíme na dvì mno¾iny, podle hodnot prvkù na $c$-tém bitu v
70 binárním zápisu: $$ \X_0 = \{ x_i \vert x_i \in \X\and x_i[c]=0 \}$$
71 $$ \X_1 = \{x_i \vert x_i \in \X\and x_i[c]=1\}$$
73 Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$
75 Èíslo $c$ -- øíkejme mu znaèka -- vlo¾íme do koøene právì budovaného (pod)stromu
76 a jako levý podstrom pøipojím strom, který vznikne stejnou oparací na mno¾inì
77 $\X_ 0$, prièem¾ $c$ vybíráme jen pøes prvky $\X_0$. Pravý podstrom vznikne
78 stejnì z mno¾iny $\X_1$. Pokud je ji¾ mno¾ina pouze jednoprvková, dále
79 nepokraèujeme v dìlení a zbývající prvek vlo¾íme jako list. Hodnoty (data) jsou
80 tak ulo¾eny v listech a ve vnitøích uzlech jsou znaèky.
84 \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
89 \: Tvar stromu (oznaème ho $T$) je jednozaène urèen vektrorem
90 $\vec c=(c_1,\ldots,c_r)$.
91 \: Prvky jsou v trii umístìny vzestupnì zleva doprava.
94 To je sice v¹echno moc pìkné, ale pro aplikaci v Q-Heapech budeme muset umìt
95 poèítat $\rank_\X(x)$ v konstatním èase. Jak tedy na to?
97 \s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì:
100 \: èíslem $i$: x vede v $T$ do $x_i$
101 \: vztahem mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím $<,>,=$
102 \: $\msb(x \oplus x_i)$
105 \s{Zdùvodnìní.} Pokud $x=x_i$, tak zjevnì $\rank_\X(x) = i$. Nech» tedy $x\neq
106 x_i$. Hodnoty znaèek klesají ve smìru od koøene k
107 listùm a na cestì od koøene k $x_i$ se v¹echny bity v $x_i$ na pozicích urèených
108 znaèkami shodují s bity v $x$ -- tak jsme k danému $x$ ve (ii) vybrali $x_i$.
109 Vezmeme do ruky $x$ a vydáme se na cestu od koøene do místa, kde bychom
110 oèekávali $x$, kdyby v trii bylo. Jeliko¾ $\msb(x \oplus x_i)$ urèitì není
111 znaèka na cestì z koøene do $x_i$ (v tom pøípadì by cesta podle znaèek nevedla
112 do $x_i$ -- $x$ se na této pozici od $x_i$, vydali bychom se tedy do opaèné
113 (shodující) vìtve), tak na této cestì je $\msb(x \oplus x_i)$ ostøe mezi
114 nìjakými znaèkami, co¾ mi urèí hranu -- breakpoint, pod kterou u¾ jsou v¹echny
115 hodnoty v listech buï men¹í (pokud $x>x_i$), nebo vìt¹í (pokud $x<x_i$), proto¾e
116 na bitech vy¹¹ích, ne¾ je znaèka následující po breakpointu, mají v¹echny prvky
117 v podstromì stejnou èíslici.
119 \s{Pøíklad:} Vezmìme mno¾inu $\X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
120 a poèítejme $\rank_\X(011001)$. Bod zlomu -- breakpoint -- je oznaèen puntíkem.
121 A $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$ a tudí¾ $\rank_\X(011001)=4$.
125 \: $\B = \{c_1,\ldots,c_k\}$
126 \: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
129 \s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z:
131 \: $\B,\varphi$ -- tyto objekty urèují strom $T$
132 \: $\equiv$ (ii), tj. èísla $i$: x vede v $T$ do $x_i$
133 \: $\equiv$ (iii), tj. vztahu mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím
135 \: $\rank_\B(\msb(x \oplus x_i))$
137 a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase.
142 \: Nic se nepoèítá, tak je strom ulo¾en.
146 \>A teï konkrétnì, jak bude Q-Heap realizována:
150 \: $\check x_1,\ldots,\check x_2$, hodnoty v libovolném poøadí
151 \: $\rho:$ permutace na $\{1,\ldots,k\}$ urèující $x_i = \check x_{\rho(i)}$ pro
152 $1 \le i \le r$, platí $x_1 < \ldots < x_r$
154 \: $B$, mno¾ina ``zajímavých'' bitových pozic, reprezentovaná jako vektor
155 \: $R$, vektor popisující funkci $\varphi: \{1,\ldots,k\} \to \{1,\ldots,k\}$, t.¾.
156 $B[\varphi(i)] = c_i$
159 \> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.
166 \: zaøadíme $x$ do $x_1,\ldots,x_r, r++$
167 \: spoèítáme $c_i',c_{i+1}'$
174 \: $i = \rank_\X(x)$, pøedpokládáme $x=x_i$, tedy ¾e prvek v haldì je
175 \: sma¾eme $x_i$ (uvolnìní $\check x_{\rho(i)}$, se¹oupnutí $\rho$); $r--$
176 \: rozhodneme, jestli zmizí $c_i$, nebo $c_{i+1}$
177 \: update $B$ (dle výsledku pøedchozího kroku), update $R$ (se¹oupnutí)
182 \h{Union-Find problem}
183 Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí,
184 inkrementální souvislost grafu). K èemu je to dobré?
185 Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
186 \h{Udr¾ování tøíd ekvivalence }
187 Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt
188 dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)).
189 \h{Inkrementální idr¾ování komponent souvislosti grafu}
190 Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E).
191 Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
192 se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran,
193 øe©ení problému je výraznì te¾¹í.
195 \h{Bì¾ná implementace }
196 Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù.
197 Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat
198 v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.)
199 \h {Chytøej¹í implementace }
200 Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
201 provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
202 Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého).
203 Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find,
204 v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.
206 Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
207 První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
208 Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1<r2$ pak strom s r1 povìsíme dolu.
209 Pokud $r1=r2$ pak ve slouèeném stromù zvý¹íme v koøeni rank o 1. Informace o ranku nám zabere ménì pamìti ne¾ o velikosti stromu.
211 Dal¹i mo¾nost pro zkrácení vý¹ky stromu je path compression. Pøi operaci find si pamatujeme pro¹lé vrcholy a pøesmìrujeme
212 jejich ukazatele na otce na koøen.
214 \s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì
215 slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)
217 \h {Microtree/Macrotree decomposition}
219 \s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?
221 Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$ zvládnout amortizovanì v èase $\O(1)$ na U,F.
224 \s {Definice: } Nech» G je je graf kde $\forall v \in V(G): deg(v)<=3$ a $c \in N$ pak c-clusterizací grafu G je rozklad
225 G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
227 \: $\forall v \in V \exists !\ i: v \in C_i$
228 \: $\forall i\ C_i\leq C$
229 \: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
230 \: ¾ádné dva sousední clustery nelze spojit
233 Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
234 V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou.
235 Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.
238 \s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je $\O(n/C)$ clusterù.
240 \s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.
242 \s{Dùkaz: } za pomoci DFS ...
243 \h{Jednodu¹¹í clusterizace}
244 Pøedpokládejme, ¾e máme zakoøeòené stromy
245 \s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
246 Celá clusterizace se nám rozpadne na následujíci pøipady:
248 \:N-strom: (má stupeò 1)
249 \:M-strom: (má stupeò 2)
250 \:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
252 poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$
254 \s{Co si potøebujeme pamatovat}
256 \: $\log(n)$ na clusterizaci
257 \: makrostrom G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$
258 \:mikrostromy, bitovì popsány
262 V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
263 vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme
264 hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.
268 nech» $i,j: x \in C_i, y \in C_j$
269 \:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
270 \:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$)
271 find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
276 \: pokud $x,y$ je makro-hrana, sma¾eme ji
277 \: pokud $x,y \in C_i$ pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy),
278 pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
282 \: strom zakoøením a oèísluji mu hrany $0..h < \log(n)$
283 \: pamatujeme si: \itemize\ibull
284 \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
285 \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
288 \: $P_x \oplus P_y$ je cesta z x do y