From 6d8b0faa3aba225c16ee40d3d9e06a156d0ae05b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 16 Oct 2010 21:47:03 +0200 Subject: [PATCH] Cesty: HOT Queue (opravena oproti clanku) --- 13-dijkstra/13-dijkstra.tex | 74 ++++++++++++++++++++++++++++++------- 1 file changed, 61 insertions(+), 13 deletions(-) diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex index d10e46b..1794049 100644 --- a/13-dijkstra/13-dijkstra.tex +++ b/13-dijkstra/13-dijkstra.tex @@ -404,9 +404,10 @@ Tehdy Dijkstra vyd 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. +Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. My si pøedvedeme její upravenou +variantu (v~té pùvodní se skrývá nìkolik chyb). -Poøídíme si tedy haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající, +Poøídíme si 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 @@ -416,23 +417,70 @@ skute 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). +Promìnnou~$\mu$ necháme ukazovat na~místo, kde jsme se pøi hledání minima v~pøihrádkách +zastavili. Souèasné globální minimum struktury tedy mù¾e být ni¾¹í, kdy¾ se minimum +zrovna nachází v~haldì, ale stále je zaruèeno, ¾e pøed~$\mu$ se ji¾ nenachází ¾ádná +neprázdná pøihradka. -\ 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. +Operace budou fungovat takto: -\ funguje jako pøedtím, pouze se musí poka¾dé podívat na~minimum haldy +\>\: +\algo +\:Spoèítáme, do~které úrovnì~$i$ ma prvek padnout. +\:Pokud je poèítadlo této úrovnì men¹í ne¾~$K$, zvý¹íme ho, vlo¾íme prvek do~haldy a skoèíme. +\:Nebyly-li je¹tì pro tuto úroveò zalo¾eny pøihrádky, vyrobíme je (prázdné). +\:Vlo¾íme prvek do~pøíslu¹né pøihrádky. +\endalgo + +\>\: +\algo +\:Pokud se prvek nachází v~haldì (to si u~ka¾dého prvku pamatujeme), provedeme + \ v~haldì a skonèíme. +\:Sma¾eme prvek z~jeho pøihrádky a provedeme \ s~novou hodnotou. +\endalgo + +\>\: +\algo +\:Dokud je~$\mu$ men¹í ne¾ aktuální minimum haldy, opakujeme: +\::Najdeme pøihrádku odpovídající hodnotì~$\mu$. +\::Je-li tato pøihrádka prázdná, pøejdeme na~dal¹í (upravíme~$\mu$). Jsme-li na konci úrovnì, pak o~úroveò vý¹. +\::Rozprostøeme tuto pøihrádku o~úroveò ní¾ (stejným zpùsobem, jako pøi \u, + tak¾e prvních~$H$ prvkù vlo¾íme do~haldy). +\:Sma¾eme minimum z~haldy a vrátíme ho jako výsledek. +\endalgo + +\>Pustíme se do~analýzy slo¾itosti. Jako parametry si zvolíme poèet hladin~$d$ (tak¾e +poèet pøihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$. -FIXME +Nejprve si v¹imneme, ¾e ne¾ poèítadlo nìjaké úrovnì vynulujeme, jsou bezpeènì +z~haldy pryè v¹echny prvky patøící do~této úrovnì. Celkem se tedy v~haldì +vyskytuje nejvý¹e $\O(dH)$ prvkù. \ v~haldì tedy trvá $\O(\log(dH))$, +ostatní haldové operace $\O(1)$. -XXX: odhad na velikost haldy +Nyní rozúètujeme èas operací mezi jednotlivé prvky (opìt si v¹e pøedplatíme +v~\u a ostatní operace pobì¾í v~amortizovanì konstantním èase): + +\itemize\ibull +\:Ka¾dý prvek mù¾e být nejvý¹e jednou za~dobu svého ¾ivota vlo¾en do~haldy + a nejvý¹e jednou z~ní vyjmut. Na~obojí dohromady pøispìje $\O(\log dH)$. +\:Prvek se úèastní nejvý¹e~$d$ pøehození do~ni¾¹í úrovnì. Pokud byl pøihozen + do~haldy, u¾ tam setrvá, jinak poka¾dé zaplatí $\O(1)$ za~zaøazení do~pøihrádky, + celkem tedy $\O(d)$ na prvek. +\:Vytvoøení, projití a smazání pøihrádek na~jedné úrovni nastane a¾ tehdy, co bylo + $H$~prvkù patøících do~této úrovnì vlo¾eno do~haldy. Staèí tedy, aby ka¾dý + prvek pøispìl èasem $\O(B/H) = \O(L^{1/d}/H)$. +\endlist -XXX: proè je~$B$ velké, ale~$d$ malé? +\>Ka¾dý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$. +Pojïme najít nastavení parametrù, abychom tento výraz minimalizovali. +Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$. +Celý výraz tím zjednodu¹íme na $\O(d + \log\,(L^{1/d}/d))$ = +$\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Dále zvolíme~$d$ +tak, aby se oba výrazy vyrovnaly, èili $d=\sqrt{\log L}$. -XXX: prvek pøispìje $d + T(H) + dL^{1/d}/H$. +HOT Queue tedy zvládne \ amortizovanou èasovou slo¾itostí $\O(\sqrt{\log L})$ +a ostatní operace v~èase amortizovanì konstantním. Pou¾ijeme-li tuto strukturu +v~Dijkstrovì algoritmu, spoète vzdálenosti v~èase $\O(m + n\sqrt{\log L})$. %\references \bye -- 2.39.2