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 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.
  21 V dal¹ím budeme BÚNO
  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.
  25
  26 \s{Znaèení:}
  27 \itemize\ibull
  28 \: $w$, ¹íøka slova daného stroje (RAMu)
  29 \: $n$, velikost vstupu
  30 \endlist
  31 Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$.
  32
  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.
  42
  43 \h{Q-Heaps}
  44
  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.
  48
  49 \s{Znaèení:}
  50 \itemize\ibull
  51 \: $k = \O(w^{1/4})$
  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
  56 $x_{i+1}$
  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$.
  59 \endlist
  60
  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.
  64
  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\}$$
  71
  72 Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$
  73
  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.
  80
  81 \s{Pøíklad:}
  82
  83 \nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
  84 souèástí trie.}
  85
  86 \>Pozorování:
  87 \itemize\ibull
  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.
  91 \endlist
  92
  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?
  95
  96 \s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì:
  97 \numlist\pnromanp
  98 \: stromem $T$
  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)$
 102 \endlist
 103
 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.
 117
 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$.
 121
 122 \s{Znaèení:}
 123 \itemize\ibull
 124 \: $\B = \{c_1,\ldots,c_k\}$
 125 \: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
 126 \endlist
 127
 128 \s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z:
 129 \numlist\pnromanap
 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
 133 $<,>,=$
 134 \: $\rank_\B(\msb(x \oplus x_i))$
 135 \endlist
 136 a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase.
 137
 138 \s{Zdùvodnìní.}
 139
 140 \numlist\pnromanap
 141 \: Nic se nepoèítá, tak je strom ulo¾en.
 142 \:
 143 \endlist
 144
 145 \>A teï konkrétnì, jak bude Q-Heap realizována:
 146
 147 \>Pamatujeme si:
 148 \itemize\ibull
 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$
 152 \: $r$, poèet prvkù
 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$
 156 \endlist
 157
 158 \> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.
 159
 160 \s{Insert(x)}
 161
 162 \algo
 163 \: $i = \rank_\X(x)$
 164 \: porovnáme $x,x_i$
 165 \: zaøadíme $x$ do $x_1,\ldots,x_r, r++$
 166 \: spoèítáme $c_i',c_{i+1}'$
 167 \: update $B,R$
 168 \endalgo
 169
 170 \s{Delete(x)}
 171
 172 \algo
 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í)
 177 \endalgo
 178
 179 \bye