8-qheap/8-qheap.tex

   1 \def\msb{{\rm MSB}}
   2 \def\rank{{\rm Rank}}
   3
   4 \def\pnromanp{(\nroman)}
   5 \def\pnromanap{(\nroman ')}
   6
   7 \input ../sgr.tex
   8
   9 \prednaska{8}{Q-Heaps}{}
  10
  11 V~minulé kapitole jsme zavedli výpoèetní model RAM a nahlédli jsme,
  12 ¾e na~nìm mù¾eme snadno simulovat vektorový poèítaè s~vektorovými operacemi pracujícími v~konstantním èase.
  13 Kdy¾ u¾ máme takový poèítaè, pojïme si ukázat, jaké datové struktury na~nìm mù¾eme
  14 vytváøet.
  15
  16 Svým sna¾ením budeme smìøovat ke~strukturám, které zvládnou operace \<Insert> a \<Delete>
  17 v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost
  18 struktury nebo obojí. Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur
  19 ukládáme, jsou navzájem rùzné.
  20
  21 \s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu a $n$~velikost vstupu algoritmu,
  22 v~nìm¾ datovou strukturu vyu¾íváme (speciálnì tedy víme, ¾e $w\ge\log n$).
  23
  24 \h{Word-Encoded B-Tree}
  25
  26 První strukturou, kterou popí¹eme, bude vektorová varianta B-stromu. Nemá je¹tì
  27 tak zajímavé parametry, ale odvozuje se snadno a jsou na~ní dobøe vidìt mnohé
  28 my¹lenky pou¾ívané ve~strukturách slo¾itìj¹ích.
  29
  30 Pùjde o~obyèejný B-strom s daty v~listech, ov¹em kódovaný vektorovì. Do~listù
  31 stromu budeme ukládat $k$-bitové hodnoty, vnitøní vrcholy budou obsahovat pouze
  32 pomocné klíèe a budou mít nejvý¹e $B$ synù. Strom bude mít hloubku~$h$. Hodnoty
  33 v¹ech klíèù ve~vrcholu si budeme ukládat jako vektor, ukazatele na~jednotlivé
  34 syny jakbysmet.
  35
  36 Se~stromem zacházíme jako s~klasickým B-stromem, pøitom operace s~vrcholy
  37 provádíme vektorovì: vyhledání pozice prvku ve~vektoru pomocí operace \<Rank>,
  38 rozdìlení a sluèování vrcholù pomocí bitových posuvù a maskování, to v¹e
  39 v~èase $\O(1)$. Stromové operace (\<Find>, \<FindNext>, \<Insert>, \<Delete>, \dots)
  40 tedy stihneme v~èase $\O(h)$.
  41
  42 Zbývá si rozmyslet, co~musí splòovat parametry struktury, aby se v¹echny
  43 vektory ve¹ly do~konstantního poètu slov. Kvùli vektorùm klíèù musí platit
  44 $Bk=\O(w)$. Jeliko¾ strom má a¾~$B^h$ listù a nejvý¹e tolik vnitøních vrcholù,
  45 ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme,
  46 aby bylo $Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾
  47 získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech, která
  48 pracuje v~konstantním èase.
  49
  50 \h{Q-Heap}
  51
  52 Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití
  53 znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í
  54 konstrukci od~Fredmana a Willarda \cite{fw90trans}, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly.
  55 Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná
  56 a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných
  57 i prakticky.
  58
  59 \s{Znaèení:}
  60 \itemize\ibull
  61 \:$k = \O(w^{1/4})$ -- omezení na~velikost haldy,
  62 \:$r\le k$ -- aktuální poèet prvkù v~haldì,
  63 \:$X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$,
  64 \:$c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, ve~kterém se li¹í $x_i$ a
  65 $x_{i+1}$,
  66 \:$\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$
  67 (pøièem¾ $x$ mù¾e le¾et i mimo~$X$).
  68 \endlist
  69
  70 \s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet.
  71 To mù¾e znít hrozivì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e
  72 pøedvýpoèet stihneme v~èase $\O(n)$. V~takovém èase mimo jiné stihneme
  73 pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$
  74 bitù a kterou pro ka¾dý vstup dovedeme vyhodnotit v~polynomiálním èase.
  75 Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce
  76 umíme spoèítat v~konstantním èase.
  77
  78 \s{Iterování:} V¹imnìte si, ¾e jakmile doká¾eme sestrojit haldu s~$k$ prvky
  79 pracující v~konstantním èase, mù¾eme s~konstantním zpomalením sestrojit
  80 i haldu s~$k^{\O(1)}$ prvky. Staèí si hodnoty ulo¾it do~listù stromu
  81 s~vìtvením $k$ a konstantním poètem hladin a v~ka¾dém vnitøním vrcholu
  82 si pamatovat minimum podstromu a Q-Heap s~hodnotami jeho synù. Tak doká¾eme
  83 ka¾dé vlo¾ení i odebrání prvku pøevést na~konstantnì mnoho operací s~Q-Heapy.
  84
  85 \s{Náèrt} fungování Q-Heapu:
  86 Nad~prvky $x_1,\ldots,x_r$ sestrojíme trii~$T$ a nevìtvící se cesty zkomprimujeme
  87 (nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol,
  88 který le¾í mezi $x_i$ a $x_{i+1}$, bude testovat $c_i$-tý bit èísla.
  89 Pokud budeme hledat nìkteré z~$x_i$, tyto vnitøní vrcholy (budeme jim
  90 øíkat {\I znaèky}\foot{tøeba turistické pro~orientaci v~lese}) nás správnì dovedou do~pøíslu¹ného listu. Pokud ale
  91 budeme hledat nìjaké jiné~$x$, zavedou nás do~nìjakého na~první pohled
  92 nesouvisejícího listu a teprve tam zjistíme, ¾e jsme zabloudili. K~na¹emu
  93 pøekvapení v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku
  94 prvku a z~rankù u¾ odvodíme i ostatní operace.
  95
  96 \s{Pøíklad:} Trie pro zadanou mno¾inu èísel. Ohodnocení hran je pouze pro názornost, není
  97 souèástí struktury.
  98 \fig{trie.eps}{\hsize}
  99
 100 \s{Lemma R:} $\rank_X(x)$ je urèen jednoznaènì kombinací:
 101 \numlist\pnromanp
 102 \:tvaru stromu $T$,
 103 \:indexu $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu,
 104 \:vztahu mezi $x$ a $x_i$ ($x<x_i$, $x>x_i$ nebo $x=x_i$) a
 105 \:pozice $b=\msb(x \oplus x_i)$.
 106 \endlist
 107
 108 \proof Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne x_i$.
 109 Hodnoty znaèek klesají ve~smìru od koøene k~listùm a na cestì od koøene k~$x_i$ se
 110 v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$. Pøitom
 111 a¾ do~pozice $b$ se shodují i bity znaèkami netestované. Sledujme tuto cestu
 112 od~koøene a¾ po~$b$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty
 113 v~levém podstromu men¹í ne¾~$x$, a~tedy se do~ranku zapoèítají. Pokud odboèuje
 114 doleva, jsou hodnoty v~pravém podstromu zaruèenì vìt¹í a nezapoèítají se.
 115 Pokud nastala neshoda a $x<x_i$ (tedy $b$-tý bit v~$x$ je nula, zatímco v~$x_i$
 116 je jednièkový), jsou v¹echny hodnoty pod touto hranou vìt¹í; pøi opaèné nerovnosti
 117 jsou men¹í.
 118 \qed
 119
 120 \s{Pøíklad:} Vezmìme mno¾inu $X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
 121 a poèítejme $\rank_X(011001)$. Místo první neshody je oznaèeno puntíkem.
 122 Platí $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$, a~tak je $\rank_X(011001)=4$.
 123
 124 Rádi bychom pøedchozí lemma vyu¾ili k~sestrojení tabulek, které podle uvedených
 125 hodnot vrátí rank prvku~$x$. K~tomu potøebujeme pøedev¹ím umìt indexovat tvarem
 126 stromu.
 127
 128 \s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_{r-1}$
 129 (je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích
 130 stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ v~poøadí zleva doprava.
 131
 132 Kdykoliv chceme indexovat tvarem stromu, mù¾eme tedy indexovat pøímo vektorem
 133 $(c_1,\ldots,c_r)$, který má pouze $k\log w=\O(k^2)$ bitù. Pro zjednodu¹ení ostatních
 134 operací ale zvolíme trochu jinou, ekvivalentní reprezentaci:
 135
 136 \itemize\ibull
 137 \:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì),
 138 \:$C: \{1,\ldots,r\} \to B: B[C(i)]=c_i$.
 139 \endlist
 140
 141 \s{Lemma R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
 142 \numlist\pnromanap
 143 \:funkce $C$,
 144 \:hodnot $x_1,\ldots,x_r$,
 145 \:$x[B]$ -- hodnot bitù na~\uv{zajímavých} pozicích v~èísle~$x$.
 146 \endlist
 147
 148 \proof Z~pøedchozího lemmatu:
 149 \numlist\pnromanp
 150 \:Tvar stromu závisí jen na~nerovnostech mezi polohami znaèek,
 151   tak¾e je jednoznaènì urèený funkcí~$C$.
 152 \:Z~tvaru stromu a $x[B]$ jednoznaènì plyne list $x_i$ a tyto vstupy
 153   jsou dostateènì krátké na~to, abychom mohli pøedpoèítat tabulku
 154   pro prùchod stromem.
 155 \:Relaci zjistíme prostým porovnáním, jakmile známe~$x_i$.
 156 \:MSB umíme na~RAMu poèítat v~konstantním èase.
 157 \endlist
 158 Mezivýsledky (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli
 159 indexovat tabulku.
 160 \qed
 161
 162 \>Poèítání rankù je témìø v¹e, co potøebujeme k~implementaci operací
 163 \<Find>, \<Insert> a \<Delete>. Jedinou dal¹í pøeká¾ku tvoøí zatøiïování
 164 do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se ve¹el
 165 do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» hodnoty v~libovolném
 166 poøadí a zvlá¹» permutaci, která je setøídí -- ta se ji¾ do~vektoru vejde.
 167 Øeknìme tedy poøádnì, co~v¹e si bude struktura pamatovat:
 168
 169 \s{Stav struktury:}
 170 \itemize\ibull
 171 \:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla),
 172 \:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel),
 173 \:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$
 174   a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log r$ bitech),
 175 \:$B$ -- mno¾ina \uv{zajímavých} bitových pozic (setøídìný vektor o~$r\cdot\log w$ bitech),
 176 \:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log r$ bitech),
 177 \:pøedpoèítané tabulky pro rùzné funkce.
 178 \endlist
 179
 180 \>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace:
 181
 182 \>$\<Find>(x):$
 183
 184 \algo
 185 \:$i \leftarrow \rank_X(x)$.
 186 \:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
 187 \endalgo
 188
 189 \>$\<Insert>(x):$
 190
 191 \algo
 192 \:$i \leftarrow \rank_X(x)$.
 193 \:Pokud $x=x_i$, hodnota u¾ je pøítomna.
 194 \:Ulo¾íme $x$ do~$X[\mathop{{+}{+}}r]$ a vlo¾íme $r$ na~$i$-té místo v~permutaci~$\varrho$.
 195 \:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$:
 196 \::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam.
 197 \::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu.
 198 \::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$.
 199 \endalgo
 200
 201 \>$\<Delete>(x):$
 202
 203 \algo
 204 \:$i \leftarrow \rank_X(x)$ (víme, ¾e $x_i=x$).
 205 \:Sma¾eme $x_i$ z~pole~$X$ (napøíklad prohozením s~posledním prvkem) a pøíslu¹nì upravíme~$\varrho$.
 206 \:Pøepoèítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako pøi Insertu.
 207 \endalgo
 208
 209 \s{Èasová slo¾itost:} V¹echny kroky operací po~výpoètu ranku trvají konstantní èas, rank
 210 samotný zvládneme spoèítat v~$\O(1)$ pomocí tabulek, pokud známe $x[B]$. Zde je ov¹em
 211 nalíèen háèek -- tuto operaci nelze na~Word-RAMu konstantním poètem instrukcí spoèítat.
 212 Pomoci si mù¾eme dvìma zpùsoby:
 213
 214 \numlist\nalpha
 215 \:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$, a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM.
 216 Zde dokonce mù¾eme vytváøet haldy velikosti a¾ $w\log w$. Také pøi praktické implementaci mù¾eme vyu¾ít
 217 toho, ¾e souèasné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz napø. pìkný
 218 rozbor v \cite{thorup:ac0}.
 219 \:Jeliko¾ $B$ se pøi jedné Q-Heapové operaci mìní pouze o~konstantní poèet prvkù, mù¾eme
 220 si udr¾ovat pomocné struktury, které budeme umìt pøi lokální zmìnì~$B$ v~lineárním èase
 221 pøepoèítat a pak pomocí nich indexovat. To pomocí Word-RAMu lze zaøídit, ale je to technicky
 222 dosti nároèné, tak¾e ètenáøe zvìdavého na~detaily odkazujeme na~èlánek \cite{fw90trans}.
 223 \endlist
 224
 225 \h{Aplikace Q-Heapù}
 226
 227 Jedním velice pìkným dùsledkem existence Q-Heapù je lineární algoritmus na~nalezení
 228 minimální kostry grafu ohodnoceného celými èísly. Získáme ho z~Fredmanovy a Tarjanovy
 229 varianty Jarníkova algoritmu (viz kapitoly o~kostrách) tak, ¾e v~první iteraci pou¾ijeme
 230 jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak budeme pokraèovat s~pùvodní Fibonacciho
 231 haldou. Tak provedeme tolik prùchodù, kolikrát je potøeba zlogaritmovat $n$,
 232 aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. V¹imnìte si, ¾e by nám
 233 dokonce staèila halda velikosti $\Omega(\log^{(k)} n)$ s~operacemi v~konstantním èase
 234 pro nìjaké libovolné~$k$.
 235
 236 \references
 237 \bye