From c63f22938a0dcd257d2914cea09b9b5c832d0520 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 16 Oct 2010 18:46:03 +0200 Subject: [PATCH] Cesty: par prihradkovych datovych struktur, jeste nedopsanych --- 13-dijkstra/13-dijkstra.tex | 165 +++++++++++++++++++++++++++++++++++- sgr.tex | 2 +- 2 files changed, 164 insertions(+), 3 deletions(-) diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex index 8673f99..d10e46b 100644 --- a/13-dijkstra/13-dijkstra.tex +++ b/13-dijkstra/13-dijkstra.tex @@ -253,7 +253,11 @@ na~struktu \:{\I Fibonacciho halda} -- \ a \ stojí $\O(1)$, \ má slo¾itost $\O(\log n)$ [v¹e amortizovanì]. Dijkstrùv algoritmus tedy dobìhne v~èase $\O(m + n\log n)$. To je lineární pro grafy s~hustotou $\Omega(\log n)$. -\:{\I Datové struktury pro èísla omezeného rozsahu} -- prozkoumáme vzápìtí. +\:{\I Monotónní haldy} -- mù¾eme pou¾ít nìjakou jinou haldu, která vyu¾ívá toho, + ¾e posloupnost odebíraných prvkù neklesající. Pro celá èísla na~RAMu to mù¾e + být napøíklad Thorupova halda (REF) se slo¾itostí $\O(\log\log n)$ na~\ + a $\O(1)$ u~ostatních operací. Dijkstra tedy bì¾í v~$\O(m + n\log\log n)$. +\:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápìtí. \endlist \>\s{Cvièení:} @@ -263,7 +267,8 @@ na~struktu na~kterém Dijkstrùv algoritmus sel¾e. \:Rozmyslete si, ¾e pokud nevyu¾ijeme nìjaké speciální vlastnosti èísel (celoèíselnost, omezený rozsah), je mez $\O(m+n\log n)$ nejlep¹í mo¾ná, proto¾e Dijkstrovým algoritmem - mù¾eme tøídit $n$-tici èísel. + mù¾eme tøídit $n$-tici èísel. Thorup dokonce dokázal (REF), ¾e z~ka¾dého tøídícího algoritmu + se slo¾itostí $nT(n)$ mù¾eme odvodit monotónní haldu se slo¾itostí mazání $\O(T(n))$. \:Jsou-li délky hran celoèíselné, mù¾eme se na Dijkstrùv algoritmus dívat i takto: Pøedstavme si, ¾e ka¾dou hranu nahradíme cestou tvoøenou hranami jednotkové délky a na vzniklý neohodnocený graf spustíme prohledávání do~¹íøky. To samozøejmì vydá @@ -273,5 +278,161 @@ na~struktu Doka¾te, ¾e tento algoritmus je ekvivalentní s~Dijkstrovým. \endlist +\h{Celoèíselné délky} + +Uva¾ujme nyní grafy, v~nich¾ jsou v¹echny délky hran nezáporná celá èísla omezená +nìjakou konstantou~$L$. V¹echny vzdálenosti jsou tedy omezeny èíslem~$nL$, tak¾e +nám staèí datová struktura schopná uchovávat takto omezená celá èísla. + +Pou¾ijeme jednoduchou pøihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$, +jeho $i$-tý prvek bude obsahovat seznam vrcholù, jejich¾ ohodnocení je rovno~$i$. +Operace \ a \ zvládneme v~konstantním èase, budeme-li si u~ka¾dého +prvku pamatovat jeho polohu v~seznamu. Operace \ potøebuje najít první +neprázdnou pøihrádku, ale jeliko¾ víme, ¾e posloupnost odebíraných minim je monotónní, +staèí hledat od místa, kde se hledání zastavilo minule. V¹echna hledání pøihrádek +tedy zaberou dohromady $\O(nL)$ a celý Dijkstrùv algoritmus bude trvat $\O(nL + m)$. + +Prostorová slo¾itost $\O(nL+m)$ je nevalná, ale mù¾eme ji jednoduchým trikem +sní¾it: V¹imneme si, ¾e v¹echna koneèná ohodnocení vrcholù nemohou být vìt¹í +ne¾ aktuální minimum zvìt¹ené o~$L$. Jinými slovy v¹echny neprázdné pøihrádky +se nacházejí v~úseku pole dlouhém~$L+1$, tak¾e staèí indexovat modulo~$L+1$. +Pouze si musíme dávat pozor, abychom správnì poznali, kdy se struktura +vyprázdnila, co¾ zjistíme napøíklad pomocí poèítadla otevøených vrcholù. Èas si +asymptoticky nezhor¹íme, prostor klesne na~$\O(L+m)$. + +Podobný trik mù¾eme pou¾ít i pro libovolnou jinou datovou strukturu: rozsah èísel +rozdìlíme na~\uv{okna} velikosti~$L$ (v~$i$-tém oknì jsou èísla $Li,\ldots,L(i+1)-1$). +V~libovolné chvíli mohou tedy být neprázdná nejvý¹e dvì okna. Staèí nám proto +poøídit si dvì struktury pro ukládání èísel v~rozsahu $0,\ldots,L-1$ -- jedna +z~nich bude reprezentovat aktuální okno (to, v~nìm¾ le¾elo minulé minimum), +druhá okno bezprostøednì následující. Minimum ma¾eme z~první struktury; pokud +u¾ je prázdná, obì struktury prohodíme. Operace \ podle hodnoty urèí, +do~které struktury se má vkládat. S~operací \ je to slo¾itìj¹í -- +hodnota z~vy¹¹í struktury mù¾e pøeskoèit do té ni¾¹í, ale v~takovém pøípadì +ji ve~vy¹¹í struktuøe vyma¾eme (to je \ na $-\infty$ následovaný +\em) a do~ni¾¹í vlo¾íme. To se ka¾dému prvku mù¾e pøihodit nejvý¹e +jednou, tak¾e stále platí, ¾e se ka¾dý prvek úèastní $\O(1)$ vlo¾ení a $\O(1)$ +extrakcí minima. + +Ukázali jsme tedy, ¾e pro na¹e potøeby postaèuje struktura schopná uchovávání +èísel men¹ích nebo rovných~$L$. + +Nabízí se pou¾ít van Emde-Boasùv strom z~kapitoly o~výpoèetních modelech. +Ten dosahuje slo¾itosti $\O(\log\log L)$ pro operace \ a \, +operaci \ musíme pøekládat na \ a \. Celková +slo¾itost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, pøièem¾ èas~$L$ +spotøebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout, +viz zmínìná kapitola). + +Vra»me se ale je¹tì k~vyu¾ití pøihrádek\dots + +\h{Víceúrovòové pøihrádky} + +Podobnì jako u~tøídìní èísel, i~zde se vyplácí stavìt pøihrádkové struktury +víceúrovòovì. Jednotlivé hodnoty budeme zapisovat v~soustavì o~základu~$B$, +který zvolíme jako nìjakou mocnina dvojky, abychom mohli s~èíslicemi tohoto +zápisu snadno zacházet pomocí bitových operací. Ka¾dé èíslo tedy zabere nejvý¹e +$d=1+\lfloor\log_B L\rfloor$ èíslic; pokud bude krat¹í, doplníme ho zleva nulami. + +Nejvy¹¹í patro struktury bude tvoøeno polem $B$~pøihrádek, v~$i$-té z~nich +budou ulo¾ena ta èísla, jejich¾ nejvy¹¹í øád je roven~$i$. Za~{\I aktivní} +prohlásíme tu pøihrádku, která obsahuje aktuální minimum. Pøihrádky s~men¹ími +indexy jsou prázdné a zùstanou takové a¾ do~konce výpoètu, proto¾e halda +je monotónní. Pokud v~pøihrádce obsahující minimum bude více prvkù, budeme +ji rozkládat podle druhého nejvy¹¹ího øádu na dal¹ích~$B$ pøihrádek atd. +Celkem tak vznikne a¾~$d$ úrovní. + +\>Struktura bude obsahovat následující data: + +\itemize\ibull +\:Parametry $L$, $B$ a~$d$. +\:Pole úrovní (nejvy¹¹í má èíslo~$d-1$, nejni¾¹í~0), ka¾dá úroveò je buïto prázdná + (a pak jsou prázdné i~v¹echny ni¾¹í), nebo obsahuje pole~$U_i$ o~$B$ pøihrádkách, + z~nich¾ ka¾dá obsahuje seznam prvkù. Toto pole pou¾íváme jako zásobník, udr¾ujeme + si èíslo nejni¾¹í neprázdné úrovnì. +\:Hodnotu~$\mu$ pøedchozího odebraného minima. +\endlist + +Operace \ vlo¾í hodnotu do~nejhlub¹í mo¾né pøihrádky. Podívá se tedy +na~nejvy¹¹í úroveò: pokud hodnota patøí do pøihrádky, která není aktivní, vlo¾í +ji pøímo. Jinak pøejde o~úroveò ní¾e a zopakuje stejný postup. To v¹e lze provést +v~konstantním èase: staèí se podívat, jaký je nejvy¹¹í jednièkový bit ve~{\sc xor}u +nové hodnoty s~èíslem~$\mu$ (opìt viz kapitola o~výpoèetních modelech). + +Pokud chceme provést \, odstraníme hodnotu z~pøihrádky, ve~které se +právì nachází (polohu si mù¾eme u~ka¾dé hodnoty pamatovat zvlá¹»), a znovu ji +vlo¾íme. + +Vìt¹inu práce samozøejmì pøenecháme funkci \. Ta zaène prohledávat +nejni¾¹í obsazenou úroveò od~aktivní pøihrádky dál (to, která pøihrádka je na +které úrovni aktivní, poznáme z~èíslic hodnoty~$\mu$). Pokud pøihrádky na~této +úrovni dojdou, prázdnou úroveò zru¹í a pokraèuje o~patro vý¹e. + +Jakmile najde neprázdnou pøihrádku, nalezne v~ní minimum a to se stane novým~$\mu$. +Pokud v~pøihrádce nebyly ¾ádné dal¹í prvky, skonèí. Jinak zbývající prvky +rozprostøe do~pøihrádek na~bezprostøednì ni¾¹í úrovni, kterou tím zalo¾í. + +Èas strávený hledáním minima mù¾eme rozdìlit na~nìkolik èástí: + +\itemize\ibull +\:$\O(B)$ na inicializaci nové úrovnì -- to naúètujeme prvku, který jsme + právì mazali; +\:hledání neprázdných pøihrádek -- prozkoumání ka¾dé prázdné pøihrádky + naúètujeme jejímu vytvoøení, co¾ se rozpustí v~$\O(B)$ na inicializaci + úrovnì; +\:zru¹ení úrovnì -- opìt naúètujeme jejímu vzniku; +\:rozhazování prvkù do pøihrádek -- jeliko¾ prvky v~hierarchii pøihrádek + putují bìhem operací pouze doleva a dolù (jejich hodnoty se nikdy nezvìt¹ují), + klesne ka¾dý prvek nejvý¹e~$d$-krát, tak¾e staèí, kdy¾ na v¹echna rozhazování + pøispìje èasem $\O(d)$. +\endlist + +\>Staèí tedy, aby ka¾dý prvek pøi \u zaplatil èas $\O(B+d)$ a jak \, +tak \ pak budou mít konstantní amortizovanou slo¾itost. Dijkstrùv +algoritmus pak pobì¾í v~$\O(m + n(B+d))$. + +Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$. +Vhodná volba je $B=\log L/\log\log L$. Pøi ní platí +$$ +{\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) } += {\log L\over \log\log L - \log\log\log L} = \Theta(B). +$$ +Tehdy Dijkstra vydá výsledek v~èase $\O(m + n\cdot{\log L\over\log\log L})$. + +\h{HOT Queue -- kombinace pøihrádek s~haldou} + +Goldberg a Cherkassky (REF) si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách +platíme pøíli¹ mnoho za~úrovnì, ve~kterých se za~dobu jejich existence objeví jen malé +mno¾ství prvkù. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~spoleèné haldy. +Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. + +Poøídíme si tedy haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající, +kolik prvkù z~této úrovnì jsme ulo¾ili do~haldy. Dokud toto poèítadlo nepøeroste nìjaký +parametr~$H$, pøihrádky nebudeme zakládat a prvky poputují do~haldy. Èas $\O(B)$ na +zalo¾ení úrovnì a její procházení tedy mù¾eme rozpoèítat mezi~$H$ prvkù, které se musely +na~dané úrovni objevit, ne¾ byla rozpøihrádkována. (Pov¹imnìte si, ¾e poèítadlo nikdy +nesni¾ujeme, pouze ho vynulujeme, kdy¾ je úroveò zru¹ena, tak¾e vùbec nemusí odpovídat +skuteènému poètu prvkù z~pøíslu¹né úrovnì, které jsou právì ulo¾eny v~haldì. To ov¹em +vùbec nevadí -- poèítadlo pouze hlídá, aby se úroveò nevytvoøila pøíli¹ brzy a abychom +mìli dost prvkù k~rozúètování èasu.) + +\ tedy pøed zaøazením na pøíslu¹nou úroveò zvý¹í poèítadlo a pokud je +stále men¹í ne¾~$H$, vlo¾í prvek do~haldy. Jinak prvek vlo¾í do~pøíslu¹né pøihrádky +(pokud je¹tì pøihrádky neexistují, zalo¾í je). + +\ se podívá, zda je prvek v~haldì nebo v~pøihrádce (to si o~nìm pamatuje). +Pokud v~haldì, pøedá øízení operaci \ haldy. Pokud v~pøihrádce, pøevede se +na smazání a \. S~poèítadly sám nehýbe. + +\ funguje jako pøedtím, pouze se musí poka¾dé podívat na~minimum haldy + +FIXME + +XXX: odhad na velikost haldy + +XXX: proè je~$B$ velké, ale~$d$ malé? + +XXX: prvek pøispìje $d + T(H) + dL^{1/d}/H$. + %\references \bye diff --git a/sgr.tex b/sgr.tex index a7161ff..fba5dbb 100644 --- a/sgr.tex +++ b/sgr.tex @@ -86,7 +86,7 @@ \def\algohang:{\advance\hangindent by 2em \hskip 2em\futurelet\next\algoitemh} % Nekolikapismenkova promenna (mozno pouzit v textovem i math modu) -\def\<#1>{\hbox{\it #1\/}} +\def\<#1>{\leavevmode\hbox{\it #1\/}} % Asymptoticke O-cko \def\O{{\cal O}} -- 2.39.2