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}{zapsal Cyril Strejc}
17 Na minulém semináøi jsme si mimo jiné ukázali výpoèetní model RAM a nahlédli
18 jsme, ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat
19 vektorový poèítaè. A kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké
20 datové struktury bychom s ním mohli vytváøet. Vektor ukládáme v $\O(w)$ slovech.
22 pøedpokládat, ¾e hodnoty, které do stuktur ukládáme, jsou rùzné. Svým sna¾ením
23 smìrujeme ke strukturám, které zvládnou operace {\it Insert} a {\it Delete} v
24 kostantním èase s rozumnou konstantou.
28 \: $w$, ¹íøka slova daného stroje (RAMu)
29 \: $n$, velikost vstupu
31 Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$.
33 \h{Word-Encoded B-Tree}
34 V podstatì pùjde o obyèejný B-strom s daty v listech. Faktor stromu oznaème $B$.
35 Ukládáme $k$-bitové hodnoty a chceme aby $Bk=\O(w)$ -- tehdy se nám uzel stromu
36 vejde do vektoru a my budeme dostateènì rychle umìt operace s uzly, které do
37 B-stromu potøebujeme, t.j. dìlení, spojování, vyhledávání. Té¾ ukládáme pointry
38 na syny. Je tøeba si trochu rozmyslet, ¾e v ka¾dém uzlu se pointry na syny také
39 povede ``scucnout'' do vektoru. Jen¾e poèet prvkù ($\vert T\vert$), které se do
40 stromu vejdou je øádovì $B^h$, kde $h$ je hloubka stromu, a tudí¾ $\log\vert
41 T\vert = \O(h)$. Proto se pointry do vektoru pìknì vejdou.
45 Q-Heap je teoreticky zajímavá datová struktura, v praxi neimplementovatelná.
46 Narozdíl od Word-Encoded B-Tree není takové omezení na velikost ukládaného èísla
47 -- maximální velikost èísla odpovídá velikost slova.
52 \: $r\le k$, poèet prvkù v Q-haldì
53 \: $x_1 < \ldots < x_r$, prvky (o $w$ bitech) v Q-haldì
54 \: $\X = (x_1,\ldots,x_r)$
55 \: $c_i = \msb(x_i \oplus x_{i+1})$, nejvy¹¹í bit, na kterém se li¹í $x_i$ a
57 \: $\rank_\X(x)$, poèet prvkù mno¾iny $\X$, které jsou men¹í ne¾ $x$.
58 Samotné $x$ ov¹em nemusí být prvek mno¾iny $\X$.
61 Haldové operace budeme umìt v $\O(1)$, nicménì bude nutný preprocesing v èase
62 $\O(2^{k^4})$, co¾ ov¹em není tak hrozné, jak na prní pohled vypadá, jeliko¾
63 $k = \O(\root 4 \of {\log n})$, èili nakonec ho stihneme v lineárním èase.
65 A jak to tedy vypadá? Prvky $x_1,\ldots,x_r$ budeme ukládat do tzv. trie.
66 {\it Trie} je binární strom s prvky (daty) v listech, v na¹em pøípadì s
67 hodnotami $x_1,\ldots,x_r$. Popí¹u konstrukci trie. Oznaèím $c = \max(c_i)$.
68 Mno¾inu $\X$ rozdìlíme na dvì mno¾iny, podle hodnot prvkù na $c$-tém bitu v
69 binárním zápisu: $$ \X_0 = \{ x_i \vert x_i \in \X\and x_i[c]=0 \}$$
70 $$ \X_1 = \{x_i \vert x_i \in \X\and x_i[c]=1\}$$
72 Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$
74 Èíslo $c$ -- øíkejme mu znaèka -- vlo¾íme do koøene právì budovaného (pod)stromu
75 a jako levý podstrom pøipojím strom, který vznikne stejnou oparací na mno¾inì
76 $\X_ 0$, prièem¾ $c$ vybíráme jen pøes prvky $\X_0$. Pravý podstrom vznikne
77 stejnì z mno¾iny $\X_1$. Pokud je ji¾ mno¾ina pouze jednoprvková, dále
78 nepokraèujeme v dìlení a zbývající prvek vlo¾íme jako list. Hodnoty (data) jsou
79 tak ulo¾eny v listech a ve vnitøích uzlech jsou znaèky.
83 \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
88 \: Tvar stromu (oznaème ho $T$) je jednozaène urèen vektrorem
89 $\vec c=(c_1,\ldots,c_r)$.
90 \: Prvky jsou v trii umístìny vzestupnì zleva doprava.
93 To je sice v¹echno moc pìkné, ale pro aplikaci v Q-Heapech budeme muset umìt
94 poèítat $\rank_\X(x)$ v konstatním èase. Jak tedy na to?
96 \s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì:
99 \: èíslem $i$: x vede v $T$ do $x_i$
100 \: vztahem mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím $<,>,=$
101 \: $\msb(x \oplus x_i)$
104 \s{Zdùvodnìní.} Pokud $x=x_i$, tak zjevnì $\rank_\X(x) = i$. Nech» tedy $x\neq
105 x_i$. Hodnoty znaèek klesají ve smìru od koøene k
106 listùm a na cestì od koøene k $x_i$ se v¹echny bity v $x_i$ na pozicích urèených
107 znaèkami shodují s bity v $x$ -- tak jsme k danému $x$ ve (ii) vybrali $x_i$.
108 Vezmeme do ruky $x$ a vydáme se na cestu od koøene do místa, kde bychom
109 oèekávali $x$, kdyby v trii bylo. Jeliko¾ $\msb(x \oplus x_i)$ urèitì není
110 znaèka na cestì z koøene do $x_i$ (v tom pøípadì by cesta podle znaèek nevedla
111 do $x_i$ -- $x$ se na této pozici od $x_i$, vydali bychom se tedy do opaèné
112 (shodující) vìtve), tak na této cestì je $\msb(x \oplus x_i)$ ostøe mezi
113 nìjakými znaèkami, co¾ mi urèí hranu -- breakpoint, pod kterou u¾ jsou v¹echny
114 hodnoty v listech buï men¹í (pokud $x>x_i$), nebo vìt¹í (pokud $x<x_i$), proto¾e
115 na bitech vy¹¹ích, ne¾ je znaèka následující po breakpointu, mají v¹echny prvky
116 v podstromì stejnou èíslici.
118 \s{Pøíklad:} Vezmìme mno¾inu $\X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
119 a poèítejme $\rank_\X(011001)$. Bod zlomu -- breakpoint -- je oznaèen puntíkem.
120 A $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$ a tudí¾ $\rank_\X(011001)=4$.
124 \: $\B = \{c_1,\ldots,c_k\}$
125 \: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
128 \s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z:
130 \: $\B,\varphi$ -- tyto objekty urèují strom $T$
131 \: $\equiv$ (ii), tj. èísla $i$: x vede v $T$ do $x_i$
132 \: $\equiv$ (iii), tj. vztahu mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím
134 \: $\rank_\B(\msb(x \oplus x_i))$
136 a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase.
141 \: Nic se nepoèítá, tak je strom ulo¾en.
145 \>A teï konkrétnì, jak bude Q-Heap realizována:
149 \: $\check x_1,\ldots,\check x_2$, hodnoty v libovolném poøadí
150 \: $\rho:$ permutace na $\{1,\ldots,k\}$ urèující $x_i = \check x_{\rho(i)}$ pro
151 $1 \le i \le r$, platí $x_1 < \ldots < x_r$
153 \: $B$, mno¾ina ``zajímavých'' bitových pozic, reprezentovaná jako vektor
154 \: $R$, vektor popisující funkci $\varphi: \{1,\ldots,k\} \to \{1,\ldots,k\}$, t.¾.
155 $B[\varphi(i)] = c_i$
158 \> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.
165 \: zaøadíme $x$ do $x_1,\ldots,x_r, r++$
166 \: spoèítáme $c_i',c_{i+1}'$
173 \: $i = \rank_\X(x)$, pøedpokládáme $x=x_i$, tedy ¾e prvek v haldì je
174 \: sma¾eme $x_i$ (uvolnìní $\check x_{\rho(i)}$, se¹oupnutí $\rho$); $r--$
175 \: rozhodneme, jestli zmizí $c_i$, nebo $c_{i+1}$
176 \: update $B$ (dle výsledku pøedchozího kroku), update $R$ (se¹oupnutí)