Kdy¾ u¾ máme takový poèítaè, pojïme si ukázat, jaké datové struktury na~nìm mù¾eme
vytváøet.
-Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur ukládáme,
-jsou navzájem rùzné.
-
Svým sna¾ením budeme smìøovat ke~strukturám, které zvládnou operace \<Insert> a \<Delete>
v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost
-struktury nebo obojí.
+struktury nebo obojí. Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur
+ukládáme, jsou navzájem rùzné.
\s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu a $n$~velikost vstupu algoritmu,
-v~nìm¾ datovou strukturu vyu¾íváme (tedy speciálnì víme, ¾e $w\ge\log n$).
+v~nìm¾ datovou strukturu vyu¾íváme (speciálnì tedy víme, ¾e $w\ge\log n$).
\h{Word-Encoded B-Tree}
+První strukturou, kterou popí¹eme, bude vektorová varianta B-stromu. Nemá je¹tì
+tak zajímavé parametry, ale odvozuje se snadno a jsou na~ní dobøe vidìt mnohé
+my¹lenky pou¾ívané ve~strukturách slo¾itìj¹ích.
+
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
$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,
aby bylo $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 pracující
-v~konstantním èase.
+získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech, která
+pracuje 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¹í
-konstrukci \cite{fw90trans}, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly.
+konstrukci od~Fredmana a Willarda \cite{fw90trans}, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly.
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.
+i prakticky.
\s{Znaèení:}
\itemize\ibull
-\: $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
+\:$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, ve~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$).
+\:$\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$
+(pøièem¾ $x$ mù¾e le¾et i mimo~$X$).
\endlist
\s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet.
To mù¾e znít hrozivì, 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øedvýpoèet stihneme v~èase $\O(n)$. V~takovém èase mimo jiné stihneme
pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$
bitù a kterou pro ka¾dý vstup dovedeme vyhodnotit v~polynomiálním èase.
Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce
(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
+øí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
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í v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku
prvku a z~rankù u¾ odvodíme i ostatní operace.
-\s{Pøíklad:}
-\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
-souèástí trie.}{\epsfxsize}
+\s{Pøíklad:} Trie pro zadanou mno¾inu èísel. Ohodnocení hran je pouze pro názornost, není
+souèástí struktury.
+\fig{trie.eps}{\hsize}
-\s{Lemma 1:} $\rank_X(x)$ je urèen jednoznaènì:
+\s{Lemma R:} $\rank_X(x)$ je urèen jednoznaènì kombinací:
\numlist\pnromanp
-\: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$ ($x<x_i$, $x>x_i$ nebo $x=x_i$),
-\:pozicí $b=\msb(x \oplus x_i)$.
+\:tvaru stromu $T$,
+\:indexu $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu,
+\:vztahu mezi $x$ a $x_i$ ($x<x_i$, $x>x_i$ nebo $x=x_i$) a
+\:pozice $b=\msb(x \oplus x_i)$.
\endlist
\proof Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne 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$, pøièem¾
+v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$. Pøitom
a¾ do~pozice $b$ se shodují i bity znaèkami netestované. Sledujme tuto cestu
od~koøene a¾ po~$b$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty
v~levém podstromu men¹í ne¾~$x$, a~tedy se do~ranku zapoèítají. Pokud odboèuje
\s{Pøíklad:} Vezmìme mno¾inu $X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
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$.
+Platí $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$, a~tak je $\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$
+\s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_{r-1}$
(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.
+stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ 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í ale zvolíme trochu jinou,
-ekvivalentní reprezentaci:
+Kdykoliv chceme indexovat tvarem stromu, mù¾eme místo toho pou¾ít pøimo vektor
+$(c_1,\ldots,c_r-1)$, který má $k\log w$ bitù. To se sice u¾ vejde do vektoru,
+ale pro indexování tabulek je to stále pøíli¹ (v¹imnìte si, ¾e $\log w$ smí být
+vùèi~$k$ libovolnì vysoký -- pro~$w$ známe pouze dolní mez). Proto reprezentaci
+je¹tì rozdìlíme na dvì èásti:
-\s{Znaèení:}
\itemize\ibull
-\:$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$.
+\:$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$ taková, ¾e $B[C(i)]=c_i$.
\endlist
-\s{Lemma 1':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
+\s{Lemma R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
\numlist\pnromanap
\:funkce $C$,
\:hodnot $x_1,\ldots,x_r$,
\:Z~tvaru stromu a $x[B]$ jednoznaènì plyne list $x_i$ a tyto vstupy
jsou dostateènì krátké na~to, abychom mohli pøedpoèítat tabulku
pro prùchod stromem.
-\:Zjistíme prostým porovnáním.
-\:$x_i$ známe a MSB umíme na~RAMu poèítat v~konstantním èase.
+\:Relaci zjistíme prostým porovnáním, jakmile známe~$x_i$.
+\:MSB umíme na~RAMu poèítat v~konstantním èase.
\endlist
-Pøitom (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli
+Mezivýsledky (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli
indexovat tabulku.
\qed
\:$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<x_2<\ldots<x_r$ (vektor o~$r\cdot\log r$ bitech),
+ a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log k$ bitech),
\:$B$ -- mno¾ina \uv{zajímavých} bitových pozic (setøídìný vektor o~$r\cdot\log w$ bitech),
-\:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log r$ bitech),
+\:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log k$ bitech),
\:pøedpoèítané tabulky pro rùzné funkce.
\endlist
\>$\<Find>(x):$
\algo
-\:$i := \rank_X(x)$.
+\:$i \leftarrow \rank_X(x)$.
\:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
\endalgo
\>$\<Insert>(x):$
\algo
-\:$i := \rank_X(x)$
+\:$i \leftarrow \rank_X(x)$.
\:Pokud $x=x_i$, hodnota u¾ je pøítomna.
\:Ulo¾íme $x$ do~$X[\mathop{{+}{+}}r]$ a vlo¾íme $r$ 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.
+\::Upravíme ostatní prvky~$C$, ukazující na hodnoty v~$B$, které se vlo¾ením posunuly.
\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$.
\endalgo
\>$\<Delete>(x):$
\algo
-\:$i := \rank_X(x)$ (víme, ¾e $x_i=x$).
+\:$i \leftarrow \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
\s{Èasová slo¾itost:} V¹echny kroky operací po~výpoètu ranku trvají konstantní èas, rank
samotný zvládneme spoèítat v~$\O(1)$ pomocí tabulek, pokud známe $x[B]$. Zde je ov¹em
nalíèen háèek -- tuto operaci nelze na~Word-RAMu konstantním poètem instrukcí spoèítat.
-Jak si pomù¾eme:
+Pomoci si mù¾eme dvìma zpùsoby:
-\itemize\ibull
-\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$ a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM.
+\numlist\nalpha
+\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$, a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM.
Zde dokonce mù¾eme vytváøet haldy velikosti a¾ $w\log w$. Také pøi praktické implementaci mù¾eme vyu¾ít
toho, ¾e souèasné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz napø. pìkný
rozbor v \cite{thorup:ac0}.
\:Jeliko¾ $B$ se pøi jedné Q-Heapové operaci mìní pouze o~konstantní poèet prvkù, mù¾eme
si udr¾ovat pomocné struktury, které budeme umìt pøi lokální zmìnì~$B$ v~lineárním èase
pøepoèítat a pak pomocí nich indexovat. To pomocí Word-RAMu lze zaøídit, ale je to technicky
-dosti nároèné, tak¾e ètenáøe odkazujeme na~Fredmanùv a Willardùv èlánek \cite{fw90trans}.
+dosti nároèné, tak¾e ètenáøe zvìdavého na~detaily odkazujeme na~èlánek \cite{fw90trans}.
\endlist
\h{Aplikace Q-Heapù}
Jedním velice pìkným dùsledkem existence Q-Heapù je lineární algoritmus na~nalezení
minimální kostry grafu ohodnoceného celými èísly. Získáme ho z~Fredmanovy a Tarjanovy
varianty Jarníkova algoritmu (viz kapitoly o~kostrách) tak, ¾e v~první iteraci pou¾ijeme
-jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak u¾ budeme pokraèovat s~Fibonacciho
+jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak budeme pokraèovat s~pùvodní Fibonacciho
haldou. Tak provedeme tolik prùchodù, kolikrát je potøeba zlogaritmovat $n$,
aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. V¹imnìte si, ¾e by nám
-dokonce staèila halda velikosti $\O(\log^{(k)} n)$ a~operacemi v~konstantím èase
+dokonce staèila halda velikosti $\Omega(\log^{(k)} n)$ s~operacemi v~konstantním èase
pro nìjaké libovolné~$k$.
\references
projects / ga.git / blobdiff