8-qheap/8-qheap.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}{zapsal Cyril Strejc}
  16
  17 V~minulé pøedná¹ce jsme mimo jiné ukázali výpoèetní model RAM a nahlédli jsme,
  18 ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat vektorový poèítaè.
  19 Kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké datové struktury s~ním mù¾eme
  20 vytváøet.
  21
  22 \s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu, $n$~velikost vstupu algoritmu,
  23 v~nìm¾ datovou strukturu vyu¾íváme (tedy speciálnì víme, ¾e $w\ge\log n$).
  24
  25 Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur ukládáme,
  26 jsou navzájem rùzné.
  27
  28 Svým sna¾ením smìrujeme ke strukturám, které zvládnou operace \<Insert> a \<Delete>
  29 v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost
  30 struktury nebo obojí.
  31
  32 \h{Word-Encoded B-Tree}
  33
  34 Pùjde o~obyèejný B-strom s daty v~listech, ov¹em kódovaný vektorovì. Do~listù
  35 stromu budeme ukládat $k$-bitové hodnoty, vnitøní vrcholy budou obsahovat pouze
  36 pomocné klíèe a budou mít nejvý¹e $B$ synù, strom bude mít hloubku~$h$. Hodnoty
  37 v¹ech klíèù ve~vrcholu si budeme ukládat jako vektor, ukazatele na~jednotlivé
  38 syny jakbysmet.
  39
  40 Se~stromem zacházíme jako s~klasickým B-stromem, ov¹em operace s~vrcholy
  41 provádíme vektorovì: vyhledání pozice prvku ve~vektoru pomocí operace \<Rank>,
  42 rozdìlení a sluèování vrcholù pomocí bitových posuvù a maskování, to v¹e
  43 v~èase $\O(1)$. Stromové operace tedy stihneme v~èase $\O(h)$.
  44
  45 Zbývá si rozmyslet, co~musí splòovat parametry struktury, aby se v¹echny
  46 vektory ve¹ly do~konstantního poètu slov. Kvùli vektorùm klíèù musí platit
  47 $Bk=\O(w)$. Jeliko¾ strom má a¾~$B^h$ listù a nejvý¹e tolik vnitøních vrcholù,
  48 ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme
  49 $Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾
  50 získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech pracujicí
  51 v~konstantním èase.
  52
  53 \h{Q-Heap}
  54
  55 Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití
  56 znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í
  57 strukturu, která doká¾e toté¾, ale lze do~ní ukládat a¾ $w$-bitová èísla.
  58 Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná
  59 a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných
  60 i v~praxi.
  61
  62 \s{Znaèení:}
  63 \itemize\ibull
  64 \: $k = \O(w^{1/4})$ -- omezení na~velikost haldy.
  65 \: $r\le k$ -- aktuální poèet prvkù v~haldì.
  66 \: $X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$.
  67 \: $c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, na kterém se li¹í $x_i$ a
  68 $x_{i+1}$.
  69 \: $\rank_X(x)$, poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$
  70 (definujeme i~pro $x\not\in X$).
  71 \endlist
  72
  73 \s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet.
  74 To mù¾e znít hroznì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e
  75 pøedvýpoèet stihneme v~èase $\O(n)$. V~tomto èase mimo jiné stihneme
  76 pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$
  77 bitù a pro ka¾dý vstup ji dovedeme vyhodnotit v~polynomiálním èase.
  78 Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce
  79 umíme spoèítat v~konstantním èase.
  80
  81 \s{Iterování:} V¹imnìte si, ¾e jakmile doká¾eme sestrojit haldu s~$k$ prvky
  82 pracující v~konstantním èase, mù¾eme s~konstantním zpomalením sestrojit
  83 i haldu s~$k^{\O(1)}$ prvky. Staèí si hodnoty ulo¾it do~listù stromu
  84 s~vìtvením $k$ a konstantním poètem hladin a v~ka¾dém vnitøním vrcholu
  85 si pamatovat minimum podstromu a Q-Heap s~hodnotami jeho synù. Tak doká¾eme
  86 ka¾dé vlo¾ení i odebrání prvku pøevést na~konstantnì mnoho operací s~Q-Heapy.
  87
  88 \s{Náèrt} fungování Q-Heapu:
  89 Nad~prvky $x_1,\ldots,x_r$ sestrojíme komprimovanou trii~$T$ (nevìtvicí se cesty
  90 nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol,
  91 který le¾í mezi $x_i$ a $x_{i+1}$, bude testovat $c_i$-tý bit èísla.
  92 Pokud budeme hledat nìkteré z~$x_i$, tyto vnitøní vrcholy (budeme jim
  93 øíkat {\I znaèky}) nás správnì dovedou do~pøíslu¹ného listu. Pokud ale
  94 budeme hledat nìjaké jiné~$x$, zavedou nás do~nìjakého na~první pohled
  95 nesouvisejícího listu a teprve tam zjistíme, ¾e jsme zabloudili. K~na¹emu
  96 pøekvapení ale to, kam jsme se dostali, bude staèit ke~spoèítáním ranku
  97 prvku, a~tím pádem i k~jeho vlo¾ení do~struktury.
  98
  99 \s{Pøíklad:}
 100 \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
 101 souèástí trie.}
 102
 103 \s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì:
 104 \numlist\pnromanp
 105 \:tvarem stromu $T$
 106 \:indexem $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu,
 107 \:vztahem mezi $x$ a $x_i$ ($x<x_i$, $x>x_i$ nebo $x=x_i$)
 108 \:$\msb(x \oplus x_i)$
 109 \endlist
 110
 111 \s{Dùkaz:} Pokud $x=x_i$, je zjevnì $\rank_\X(x) = i$. Pøedpokládejme tedy $x\ne x_i$.
 112 Hodnoty znaèek klesají ve~smìru od koøene k~listùm a na cestì od koøene k~$x_i$ se
 113 v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$, pøièem¾
 114 a¾ do~pozice $c_i$ se shodují i bity znaèkami netestované. Sledujme tuto cestu
 115 od~koøene a¾ po~$c_i$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty
 116 v~levém podstromu men¹í ne¾~$x$, a~tedy se do~ranku zapoèítají. Pokud odboèuje
 117 doleva, jsou hodnoty v~pravém podstromu zaruèenì vìt¹í a nezapoèítají se.
 118 Pokud nastala neshoda a $x<x_i$ (tedy $c_i$-tý bit v~$x$ je nula, zatímco v~$x_i$
 119 je jednièkový), jsou v¹echny hodnoty pod touto hranou vìt¹í; pøi opaèné nerovnosti
 120 jsou men¹í.
 121 \qed
 122
 123 \s{Pøíklad:} Vezmìme mno¾inu $\X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
 124 a poèítejme $\rank_\X(011001)$. Místo první neshody je oznaèeno puntíkem.
 125 Platí $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$, proèe¾ $\rank_\X(011001)=4$.
 126
 127 Rádi bychom pøedchozí lemma vyu¾ili k~sestrojení tabulek, které podle uvedených
 128 hodnot vrátí rank prvku~$x$. K~tomu potøebujeme pøedev¹ím umìt indexovat tvarem
 129 stromu.
 130
 131 \s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_n$
 132 (je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích
 133 stromù), hodnoty v~listech jsou $x_1,\ldots,x_n$ v~poøadí zleva doprava.
 134
 135 Vektor $(c_1,\ldots,c_n)$ má pouze $k\log w=\O(k^2)$ bitù, tak¾e jím mù¾eme
 136 indexovat. Pro zjednodu¹ení ostatních operací zvolíme trochu jinou, ale
 137 ekvivalentní reprezentaci:
 138
 139 \s{Znaèení:}
 140 \itemize\ibull
 141 \:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì)
 142 \:$C: \{1,\ldots,r\} \to B: B[C(i)]:=c_i$.
 143 \endlist
 144
 145 \s{Lemma 1':} $\rank_X(x)$ lze spoèítat v~konstatním èase~z:
 146 \numlist\pnromanap
 147 \:funkce $C$
 148 \:$x_1,\ldots,x_r$
 149 \:$x[B]$ -- hodnoty bitù na~\uv{zajímavých} pozicích v~èísle~$x$,
 150 \endlist
 151
 152 \s{Dùkaz:} Z~pøedchozího lemmatu:
 153 \numlist\pnromanp
 154 \:Tvar stromu závisí jen na~vzájemných vztazích mezi polohami znaèek,
 155   tak¾e je jednoznaènì urèený funkcí~$C$.
 156 \:Z~tvaru stromu a $x[B]$ jednoznaènì plyne list $x_i$ a tyto vstupy
 157   jsou dostatenènì krátké na~to, abychom mohli pøedpoèítat tabulku.
 158 \:Zjistíme prostým porovnáním.
 159 \:$x_i$ známe a MSB umíme na~RAMu poèítat v~konstantním èase.
 160 \endlist
 161 Pøitom (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli
 162 indexovat tabulku.
 163 \qed
 164
 165 \>Poèítání rankù je témìø v¹e, co potøebujeme k~implementaci operací
 166 \<Find>, \<Insert> a \<Delete>. Jediná dal¹í pøeká¾ka u¾ je zatøiïování
 167 do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se ve¹el
 168 do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» tyto hodnoty v~libovolném
 169 poøadí a zvlá¹» permutaci, která je setøídí -- ta se ji¾ do~vektoru vejde.
 170 Øeknìme tedy poøádnì, co~v¹e si bude struktura pamatovat:
 171
 172 \s{Stav struktury:}
 173 \itemize\ibull
 174 \:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla)
 175 \:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel)
 176 \:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$
 177   a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log r$ bitech)
 178 \:$B$ -- mno¾ina \uv{zajímavých} bitových pozic (setøidìný vektor o~$r\cdot\log w$ bitech)
 179 \:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot r$ bitech)
 180 \endlist
 181
 182 \>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace:
 183
 184 \s{Find(x)}
 185
 186 \algo
 187 \:$i := \rank_X(x)$
 188 \:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
 189 \endalgo
 190
 191 \s{Insert(x)}
 192
 193 \algo
 194 \:$i := \rank_\X(x)$
 195 \:Pokud $x=x_i$, hodnota u¾ je pøítomna.
 196 \:Ulo¾íme $x$ do~pole~$X$ a vlo¾íme jeho pozici na~$i$-té místo v~permutaci~$\varrho$.
 197 \:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$:
 198 \::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam.
 199 \::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu.
 200 \::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(k)$, sma¾eme ji z~$B$.
 201 \endalgo
 202
 203 \s{Delete(x)}
 204
 205 \algo
 206 \:$i := \rank_\X(x)$ (víme, ¾e $x_i=x$).
 207 \:Sma¾eme $x_i$ z~pole~$X$ (napøíklad prohozením s~posledním prvkem) a pøíslu¹nì upravíme~$\varrho$.
 208 \:Pøepoèítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako pøi Insertu.
 209 \endalgo
 210
 211 \todo{Popsat, jak se poèítá $x[B]$.}
 212
 213 \todo{Aplikace na~kostry.}
 214
 215 \bye