From 4ca5afba4e6368811f753dc03635522a3a5cc6ce Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 29 Dec 2006 21:50:49 +0100 Subject: [PATCH] New. --- 8-qheap/8-qheap.tex | 278 +++++++++++++++++++++++++------------------- 1 file changed, 157 insertions(+), 121 deletions(-) diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 2cb2601..c56b945 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -14,166 +14,202 @@ \prednaska{8}{Q-Heaps}{zapsal Cyril Strejc} -Na minulém semináøi jsme si mimo jiné ukázali výpoèetní model RAM a nahlédli -jsme, ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat -vektorový poèítaè. A kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké -datové struktury bychom s ním mohli vytváøet. Vektor ukládáme v $\O(w)$ slovech. -V dal¹ím budeme BÚNO -pøedpokládat, ¾e hodnoty, které do stuktur ukládáme, jsou rùzné. Svým sna¾ením -smìrujeme ke strukturám, které zvládnou operace {\it Insert} a {\it Delete} v -kostantním èase s rozumnou konstantou. +V~minulé pøedná¹ce jsme mimo jiné ukázali výpoèetní model RAM a nahlédli jsme, +¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat vektorový poèítaè. +Kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké datové struktury s~ním mù¾eme +vytváøet. -\s{Znaèení:} -\itemize\ibull -\: $w$, ¹íøka slova daného stroje (RAMu) -\: $n$, velikost vstupu -\endlist -Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$. +\s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu, $n$~velikost vstupu algoritmu, +v~nìm¾ datovou strukturu vyu¾íváme (tedy speciálnì víme, ¾e $w\ge\log n$). -\h{Word-Encoded B-Tree} -V podstatì pùjde o obyèejný B-strom s daty v listech. Faktor stromu oznaème $B$. -Ukládáme $k$-bitové hodnoty a chceme aby $Bk=\O(w)$ -- tehdy se nám uzel stromu -vejde do vektoru a my budeme dostateènì rychle umìt operace s uzly, které do -B-stromu potøebujeme, t.j. dìlení, spojování, vyhledávání. Té¾ ukládáme pointry -na syny. Je tøeba si trochu rozmyslet, ¾e v ka¾dém uzlu se pointry na syny také -povede ``scucnout'' do vektoru. Jen¾e poèet prvkù ($\vert T\vert$), které se do -stromu vejdou je øádovì $B^h$, kde $h$ je hloubka stromu, a tudí¾ $\log\vert -T\vert = \O(h)$. Proto se pointry do vektoru pìknì vejdou. +Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur ukládáme, +jsou navzájem rùzné. -\h{Q-Heaps} +Svým sna¾ením smìrujeme ke strukturám, které zvládnou operace \ a \ +v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost +struktury nebo obojí. -Q-Heap je teoreticky zajímavá datová struktura, v praxi neimplementovatelná. -Narozdíl od Word-Encoded B-Tree není takové omezení na velikost ukládaného èísla --- maximální velikost èísla odpovídá velikost slova. +\h{Word-Encoded B-Tree} + +Pùjde o~obyèejný B-strom s daty v~listech, ov¹em kódovaný vektorovì. Do~listù +stromu budeme ukládat $k$-bitové hodnoty, vnitøní vrcholy budou obsahovat pouze +pomocné klíèe a budou mít nejvý¹e $B$ synù, strom bude mít hloubku~$h$. Hodnoty +v¹ech klíèù ve~vrcholu si budeme ukládat jako vektor, ukazatele na~jednotlivé +syny jakbysmet. + +Se~stromem zacházíme jako s~klasickým B-stromem, ov¹em operace s~vrcholy +provádíme vektorovì: vyhledání pozice prvku ve~vektoru pomocí operace \, +rozdìlení a sluèování vrcholù pomocí bitových posuvù a maskování, to v¹e +v~èase $\O(1)$. Stromové operace tedy stihneme v~èase $\O(h)$. + +Zbývá si rozmyslet, co~musí splòovat parametry struktury, aby se v¹echny +vektory ve¹ly do~konstantního poètu slov. Kvùli vektorùm klíèù musí platit +$Bk=\O(w)$. Jeliko¾ strom má a¾~$B^h$ listù a nejvý¹e tolik vnitøních vrcholù, +ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme +$Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾ +získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech pracujicí +v~konstantním èase. + +\h{Q-Heap} + +Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití +znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í +strukturu, která doká¾e toté¾, ale lze do~ní ukládat a¾ $w$-bitová èísla. +Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná +a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných +i v~praxi. \s{Znaèení:} \itemize\ibull -\: $k = \O(w^{1/4})$ -\: $r\le k$, poèet prvkù v Q-haldì -\: $x_1 < \ldots < x_r$, prvky (o $w$ bitech) v Q-haldì -\: $\X = (x_1,\ldots,x_r)$ -\: $c_i = \msb(x_i \oplus x_{i+1})$, nejvy¹¹í bit, na kterém se li¹í $x_i$ a -$x_{i+1}$ -\: $\rank_\X(x)$, poèet prvkù mno¾iny $\X$, které jsou men¹í ne¾ $x$. -Samotné $x$ ov¹em nemusí být prvek mno¾iny $\X$. +\: $k = \O(w^{1/4})$ -- omezení na~velikost haldy. +\: $r\le k$ -- aktuální poèet prvkù v~haldì. +\: $X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$. +\: $c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, na kterém se li¹í $x_i$ a +$x_{i+1}$. +\: $\rank_X(x)$, poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$ +(definujeme i~pro $x\not\in X$). \endlist -Haldové operace budeme umìt v $\O(1)$, nicménì bude nutný preprocesing v èase -$\O(2^{k^4})$, co¾ ov¹em není tak hrozné, jak na prní pohled vypadá, jeliko¾ -$k = \O(\root 4 \of {\log n})$, èili nakonec ho stihneme v lineárním èase. - -A jak to tedy vypadá? Prvky $x_1,\ldots,x_r$ budeme ukládat do tzv. trie. -{\it Trie} je binární strom s prvky (daty) v listech, v na¹em pøípadì s -hodnotami $x_1,\ldots,x_r$. Popí¹u konstrukci trie. Oznaèím $c = \max(c_i)$. -Mno¾inu $\X$ rozdìlíme na dvì mno¾iny, podle hodnot prvkù na $c$-tém bitu v -binárním zápisu: $$ \X_0 = \{ x_i \vert x_i \in \X\and x_i[c]=0 \}$$ -$$ \X_1 = \{x_i \vert x_i \in \X\and x_i[c]=1\}$$ - -Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$ - -Èíslo $c$ -- øíkejme mu znaèka -- vlo¾íme do koøene právì budovaného (pod)stromu -a jako levý podstrom pøipojím strom, který vznikne stejnou oparací na mno¾inì -$\X_ 0$, prièem¾ $c$ vybíráme jen pøes prvky $\X_0$. Pravý podstrom vznikne -stejnì z mno¾iny $\X_1$. Pokud je ji¾ mno¾ina pouze jednoprvková, dále -nepokraèujeme v dìlení a zbývající prvek vlo¾íme jako list. Hodnoty (data) jsou -tak ulo¾eny v listech a ve vnitøích uzlech jsou znaèky. +\s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet. +To mù¾e znít hroznì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e +pøedvýpoèet stihneme v~èase $\O(n)$. V~tomto èase mimo jiné stihneme +pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$ +bitù a pro ka¾dý vstup ji dovedeme vyhodnotit v~polynomiálním èase. +Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce +umíme spoèítat v~konstantním èase. + +\s{Iterování:} V¹imnìte si, ¾e jakmile doká¾eme sestrojit haldu s~$k$ prvky +pracující v~konstantním èase, mù¾eme s~konstantním zpomalením sestrojit +i haldu s~$k^{\O(1)}$ prvky. Staèí si hodnoty ulo¾it do~listù stromu +s~vìtvením $k$ a konstantním poètem hladin a v~ka¾dém vnitøním vrcholu +si pamatovat minimum podstromu a Q-Heap s~hodnotami jeho synù. Tak doká¾eme +ka¾dé vlo¾ení i odebrání prvku pøevést na~konstantnì mnoho operací s~Q-Heapy. + +\s{Náèrt} fungování Q-Heapu: +Nad~prvky $x_1,\ldots,x_r$ sestrojíme komprimovanou trii~$T$ (nevìtvicí se cesty +nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol, +který le¾í mezi $x_i$ a $x_{i+1}$, bude testovat $c_i$-tý bit èísla. +Pokud budeme hledat nìkteré z~$x_i$, tyto vnitøní vrcholy (budeme jim +øíkat {\I znaèky}) nás správnì dovedou do~pøíslu¹ného listu. Pokud ale +budeme hledat nìjaké jiné~$x$, zavedou nás do~nìjakého na~první pohled +nesouvisejícího listu a teprve tam zjistíme, ¾e jsme zabloudili. K~na¹emu +pøekvapení ale to, kam jsme se dostali, bude staèit ke~spoèítáním ranku +prvku, a~tím pádem i k~jeho vlo¾ení do~struktury. \s{Pøíklad:} - -\nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není +\nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není souèástí trie.} -\>Pozorování: -\itemize\ibull -\: Tvar stromu (oznaème ho $T$) je jednozaène urèen vektrorem -$\vec c=(c_1,\ldots,c_r)$. -\: Prvky jsou v trii umístìny vzestupnì zleva doprava. -\endlist - -To je sice v¹echno moc pìkné, ale pro aplikaci v Q-Heapech budeme muset umìt -poèítat $\rank_\X(x)$ v konstatním èase. Jak tedy na to? - -\s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì: +\s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì: \numlist\pnromanp -\: stromem $T$ -\: èíslem $i$: x vede v $T$ do $x_i$ -\: vztahem mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím $<,>,=$ -\: $\msb(x \oplus x_i)$ +\:tvarem stromu $T$ +\:indexem $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu, +\:vztahem mezi $x$ a $x_i$ ($xx_i$ nebo $x=x_i$) +\:$\msb(x \oplus x_i)$ \endlist -\s{Zdùvodnìní.} Pokud $x=x_i$, tak zjevnì $\rank_\X(x) = i$. Nech» tedy $x\neq -x_i$. Hodnoty znaèek klesají ve smìru od koøene k -listùm a na cestì od koøene k $x_i$ se v¹echny bity v $x_i$ na pozicích urèených -znaèkami shodují s bity v $x$ -- tak jsme k danému $x$ ve (ii) vybrali $x_i$. -Vezmeme do ruky $x$ a vydáme se na cestu od koøene do místa, kde bychom -oèekávali $x$, kdyby v trii bylo. Jeliko¾ $\msb(x \oplus x_i)$ urèitì není -znaèka na cestì z koøene do $x_i$ (v tom pøípadì by cesta podle znaèek nevedla -do $x_i$ -- $x$ se na této pozici od $x_i$, vydali bychom se tedy do opaèné -(shodující) vìtve), tak na této cestì je $\msb(x \oplus x_i)$ ostøe mezi -nìjakými znaèkami, co¾ mi urèí hranu -- breakpoint, pod kterou u¾ jsou v¹echny -hodnoty v listech buï men¹í (pokud $x>x_i$), nebo vìt¹í (pokud $xx_i$, tedy celý podstrom je men¹í ne¾ $x$ a tudí¾ $\rank_\X(011001)=4$. +a poèítejme $\rank_\X(011001)$. Místo první neshody je oznaèeno puntíkem. +Platí $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$, proèe¾ $\rank_\X(011001)=4$. + +Rádi bychom pøedchozí lemma vyu¾ili k~sestrojení tabulek, které podle uvedených +hodnot vrátí rank prvku~$x$. K~tomu potøebujeme pøedev¹ím umìt indexovat tvarem +stromu. + +\s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_n$ +(je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích +stromù), hodnoty v~listech jsou $x_1,\ldots,x_n$ v~poøadí zleva doprava. + +Vektor $(c_1,\ldots,c_n)$ má pouze $k\log w=\O(k^2)$ bitù, tak¾e jím mù¾eme +indexovat. Pro zjednodu¹ení ostatních operací zvolíme trochu jinou, ale +ekvivalentní reprezentaci: \s{Znaèení:} \itemize\ibull -\: $\B = \{c_1,\ldots,c_k\}$ -\: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$ +\:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì) +\:$C: \{1,\ldots,r\} \to B: B[C(i)]:=c_i$. \endlist -\s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z: +\s{Lemma 1':} $\rank_X(x)$ lze spoèítat v~konstatním èase~z: \numlist\pnromanap -\: $\B,\varphi$ -- tyto objekty urèují strom $T$ -\: $\equiv$ (ii), tj. èísla $i$: x vede v $T$ do $x_i$ -\: $\equiv$ (iii), tj. vztahu mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím -$<,>,=$ -\: $\rank_\B(\msb(x \oplus x_i))$ +\:funkce $C$ +\:$x_1,\ldots,x_r$ +\:$x[B]$ -- hodnoty bitù na~\uv{zajímavých} pozicích v~èísle~$x$, \endlist -a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase. - -\s{Zdùvodnìní.} -\numlist\pnromanap -\: Nic se nepoèítá, tak je strom ulo¾en. -\: +\s{Dùkaz:} Z~pøedchozího lemmatu: +\numlist\pnromanp +\:Tvar stromu závisí jen na~vzájemných vztazích mezi polohami znaèek, + tak¾e je jednoznaènì urèený funkcí~$C$. +\:Z~tvaru stromu a $x[B]$ jednoznaènì plyne list $x_i$ a tyto vstupy + jsou dostatenènì krátké na~to, abychom mohli pøedpoèítat tabulku. +\:Zjistíme prostým porovnáním. +\:$x_i$ známe a MSB umíme na~RAMu poèítat v~konstantním èase. \endlist - -\>A teï konkrétnì, jak bude Q-Heap realizována: - -\>Pamatujeme si: +Pøitom (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli +indexovat tabulku. +\qed + +\>Poèítání rankù je témìø v¹e, co potøebujeme k~implementaci operací +\, \ a \. Jediná dal¹í pøeká¾ka u¾ je zatøiïování +do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se ve¹el +do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» tyto hodnoty v~libovolném +poøadí a zvlá¹» permutaci, která je setøídí -- ta se ji¾ do~vektoru vejde. +Øeknìme tedy poøádnì, co~v¹e si bude struktura pamatovat: + +\s{Stav struktury:} \itemize\ibull -\: $\check x_1,\ldots,\check x_2$, hodnoty v libovolném poøadí -\: $\rho:$ permutace na $\{1,\ldots,k\}$ urèující $x_i = \check x_{\rho(i)}$ pro -$1 \le i \le r$, platí $x_1 < \ldots < x_r$ -\: $r$, poèet prvkù -\: $B$, mno¾ina ``zajímavých'' bitových pozic, reprezentovaná jako vektor -\: $R$, vektor popisující funkci $\varphi: \{1,\ldots,k\} \to \{1,\ldots,k\}$, t.¾. -$B[\varphi(i)] = c_i$ +\:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla) +\:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel) +\:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$ + a $x_1 A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}. +\>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace: + +\s{Find(x)} + +\algo +\:$i := \rank_X(x)$ +\:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.} +\endalgo \s{Insert(x)} \algo -\: $i = \rank_\X(x)$ -\: porovnáme $x,x_i$ -\: zaøadíme $x$ do $x_1,\ldots,x_r, r++$ -\: spoèítáme $c_i',c_{i+1}'$ -\: update $B,R$ +\:$i := \rank_\X(x)$ +\:Pokud $x=x_i$, hodnota u¾ je pøítomna. +\:Ulo¾íme $x$ do~pole~$X$ a vlo¾íme jeho pozici na~$i$-té místo v~permutaci~$\varrho$. +\:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$: +\::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam. +\::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu. +\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(k)$, sma¾eme ji z~$B$. \endalgo \s{Delete(x)} \algo -\: $i = \rank_\X(x)$, pøedpokládáme $x=x_i$, tedy ¾e prvek v haldì je -\: sma¾eme $x_i$ (uvolnìní $\check x_{\rho(i)}$, se¹oupnutí $\rho$); $r--$ -\: rozhodneme, jestli zmizí $c_i$, nebo $c_{i+1}$ -\: update $B$ (dle výsledku pøedchozího kroku), update $R$ (se¹oupnutí) +\:$i := \rank_\X(x)$ (víme, ¾e $x_i=x$). +\:Sma¾eme $x_i$ z~pole~$X$ (napøíklad prohozením s~posledním prvkem) a pøíslu¹nì upravíme~$\varrho$. +\:Pøepoèítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako pøi Insertu. \endalgo +\todo{Popsat, jak se poèítá $x[B]$.} + +\todo{Aplikace na~kostry.} + \bye -- 2.39.5