8-qheapuf/8-qheapuf.tex

   1 \def\X{{\cal X}}
   2 \def\B{{\cal B}}
   3 \def\and{\ \&\ }
   4 \def\msb{{\rm MSB}}
   5 \def\rank{{\rm Rank}}
   6
   7 \def\pnromanp{(\nroman)}
   8 \def\pnromanap{(\nroman ')}
   9
  10 % Vlozeni obrazku {obrazek}{popisek}
  11 \def\nosizefigure#1#2{\bigskip\vbox{\centerline{\epsfbox{#1}}\smallskip\centerline{#2}}\bigskip}
  12
  13 \input ../sgr.tex
  14
  15 \prednaska{8}{Q-Heaps \& Union-Find problem}{zapsali Cyril Strejc a Ale¹
  16 ©nupárek}
  17
  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.
  22 V dal¹ím budeme BÚNO
  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.
  26
  27 \s{Znaèení:}
  28 \itemize\ibull
  29 \: $w$, ¹íøka slova daného stroje (RAMu)
  30 \: $n$, velikost vstupu
  31 \endlist
  32 Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$.
  33
  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.
  43
  44 \h{Q-Heaps}
  45
  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.
  49
  50 \s{Znaèení:}
  51 \itemize\ibull
  52 \: $k = \O(w^{1/4})$
  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
  57 $x_{i+1}$
  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$.
  60 \endlist
  61
  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.
  65
  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\}$$
  72
  73 Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$
  74
  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.
  81
  82 \s{Pøíklad:}
  83
  84 \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
  85 souèástí trie.}
  86
  87 \>Pozorování:
  88 \itemize\ibull
  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.
  92 \endlist
  93
  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?
  96
  97 \s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì:
  98 \numlist\pnromanp
  99 \: stromem $T$
 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)$
 103 \endlist
 104
 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.
 118
 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$.
 122
 123 \s{Znaèení:}
 124 \itemize\ibull
 125 \: $\B = \{c_1,\ldots,c_k\}$
 126 \: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
 127 \endlist
 128
 129 \s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z:
 130 \numlist\pnromanap
 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
 134 $<,>,=$
 135 \: $\rank_\B(\msb(x \oplus x_i))$
 136 \endlist
 137 a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase.
 138
 139 \s{Zdùvodnìní.}
 140
 141 \numlist\pnromanap
 142 \: Nic se nepoèítá, tak je strom ulo¾en.
 143 \:
 144 \endlist
 145
 146 \>A teï konkrétnì, jak bude Q-Heap realizována:
 147
 148 \>Pamatujeme si:
 149 \itemize\ibull
 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$
 153 \: $r$, poèet prvkù
 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$
 157 \endlist
 158
 159 \> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.
 160
 161 \s{Insert(x)}
 162
 163 \algo
 164 \: $i = \rank_\X(x)$
 165 \: porovnáme $x,x_i$
 166 \: zaøadíme $x$ do $x_1,\ldots,x_r, r++$
 167 \: spoèítáme $c_i',c_{i+1}'$
 168 \: update $B,R$
 169 \endalgo
 170
 171 \s{Delete(x)}
 172
 173 \algo
 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í)
 178 \endalgo
 179
 180
 181
 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¾¹í.
 194
 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ù.
 205
 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.
 210
 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.
 213
 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$)
 216
 217 \h {Microtree/Macrotree decomposition}
 218
 219 \s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?
 220
 221 Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.
 222
 223 \h{Clusterizace}
 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:
 226 \itemize\ibull
 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
 231 \endlist
 232
 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.
 236
 237
 238 \s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.
 239
 240 \s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.
 241
 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:
 247 \itemize\ibull
 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
 251 \endlist
 252 poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$
 253
 254 \s{Co si potøebujeme pamatovat}
 255 \itemize\ibull
 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
 259 \endlist
 260
 261 \h{Makrostromy}
 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ì.
 265
 266 \s{find(x,y)}
 267 \algo
 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$);
 272 \endalgo
 273
 274 \s{delete(x,y)}
 275 \algo
 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á)
 279 \endalgo
 280 \h{Mikrostromy}
 281 \itemize\ibull
 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
 286   \:hranièní vrcholy
 287   \endlist
 288 \: $P_x \oplus  P_y$ je cesta z x do y
 289 \endlist
 290 \bye
 291