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 místo toho použít přimo vektor
 133 $(c_1,\ldots,c_r-1)$, který má $k\log w$ bitů. To se sice už vejde do vektoru,
 134 ale pro indexování tabulek je to stále příliš (všimněte si, že $\log w$ smí být
 135 vůči~$k$ libovolně vysoký -- pro~$w$ známe pouze dolní mez). Proto reprezentaci
 136 ještě rozdělíme na dvě části:
 137
 138 \itemize\ibull
 139 \:$B := \{c_1,\ldots,c_r\}$ (množina všech pozic bitů, které trie testuje, uložená ve~vektoru setříděně),
 140 \:$C: \{1,\ldots,r\} \to B$ taková, že $B[C(i)]=c_i$.
 141 \endlist
 142
 143 \s{Lemma R':} $\rank_X(x)$ lze spočítat v~konstantním čase~z:
 144 \numlist\pnromanap
 145 \:funkce $C$,
 146 \:hodnot $x_1,\ldots,x_r$,
 147 \:$x[B]$ -- hodnot bitů na~\uv{zajímavých} pozicích v~čísle~$x$.
 148 \endlist
 149
 150 \proof Z~předchozího lemmatu:
 151 \numlist\pnromanp
 152 \:Tvar stromu závisí jen na~nerovnostech mezi polohami značek,
 153   takže je jednoznačně určený funkcí~$C$.
 154 \:Z~tvaru stromu a $x[B]$ jednoznačně plyne list $x_i$ a tyto vstupy
 155   jsou dostatečně krátké na~to, abychom mohli předpočítat tabulku
 156   pro průchod stromem.
 157 \:Relaci zjistíme prostým porovnáním, jakmile známe~$x_i$.
 158 \:MSB umíme na~RAMu počítat v~konstantním čase.
 159 \endlist
 160 Mezivýsledky (i)--(iv) jsou opět dost krátké na~to, abychom jimi mohli
 161 indexovat tabulku.
 162 \qed
 163
 164 \>Počítání ranků je téměř vše, co potřebujeme k~implementaci operací
 165 \<Find>, \<Insert> a \<Delete>. Jedinou další překážku tvoří zatřiďování
 166 do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se vešel
 167 do~$\O(1)$ slov. Proto si budeme pamatovat zvlášť hodnoty v~libovolném
 168 pořadí a zvlášť permutaci, která je setřídí -- ta se již do~vektoru vejde.
 169 Řekněme tedy pořádně, co~vše si bude struktura pamatovat:
 170
 171 \s{Stav struktury:}
 172 \itemize\ibull
 173 \:$k$, $r$ -- kapacita haldy a aktuální počet prvků (čísla),
 174 \:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvků v libovolném pořadí (pole čísel),
 175 \:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, že $x_i=X[\varrho(i)]$
 176   a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log k$ bitech),
 177 \:$B$ -- množina \uv{zajímavých} bitových pozic (setříděný vektor o~$r\cdot\log w$ bitech),
 178 \:$C$ -- funkce popisující značky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log k$ bitech),
 179 \:předpočítané tabulky pro různé funkce.
 180 \endlist
 181
 182 \>Nyní již ukážeme, jak provádět jednotlivé operace:
 183
 184 \>$\<Find>(x):$
 185
 186 \algo
 187 \:$i \leftarrow \rank_X(x)$.
 188 \:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
 189 \endalgo
 190
 191 \>$\<Insert>(x):$
 192
 193 \algo
 194 \:$i \leftarrow \rank_X(x)$.
 195 \:Pokud $x=x_i$, hodnota už je přítomna.
 196 \:Uložíme $x$ do~$X[\mathop{{+}{+}}r]$ a vložíme $r$ 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 \::Upravíme ostatní prvky~$C$, ukazující na hodnoty v~$B$, které se vložením posunuly.
 201 \::Pokud se na~starou hodnotu neodkazuje žádné jiné $C(\cdot)$, smažeme ji z~$B$.
 202 \endalgo
 203
 204 \>$\<Delete>(x):$
 205
 206 \algo
 207 \:$i \leftarrow \rank_X(x)$ (víme, že $x_i=x$).
 208 \:Smažeme $x_i$ z~pole~$X$ (například prohozením s~posledním prvkem) a příslušně upravíme~$\varrho$.
 209 \:Přepočítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako při Insertu.
 210 \endalgo
 211
 212 \s{Časová složitost:} Všechny kroky operací po~výpočtu ranku trvají konstantní čas, rank
 213 samotný zvládneme spočítat v~$\O(1)$ pomocí tabulek, pokud známe $x[B]$. Zde je ovšem
 214 nalíčen háček -- tuto operaci nelze na~Word-RAMu konstantním počtem instrukcí spočítat.
 215 Pomoci si můžeme dvěma způsoby:
 216
 217 \numlist\nalpha
 218 \:Využijeme toho, že operace $x[B]$ je v~${\rm AC}^0$, a vystačíme si se strukturou pro ${\rm AC}^0$-RAM.
 219 Zde dokonce můžeme vytvářet haldy velikosti až $w\log w$. Také při praktické implementaci můžeme využít
 220 toho, že současné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz např. pěkný
 221 rozbor v \cite{thorup:ac0}.
 222 \:Jelikož $B$ se při jedné Q-Heapové operaci mění pouze o~konstantní počet prvků, můžeme
 223 si udržovat pomocné struktury, které budeme umět při lokální změně~$B$ v~lineárním čase
 224 přepočítat a pak pomocí nich indexovat. To pomocí Word-RAMu lze zařídit, ale je to technicky
 225 dosti náročné, takže čtenáře zvědavého na~detaily odkazujeme na~článek \cite{fw90trans}.
 226 \endlist
 227
 228 \h{Aplikace Q-Heapů}
 229
 230 Jedním velice pěkným důsledkem existence Q-Heapů je lineární algoritmus na~nalezení
 231 minimální kostry grafu ohodnoceného celými čísly. Získáme ho z~Fredmanovy a Tarjanovy
 232 varianty Jarníkova algoritmu (viz kapitoly o~kostrách) tak, že v~první iteraci použijeme
 233 jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak budeme pokračovat s~původní Fibonacciho
 234 haldou. Tak provedeme tolik průchodů, kolikrát je potřeba zlogaritmovat $n$,
 235 aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. Všimněte si, že by nám
 236 dokonce stačila halda velikosti $\Omega(\log^{(k)} n)$ s~operacemi v~konstantním čase
 237 pro nějaké libovolné~$k$.
 238
 239 \references
 240 \bye