From 0019a1a661b0558c5f8c4bcd44c9ff38c2b8999b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 17:12:23 +0100 Subject: [PATCH] Q-Heapy: pacifikace slohu a sazby. --- 8-qheap/8-qheap.tex | 79 +++++++++++++++++++++++---------------------- 1 file changed, 40 insertions(+), 39 deletions(-) diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex index 507e78c..46ebdc5 100644 --- a/8-qheap/8-qheap.tex +++ b/8-qheap/8-qheap.tex @@ -13,18 +13,20 @@ V~minul 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 \ a \ 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 @@ -42,32 +44,32 @@ vektory ve $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 +\:$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$). +(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 @@ -85,27 +87,27 @@ Nad~prvky $x_1,\ldots,x_r$ sestroj (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. \ss{Pøíklad:} -\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není -souèástí trie.}{\hsize} +\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost, není +souèástí struktury.}{\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$ ($xx_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$ ($xx_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 @@ -117,7 +119,7 @@ jsou men \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 @@ -127,17 +129,16 @@ stromu. (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í ale zvolíme trochu jinou, -ekvivalentní reprezentaci: +Kdykoliv chceme indexovat tvarem stromu, mù¾eme tedy indexovat pøímo vektorem +$(c_1,\ldots,c_n)$, který má pouze $k\log w=\O(k^2)$ bitù. Pro zjednodu¹ení ostatních +operací ale zvolíme trochu jinou, ekvivalentní reprezentaci: -\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ì) +\:$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~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$, @@ -151,10 +152,10 @@ ekvivalentn \: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 @@ -181,14 +182,14 @@ po \>$\(x):$ \algo -\:$i := \rank_X(x)$. +\:$i \leftarrow \rank_X(x)$. \:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.} \endalgo \>$\(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$: @@ -200,7 +201,7 @@ po \>$\(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 @@ -208,9 +209,9 @@ po \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 +\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ý @@ -218,7 +219,7 @@ 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ù} @@ -226,10 +227,10 @@ dosti n 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~konstantním èase +dokonce staèila halda velikosti $\Omega(\log^{(k)} n)$ s~operacemi v~konstantním èase pro nìjaké libovolné~$k$. \references -- 2.39.2