Fibonacciho haldy- jejich varianty a alternativní datové struktury

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

DIPLOMOVÁ PRÁCE

Jakub Melka Fibonacciho haldy - jejich varianty a alternativní datové struktury Katedra softwarového inženýrství Vedoucí diplomové práce: RNDr. Alena Koubková CSc. Studijní program: Informatika Studijní obor: Softwarové systémy Praha 2012

Děkuji své vedoucí RNDr. Aleně Koubkové, CSc. za vedení diplomové práce, cenné rady a připomínky.

Prohlašuji, že jsem tuto diplomovou práci vypracoval(a) samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona. V . . . . . . . . dne . . . . . . . . . . . .

Podpis autora

Název práce: Fibonacciho haldy - jejich varianty a alternativní datové struktury Autor: Jakub Melka Katedra: Katedra softwarového inženýrství Vedoucí diplomové práce: RNDr. Alena Koubková CSc., Katedra distribuovaných a spolehlivých systémů Abstrakt: V této práci budeme zkoumat Fibonacciho haldy a jejich varianty. Alternativní verze Fibonacciho hald, tzv. thin a thick haldu zavedli H. Kaplan a R. E. Tarjan v roce 2008. Srovnáme tyto haldy jak z experimentálního, tak z teoretického hlediska a do tohoto srovnání zahrneme i některé klasické druhy hald, jmenovitě párovací a regulární haldu. Při experimentech nás bude nejvíce zajímat celkový čas nutný pro běh algoritmu, který pracuje s haldou. Na výsledcích ukážeme, že thin a thick haldy jsou obvykle rychlejší, než Fibonacciho halda a pomalejší, než regulární haldy. Na závěr shrneme poznatky získané experimenty. Klíčová slova: halda, Fibonacciho halda, thin halda, thick halda Title: Fibonacci heaps - their variations and alternative data structures Author: Jakub Melka Department: Department of Software Engineering Supervisor: RNDr. Alena Koubková CSc., Department of Distributed and Dependable Systems Abstract: In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments. Keywords: heap, Fibonacci heap, thin heap, thick heap

Obsah Úvod

3

1 Základy teorie složitosti 1.1 Složitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Amortizovaná složitost . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 7

2 Haldy - teoretický přehled 2.1 d-regulární haldy . . . . . . 2.2 Binomiální haldy . . . . . . 2.3 Líná verze binomiální haldy 2.4 Fibonacciho haldy . . . . . 2.5 Párovací haldy . . . . . . . 2.6 Thin haldy . . . . . . . . . . 2.7 Thick haldy . . . . . . . . . 2.8 Další typy hald . . . . . . . 2.9 Algoritmy využívající haldy

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

11 11 15 18 20 24 27 31 34 35

3 Vyhodnocování měření a základy statistiky 3.1 Úvod do teorie pravděpodobnosti . . . . . . 3.2 Základy matematické statistiky . . . . . . . 3.3 Diagramy . . . . . . . . . . . . . . . . . . . 3.4 Měření a vyhodnocení naměřených dat . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

39 39 41 44 47

4 Benchmarky a výsledky měření 4.1 Implementace datových struktur . 4.2 Benchmark - budování haldy . . . 4.3 Benchmark - heapsort . . . . . . 4.4 Benchmark - Dijkstrův algoritmus 4.5 Benchmark - heapsequence . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

51 51 52 54 55 59

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . .

5 Závěr 61 5.1 Další výzkum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Dodatek - Obsah CD

63

Literatura

69

1

2

Úvod V mnoha praktických problémech se setkáváme s potřebou mít datovou strukturu operující nad prvky s lineárním uspořádáním, do které lze rychle vkládat, snižovat či zvyšovat hodnotu prvku a rychle vybírat minimum z prvků obsažených v dané datové struktuře. Tato datová struktura splňující výše uvedené požadavky se nazývá halda. V této oblasti probíhá rozsáhlý vývoj a existuje nepřeberné množství druhů hald. Haldy nalézají uplatnění například v teorii grafů, velice známý Dijkstrův algoritmus [8] pro počítání nejkratších cest v grafu využívá haldu, dále pomocí haldy můžeme třídit. Halda se také často používá pro implementaci prioritních front. Cílem této práce je poskytnout experimentální studii variant Fibonacciho hald, publikovaných v článku [23], vzhledem k obvyklým druhům hald, jako je například d-regulární halda [32], Fibonacciho halda [17] a párovací halda [14]. Budeme tyto haldy zkoumat z hlediska výkonu v různých situacích a také při použití v algoritmech jako je heapsort nebo zmíněný Dijkstrův algoritmus. Zajímají nás nejpoužívanější operace - INSERT, DECREASEKEY a DELETEMIN, na kterých budeme rychlost haldy měřit. V první kapitole uvedeme základní poznatky z teorie složitosti a amortizované složitosti, která je nutná k pochopení studia časové složitosti jednotlivých druhů hald. Ve druhé kapitole uvedeme přehled testovaných druhů hald, krátký přehled ostatních druhů hald a algoritmy využívající haldy, na kterých budeme jednotlivé druhy hald testovat. Ve třetí kapitole uvedeme úvod do statistiky nutný ke zpracování výsledků měření, princip měření a vyhodnocování výsledků měření. Ve čtvrté kapitole popíšeme testy hald a jejich výsledky. V páté závěrečné kapitole shrneme naměřené výsledky.

3

4

1. Základy teorie složitosti V této kapitole uvedeme některé základní teoretické poznatky, které je vhodné znát pro správné pochopení teoretických znalostí o složitosti operací datových struktur uvedených v této diplomové práci. Chceme znát jakousi míru, podle které bychom dokázali určit, jak dlouho daná operace bude trvat. Protože na každém počítači může být v závislosti na tom, jak je ten počítač rychlý, doba běhu různá, z teoretického hlediska se zavedly formální modely výpočetních strojů. Prvním modelem je všeobecně známý Turingův stroj pracující s řídící jednotkou nad nekonečnou páskou s konečnou abecedou. Časová složitost je počet vykonaných instrukcí řídící jednotky. Existují ještě další modely, například RAM a Pointer machine. Hlubší poznatky z teorie složitosti lze nalézt v knihách [4] a [18]. V praxi se obvykle měří složitost méně formálním způsobem. Měří se například počet operací charakteristických pro daný algoritmus (pro třídění to může být například celkový počet porovnání), počet časově nejnáročnějších operací (pro databáze například počet I/O operací), případně celkový čas, než algoritmus dokončil svoji práci, v tom případě je nutné uvést parametry systému, na kterém je čas měřen. Obvykle se složitost vyjadřuje asymptoticky v symbolech O, Θ a Ω, protože často nás zajímá chování na velkých datech, případně jak rychle složitost roste s velikostí vstupu. Toto vyjádření umožňuje klasifikovat algoritmy z hlediska časové složitosti například jako lineární, kvadratické nebo exponenciální.

1.1

Složitost

Obvykle se definují pojmy časová a prostorová složitost algoritmu pro nějaký vstup velikosti n. U datových struktur musíme také brát v úvahu vnitřní strukturu dané datové struktury, protože časová složitost operace na datové struktuře závisí na tom, jak je tato datová struktura uvnitř organizována. Definice. Nechť A(x) je algoritmus, Dn jsou všechny možné vstupy algoritmu velikosti n a t(x) je spotřebovaný čas1 algoritmu pro vstup x ∈ Dn . Zavedeme následující druhy časové složitosti: (a) Časovou složitost v nejlepším případě OP T (n) definujeme jako OP T (n) = min t(x). x∈Dn

(1.1)

(b) Nechť Pn je pravděpodobnostní distribuce nad Dn , pak časovou složitost v průměrném případě vzhledem k Pn definujeme jako X EXP (n) = t(x)Pn (x) (1.2) x∈Dn

1

Zde tím míníme počet instrukcí provedených touto operací.

5

(c) Časovou složitost v nejhorším případě T (n) definujeme jako T (n) = max t(x). x∈Dn

(1.3)

Pokud neuvedeme druh složitosti, obvykle se tím míní složitost v nejhorším případě a jestliže není u průměrné časové složitosti uvedena distribuce, míní se tím použití uniformní2 distribuce. Protože v následující podkapitole definujeme amortizovanou složitost, pro zdůraznění odlišností mezi amortizovanou složitostí a složitostí v průměrném případě ukážeme příklad výpočtu složitosti v průměrném případě algoritmu QuickSort[19]. Input: posloupnost a1 , a2 , . . . , an navzájem různých prvků Output: setříděná vstupní posloupnost if n ≤ 1 then return else k ← náhodně vybraná hodnota z {1, 2, . . . , n} L ← {ai |ai < ak , i = 1, . . . , n} U ← {ai |ai > ak , i = 1, . . . , n} return QuickSort(L),ak ,QuickSort(U ) end Algoritmus 1: Quicksort

Věta 1. Průměrný počet porovnání algoritmu QuickSort na vstupu s n prvky je O(n log n). Časová složitost v průměrném případě algoritmu QuickSort je O(n log n). Důkaz. Důkaz časové složitosti plyne snadno z odhadu počtu porovnání, protože v algoritmu provádíme pouze konstantně mnoho práce na jedno porovnání. Označme X jako náhodnou proměnnou udávající počet porovnání. Pro i, j ∈ {1, 2, . . . , n} zavedeme následující náhodné proměnné: ( 1 i < j, ai a aj jsou porovnány, Xij = 0 jinak, kde al je l-tý nejmenší prvek posloupnosti. Předpokládáme, že pivot vybíráme uniformně náhodně. Pokud vybereme jako pivot nějaký prvek, který není v množině {ai , ai+1 , . . . , aj }, tak celá tato množina skončí ve stejné části při rozdělování prvků podle pivota. Pokud vybereme jako pivota jeden z prvků ai+1 , . . . , aj−1 , tak pak už nikdy neporovnáme ai a aj , protože ai a aj budou rozdělení pivotem. Xij tedy závisí pouze na výběru pivota z množiny {ai , ai+1 , . . . , aj }. Pravděpodobnost, že dva prvky 2

všechny vstupy mají stejnou pravděpodobnost

6

jsou porovnány, je tedy rovna pravděpodobnosti, že jeden z nich bude vybrán jako pivot, tedy 2 P r [Xij = 1] = j−i+1 P Xij a Pak X = i<j

E [X] = E

" X

Xij

i<j

= = ≤

X

i<j n X

#

E [Xij ] n X

2 j−i+1 j=i+1

i=1 n X n X i=1 k=1

2 k+1

= 2n(Hn − 1) ≈ 2n log n Proto je střední hodnota počtu porovnání O(n log n).

1.2

Amortizovaná složitost

Pojem „amortizovaná složitostÿ zavedl R.E. Tarjan v roce 1985 v publikaci [31]. Amortizovanou složitost operace na dané datové struktuře si můžeme představit jako horní odhad průměrné složitosti operace v nějaké posloupnosti operací, počítáno přes všechny konečné posloupnosti operací. Mezi složitostí v průměrném případě a amortizovanou složitostí je zásadní rozdíl, protože amortizovaná složitost vychází z horního odhadu doby výpočtu posloupnosti operací, kdežto složitost v průměrném případě počítá průměrnou dobu výpočtu přes nějakou distribuci dat na vstupu. K počítání amortizované složitosti slouží několik metod. Ukážeme si agregační metodu, účetní metodu a metodu potenciálu na příkladu převzatém z učebního textu [29]. Zadefinujeme následující operace nad zásobníkem: a) PUSH(S, x) - vloží prvek x na zásobník, b) POP(S) - sejme jeden prvek ze zásobníku, c) MULTIPOP(S, k) - sejme min{|S|, k} prvků ze zásobníku. Postupně zmíněnými třemi metodami dokážeme následující větu. Věta 2. Nechť na začátku S = ∅. Pak operace PUSH, POP a MULTIPOP definované výše mají amortizovanou složitost O(1). 7

Důkaz. Nejprve větu dokážeme pomocí agregační metody. V ní odhadneme seshora celkový čas k provedení posloupnosti n operací a vydělíme ho n. Pak dostaneme amortizovaný čas na jednu operaci. U této metody se nerozlišují jednotlivé druhy operací. Operace PUSH i POP mají konstantní časovou složitost i v nejhorším případě. Protože velikost zásobníku je nejvýše n, můžeme z něj odebrat nejvýše n prvků, tedy celkový čas T (n) ≤ 2n a proto amortizovaný čas jedné operace je T (n)/n = O(1). Další (účetní) metoda využívá následující myšlenky: za každou operaci platíme určitý obnos, ten může být využit přímo pro změnu datové struktury, nebo se může vložit na účet dané datové struktury (nebo její části) pro jeho pozdější využití. Operace tedy mohou vybírat nastřádaný obnos ušetřený a vložený na účet předchozími operacemi. Obnos, který operace i zaplatí, označíme ci a množství operací skutečně spotřebovaného času označíme ci . Pokud dokážeme zajistit, že pro každou posloupnost operací délky n platí, že n X i=1

ci ≥

n X

ci ,

(1.4)

i=1

pak ci je amortizovaná složitost operace i. Operaci PUSH a POP lze provést v konstantním čase, proto ci = 1, pokud itá operace je PUSH nebo POP. Operaci MULTIPOP3 lze provést v čase ki , proto ci = ki , pokud i-tá operace je MULTIPOP(S, ki ). Nyní definujeme ci podle druhu i-té operace, která se provádí: ( 2 i-tá operace je PUSH, ci = (1.5) 1 jinak. Nyní stačí dokázat, že součet ci je větší nebo roven součtu ci . Ukážeme, že tomu tak je. V případě operace POP je ci = ci a příspěvek do obou součtů je stejný. V případě operace PUSH jednu jednotku uložíme na účet vloženého prvku a zbylá jednotka přispěje do obou součtů stejně. V případě operace MULTIPOP(S, ki ) je situace trochu složitější. Pokud provádíme tuto operaci, předpokládáme, že ki ≤ |S|, jinak bychom ki patřičně snížili. Protože každý prvek na zásobníku má na účtu jednu jednotku, použijeme ji na odstranění prvku ze zásobníku. Odstraňujeme ki prvků, proto obnosem ki vybraným z účtů prvků zaplatíme za čas ci a nerovnost součtů bude platit. Poslední metodou je potenciálová metoda. Nechť M je množina všech konfigurací datové struktury. Zavedeme funkci Φ : M → N takovou, že pokud S0 , S1 , . . . , Sn je posloupnost konfigurací datové struktury taková, že S0 je počáteční konfigurace a datová struktura s konfigurací Si vznikne aplikací operace i na datovou strukturu s konfigurací Si−1 , tak Φ(Si ) ≥ Φ(S0 ) pro každé i a obvykle volíme Φ(S0 ) = 0. Funkce Φ určuje amortizované složitosti jednotlivých operací následujícím způsobem: ci = ci + Φ(Si ) − Φ(Si−1 ) 3

předpokládáme ki ≤ |S|

8

(1.6)

Zbývá ukázat, že skutečně to je korektní postup: n X i=1

ci =

n n n X X X (ci + Φ(Si ) − Φ(Si−1 )) = ci + Φ(Sn ) − Φ(S0 ) ≥ ci i=1

i=1

(1.7)

i=1

Zvolme Φ(S) = |S| a počítejme. Pokud i je operace PUSH, pak ci = 1, potenciál vzroste o jedna a dostáváme, že ci = 1 + |Si−1 | + 1 − |Si−1 | = 2. Pokud i je operace POP, pak ci = 1, potenciál klesne o jedna a dostaneme ci = 1 + |Si−1 | − 1 − |Si−1 | = 0. Nutno podotknout, že zde považujeme amortizovaný čas za konstantní, nikoliv nulový. Poslední je operace MULTIPOP(Si , ki ), ci = ki + 1. ci = ki + 1 + |Si−1 | − ki − |Si−1 | = 1 | {z } | {z } | {z } ci

Φ(Si )

Φ(Si−1 )

Tedy amortizovaná složitost všech operací je konstantní.

9

(1.8)

10

2. Haldy - teoretický přehled Halda je stromová datová struktura umožňující rychlé zjišťování minima (MIN) prvků v haldě, dále rychlé mazání minimálního prvku (DELETEMIN) a přidávání prvků (INSERT), obvykle vše v čase O(log n). Halda pracuje s libovolnými prvky (nazývané také klíči), na nichž je definováno lineární uspořádání, což jsou například přirozená čísla. Dále haldy podporují snižování (DECREASEKEY) a zvyšování hodnoty klíče (INCREASEKEY), obvykle rovněž v logaritmickém čase. Některé typy hald podporují spojování (operace MERGE) hald rovněž v logaritmickém čase, některé typy, jako například d-regulární haldy, umožňují spojování pouze v lineárním čase. Dále haldy většinou podporují operaci DELETE, která smaže daný prvek z haldy. Protože haldy nepodporují vyhledávání podle klíče, je nutné si někde poznamenat ukazatel na daný prvek v haldě. Dále předpokládáme korektnost vstupu při použití jednotlivých operací. To znamená, že pokud použijeme operaci INSERT, daný prvek nesmí být v haldě, při volání DELETE a DECREASEKEY musí být ukazatel na daný prvek v haldě korektní a operaci DELETEMIN a MIN použijeme pouze v případě, že halda není prázdná. V následujícím textu označme jako key(v) klíč uzlu v a označme dále rodiče uzlu v jako parent(v). Definice. Zakořeněný strom T má vlastnost haldy, pokud pro každý vrchol v různý od kořene r platí, že key(v) ≥ key(parent(v)).

2.1

d-regulární haldy

Tyto haldy zavedl poprvé Donald B. Johnson ve své publikaci [21], zobecnil tím binární haldu popsanou J.W.J. Williamsem v publikaci [34] v roce 1964. Ačkoliv se jedná o poměrně starou datovou strukturu, v praxi se ukazuje, že je velmi rychlá. Definice. d-regulární halda je datová struktura reprezentovaná zakořeněným stromem T spolu s uspořádáním vrcholů podle průchodu do šířky s následujícími vlastnostmi: (i) T má vlastnost haldy (ii) Každý uzel v ∈ T s výjimkou maximálně jednoho je buď list, nebo má právě d synů (iii) Každý uzel v ∈ T má nejvýše d synů. (iv) Všechny vrstvy, eventuálně kromě poslední, jsou úplné a poslední vrstva je naplněna zleva doprava, bráno podle daného uspořádání. Jinak řečeno, d-regulární halda je až na eventuálně poslední vrstvu úplný d-ární strom a poslední vrstva může být neúplná - zaplňuje se zleva doprava. Příklad 2regulární haldy je na obrázku 2.1. Jak uvedeme v následujícím tvrzení, tento typ hald má logaritmickou výšku: 11

Věta 3. [25] Výška d-regulární haldy s n vrcholy je nejvýše ⌈logd (n(d − 1) + 1)⌉ − 1. 2

8

17

19

7

10

30

9

12

15

Obrázek 2.1: Příklad 2-regulární haldy Nyní popíšeme algoritmy běžných operací pro práci s touto haldou. Základní operace UP a DOWN se používají ve většině algoritmů pro ostatní operace. Pro odhady složitosti budeme předpokládat, že halda je implementována v poli. Halda se v poli implementuje tak, že se prvky haldy určitým způsobem umístí do pole a indexy prvků v poli budou odpovídat uzlu v haldě následujícím způsobem: kořen bude mít index 0 a pokud máme uzel s indexem i, tak jeho děti budou mít indexy i · d + 1, . . . , i · d + d. Rodič uzlu s indexem i bude mít index ⌊(i − 1)/d⌋. Input: halda H, vrchol v haldy Output: upravená halda H vp ← otec v, pokud neexistuje, konec if key(vp ) > key(v) then vyměň klíče vp a v UP(vp ) end return upravená halda H Algoritmus 2: Operace UP(v) pro d-regulární haldy Výpočet indexu synů nebo rodiče zvládneme v konstantním čase pomocí aritmetických operací - konstanta je různá pro různé d. Operace UP trvá maximálně O(log n), protože hloubka haldy je logaritmická. Operace DOWN trvá O(d log n), protože v každém kroku musíme hledat nejmenšího syna a kroků je O(log n). Protože d je konstanta, celková složitost je O(log n). Na obrázku 2.2 je jako ilustrace provedeno DELETEMIN na haldě z obrázku 2.1. Dvojka se vyjme z haldy a na její místo se dosadí hodnota z posledního uzlu v poslední vrstvě - v tomto případně se jedná o hodnotu 15. Ta se uloží do kořene a zavolá se operace DOWN(kořen), jejíž průběh je naznačen čárkovanými šipkami. 12

Input: halda H, vrchol v haldy Output: upravená halda H vs ← nejmenší ze synů v, pokud neexistuje, konec if key(vs ) < key(v) then vyměň klíče vs a v DOWN(vs ) end return upravená halda H Algoritmus 3: Operace DOWN(v) pro d-regulární haldy

Input: halda H, klíč x vkládaný do haldy Output: upravená halda H v ← nový vrchol v poslední vrstvě (obsazovaný zleva) key(v) ← x UP(v) return upravená halda H Algoritmus 4: Operace INSERT(x) pro d-regulární haldy

Input: halda H Output: upravená halda H r ← kořen haldy H v ← poslední vrchol v poslední vrstvě H, hodnota min. prvku if r 6= v then x ← key(r) key(r) ← key(v), smažeme v z H DOWN(r) return upravená halda H, x else H←∅ return upravená halda H, key(r) end Algoritmus 5: Operace DELETEMIN pro d-regulární haldy

13

15

8

17

19

7

10

9

12

30

Obrázek 2.2: Příklad DELETEMIN(2) na 2-regulární haldě

Input: halda H Output: minimální prvek haldy H v ← kořen H return key(v) Algoritmus 6: Operace MIN pro d-regulární haldy

Input: halda H, uzel v, nová hodnota uzlu x menší než key(v) Output: upravená halda H key(v) ← x UP(v) return upravená halda H Algoritmus 7: Operace DECREASEKEY pro d-regulární haldy

Input: halda H, uzel v, nová hodnota uzlu x větší než key(v) Output: upravená halda H key(v) ← x DOWN(v) return upravená halda H Algoritmus 8: Operace INCREASEKEY pro d-regulární haldy Operace DELETEMIN, INCREASEKEY, DELETE mají časovou složitost O(d log n), protože používají operaci DOWN a operace trvající konstantní čas. Operaci MIN lze 14

Input: halda H, uzel v Output: upravená halda H DECREASEKEY(v,−∞) DELETEMIN return upravená halda H Algoritmus 9: Operace DELETE pro d-regulární haldy

provést v konstantním čase. Ostatní operace (DECREASEKEY a INSERT) mají časovou složitost O(log n), protože používají jen operace trvající konstantní čas nebo operaci UP.

2.2

Binomiální haldy

Nový druh hald definoval Vuillemin ve své publikaci [32] z roku 1978. Motivací pro zavedení těchto hald je bitové sčítání přirozených čísel. Budeme mít pole s ukazateli na stromy, kde index ukazatele v poli bude odpovídat řádu stromu, na který ukazatel ukazuje. Spojením dvou stromů se stejným řádem vznikne strom s řádem o jedna vyšším. Spojování hald je pak analogie bitového sčítání vektorů, kde jednička odpovídá ukazateli na nějaký strom a nula odpovídá ukazateli na prázdný strom. Operace sčítání bitů je analogie spojení dvou stromů. Vkládání prvku do haldy pak je možné chápat jako analogii přičítání jedničky. Definice. Binomiální strom Bi řádu i je zakořeněný strom T s následujícími vlastnostmi: B0 je jediný vrchol a Bi je vrchol s i syny, které jsou stromy B0 , B1 , . . . , Bi−1 .

Obrázek 2.3: Stromy řádu 0,1,2,3 Na obrázku 2.3 jsou stromy řádu 0,1,2,3. Na obrázku 2.4 je zobrazen jeden strom řádu čtyři. Když utrhneme ze stromu Bi poslední podstrom Bi−1 , dostaneme z definice dva stromy řádu i − 1. Z indukce snadno dostaneme, že |Bi | = 2|Bi−1 | = 2i . Stejně 15

snadno se nahlédne, že strom Bi má výšku nejvýše i, tj. nejdelší cesta od kořene k listům má délku i. Haldu s n prvky lze reprezentovat vektorem délky ⌈log2 n⌉ + 1 s ukazateli na jednotlivé stromy, protože strom má exponenciálně mnoho prvků v závislosti na jeho řádu.

Obrázek 2.4: Binomiální strom řádu 4 Definice. Binomiální halda je soubor stromů H = {Bi |i ∈ J }, kde J ⊆ N, J je konečná, a kde každý strom v H má vlastnost haldy. P j 2 prvků. Naopak pro každé n ∈ N platí, Je jasné, že taková halda bude mít j∈J

že binomiální halda s n prvky a zápisem v binární soustavě n =

∞ P

i=0

ai 2i , ai ∈ {0, 1},

je určena množinou J = {i|ai = 1}. Konečnost J je zaručena konečností čísla n. Narozdíl od d- regulární haldy podporuje binomiální halda rychlou operaci MERGE a tato operace tvoří základ pro další operace. Operace INCREASEKEY a DECREASEKEY se provádějí stejně jako v d-regulární haldě. Operace DECREASEKEY má opět složitost O(log n), neboť hloubka každého stromu je logaritmická v závislosti na n, operace INCREASEKEY má složitost O(log2 n), neboť pro strom Bi v každém kroku musíme projít i synů, abychom vybrali minimum, a počet kroků je nejvýše i, takže složitost je O(i2 ). Horní odhad pro i je O(log2 n), tedy celkem bude časová složitost O(log2 n). Existuje alternativní varianta, kde složitost operace bude O(log n) - použití operace DELETE, následná změna hodnoty prvku a poté opětovné vložení do haldy operací INSERT. Předpokládejme, že vstup operace MERGE(H1 , H2 ) je reprezentován poli H1 = U1 , . . . , Uk a H2 = V1 , . . . , Vk , kde Ui , Vi jsou ukazatele na stromy Bi s příslušnými prvky, nebo jsou položky prázdné (Ui = ∅, Vi = ∅), a navíc k je tak velké, že s pomocí pole délky k + 1 se dá reprezentovat binomiální halda s n1 + n2 prvky, stačí vzít k = ⌈log2 (n1 + n2 )⌉ + 1. 16

Spojení dvou stromů stejného řádu budeme značit jako JOIN (Ui , Vi ) a v čase O(1) stromy spojíme do nového stromu o řád většího tak, že strom s větším kořenem připojíme jako syna ke stromu s menším kořenem. Input: halda H1 = U1 , . . . , Uk , halda H2 = V1 , . . . , Vk Output: halda H = W1 , . . . , Wk C←∅ for i = 0, 1, . . . , k do T ← {C, Ui , Vi }, nevkládáme do T prázdné ukazatele switch T do case ∅ Wi ← ∅ endsw case {T1 } Wi ← T 1 , C ← ∅ endsw case {T1 , T2 } Wi ← ∅, C ←JOIN(T1 , T2 ) endsw case {T1 , T2 , T3 } Wi ← T1 , C ←JOIN(T2 , T3 ) endsw endsw end return H Algoritmus 10: Operace MERGE pro binomiální haldy

Složitost operace MERGE je O(log n), kde n je součet velikostí obou hald. Používáme operace trvající konstantní čas ve for cyklu, který má O(log n) iterací. Input: halda H, prvek x Output: halda H ′ v = vrchol, odpovídá B0 key(v) = x H ′ ← MERGE(H, {v}) return H ′ Algoritmus 11: Operace INSERT pro binomiální haldy

Operace MIN má složitost O(log n), avšak pokud se implementuje chytře, pravidelně upravovaným ukazatelem na minimum během aktualizačních operací, tak je složitost O(1). Operace INSERT i DELETEMIN pak běží v čase O(log n). Operace DELETE rovněž poběží v čase O(log n). 17

Input: halda H = U1 , . . . , Uk Output: x, které je minimum, H ′ je upravená halda r ← min{key( kořen Ui )|i = 0, 1, . . . , k, Ui 6= ∅} i

T ← strom Uj vybraný z U1 , . . . , Uk takový, že key( kořen Uj ) = r x ← key( kořen T ) {T0 , T1 , . . . Tj−1 } ← synové T H ′ ← MERGE(H \ T , {T0 , T1 , . . . Tj−1 }) return upravená halda H ′ , prvek x Algoritmus 12: Operace DELETEMIN pro binomiální haldy

Input: halda H = U1 , . . . , Uk Output: x, které je minimum x ← min{key( kořen Ui )|i = 0, 1, . . . , k, Ui 6= ∅} i return x Algoritmus 13: Operace MIN pro binomiální haldy

Input: halda H, ukazatel na vrchol v Output: upravená halda H ′ DECREASEKEY(v,−∞) H ′ ← DELETEMIN return upravená halda H ′ Algoritmus 14: Operace DELETE pro binomiální haldy

2.3

Líná verze binomiální haldy

Chtěli bychom, aby časová složitost (v nejhorším případě) operací INSERT a MERGE byla konstantní, za cenu toho, že časová složitost operace DELETEMIN a MIN bude O(n), avšak jejich amortizovaná časová složitost bude O(log n). Toho docílíme tím, že povolíme výskyt stromů stejného řádu v binomiální haldě. Definice. Líná binomiální halda je konečný soubor stromů {T1 , . . . , Tk } takový, že každý strom Ti má vlasnost haldy a je izomorfní se stromem Bj pro nějaké j ∈ N. Haldu můžeme reprezentovat jako spojový seznam kořenů stromů. Aby byla zachována časová složitost, musíme přidat novou operaci CONSOLIDATE a upravit operace MERGE, MIN a DELETEMIN. Operace CONSOLIDATE zajistí, že ve spojovém seznamu kořenů stromů budou pouze stromy s navzájem různým rankem. Tuto operaci implementujeme pomocí pole velikosti ⌈log2 n⌉ + 1 s ukazateli na stromy. Index v poli bude odpovídat řádu stromu, na který daný ukazatel v poli ukazuje. Postupně budeme odebírat stromy ze spojového seznamu kořenů stromů a budeme je vkládat do pole podle příslušných řádů stromů. Pokud se v poli strom daného řádu už vyskytuje, pomocí operace JOIN 18

tyto dva stromy spojíme v jeden s řádem o jedna větším a operaci vložení do pole opakujeme. Až vložíme všechny stromy ze spojového seznamu do pole, z pole stromy vyjmeme a uděláme z nich nový spojový seznam. Algoritmy pro operace INSERT a DELETE jsou stejné jako u binomiálních hald. Input: halda H = {T1 , . . . , Tk } Output: upravená halda H ′ Vytvoř množiny Oi , i ∈ {1, . . . , ⌈log2 n⌉ + 1}: v Oi budou stromy z H řádu i for i ∈ {1, . . . , ⌈log2 n⌉ + 1} do while |Oi | ≥ 2 do T A , T B ∈ Oi , Oi ← Oi \ {TA , TB }, Oi+1 ← Oi+1 ∪ JOIN (TA , TB ) end end H ′ ← spoj výsledné stromy z množin Oi do spojového seznamu return H ′ Algoritmus 15: Operace CONSOLIDATE pro líné binomiální haldy

Input: halda H1 , halda H2 Output: halda H H ← spoj spojové seznamy z H1 a H2 return H Algoritmus 16: Operace MERGE pro líné binomiální haldy

Input: halda H = U1 , . . . , Uk Output: x, které je minimum, H ′ je upravená halda r ← min{key( kořen Ui )|i = 0, 1, . . . , k, Ui 6= ∅} i

T ← strom Uj vybraný z U1 , . . . , Uk takový, že key( kořen Uj ) = r x ← key( kořen Ui ) {T0 , T1 , . . . Tj−1 } ← synové T H ′ ← MERGE(H \ T , {T0 , T1 , . . . Tj−1 }) CONSOLIDATE H ′ return upravená halda H ′ , prvek x Algoritmus 17: Operace DELETEMIN pro líné binomiální haldy Spojení dvou spojových seznamů zvládneme v konstantním čase, proto operace MERGE a INSERT lze provést v konstantním čase.

19

Input: halda H = U1 , . . . , Uk Output: x, které je minimum x ← min{key( kořen Ui )|i = 0, 1, . . . , k, Ui 6= ∅} i CONSOLIDATE H return x Algoritmus 18: Operace MIN pro líné binomiální haldy

2.4

Fibonacciho haldy

Tento typ hald zavedli M. L. Fredman s R. E. Tarjanem v publikaci [17] jako vylepšení líné verze binomiální haldy. Pro některé aplikace hald, zejména pro grafové algoritmy, jako například Dijkstrův algoritmus [8] nebo algoritmus hledající minimální kostru, se hodí, aby operace INSERT, DECREASEKEY a MERGE mohly být provedeny v konstantním čase, a přitom amortizovaný čas ostatních operací by byl O(log n). Zaplatíme za to tak, že nejhorší složitost operací bude O(n). Definice. Fibonacciho halda je soubor stromů definovaný rekurzivně takto: • ∅ je Fibonacciho halda. • Pokud H je Fibonacciho halda, pak H ′ =INSERT(H, x) je Fibonacciho halda, kde INSERT je provedený algoritmem 20 • Pokud H1 , H2 jsou Finobacciho haldy, pak H ′ =MERGE(H1 , H2 ) je Fibonacciho halda, kde MERGE je provedený algoritmem 19 • Pokud H je neprázdná Fibonacciho halda, pak H ′ =DELETEMIN(H) je Fibonacciho halda, kde DELETEMIN je provedený algoritmem 21. • Pokud H je Fibonacciho halda, v je vrchol v haldě a x < key(v), pak také H ′ =DECREASEKEY(H, v, x) je Fibonacciho halda, kde DECREASEKEY je provedený algoritmem 22. Definice. Nechť H = {T1 , . . . , Tk } je Fibonacciho halda tvořená zakořeněnými stromy T1 , . . . , Tk . Fibonacciho strom T řádu l je takový strom, jehož kořen má právě l synů. Definujme funkci rank : {T1 , . . . , Tk } → N0 , kde rank(Ti ) je řád stromu Ti . Definice. Nechť H = {T1 , . . . , Tk } je Fibonacciho halda tvořená zakořeněnými stromy T1 , . . . , Tk . Pokud vrcholu v ∈ Ti , který není kořen, byl operací DECREASEKEY utržen libovolný podstrom, řekneme, že vrchol v je označený (marked), neboli černý. Dá se ukázat, že počet prvků ve Fibonacciho stromu exponenciálně závisí na jeho řádu. Věta 4. [25] Mějme nějaký strom T řádu i ve Fibonacciho haldě. Pak |T | ≥ Fi+2 , kde Fk je k-tý člen Fibonacciho posloupnosti. 20

√

Prvek Fi Fibonacciho posloupnosti je zezdola omezen φi , kde φ = 1+2 5 je hodnota zlatého řezu, proto Fibonacciho strom má exponenciálně mnoho prvků v závislosti na jeho řádu. Na obrázcích 2.5 a 2.6 jsou nejmenší stromy řádu 0, 1, 2, 3 a 5. Budeme vycházet z binomiálních haldy, ale upravíme některé její operace. Haldu budeme reprezentovat spojovým seznamem kořenů stromů v haldě a řád stromu T budeme zaznamenávat v kořeni tohoto stromu.

Obrázek 2.5: Fibonacciho stromy řádu 0,1,2,3

Obrázek 2.6: Příklad Fibonacciho stromu řádu 5 Input: halda H1 , halda H2 Output: halda H H ← sjednocené seznamy H1 a H2 return H Algoritmus 19: Operace MERGE pro Fibonacciho haldy Jak MERGE, tak INSERT pracují v konstantním čase - amortizovaném i nejhorším. Operaci MIN implementujeme tak, že si vždy pamatujeme ukazatel na nejmenší prvek (o to se postarají jiné operace), tedy také bude pracovat v konstantním čase. While cyklu u algoritmu DELETEMIN se říká konsolidace. Nebudeme ji provádět tak, že budeme hledat dvojice ve spojovém seznamu, protože složitost by byla příliš 21

Input: halda H, prvek x Output: halda H ′ v = vrchol, odpovídá B0 key(v) = x H ′ ← MERGE(H, {v}) return H ′ Algoritmus 20: Operace INSERT pro Fibonacciho haldy

Input: halda H Output: halda H ′ , minimální prvek x T ← strom s minimem, vyjmi ho z H x ← key( kořen T ) syny kořene T přidej do spojového seznamu H while A ∈ H, B ∈ H, rank(A) = rank(B) do C ←JOIN(A, B) H ←MERGE(H \ {A, B}, C) end H′ ← H return upravená halda H ′ , prvek x Algoritmus 21: Operace DELETEMIN pro Fibonacciho haldy

velká, ale alokujeme si pole logaritmické délky, do nějž postupně zařazujeme stromy a spojujeme je operací JOIN s těmi, které už tam jsou. Operace JOIN je stejná jako u binomiálních hald a pracuje v konstantním čase. Na konci pouze převedeme pole opět do spojového seznamu. Input: halda H, uzel v, nová hodnota uzlu x menší než key(v) Output: upravená halda H key(v) ← x if key(v) < key(parent(v)) then CUT(v) end return upravená halda H Algoritmus 22: Operace DECREASEKEY pro Fibonacciho haldy Operace DECREASEKEY má amortizovaný čas O(1) a používá speciální operaci CU T , která odtrhne podstrom reprezentovaný vrcholem v a zařadí ho do spojového seznamu stromů. Zároveň je nutné označit rodiče uzlu v, pokud není kořenem a nebyl odtržen. Pro operaci INCREASE označme syny vrcholu v jako {s1 , . . . , sk }, po této operaci bude vrchol v samostatný v haldě, tedy do haldy bude přidáno minimálně k + 1 nových stromů. 22

Input: halda H, uzel v Output: upravená halda H u ← parent(v) if v není kořen then odeber podstrom s kořenem v a zařaď ho do spojového seznamu haldy if u je označený then odznač u CUT(u) else if u není kořen then označ u end end end return upravená halda H Algoritmus 23: Operace CUT pro Fibonacciho haldy

Input: halda H, uzel v, nová hodnota uzlu x větší než key(v) Output: upravená halda H key(v) ← x if v není list then CUT(v) foreach s ∈ {s1 , . . . , sk } do CUT(s) end end return upravená halda H Algoritmus 24: Operace INCREASEKEY pro Fibonacciho haldy

23

Algoritmus DELETE se provede obdobně jako INCREASEKEY, akorát na konci odebereme strom reprezentující v z haldy. Alternativně lze k implementaci operace DELETE opět využít operace DECREASEKEY a DELETEMIN. V roce 1994 publikovali D. Abuaiadh s J.H. Kingstonem práci [1] v níž se zabývali otázkou optimality Fibonacciho hald a časové složitosti prioritních front jako abstraktní datové struktury. V této publikaci navrhli mírnou modifikaci Fibonacciho hald takovou, že dosahuje optimální časové složitosti za určitých rozumných předpokladů. Výsledky v tomto článku napsané lze shrnout tak, že za určitých rozumných předpokladů existuje posloupnost příkazů n operací INSERT, n operací DELETE, m operací DECREASEKEY a t operací FINDMIN taková, že časová složitost provedení těchto operací na prioritní frontě je Ω(n log t + n + m).

2.5

Párovací haldy

Tento typ hald zavedli M.L. Fredman, R.E. Tarjan a spoluautoři v publikaci [14] v roce 1986. Narozdíl od Fibonacciho haldy je tato halda snadno implementovatelná, což je z hlediska praxe také důležité. Párovací haldu si můžeme představit jako zakořeněný strom s vlastností haldy, ale to není úplně přesné - musel vzniknout jedině pomocí operací párovací haldy. Popíšeme algoritmy pro práci s touto haldou. Input: párovací haldy T1 , T2 Output: nová párovací halda L ← halda s menším klíčem kořene vybraná z {T1 , T2 } H ← halda s větším klíčem kořene vybraná z {T1 , T2 } přidej strom H do seznamu dětí L return L Algoritmus 25: Operace LINK pro párovací haldy

Input: párovací halda H, prvek x Output: párovací halda H ′ v ← vrchol s klíčem x, odpovídá zakořeněnému stromu s jedním vrcholem return H ′ =LINK(H, v) Algoritmus 26: Operace INSERT pro párovací haldy

Input: párovací haldy T1 , T2 Output: nová párovací halda return LINK(T1 ,T2 ) Algoritmus 27: Operace MERGE pro párovací haldy

24

Input: párovací halda H, uzel v, nová hodnota uzlu x menší než key(v) Output: upravená halda H key(v) ← x if v není kořen haldy H then T1 ← H \ {v s podstromem } T2 ← vrchol v se svým podstromem H ← LINK(T1 , T2 ) end return H Algoritmus 28: Operace DECREASEKEY pro párovací haldy

Input: párovací halda H, uzel v v ní obsažený Output: upravená párovací halda T1 ← H \ {v s podstromem } T2 ← vrchol v se svým podstromem return LINK(T1 ,DELETEMIN(T2 )) Algoritmus 29: Operace DELETE pro párovací haldy

Nejsložitější operace u párovacích hald je operace DELETEMIN. Existuje několik přístupů, jak tuto operaci naimplementovat. První přístup zmíněný v práci [14] je následující: napřed odtrhneme kořen, děti kořene seřadíme do dvojic a ty spárujeme. Poté spojujeme spárované stromy od pravé strany k levé operací LINK, až nám vznikne jediný strom. Druhý přístup, v práci [14] označovaný jako tzv. víceprůchodová varianta, je následující: odtrheme kořen a jeho uzly seřadíme do fronty. Dokud fronta obsahuje více než jeden strom, vybereme vždy dva stromy z fronty, tyto spárujeme a zařadíme na začátek fronty. Poté prohlásíme ten jediný zbylý strom ve frontě za výslednou párovací haldu. Ačkoliv není tento přístup z hlediska časové složitosti optimální (amortizovaná časová složitost se zvedne o faktor logloglogloglogn n oproti předchozí variantě), je velmi snadný na implementaci. Input: párovací halda H Output: párovací halda H ′ , minimální prvek x fronta Q ← děti kořene H x ← key( kořen H) while |Q| > 1 do vyber T1 , T2 z konce fronty Q na začátek fronty Q přidej LINK(T1 , T2 ) end H ′ ← jediný prvek Q return upravená halda H ′ , prvek x Algoritmus 30: Operace DELETEMIN pro párovací haldy

25

Z hlediska časové složitosti trvají operace INSERT, MERGE, DECREASEKEY O(1) v nejhorším případě. Operace DELETE a DELETEMIN mají časovou složitost O(n) v nejhorším případě. Analýza amortizované složitosti je pro tuto haldu velmi problematická. V publikaci [14] bylo dokázáno, že všechny operace měnící nějakým způsobem haldu běží v amortizovaném čase O(log n). Autoři vyslovili domněnku, že se párovací halda chová stejně jako Fibonacciho halda - že amortizovaný čas operací DELETEMIN a DELETE je O(log n) a pro všechny jiné operace je konstantní. Tato domněnka byla experimentálně zkoumána v roce 1987 v publikaci [30], kde se autoři domnívali, že tomu tak skutečně je. Dokonce dokázali, že pokud nepoužijeme operaci DECREASEKEY, pak párovací halda se z hlediska amortizované složitosti chová stejně jako Fibonacciho halda. Avšak v roce 1997 publikoval Michael L. Fredman článek [15], ve kterém dokázal, že amortizovaný čas operace DECREASEKEY v párovací haldě není konstantní a později v roce 1999 v článku [16] dokázal, že amortizovaná složitost této operace je vždy Ω(log log n). Horní odhady na amortizovanou složitost operací párovací haldy byly dokázány v publikaci [28] v roce 2005. Ukázalo se tam, že amorizovaná složitost operací DELETEMIN a DELETE je O(log n) a √ amortizovaná složitost všech ostatních operací je nejvýše O(22 log log n ). Zatím nejnovější výsledek je práce A. Elmasryho [11] z roku 2009, který popisuje variantu párovací haldy, dosahující O(1) amortizovaného času pro operaci INSERT, O(log n) amortizovaného času pro operace DELETEMIN a DELETE a konečně O(log log n) amortizovaného času pro operace DECREASEKEY a MERGE, čímž dosáhl pro operaci DECREASEKEY optimální časové složitosti vzhledem k zmíněném dolnímu odhadu Ω(log log n) uvedeném M. L. Fredmanem v publikaci [16]. Na obrázku 2.7 je příklad párovací haldy. 2

6

5

4

9

16

7

14

8

11

3

10

12

15

Obrázek 2.7: Příklad párovací haldy s 15 prvky 26

13

2.6

Thin haldy

Tuto variantu Fibonacciho haldy navrhli H. Kaplan a R. E. Tarjan v roce 2008 a publikovali v [23]. Neformálně řečeno, thin haldu si můžeme představit jako binomiální haldu, jejíž některé uzly mají odebraného syna s nejvyšším řádem. Začneme se základními definicemi, které jsou převzaté z článku [23]. Definice. Thin strom T je zakořeněný strom s vlastností haldy spolu s funkcí r(v) : V (T ) → N0 , kde V (T ) jsou vrcholy stromu T , který má následující vlastnosti: (i) Pro děti uzlu s k dětmi nabývá funkce r postupně hodnot k − 1, k − 2, . . . , 1, 0, počítáno od prvního syna. (ii) Pro uzel v s k dětmi platí, že r(v) ∈ {k, k + 1}. Pokud r(v) = k + 1, řekneme, že daný uzel je tenký, v opačném případě řekneme, že je normální. (iii) Kořen stromu T je normální. Hodnotu funkce r pro daný uzel v ∈ V (T ) budeme nazývat rank a jako rank stromu T budeme označovat rank kořene. Z technických důvodů zadefinujeme r(∅) = −1. Dá se podobným způsobem jako pro Fibonacciho haldy ukázat, že počet uzlů v thin stromě závisí exponenciálně na jeho ranku, jak uvedeme v následujícím lemmatu. Lemma 1. [23] Nechť T je thin strom a v ∈ V (T ), navíc nechť má v přesně k synů. √ 1+ 5 k Pak počet uzlů v podstromě s kořenem ve v je alespoň φ , kde φ = 2 . Nyní můžeme přistoupit k definici thin haldy. Definice. Thin halda je soubor thin stromů. Thin haldu implementujeme jako kruhový spojový seznam kořenů thin stromů v haldě. Velká část operací je stejná jako u Fibonacciho haldy, liší se pouze operace DECREASEKEY. Operaci JOIN zadefinujeme obdobně jako u Fibonacciho hald, na vstupu dostane dva stromy stejného řádu a vyrobí z nich strom s řádem o jedna větším tak, že strom s větším kořenem přidá jako prvního syna ke stromu s menším kořenem. Input: thin halda H1 , thin halda H2 Output: halda H H ← sjednocené seznamy H1 a H2 return H Algoritmus 31: Operace MERGE pro thin haldy Jak MERGE, tak INSERT pracují v konstantním čase - amortizovaném i nejhorším. Operaci MIN implementujeme tak, že si vždy pamatujeme ukazatel na nejmenší prvek, tedy také bude pracovat v konstantním čase. 27

Input: thin halda H, prvek x Output: halda H ′ v = vrchol, odpovídá B0 key(v) = x H ′ ← MERGE(H, {v}) return H ′ Algoritmus 32: Operace INSERT pro thin haldy

Input: thin halda H Output: thin halda H ′ , minimální prvek x T ← strom s minimem, vyjmi ho z H x ← key( kořen T ) syny kořene T udělej normální a přidej je do spojového seznamu H while A ∈ H, B ∈ H, rank(A) = rank(B) do C ←JOIN(A, B) H ←MERGE(H \ {A, B}, C) end H′ ← H return upravená halda H ′ , prvek x Algoritmus 33: Operace DELETEMIN pro thin haldy

While cyklu u algoritmu DELETEMIN se říká konsolidace. Nebudeme ji provádět tak, že budeme hledat dvojice ve spojovém seznamu, protože složitost by byla příliš velká, ale alokujeme si pole logaritmické délky, do nějž postupně zařazujeme stromy a spojujeme je operací JOIN s těmi, které už tam jsou. Operace JOIN pracuje v konstantním čase. Nový strom přidáváme jako prvního syna starého stromu. Na konci pouze převedeme pole opět do spojového seznamu. Operaci DELETE implementujeme jako zavolání DECREASEKEY na daný prvek s parametrem −∞ a následné zavolání DELETEMIN. Nejkomplikovanější je operace DECREASEKEY, která se dost liší od klasického postupu v Fibonacciho haldě.

28

Input: thin halda H, uzel v, nová hodnota uzlu x menší než key(v) Output: upravená thin halda H key(v) ← x if key(v) < key(parent(v)) then if v je kořen then oprav ukazatel na nejmenší kořen, případně nedělej nic, pokud je starý kořen pořád menší, než hodnota uzlu v else w ← levý sourozenec v nebo rodič v, pokud v nemá levého sourozence odejmi v ze seznamu dětí, udělej uzel v normální a zařaď ho do spojového seznamu kořenů REPAIR(w) end else return H end Algoritmus 34: Operace DECREASEKEY pro thin haldy

O těchto haldách byl dokázán následující výsledek: Věta 5. [23] Pokud začínáme s prázdnou haldou a spustíme libovolnou posloupnost operací nad touto haldou, pak amortizovaná složitost operací DELETE a DELETEMIN je O(log n) a amortizovaná složitost všech ostatních operací je O(1). 1

3

5

2

6 4

7

Obrázek 2.8: Příklad thin haldy

29

Input: thin halda H, uzel α Output: upravená thin halda H if α je kořen s k dětmi a má rank k + 1 (kořen je tenký) then r(α) ← k else β ← pravý sourozenec α, nebo ∅, pokud neexistuje if r(α) = r(β) + 2 then if α je tenký uzel then r(α) ← r(α) − 1 γ ← levý sourozenec α nebo rodič vrcholu α, pokud je α prvním dítětem REPAIR(γ) else δ ← první dítě uzlu α vlož δ mezi α a β α je nyní tenký uzel end else η ← první syn α nebo ∅, pokud neexistuje if r(α) = r(η) + 3 then r(α) ← r(α) − 2 ρ ← levý sourozenec α, nebo rodič α, pokud neexistuje vyjmi α ze seznamu dětí a dej ho do seznamu kořenů REPAIR(ρ) end end end return H Algoritmus 35: Operace REPAIR pro thin haldy

30

2.7

Thick haldy

Tato varianta Fibonacciho hald vznikla mírnou modifikací thin hald a je popsána rovněž v publikaci [23]. Zatímco u thin hald jsme z binomiálních stromů podstromy odebírali, zde je budeme naopak přidávat. Velká výhoda tohoto typu hald je ta, že má obvykle nižší výšku podstromů než ostatní varianty Fibonacciho hald a i než Fibonacciho halda samotná. Nyní uvedeme definice převzaté opět z článku [23]. Definice. Thick strom T je zakořeněný strom s vlastností haldy spolu s funkcí r(v) : V (T ) → N0 , kde V (T ) jsou vrcholy stromu T , který má následující vlastnosti: (i) Pro děti uzlu s k dětmi nabývá funkce r postupně hodnot k − 1, k − 2, . . . , 1, 0, počítáno od prvního syna. (ii) Pro uzel v s k dětmi platí, že r(v) ∈ {k, k − 1}. Pokud r(v) = k − 1, řekneme, že daný uzel je tlustý, v opačném případě řekneme, že je normální. (iii) Kořen stromu T je normální. Hodnotu funkce r pro daný uzel v ∈ V (T ) budeme nazývat rank a jako rank stromu T budeme označovat rank kořene. Z technických důvodů zadefinujeme r(∅) = −1. Jednoduše se dá dokázat, že počet vrcholů v thick stromě exponenciálně závisí na jeho ranku. Intuitivně, binomiální strom řádu k má 2k vrcholů a pokud k tomuto stromu něco přidáme, počet prvků můžeme jedině zvýšit. Lemma 2. [23] Nechť T je thick strom a v ∈ V (T ), navíc nechť r(v) = k. Pak počet uzlů v podstromě s kořenem ve v je alespoň 2k . Nyní můžeme přistoupit k definici thick haldy. Definice. Thick halda je soubor thick stromů. Thick haldu implementujeme jako kruhový spojový seznam kořenů thick stromů v haldě. Velká část operací je stejná jako u Fibonacciho haldy, liší se pouze operace DECREASEKEY. Operace JOIN je stejná jako u thin haldy. Input: thick halda H1 , thick halda H2 Output: halda H H ← sjednocené seznamy H1 a H2 return H Algoritmus 36: Operace MERGE pro thick haldy

31

Input: thick halda H, prvek x Output: halda H ′ v = vrchol, odpovídá B0 key(v) = x H ′ ← MERGE(H, {v}) return H ′ Algoritmus 37: Operace INSERT pro thick haldy

Jak MERGE, tak INSERT pracují v konstantním čase - amortizovaném i nejhorším. Operaci MIN implementujeme tak, že si vždy pamatujeme ukazatel na nejmenší prvek, tedy také bude pracovat v konstantním čase. Input: thick halda H Output: thick halda H ′ , minimální prvek x T ← strom s minimem, vyjmi ho z H x ← key( kořen T ) syny kořene T udělej normální a přidej je do spojového seznamu H while A ∈ H, B ∈ H, rank(A) = rank(B) do C ←JOIN(A, B) H ←MERGE(H \ {A, B}, C) end H′ ← H return x Algoritmus 38: Operace DELETEMIN pro thick haldy

Input: thick halda H, uzel v, nová hodnota uzlu x Output: upravená thick halda H key(v) ← x if key(v) < key(parent(v)) then if v je kořen then oprav ukazatel na nejmenší kořen, případně nedělej nic, pokud je starý kořen pořád menší, než hodnota uzlu v else w ← levý sourozenec v nebo rodič v, pokud v nemá levého sourozence odejmi v ze seznamu dětí, udělej uzel v normální a zařaď ho do spojového seznamu kořenů REPAIR(w) end else return H end Algoritmus 39: Operace DECREASEKEY pro thick haldy

32

Input: thick halda H, uzel α Output: upravená thick halda H β ← pravý sourozenec α, nebo ∅, pokud neexistuje γ ← levý sourozenec α, nebo rodič α, pokud sourozenec neexistuje δ ← první syn α, nebo ∅, pokud neexistuje if r(α) = r(β) + 2 then if α je normální then r(α) ← r(α) − 1 REPAIR(γ) else ξ ← první syn α odejmi α syna ξ, r(α) ← r(α) − 1 zařaď ξ před α end else if r(α) = r(δ) + 2 then r(α) ← r(α) − 1 if α není kořen then if β je normální then vyjmi α i β ze seznamu dětí a zařaď uzel η =JOIN(α, β) na jejich původní místo r(η) = r(η) − 1 REPAIR(γ) else r(β) ← r(β) + 1 zaměň α a β v seznamu dětí end end end end Algoritmus 40: Operace REPAIR pro thick haldy

33

2.8

Další typy hald

Výčet hald popsaný v této kapitole samozřejmě není vyčerpávající, do podrobna byly popsány pouze haldy, na kterých se bude provádět měření. Pro srovnání uvedeme ještě některé další druhy hald. Poměrně starý druh haldy, zvaný leftist halda, byl zaveden Clarkem A. Cranem v roce 1972 [7]. Zatímco původní prvně zavedené d-regulární haldy nemohou rychle provádět operaci MERGE, leftist halda umí tuto operaci v čase O(log n), kde n značí celkový počet prvků v obou haldách. Velmi zajímavým typem hald jsou tzv. relaxované haldy zavedené J.R. Driscollem se spoluautory v roce 1988 v publikaci [10]. Tento typ hald je založen na binomiálních stromech s tím, že vlastnost haldy může být za určitých okolností porušena (tj. rodič má menší hodnotu klíče, než syn). Shrneme výsledky uvedené v publikaci [10]. Operace DECREASEKEY má konstantní amortizovanou časovou složitost, operace DELETEMIN má amortizovanou časovou složitost O(log n). Ve zmíněné publikaci je rovněž uvedena aplikace této haldy v paralelních algoritmech: Věta 6. [10]. Nechť G je graf s n vrcholy a m hranami, m ≥ n log n a mějme výpočetní stroj typu EREW PRAM s p ≤ m/(n log n) procesory, pak (a) Minimální kostru je možné nalézt v čase O(m/p). (b) Problém nalezení párování maximální váhy ve vážených bipartitních grafech lze vyřešit v čase O(nm/p). Nalezení nejkratší cesty mezi každými dvěma vrcholy (i s hranami se zápornou váhou) lze vyřešit ve stejném čase. (c) Tok minimální váhy (viz. [2]) lze nalézt v čase O(m2 log n/p). Všechny tyto algoritmy mají prostorovou složitost O(m). V roce 2006 publikoval A. Elmasry a spoluautoři v publikaci [13] variantu relaxované haldy optimalizovanou na co nejmenší počet porovnání. Počet porovnání je pro operace INSERT, MIN a DECREASEKEY konstantní, pro operaci DELETEMIN je O(log n). V roce 2010 publikoval A. Elmasry publikaci [12], ve které zavedl nový typ haldy - Violation haldu, která má stejnou amortizovanou složitost jako Fibonacciho halda. Ve zmíněné publikaci se předpokládá, že v praxi bude tato halda rychlejší než Fibonacciho halda. Violation haldy narozdíl od Fibonacciho hald nepotřebují ukazatele na rodiče, avšak operace jsou trochu náročnější na implementaci. V roce 1998 zavedl G.S. Brodal a spoluautoři v publikaci [5] nový druh haldy nazvali ji Brodal halda. Jde o velmi komplikovanou datovou strukturu, mimo jiné proto, protože umožňuje provést paralelně INSERT - vložit posloupnost prvků setříděných podle klíče a DECREASEKEY - opět snížit hodnotu posloupnosti prvků setříděných podle klíče. Tato halda nalezla uplatnění hlavně v grafových algoritmech, uvedeme například následující výsledek: Věta 7. [5]. Paralelní Dijkstrův algoritmus (viz. tamtéž) běží (a) v čase O(n) na stroji CREW PRAM, 34

(b) v čase O(n log(m/n)) na stroji EREW PRAM. Zatím všechny zde uvedené haldy pracovaly „přesněÿ, tzn. vždy garantovaly správnost operací, například, že vždy vybereme to správné minimum z haldy. V roce 2000 přišel B. Chazelle s datovou strukturou zvanou soft halda [6], která pracuje pouze „přibližněÿ - nemusí vrátit správné minimum v εn případech, kde 0 < ε ≤ 1/2 je pevně zvolené, avšak získáme tím výrazné zrychlení všech operací - všechny operace kromě INSERT pracují v amortizovaném konstantním čase, operace INSERT pracuje v čase O(log 1ε ). Uvedeme některé příklady použití této haldy z publikace [6]: (a) S pomocí této datové struktury lze najít minimální kostru v souvislém grafu v čase O(mα(m, n)), kde m je počet hran, n je počet vrcholů a α je známá Ackermannova funkce. (b) Dalším příkladem je dynamické udržování percentilů. Soft haldy podporují dotazy na percentily v konstantním amortizovaném čase. (c) Soft haldy lze použít k počítání mediánu v lineárním čase, uvedeme ideu algoritmu: napřed vložíme všech n prvků do soft haldy s ε = 1/3. Poté zavoláme n/3 DELETEMIN. Největší číslo smazané z haldy bude mít rank někde mezi n/3 a 2n/3. Můžeme smazat n/3 prvků a na zbylé provést rekurzi. Počet prvků v rekurzi tvoří geometrickou řadu, která má konečný součet a tak je výsledný čas lineární. (d) Soft halda umožňuje tzv. přibližné třídění. Pro dané ε umí setřídit danou posloupnost různých prvků tak, že počet inverzí ve výsledné posloupnosti je nejvýše εn2 . (e) V silnější verzi přibližného třídění se pořadí každého prvku liší od správného pořadí nejvýše o εn, což soft halda také umožňuje. V roce 2009 nalezli H. Kaplan a U. Zwick efektivnější implementaci soft hald a publikovali ji v [24]. V zmíněné publikaci je rovněž snažší analýza tohoto typu hald.

2.9

Algoritmy využívající haldy

Haldy využívá celá řada algoritmů. V této práci si uvedeme algoritmy, pomocí nichž budeme měřit výkonnost jednotlivých druhů hald. Jako první si popíšeme algoritmus HEAPSORT. Je to třídící algoritmus využívající haldu, který má časovou složitost O(n log n), ale není stabilní. Tento algoritmus zavedl J. Williams v publikaci [34] v roce 1964. Původně tento algoritmus využíval pouze binární haldu, nicméně nic nebrání tomu použít libovolný typ haldy. Algoritmus HEAPSORT je popsán algoritmem 41. Pokud používáme binární (nebo obecně regulární) haldu, existuje velice efektivní implementace haldy v poli, haldu tak není nutné reprezentovat explicitně, což neplatí u jiných druhů hald. Navíc pro tento typ haldy existuje efektivnější způsob výstavby haldy, než postupné přidávání prvků (v lineárním čase). 35

Input: nesetříděná posloupnost a1 , . . . , an Output: setříděná posloupnost b1 , . . . , bn H ← prázdná halda for i = 1, . . . , n do INSERT(H, ai ) end for i = 1, . . . , n do bi ← DELETEMIN(H) end Algoritmus 41: Heapsort

Před popsáním dalšího algoritmu je nutné zadefinovat několik pojmů z teorie grafů. Budeme pracovat s orientovanými grafy, které mají hrany ohodnocené nezáporným reálným číslem. Ohodnocení hran chápeme jako vzdálenost mezi vrcholy. Definice. Nechť G = (V, E) je orientovaný graf s ohodnocenými hranami, kde funkce w : E → R+ je ohodnocením těchto hran. Posloupnost vrcholů v1 , . . . , vk nazveme cestou, pokud jsou vrcholy po dvou různé, k ≥ 2 a vi vi+1 ∈ E pro 1 ≤ i < k. Délkou cesty rozumíme součet w(vi vi+1 ) pro 1 ≤ i < k. Takový orientovaným grafem s ohodnocenými hranami můžeme reprezentovat například mapy měst, kde vrcholy budou města a hrany silnice mezi městy (obousměrné silnice ovšem musíme reprezentovat dvěma hranami), ohodnocení bude vzdálenost mezi městy. Odtud plyne přirozený optimalizační problém, jak se dostat z určitého města do jakéhokoliv jiného města po co nejkratší cestě. Algoritmus, který si zde uvedeme, je známý Dijkstrův algoritmus hledání minimální cesty v grafu z jednoho zdroje do všech ostatních vrcholů [8], který řeší optimalizační problém definovaný výše. Složitost Dijkstrova algoritmu závisí na druhu haldy, který tento algoritmus používá. Nechť má graf m hran a n vrcholů. Pokud použijeme haldu, která umí operaci DECREASEKEY v amortizovaně konstantním čase, tak dosáhneme složitosti O(m + n log n). V opačném případě dosáhneme složitosti O((m + n) · log n). Pokud vůbec nepoužijeme haldu, tak se obecně dá říct, že algoritmus bude mít složitost O(m · α + n · β), kde α je složitost operace snížení hodnoty klíče a β je složitost operace vyjmutí minima ze seznamu klíčů. Dijkstrův algoritmus je popsán v algoritmu 42. V haldě jsou vrcholy uspořádány podle aktuální vzdálenosti od počátečního vrcholu. Pole dist indexované vrcholy obsahuje po skončení algoritmu délku nejkratší cesty od počátečního vrcholu do daného vrcholu, pole prev obsahuje předcházející uzel na této nejkratší cestě.

36

Input: orientovaný graf G = (V, E), vrchol t ∈ V , w : E → R+ ohodnocení hran Output: nejkratší cesty uložené v dist a prev foreach v ∈ V do dist(v)← +∞ prev(v)← ∅ end dist(t)← 0 H ← halda se všemi vrcholy V while H 6= ∅ do u ← DELETEMIN(H) if dist(u) = ∞ then ukonči algoritmus a vydej dist a prev jako výstup else foreach (u, v) ∈ E do p ← dist(u)+w((u, v)) if p < dist(v) then dist(v)← p prev(v)← u DECREASEKEY(H,v, p) end end end end Algoritmus 42: Dijkstrův algoritmus.

37

38

3. Vyhodnocování měření a základy statistiky V této kapitole si probereme základní poznatky z pravděpodobnosti a matematické statistiky nutné k pochopení měření testů a také metodu vyhodnocování měření. K matematické statistice existuje celá řada odborných publikací. Při zpracovávání této kapitoly jsem použil knihu [3] a úvod do teorie pravděpodobnosti, tvořící předpoklad či základ matematické statistiky, byl zpracován podle knížky [35] a učebního textu J. Walranda [33].

3.1

Úvod do teorie pravděpodobnosti

Teorie pravděpodobnosti je důležitá partie matematiky, z níž vychází matematická statistika. Ukážeme si tzv. Kolmogorovovu definici pravděpodobnosti, která vychází z teorie míry. Více poznatků o teorii míry lze nalézt v publikaci [27], z níž pochází následující dvě definice: Definice. σ-algebra A je systém množin nad neprázdnou množinou Ω takový, že 1. ∅ ∈ A, Ω ∈ A 2. P, Q ∈ A ⇒ Ω \ P ∈ A, P ∩ Q ∈ A 3. Qi ∈ A, i ∈ N ⇒

∞ S

i=1

Qi ∈ A

Definice. Nechť A je σ-algebra. Definujeme funkci µ : A → [0, +∞) takovou, že 1. µ(∅) = 0 2. Když Qi ∈ A, i ∈ N, Qi jsou po dvou disjunktní, pak µ(∪i∈N Qi ) = Pak takovou funkci µ nazveme mírou na A.

∞ P

µ(Qi ).

i=1

Definice. Pravděpodobností prostor je trojice (Ω, A, P ), kde Ω je neprázdná množina, A je σ-algebra a P je pravděpodobnostní míra (míra, kde P (Ω) = 1) na A. Pokud to bude z kontextu jasné, budeme vynechávat Ω a A v definici pravděpodobnostního prostoru. Prvku J ∈ A budeme říkat náhodný jev, a P [J] budeme označovat jako pravděpodobnost jevu J. Definice. Nechť A, B jsou nějaké náhodné jevy a P [B] > 0. Pak označme podmíněnou pravděpodobnost jevu A za předpokladu jevu B jako P [A|B]. Tato pravděpodobnost se spočte pomocí vzorce P [A|B] =

P [A ∩ B] . P [B]

39

(3.1)

Definice. Řekneme, že dva jevy A, B jsou nezávislé, pokud platí P [A ∩ B] = P [A] · P [B].

(3.2)

Nezávislost dvou jevů si můžeme představit tak, že pravděpodobnost jednoho jevu nezávisí na tom, zda nastane druhý jev a naopak. Definici lze přirozeným způsobem rozšířit na větší počet jevů. Zadefinujeme velmi důležitý pojem náhodné veličiny na pravděpodobnostním prostoru a jejího rozdělení. Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor. Nechť (R, B) je dvojice, kde R je reálná množina a B je systém borelovských množin nad R. Nechť X(ω) : Ω → R je měřitelná funkce. Pak X(ω) je náhodná veličina. Obvykle se značí pouze jako X. Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor. Nechť X je libovolná náhodná veličina na tomto prostoru a M ⊆ R je měřitelná množina. Zaveďme pravděpodobnostní míru Q(M ) = P [X −1 (M )]. Tato míra se nazývá rozdělení náhodné veličiny X. Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor. Nechť X je libovolná náhodná veličina na tomto prostoru. Funkci F (x) : R → [0, 1] definovanou jako F (x) = P [X < x]

(3.3)

nazveme distribuční funkcí náhodné veličiny X. Definice. Nechť F (x) je distribuční funkce nějaké náhodné veličiny X. Pokud existuje taková nezáporná funkce f (x), že platí F (x) =

Zx

f (t)dt,

(3.4)

−∞

pak tuto funkci f (x) nazveme hustotou náhodné veličiny X. Definice. Nechť X1 , . . . , Xk jsou náhodné veličiny definované na stejném pravděpodobnostním prostoru. Řekneme, že tyto náhodné veličiny jsou nezávislé, pokud pro každou k-tici reálných čísel c1 , . . . , ck platí, že náhodné jevy Ai = {Xi < ci } pro 1 ≤ i ≤ k jsou nezávislé. Pokud nějaká distribuční funkce F (x) je funkce skoků (tj. nabývá pouze konečně nebo spočetně mnoha různých hodnot), pak o příslušné náhodné veličině říkáme, že má diskrétní rozdělení. Náhodná veličina s diskrétním rozdělením nabývá pouze konečně nebo spočetně mnoha hodnot. Jako
příklad můžeme uvést tzv. binomické rozdělení s parametry n, p, kde P [X = k] = nk pk (1−p)n−k . Zápis X ∼ Bi(n, p) značí, že náhodná veličina X má binomické rozdělení s danými parametry. Pro diskrétní náhodné veličiny je množina Ω v definici pravděpodobnostního prostoru konečná či spočetná. Pokud naopak k nějaké náhodné veličině Y existuje hustota fY (x), pak mluvíme o spojité náhodné veličině. 40

Prakticky nejdůležitější ze všech pravděpodobnostních rozdělení je tzv. normální rozdělení, které je zároveň příkladem spojitého rozdělení. Distribuční funkci normálního rozdělení nelze vyjádřit pomocí základních funkcí, ale jen jako neurčitý integrál hustoty. Definice. Nechť µ ∈ R a σ 2 > 0. Pak definujeme normální rozdělení s paramery µ a σ 2 pomocí následující hustoty: (x−µ)2 1 f (x) = √ e− 2σ2 σ 2π

(3.5)

Distribuční funkci tohoto rozdělení s parametry µ = 0 a σ 2 = 1 označme Φ. Jednou z nejdůležitějších vět teorie pravděpodobnosti je tzv. Centrální limitní věta. Uvedeme si zde jednu její verzi, přičemž definice střední hodnoty a rozptylu jsou v následujícím odstavci. Věta 8. Nechť X1 , . . . , Xn je náhodný výběr z libovolného rozdělení, které má konečnou střední hodnotu a rozptyl. Nechť E[Xi ] = µ a Var[Xi ] = σ 2 . Zaveďme náhodnou veličinu Sn takto: 1 Sn = (X1 + X2 + . . . + Xn ). (3.6) n Pak pro opravdu  velká n má náhodná veličina Sn asymptoticky normální rozdělení σ2 Sn ∼ N µ, n .

3.2

Základy matematické statistiky

V této sekci uvedeme některé základní poznatky z matematické statistiky, které jsou nutné pro pochopení metody vyhodnocení naměřených výsledků. Budeme pracovat s diskrétními i spojitými náhodnými veličinami. Začneme s definicí střední hodnoty (anglicky „expected valueÿ). Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor. Nechť X je náhodná veličina s diskrétním rozdělením na tomto prostoru. Pak definujeme X X(ω) · P [ω]. (3.7) E[X] = ω∈Ω

(3.8)

Této hodnotě říkáme střední hodnota náhodné veličiny X. Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor. Nechť Y je náhodná veličina se spojitým rozdělením na tomto prostoru s hustotou fY (x). Pak definujeme Z E[Y ] = x · fY (x)dx. (3.9) R

Této hodnotě říkáme střední hodnota náhodné veličiny Y . 41

Na základě definice střední hodnoty se definují tzv. k-tý obecný moment a k-tý centrální moment. Definice. Nechť (Ω, A, P ) je pravděpodobnostní prostor a X je nějaká náhodná veličina na tomto prostoru. Pak definujeme k-tý obecný moment µ′k jako µ′k = E[X k ], dále definujeme k-tý centrální moment µk jako   µk = E (X − E[X])k ,

(3.10)

(3.11)

a to pouze v případě, že příslušné střední hodnoty existují a jsou konečné. Centrálnímu momentu µ2 se říká rozptyl náhodné veličiny X a obvykle se označuje σ 2 nebo √ Var[X]. Veličině σ = µ2 se říká směrodatná odchylka. Rozptyl i směrodatná odchylka jsou vždy nezáporné a v případě nekonstantní náhodné veličiny i kladné. Pro ilustraci definujeme níže ještě další dva méně často používané momenty. Definice. Nechť X je nějaká libovolná náhodná veličina. Pak definujeme šikmost α3 = µ3 /σ 3 a špičatost α4 = µ4 /σ 4 . Šikmost udává, jak je rozdělení náhodné veličiny šikmé vzhledem ke střední hodnotě. Při záporné šikmosti jsou odlehlejší hodnoty nalevo od střední hodnoty, při kladné naopak. Špičatost udává tvar daného rozdělení, tj. jak je „špičatéÿ. Někdy se od špičatosti ještě odečte konstanta 3, aby se to dalo porovnávat se špičatostí normálního rozdělení, které má špičatost právě 3 (resp. 0 po odečtení). Nyní uvedeme některé další důležité charakteristiky náhodné veličiny. Definice. Mějme rozdělení s distribuční funkcí F (x). Číslo m nazveme mediánem tohoto rozdělení, pokud platí, že 1 , x→m 2 1 lim+ F (x) ≥ . x→m 2 lim− F (x) ≤

(3.12) (3.13)

Pro spojité rozdělení alternativně platí, že F (m) = 21 , protože F (x) je spojitá funkce. Takové číslo nemusí být určeno jednoznačně. Definice. Mějme náhodnou veličinu X s diskrétním rozdělením a náhodnou veličinu Y se spojitým rozdělením a hustotou fY (x). U diskrétní náhodné veličiny X definujeme modus jako reálné číslo c, pro které platí, že P [X = c] ≥ P [X = xi ], ∀i,

(3.14)

kde xi jsou příslušné možné hodnoty daného diskrétního rozdělení. Obdobně definujeme modus veličiny Y jako reálné číslo cˆ , pro které platí, že f (ˆ c) ≥ f (x), ∀x ∈ R. Obdobně jako u mediánu, ani modus nemusí být určen jednoznačně. 42

(3.15)

Zavedeme si pro měření důležitý pojem náhodného výběru. Při měření nějaké veličiny získáváme naměřené hodnoty. Tyto hodnoty umístíme do vektoru (x1 , . . . , xn ), který je realizací nějakého vektoru náhodných veličin (X1 , . . . , Xn ). Definice. Náhodný výběr je n-tice náhodných veličin (X1 , . . . , Xn ), kde tyto veličiny pocházejí ze stejného rozdělení a jsou nezávislé. Někdy se náhodný výběr značí bez závorek, tj. X1 , . . . , Xn . Statistika je nějaká funkce náhodného výběru. Náhodný výběr tedy odpovídá nějakému měření. V praxi však vždy neplatí, že měření jsou na sobě nezávislá a že pochází všechna ze stejného rozdělení, tuto skutečnost je nutné brát v potaz. Níže uvedeme důležité statistiky náhodného výběru. Definice. Nechť X1 , . . . , Xn je nějaký náhodný výběr. Pak zavádíme následující statistiky: • Výběrový průměr x je definován jako n

1X x= Xi . n i=1

(3.16)

• Výběrový rozptyl s2 je definován jako n

1X s = (Xi − x)2 . n i=1 2

(3.17)

• Pro k ≥ 1 k-tý výběrový obecný moment Mk′ a k-tý výběrový centrální moment Mk jsou definovány jako n

Mk′

1X k = X , n i=1 i

(3.18)

n

Mk =

1X (Xi − x)k n i=1

(3.19)

• Výběrový koeficient šikmosti A3 a výběrový koeficient špičatosti A4 jsou definovány jako A3 = A4

M3 3/2

M2 M4 = −3 M22

(3.20) (3.21)

• Označme X(1) , . . . , X(n) setříděnou posloupnost prvků X1 , . . . , Xn . Pak definujeme výběrový medián x˜ jako ( X((n+1)/2) , pro n liché (3.22) x˜ = X(n/2) +X(n/2+1) , pro n sudé 2 43

Další pojem, který zde uvedeme, je tzv. interval spolehlivosti. Je to druh intervalového odhadu, který udává míru spolehlivosti nějakého odhadu (například průměru). Definice. Nechť X1 , . . . , Xn je náhodný výběr z libovolného rozdělení. Nechť θ je nějaký parametr rozdělení tohoto náhodného výběru. Nechť α ∈ (0, 1) a θ1 , θ2 jsou nějaké dvě statistiky. Nechť dále platí, že P [θ ∈ (θ1 , θ2 )] = 1 − α,

(3.23)

pak řekneme, že interval (θ1 , θ2 ) je interval spolehlivosti (popř. konfidenční interval) se spolehlivostí 1 − α, nebo 100 · (1 − α)%-tní interval spolehlivosti. Jako příklad intervalu spolehlivosti uvedeme interval spolehlivosti pro střední hodnotu normálního rozdělení. Buď dána posloupnost x1 , . . . , xn , která je náhodným výběrem z normálního rozdělení s nám neznámou střední hodnotou a se známým rozptylem σ 2 . Dále předpokládejme, že chceme interval spolehlivosti se spolehlivostí 1−α pro α ∈ (0, 1). Dále označme x jako výběrový průměr z posloupnosti x1 , . . . , xn . Pak interval spolehlivosti pro střední hodnotu tohoto normálního rozdělení bude     σ  α σ −1 α −1 · √ ,x + Φ ·√ x−Φ 1− 2 2 n n

(3.24)

Všechny hodnoty v tomto intervalu buď známe nebo je lze spočítat z posloupnosti x1 , . . . , xn . Hodnotu funkce Φ−1 lze aproximovat pomocí tabulek nebo nějakého numerického algoritmu.

3.3

Diagramy

Diagramy tvoří důležitou část statistické analýzy. Jde z nich poznat mnoho věcí, protože člověk je stále lepší než počítač v hledání zajímavých souvislostí v diagramech. Jednotlivé diagramy si ukážeme na příkladě náhodného výběru X, který vznikl sloučením 200 hodnot z rozdělení N (0, 0.2) a 200 hodnot z rozdělení N (1, 0.2). Hodnoty generované z těchto dvou rozdělení se ve výsledné posloupnosti pravidelně střídají. Prvním druhem diagramů jsou tzv. „run sequenceÿ diagramy. Na x-ové ose je pořadí vybrané veličiny a na y-ové ose je hodnota veličiny. Příklad takového diagramu pro veličinu X je na obrázku 3.1. Z tohoto typu diagramů lze například vyčíst, zda ze začátku něco neovlivňovalo měřenou hodnotu, či o jaký typ rozdělení jde. Z obrázku je rovnou vidět, že se nejedná o jedno normální rozdělení, protože jsou v něm vidět dva „shlukyÿ. 44

0.5 −0.5

0.0

X

1.0

1.5

Run Sequence Diagram of X

0

100

200

300

400

Index

Obrázek 3.1: Příklad „run sequenceÿ diagramu

Důležitým typem diagramů jsou tzv. histogramy. Na x-ové ose mají hodnoty změřené veličiny, na y-ové ose jsou četnosti výskytů těchto hodnot. Z histogramů lze vyčíst mnoho informací, například povahu rozdělení, zda je rozdělení nějak zkosené a další podobné údaje. Příklad histogramu je uveden na obrázku 3.2. Na tomto histogramu jsou velmi dobře vidět dvě normální rozdělení posunutá o jedničku, ze kterých byla vygenerována náhodná posloupnost. Histogramy úzce souvisí s hustotou daného rozdělení. Pokud četnosti v histogramu nahradíme relativními četnostmi (tj. vydělíme je celkovým počtem pozorování), tak obrys histogramu se přibližuje hustotě tím více, čím více hodnot jsme naměřili a čím menší máme rozsah jednotlivých polí. 45

15 10 0

5

Frequency

20

Histogram of X

−0.5

0.0

0.5

1.0

1.5

X

Obrázek 3.2: Příklad histogramu

Dalším typem diagramů jsou tzv. lag diagramy. Tyto diagramy souvisí s autokorelací tím způsobem, že porovnávají veličinu X s její zpožděnou verzí, kde na tento diagram jsou vyneseny body (Xi , Xi+k ), hodnota k určuje zpoždění. Z tohoto typu diagramů se dá vyzkoumat závislost na předchozích hodnotách, případně určit, že hodnoty jsou na sobě závislé. Příklad takového lag diagramu je na obrázku 3.3. Na obrázku jsou patrné dva shluky, je tam tedy jistě nějaká autokorelace. Pokud vidíme na lag diagramu jen rovnoměrně rozložené body, pak je autokorelace patrně nízká nebo žádná. 46

0.5 −0.5

0.0

X

1.0

1.5

Lag Plot of X

−1.0

−0.5

0.0

0.5

1.0

1.5

2.0

lag 1

Obrázek 3.3: Příklad lag diagramu Obdobným typem diagramů jako lag diagramy jsou acf diagramy. Na vodorovné ose jsou zobrazeny jednotlivé lagy, na svislé jsou zobrazeny korelace nezpožděných a zpožděných hodnot o dané k. Příklad takového grafu je na obrázku 3.4. Ukazuje na silnou korelaci, přičemž pro sudé hodnoty je tato korelace kladná a pro liché záporná. To odpovídá způsobu, jakým byly hodnoty náhodné veličiny generovány.

0.0 −0.5

ACF

0.5

1.0

Series X

0

5

10

15

20

25

Lag

Obrázek 3.4: Příklad acf diagramu

3.4

Měření a vyhodnocení naměřených dat

K problematice měření výkonnosti počítačových systémů existuje celá řada publikací, například knihy [26] a [20]. Při zpracování tohoto tématu jsem vycházel z přednášky RNDr. Tomáše Kalibery, Ph.D, [22]. Výkonnost datové struktury je možné chápat několika způsoby. Může jít například o dobu provedení operace nad danou datovou strukturou, počet přístupů do paměti, počet výpadků cache, počet provedených strojových instrukcí, nebo v případě databází počet přístupů na disk při operaci 47

prováděné nad danou datovou strukturou. Výkonnost datové struktury je ovlivněna celou řadou faktorů, které je nutné brát v potaz. Jedná se například o • HW konfiguraci daného počítače - procesor, paměť, rychlost komponent, rychlost odezvy, firmware apod., • Operační systém - vnitřní stav operačního systému, umístění datové struktury v operační paměti, kvalitu a druh operačního systému, počet spuštěných úloh, stav cache u disků, popř. procesorů a jinde, • Verzi systémových knihoven, jejich možnosti, • Kvalitu kompilátoru programu s datovou strukturou, zda se jedná o nativní kód1 , či zda se jedná o kód prováděný nějakým virtuálním strojem (JVM, .NET) a kvalitu tohoto stroje, typ správy paměti programu, zda má program tzv. garbage collector2 , • Interakci uživatele s počítačem, interakce jiných počítačů v síti, pokud je počítač k síti připojen, • Aktivity systémových služeb a stále běžících programů, jako například různé antivirové programy. • Pokud je datová struktura nějakým způsobem měřena, tak toto měření rovněž ovlivňuje výkonnost datové struktury. Nyní si zadefinujeme, co je to metrika, jaké jsou různé druhy metrik, které metriky pro nás budou důležité a jak se metriky měří. Definice. Metrika je ukazatel nějaké zajímavé vlastnosti měřeného objektu. Metrikou může být například v případě síťové aplikace odezva od serveru, u jiných aplikací například doba běhu, počet výpadků stránky apod. V podstatě se jedná o ty ukazatele, které jsme uvedli výše u výkonnosti datové struktury. Zcela jiným typem metriky je například spolehlivost systému a střední doba mezi dvěma výpadky nějakého systému. Ve zmíněné přednášce [22] byly uvedeny některé vlastnosti, které by dobrá metrika určitě měla mít. Níže jsou tyto vlastnosti sepsány. 1. Linearita vzhledem k výkonnosti systému. Tedy pokud se zlepší daná metrika dvakrát, doba běhu aplikace by se měla zmenšit také dvakrát. 2. Spolehlivost. Pokud je aplikace A lepší podle dané metriky než aplikace B, pak by měla být skutečně aplikace A lepší než aplikace B. 3. Opakovatelnost. Při opakování měření metriky dostáváme (alespoň přibližně) stejné údaje. 1 2

kód spustitelný na procesoru daného počítače forma automatické správy paměti, nepoužívaná paměť se automaticky uvolní k dalšímu použití

48

4. Daná metrika by měla jít jednoduše a správně změřit. 5. Metrika by měla mít stejný význam na různých systémech, případně na různých konfiguracích jednoho systému. 6. Nezávislost. Aplikace, popř. systém by neměl být speciálně upraven tak, aby ukazoval lepší výsledky na dané metrice. V této práci budeme používat jako metriku dobu běhu nějaké operace, popř. posloupnosti operací na dané datové struktuře. Tato metrika splňuje část požadavků na dobrou metriku. Je lineární, spolehlivá, má stejný význam na různých systémech (jde o čas) a je nezávislá. Bohužel je občas obtížné ji změřit opravdu přesně (je nutné použít tzv. realtime časovače, které často využívají speciálních instrukcí procesoru ke zjištění počtu tiků - někdy ani ty nejsou dost přesné) a je problém s opakovatelností. Díky vlivu nedeterministických událostí systému (například přepnutí kontextu, výpadek stránky, apod.) není měření ani opakovatelné. Z výše uvedených důvodů je nutné tuto metriku analyzovat pomocí statistických metod. Předpokládejme, že provádíme vždy n měření, výsledkem je vektor náhodných proměnných (X1 , . . . , Xn ), resp. nějaká jeho realizace naměřenými hodnotami. Z rozumných důvodů se předpokládá, že všechna Xi pochází ze stejného pravděpodobnostního rozdělení a jsou náhodná a nezávislá. Z tohoto vektoru se pak pokusíme aproximovat naši metriku. Může se jednat o výběrový průměr tohoto vektoru, medián, nebo ještě nějaké další jiné veličiny. Obvykle se ještě uvádí intervaly spolehlivosti tohoto údaje. U počítačových aplikací navíc bývají pravděpodobnostní rozdělení často skosená doprava, takže nebývá vhodné používat např. výběrový průměr.

49

50

4. Benchmarky a výsledky měření V této kapitole popíšeme provedené testy hald. K testování je vhodné použít nejnovější počítač, proto byla zvolena následující testovací sestava: Procesor: Paměť: Grafická karta: Operační systém:

Intel Core i7-2600 Quad Core, 3.4 GHz, 8 MB cache 8192 MB, 1600 MHz, DDR3 VGA ASUS ENGTX560, 1024 MB GDDR5 Windows 7 Professional 64 bit Czech

Budeme měřit celkovou dobu běhu jednotlivých algoritmů, protože je to z hlediska praxe nejvhodnější - obvykle nás zajímá, jak rychle program dokončí svou práci. Proto nebyla vybrána různá další kritéria - například počet porovnání nebo doba běhu jedné operace, výpadky stránek cache apod. K interpretaci výsledků budeme využívat medián celkové doby běhu, protože je robustnější, než průměr - je méně ovlivňován odlehlými měřeními.

4.1

Implementace datových struktur

Správná implementace je podmínkou kvalitního provedení měření výkonu každé aplikace. Jako implementační jazyk byl zvolen jazyk C++ z důvodu vysokého výkonu, kompilace do strojového kódu a manuální správy paměti. Automatická správa paměti a interpretovaný kód by mohli nepříznivě ovlivnit výkon datových struktur. Datové struktury byly napsány jako šablony v tomto jazyce, aby se dosáhlo variability použití. K implementaci bylo využito vývojové prostředí Microsoft Visual Studio 2010.

Haldy U každé haldy je možné definovat porovnávací objekt, podle kterého se porovnávají klíče, typ objektu, který je uložen v haldě, a objekt, který manipuluje s ukazateli na prvek haldy. U d-regulárních hald je rovněž možné zadat regularitu haldy. Každá halda má implementované běžné operace, jako vložení nového prvku, smazání prvku v haldě a operace snížení hodnoty klíče. Implementace každé haldy rovněž obsahuje metodu, která zkontroluje integritu haldy, tj. zda se jedná o korektní haldu daného typu. Regulární haldy byly implementovány klasickým způsobem ve zvětšujícím se poli. Ukazatel na rodiče a na prvního syna se snadno spočítá definovanou funkcí, která dostane ukazatel na aktuální uzel. Polem je zde myšlen speciální objekt, který umí zvětšovat i zmenšovat svoji velikost, umí přistoupit na položku dle indexu v konstantím čase a sám si spravuje svoji paměť. Kvůli možnému problému s časovou náročností alokace paměti si zbylé haldy spravují paměť s prvky samy pomocí určeného spravovacího objektu, který umí v konstantním čase provést alokaci i dealokaci paměti. Fibonacciho haldy mají prvky 51

reprezentovány objektem, který obsahuje vlastní data daného prvku a dále ukazatele na rodiče, levého i pravého sourozence a první dítě daného prvku. Implementace algoritmů je provedena přímočaře podle teoretické verze, byly implementovány dvě verze uložení kořenových stromů, první je kruhový spojový seznam, druhý je pole se spojovými seznamy stromů se stejným rankem. Z výkonnostních důvodů je maximální počet prvků v haldě omezen na cca 200 milionů prvků. Párovací halda byla implementována jako multipass varianta této haldy, každý prvek má kromě dat odkaz na rodiče, na levého a pravého sourozence a na nejstarší dítě. Thick a thin halda byly implementovány přesně podle teoretického popisu algoritmů. Prvek haldy kromě dat obsahuje ukazatel na rodiče/levého sourozence, na pravého sourozence a ukazatel na první dítě.

Testy korektnosti Za účelem ověření korektnosti implementace hald byla v jazyce C++ napsána aplikace test heap, která ověřuje, zda daná halda je korektní z hlediska definice. Testy se dělí na simple a advanced. Jednoduchý (simple) test otestuje, zda algoritmus heapsort s danou haldou opravdu třídí a otestuje také minimum dané haldy a některé další jednoduché vlastnosti. Rozšířený (advanced) test pokrývá většinu scénářů a při každé operaci s haldou kontroluje korektnost haldy. Testovací aplikace je napsána jako konzolová aplikace - při benchmarcích se korektnost haldy netestuje.

Benchmarky Byly implementovány celkem 4 benchmarky měřící rychlost daných hald. Každý benchmark provede předem specifikovaný počet měření naprázdno (aby se omezil vliv nežádoucího efektu prvního spuštění) a poté provede daný předem specifikovaný počet měření, jehož výsledky zapíše do souborů. Měření se provádí pomocí funkce QueryPerformanceCounter, zanedbává se režijní zátěž volání této funkce, předpokládá se, že je tato zátěž velmi malá. Měření se poté vyhodnotí přiloženými speciálními skripty pro statistický programovací jazyk R. Vygenerují se grafy a XML soubor se statistikami pro jednotlivá měření. Tento XML soubor obsahuje například medián, průměr, rozptyl, šikmost a špičatost pro jednotlivá měření. Tento XML soubor je také vstupním souborem pro program BenchmarkEvaluate.exe, který zpracuje dané výsledky do jednoho PDF souboru.

4.2

Benchmark - budování haldy

Tento benchmark měří dobu, než se vybuduje daná halda, tj. než se vloží všechny prvky z náhodné permutace do této haldy a následně se provede konsolidace (pokud je u daného druhu haldy definována). Test je parametrizován velikostí permutace, počtem měření, počtem nezaznamenaných měření, semínkem náhodného generátoru a jménem výstupní složky. Pracuje tak, že si zvolí pevně danou posloupnost permutací a tu zkusí spustit na každou haldu napřed naprázdno (podle parametru počtu 52

nezaznamenaných měření) a pak výsledky zaznamená do příslušného souboru (počet výsledků je parametr počet měření). Poté vypíše údaje informačního charakteru do speciálního textového souboru. Měření se provádí při zvýšene prioritě, aby se minimalizoval vliv ostatních aplikací na měření. Měření probíhalo od velikosti 50000 prvků do 5000000 prvků, v krocích po 50000 do 1000000 prvků, poté byl krok 100000 prvků. Výsledky měření jsou na obrázku 4.1. Metrikou jsou zde mediány časů jednotlivých měření. 450000

2-regular 5-regular Fibonacci Pairing Thick Thin

400000 350000 Čas [µs]

300000 250000 200000 150000 100000 50000 0

0

0.5

1 1.5 2 2.5 3 3.5 4 Počet vložených prvků (miliony)

4.5

5

Obrázek 4.1: Měření - budování haldy. Jak je patrné z obrázku 4.1, výsledky dopadly zajímavě. Nejrychlejší byly párovací halda a 5-regulární halda. 5-regulární haldy mají obecně menší výšku, než 2-regulární, proto je rychlejší operace UP u 5-regulární, než u 2-regulární. Párovací halda je zřejmě tak rychlá proto, protože operace LINK této haldy je velice rychlá. Poté následuje 2-regulární halda, která je také velmi rychlá. Trochu pomalejší jsou thick a thin haldy, jejichž čas je přibližně totožný. Je tomu tak proto, protože se nevyužívaly pokročilejší operace jako například DECREASEKEY, které by měly vliv na strukturu haldy (v haldách se vyskytovaly pouze normální uzly). Jako nejpomalejší se ukázala Fibonacciho halda, u níž to ale není tak překvapivé, protože se předpokládalo, že má velké konstanty u časové složitosti. Fibonacciho, thick i thin haldy si průběžně upravují ukazatel na nejmenší prvek - zde je další zpomalení. Za povšimnutí stojí „zubÿ, který leží na křivkách mezi 3.5 a 4 miliony prvky. Je možné, že jde například o vliv cache pamětí procesoru. Vypočtené mediány jsou na přiloženém CD v adresáři benchmark/heapbuild v souboru result medians.txt. V tomtéž adresáři je také soubor measurement.xml, který obsahuje podrobné údaje o provedených měřeních a také další statistické ukazatele jednotlivých měření, jako je například rozptyl, šikmost, špičatost a další. Každý podadresář v adresáři benchmark/heapbuild obsahuje naměřené hodnoty jednotlivých měření, soubor s informacemi o měření a diagramy vyrobené z tohoto měření. 53

4.3

Benchmark - heapsort

Tento benchmark měří dobu, po kterou běží heapsort s použitím dané haldy (včetně doby výstavby haldy), tj. než se setřídí všechny prvky z náhodné permutace. Test je parametrizován velikostí permutace, počtem měření, počtem nezaznamenaných měření, semínkem náhodného generátoru a jménem výstupní složky. Pracuje tak, že si zvolí pevně danou posloupnost permutací a napřed naprázdno spustí algoritmus heapsort tolikrát, kolik bylo specifikováno v příslušném parametru. Poté spustí algoritmus heapsort a výsledky zaznamená do příslušného souboru (počet spuštění je parametr počet měření). Pak vypíše údaje informačního charakteru do speciálního textového souboru. Opět se měření provádí při zvýšene prioritě, aby se minimalizoval vliv ostatních aplikací na měření. Měření probíhalo od velikosti 50000 prvků do 5000000 prvků, v krocích po 50000 do 1000000 prvků, poté byl krok 100000 prvků. Výsledky měření jsou na obrázku 4.2. Opět jsou zde metrikou mediány naměřených časů. 30000

2-regular 5-regular Fibonacci Pairing Thick Thin

25000

Čas [ms]

20000 15000 10000 5000 0

0

0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 Počet prvků (miliony)

Obrázek 4.2: Měření - algoritmus heapsort. Jak je vidět na obrázku 4.2, nejlépe třídila 5-regulární halda, skoro stejně rychlá byla 2-regulární halda. Tyto dvě haldy třídily oproti ostatním velice rychle. Rozdíl mezi 2-regulární a 5-regulární haldou se snížil zřejmě proto, protože u 5-regulární haldy byla výhoda rychlého INSERTU kompenzována nevýhodou pomalejší operace DELETEMIN. Protože počet operací INSERT a DELETEMIN je stejný a o rychlosti operace INSERT už máme informace z předchozího experimentu, můžeme tento benchmark považovat za ilustraci toho, jak rychlá je operace DELETEMIN. Po regulárních haldách byly nejrychlejší thin a thick halda, obě byly skoro stejně rychlé, opět zřejmě proto, protože se nepoužívaly operace jako například DECREASEKEY, které by měnily strukturu stromů jinak, než operace INSERT a DELETEMIN. Za těmito dvěma haldami následuje Fibonacciho halda, která byla podle očekávání pomalá. Překvapilo však, že nejpomalejší byla párovací halda. Pro párovací haldu je 54

tedy zřejmě nejpomalejší operace DELETEMIN. Otázkou je, do jaké míry je tento výsledek ovlivněn použitým způsobem párování. Podobně jako v předešlém případě, vypočtené mediány jsou na přiloženém CD v adresáři benchmark/heapsort v souboru result medians.txt. V tomtéž adresáři je také soubor measurement.xml, který obsahuje podrobné údaje o provedených měřeních a také další statistické ukazatele jednotlivých měření, jako je například rozptyl, šikmost, špičatost a další. Každý podadresář v adresáři benchmark/heapsort obsahuje naměřené hodnoty jednotlivých měření, soubor s informacemi o měření a diagramy vyrobené z tohoto měření.

4.4

Benchmark - Dijkstrův algoritmus

Tento test spouští Dijkstrův algoritmus nad zadanými grafy. Grafy použité v tomto benchmarku jsou získány z reálných map ze zdroje [9]. Benchmark očekává vstup v tomto formátu definovaném tamtéž. Pro účely Dijkstrova algoritmu je použití jiných grafů, například náhodných, nevhodné, protože se často Dijkstrův algoritmus spouští nad reálnými daty. Benchmarková aplikace dostane na vstupu jméno souboru s grafem, počet měřených spuštění a počet měření naprázdno, semínko náhodného generátoru a jméno složky, do které se zapíší výsledky. Benchmark si na začátku definuje posloupnost vrcholů tohoto grafu, tyto vrcholy bude brát jako startovací vrcholy Dijkstrova algoritmu. Pro každou haldu se napřed spustí předem definovaný počet běhů naprázdno, pak proběhne parametrem programu definovaný počet spuštění a měření Dijkstrova algoritmu pro danou haldu. Výsledky se zapisují do souboru v parametrem definovaném adresáři. Při běhu Dijkstrova algoritmu se provádí operace DELETEMIN tolikrát, kolik je v grafu vrcholů a operace DECREASEKEY nejvýše tolikrát, kolik je v grafu hran. Čím hustší je graf, tím více se používá operace DECREASEKEY. Budeme používat rovinné grafy (reálné mapy), které mají lineárně hran v počtu vrcholů, proto zde budeme mít průměrné 2x až 3x tolik hran, co vrcholů. 55

700 600 Čas [ms]

500 400 300 200 100 0

2-reg

5-reg

Fib Pairing Thick Typ haldy

Thin

Obrázek 4.3: Měření - Dijkstrův algoritmus na graf USA-road-d.BAY.gr Z menších grafů byl otestován graf mapy okolí zátoky San Franciska. Tento graf má 321,270 vrcholů a 800,172 hran. Výsledky spuštění Dijkstrova algoritmu jsou na obrázku 4.3. Nejrychlejší byly regulární haldy. O trochu pomalejší byla párovací halda, která se ukázala poměrně efektivní narozdíl od heapsortu. Fibonacciho halda byla nejpomalejší, což nebylo překvapivé, protože se předpokládalo, že má velké konstanty v asymptotické složitosti jednotlivých algoritmů. Thick halda byla rychlejší než Fibonacciho i Thin halda, domnívám se, že je tomu tak proto, protože thick halda má obvykle nižší výšku, než thin halda. 2500

Čas [ms]

2000 1500 1000 500 0

2-reg

5-reg

Fib Pairing Thick Typ haldy

Thin

Obrázek 4.4: Měření - Dijkstrův algoritmus na graf USA-road-d.FLA.gr Další testovaný graf byl graf mapy Floridy. Tento graf má 1,070,376 vrcholů a 2,712,798 hran. Mediány časů naměřených při spuštění Dijkstrova algoritmu na tento 56

graf jsou na obrázku 4.4. Tento graf je podobný grafu 4.3, pouze s tím rozdílem, že párovací halda předstihla 2-regulární haldu. Párovací halda se tedy zdá být dost vhodná na grafové algoritmy, jako je například Dijkstrův algoritmus. Nejpomalejší halda byla opět Fibonacciho halda, následovaná thin a thick haldou. Thick halda byla rychlejší, než thin a Fibonacciho, opět se domnívám, že je tomu tak proto, protože má menší výšku stromů. Nejrychlejší byla 5-regulární halda, byla rychlejší i než 2-regulární, zřejmě má menší asymptotické konstanty u složitosti.

12 10

Čas [s]

8 6 4 2 0

2-reg

5-reg

Fib Pairing Thick Typ haldy

Thin

Obrázek 4.5: Měření - Dijkstrův algoritmus na graf USA-road-d.E.gr

Z kategorie středních grafů byl testován graf východu Spojených Států Amerických s 3,598,623 vrcholy a 8,778,114 hranami. Graf mediánů časů spuštění Dijkstrova algoritmu pro jednotlivé haldy je na obrázku 4.5. Jak je z tohoto obrázku i z předchozích obrázků patrné, grafy sledují jistý vzor, neboť pořadí jednotlivých hald dle doby běhu testu se nijak zvlášť nemění. U Fibonacciho, thick a thin haldy se začíná snižovat odstup od ostatních druhů hald, patrně se začíná projevovat konstantní amortizovaná složitost operace DECREASEKEY. Pořadí hald dle doby běhu je stejné, jako u grafu mapy Floridy (viz. obrázek 4.4). 57

70 60

Čas [s]

50 40 30 20 10 0

2-reg

5-reg

Fib Pairing Thick Typ haldy

Thin

Obrázek 4.6: Měření - Dijkstrův algoritmus na graf USA-road-d.CTR.gr

Největší graf, který se vešel do paměti, je graf centrální oblasti Spojených Států Amerických, který je v souboru USA-road-d.CTR.gr. Tento graf má 14,081,816 vrcholů a 34,292,496 hran. Mediány časů běhů Dijkstrova algoritmu jednotlivých hald jsou na obrázku 4.6. Jak je z tohoto grafu vidět, mírně se snižuje poměr mezi nejrychlejší a nejpomalejší haldou. Pořadí hald je stejné, jako u předchozích dvou měření. Nejrychlejší byla opět 5-regulární halda, následovaná párovací a 2-regulární haldou. Pokud se podíváme na všechny čtyři výsledky v této sekci, zjistíme, že párovací halda se ocitla opět mezi nejrychlejšími haldami. Je pravděpodobné, že je tomu tak proto, protože se provádělo mnoho operací DECREASEKEY, které umí párovací halda provést velice rychle. Tento vliv lze pozorovat i u 5-regulární haldy, u které byla operace DECREASEKEY rychlejší, protože 5-regulární halda má menší výšku, než 2-regulární. Pro hustší grafy by se tento jev patrně ještě více zvýšil. Vypočtené mediány jsou na přiloženém CD v adresáři benchmark/dijkstra v několika souborech. V souboru USA-road-d.BAY.TXT jsou uloženy mediány testů provedených na graf USA-road-d.BAY.gr. V souboru USA-road-d.FLA.TXT jsou uloženy mediány testů provedených na graf uložený v souboru USA-road-d.FLA.gr. V souboru USA-road-d.E.TXT jsou uloženy mediány testů provedených na graf uložený v souboru USA-road-d.E.gr. V posledním souboru USA-road-d.CTR.TXT jsou uloženy mediány testů provedených na graf uložený v souboru USA-road-d.CTR.gr. V tomtéž adresáři je také soubor measurement.xml, který obsahuje podrobné údaje o provedených měřeních a také další statistické ukazatele jednotlivých měření, jako je například rozptyl, šikmost, špičatost a další. Každý podadresář v adresáři benchmark/dijkstra obsahuje naměřené hodnoty jednotlivých měření, soubor s informacemi o měření a diagramy vyrobené z tohoto měření. 58

4.5

Benchmark - heapsequence

Tento benchmark slouží k měření rychlosti provedení posloupnosti operací INSERT, DELETEMIN a DECREASEKEY při určitém daném naplnění haldy. Parametry programu jsou velikost počáteční haldy, než se spustí měřená sekvence operací, dále velikost měřené sekvence operací, počet měření a počet spuštění naprázdno, než se začne měřit, inicializace náhodného generátoru a jméno adresáře, do kterého se budou zapisovat naměřené hodnoty. Každá z operací INSERT, DELETEMIN a DECREASEKEY je do měřené sekvence operací zařazována s pravděpodobností 1/3. Jako délka měřené posloupnosti operací byla zvolena konstanta 100000. Měřená posloupnost se generuje pomocí náhodného generátoru a jednotlivé posloupnosti jsou pro každou haldu stejné. 1600000

2-regular 5-regular Fibonacci Pairing Thick Thin

1400000

Čas [µs]

1200000 1000000 800000 600000 400000 200000 0

0

0.5 1 1.5 2 2.5 3 3.5 4 4.5 Počáteční počet prvků v haldě [miliony]

5

Obrázek 4.7: Měření - Posloupnost 100000 operací Na obrázku 4.7 jsou mediány jednotlivých měření pro posloupnost 100000 operací INSERT, DECREASEKEY a DELETEMIN. Jak je z tohoto obrázku vidět, úplně propadla párovací halda, zřejmě není vhodná pro tento druh práce. Nejlepší se ukázala být 5-regulární halda následovaná 2-regulární haldou. O trochu horší byla thin halda. Narozdíl od Dijkstrova algoritmu, zde je thick halda horší než Fibonacciho i než thin halda. Je možné, že je to tím, že nejde o reálnou aplikaci, jako například Dijkstrův algoritmus spuštěný na mapy, ale o umělou náhodně vygenerovanou posloupnost operací. Zajímavé by bylo měnit poměr zastoupení jednotlivých operací. Podobně jako v předešlém případě, vypočtené mediány jsou na přiloženém CD v adresáři benchmark/heapsequence v souboru result medians.txt. V tomtéž adresáři je také soubor measurement.xml, který obsahuje podrobné údaje o provedených měřeních a také další statistické ukazatele jednotlivých měření, jako je například rozptyl, šikmost, špičatost a další. Každý podadresář v adresáři benchmark/heapsequence obsahuje naměřené hodnoty jednotlivých měření, soubor s informacemi o měření a diagramy vyrobené z tohoto měření. 59

60

5. Závěr Varianty hald byly otestovány na několika benchmarcích. Thick a thin haldy se ukázaly jako kvalitní alternativa k Fibonacciho haldám, ačkoliv někdy nedosahovaly takového výkonu jako například regulární haldy. Při použití v třídícím algoritmu heapsort vykazovaly thick a thin haldy vyšší výkon než Fibonacciho, ale nižší než regulární haldy, obdobně se ukázaly výsledky budování haldy. Při použití na reálný grafový problém (hledání nejkratších cest v mapách pomocí Dijkstrova algoritmu) se opět thick a thin haldy ukázaly lepší než Fibonacciho, avšak horší než regulární haldy. V posledním testu - testování posloupnosti operací spuštěné na haldu s předem danou velikostí - se trochu změnilo pořadí. Thick halda byla horší, než Fibonacciho a thin haldy, opět nejlepší byly regulární haldy. Co se týče párovací haldy, někdy byla výrazně lepší než thin, thick a Fibonacciho haldy (viz. testy Dijkstrova algoritmu), někdy byla výrazně horší (například při třídění heapsortem a testování posloupnosti operací). Testy prokázaly, že thin a thick haldy jsou většinou lepší než Fibonacciho haldy, proto je doporučuji jako alternativu Fibonacciho haldy. Hlavní přínos práce spočívá v porovnání thin a thick hald s Fibonacciho haldou, tyto dvě haldy jsou poměrně nové datové struktury a zatím o nich nebylo publikováno příliš výsledků.

5.1

Další výzkum

Existuje celá řada způsobů, jak pokračovat ve výzkumu navazujícím na tuto práci. Je možné přidat další typy hald, experimentovat s některými standardními implementacemi hald, jako je například implementace binární haldy v C++ v knihovně STL. Zejména by bylo zajímavé porovnat některé další varianty párovací haldy, zda jsou lepší, či horší, než thin a thick haldy. Rovněž by bylo zajímavé rozšířit testy na více scénářů. U benchmarku heapsequence by se mohly změnit pravděpodobnosti jednotlivých operací, zejména operace DECREASEKEY by mohla mít větší pravděpodobnost. Dalším rozšířením by bylo testování více druhů grafů v benchmarku s Dijkstrovým algoritmem. Mohly by se použít v tomto benchmarku husté grafy, náhodně generované grafy, možností je zde velmi mnoho. Pro benchmarky byla zvolena omezená sada testovacích algoritmů, zde je tedy také mnoho možností, jak pokračovat ve výzkumu. Mohly by se napsat benchmarky měřící nějaké další grafové algoritmy, jako například algoritmus nalezení minimální kostry grafu.

61

62

Dodatek - Obsah CD CD přiložené k diplomové práci obsahuje naměřené výsledky, zdrojové soubory k programu a vlastní text této diplomové práce ve formátu PDF. Nejprve popíšeme soubory náležející k naměřeným výsledkům. benchmark benchmark/heapbuild benchmark/heapsort benchmark/dijkstra benchmark/heapsequence benchmark/*/measurement.xml benchmark/*/output.pdf

Adresář s výsledky testů a testovacími programy. Adresář pro benchmark heapbuild. Adresář pro benchmark heapsort. Adresář pro benchmark dijkstra. Adresář pro benchmark heapsequence. XML soubor s výsledky a spočtenými statistikami. PDF soubor s vygenerovanými diagramy.

Dále každý ze čtyř podadresářů adresáře benchmark obsahuje testovací aplikaci, vyhodnocovací aplikaci a podadresáře s jednotlivými testy. Adresáře s jednotlivými testy obsahují vlastní naměřená data, diagramy ve formátu EPS a soubor readme.txt, který obsahuje informativní údaje o naměřeném testu. Nyní popíšeme strukturu zdrojových souborů a adresářů. Adresář se zdrojovými soubory. Adresář se zdrojovými soubory benchmarku dijkstra. source/benchmark heap build Adresář se zdrojovými soubory benchmarku heapbuild. source/benchmark heapsort Adresář se zdrojovými soubory benchmarku heapsort. source/benchmark heapsequence Adresář se zdrojovými soubory benchmarku heapsequence. source/bin Adresář s výslednými binárními soubory. source/common Adresář se společnými soubory. source/libheap Adresář se zdrojovými soubory hald. source/text Adresář se zdrojovým textem práce. source source/benchmark dijkstra

Adresář source obsahuje také soubor libheap.sln, což je projekt pro Microsoft Visual Studio 2010 zastřešující zdrojové kódy. Konečně adresář text obsahuje soubor diplomka.pdf, což je soubor s textem této práce.

63

64

Seznam obrázků 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8

Příklad 2-regulární haldy . . . . . . . . . . . . Příklad DELETEMIN(2) na 2-regulární haldě Stromy řádu 0,1,2,3 . . . . . . . . . . . . . . . Binomiální strom řádu 4 . . . . . . . . . . . . Fibonacciho stromy řádu 0,1,2,3 . . . . . . . . Příklad Fibonacciho stromu řádu 5 . . . . . . Příklad párovací haldy s 15 prvky . . . . . . . Příklad thin haldy . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

12 14 15 16 21 21 26 29

3.1 3.2 3.3 3.4

Příklad Příklad Příklad Příklad

„run sequenceÿ histogramu . . lag diagramu . acf diagramu .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

45 46 47 47

4.1 4.2 4.3 4.4 4.5 4.6 4.7

Měření Měření Měření Měření Měření Měření Měření

-

. . . . . . . . . . . . . . . . . . . . . . . . USA-road-d.BAY.gr USA-road-d.FLA.gr USA-road-d.E.gr . . USA-road-d.CTR.gr . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

53 54 56 56 57 58 59

diagramu . . . . . . . . . . . . . . . . . .

. . . .

. . . .

budování haldy. . . . . . . . algoritmus heapsort. . . . . Dijkstrův algoritmus na graf Dijkstrův algoritmus na graf Dijkstrův algoritmus na graf Dijkstrův algoritmus na graf Posloupnost 100000 operací

65

. . . .

. . . .

. . . .

. . . .

. . . .

66

Seznam algoritmů 1

Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

Operace UP(v) pro d-regulární haldy . . . . . . . . Operace DOWN(v) pro d-regulární haldy . . . . . Operace INSERT(x) pro d-regulární haldy . . . . . Operace DELETEMIN pro d-regulární haldy . . . Operace MIN pro d-regulární haldy . . . . . . . . . Operace DECREASEKEY pro d-regulární haldy . Operace INCREASEKEY pro d-regulární haldy . . Operace DELETE pro d-regulární haldy . . . . . . Operace MERGE pro binomiální haldy . . . . . . . Operace INSERT pro binomiální haldy . . . . . . . Operace DELETEMIN pro binomiální haldy . . . Operace MIN pro binomiální haldy . . . . . . . . . Operace DELETE pro binomiální haldy . . . . . . Operace CONSOLIDATE pro líné binomiální haldy Operace MERGE pro líné binomiální haldy . . . . Operace DELETEMIN pro líné binomiální haldy . Operace MIN pro líné binomiální haldy . . . . . . Operace MERGE pro Fibonacciho haldy . . . . . . Operace INSERT pro Fibonacciho haldy . . . . . . Operace DELETEMIN pro Fibonacciho haldy . . . Operace DECREASEKEY pro Fibonacciho haldy . Operace CUT pro Fibonacciho haldy . . . . . . . . Operace INCREASEKEY pro Fibonacciho haldy . Operace LINK pro párovací haldy . . . . . . . . . Operace INSERT pro párovací haldy . . . . . . . . Operace MERGE pro párovací haldy . . . . . . . . Operace DECREASEKEY pro párovací haldy . . . Operace DELETE pro párovací haldy . . . . . . . Operace DELETEMIN pro párovací haldy . . . . . Operace MERGE pro thin haldy . . . . . . . . . . Operace INSERT pro thin haldy . . . . . . . . . . Operace DELETEMIN pro thin haldy . . . . . . . Operace DECREASEKEY pro thin haldy . . . . . Operace REPAIR pro thin haldy . . . . . . . . . . Operace MERGE pro thick haldy . . . . . . . . . . Operace INSERT pro thick haldy . . . . . . . . . . Operace DELETEMIN pro thick haldy . . . . . . . Operace DECREASEKEY pro thick haldy . . . . . Operace REPAIR pro thick haldy . . . . . . . . . . Heapsort . . . . . . . . . . . . . . . . . . . . . . . 67

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 12 13 13 13 14 14 14 15 17 17 18 18 18 19 19 19 20 21 22 22 22 23 23 24 24 24 25 25 25 27 28 28 29 30 31 32 32 32 33 36

42

Dijkstrův algoritmus.

. . . . . . . . . . . . . . . . . . . . . . . . . . .

68

37

Literatura [1] Abuaiadh, D.; Kingston, J. H.: Are Fibonacci Heaps Optimal? In Proceedings of the 5th International Symposium on Algorithms and Computation, ISAAC ’94, London, UK: Springer-Verlag, 1994, ISBN 3-540-58325-4, s. 442–450. URL http://portal.acm.org/citation.cfm?id=646337.688436 [2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, první vydání, Únor 1993, ISBN 9780136175490. [3] Anděl, J.: Základy matematické statistiky. matfyzpress, 2011, ISBN 978-80-7378162-0. [4] Arora, S.; Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4. [5] Brodal, G. S.; Träff, J. L.; Zaroliagis, C. D.: A Parallel Priority Queue with Constant Time Operations. Journal of Parallel and Distributed Computing, ročník 49, č. 1, 1998: s. 4 – 21, ISSN 0743-7315, doi:DOI:10.1006/jpdc.1998.1425. URL http://www.sciencedirect.com/science/article/pii/S0743731598914253 [6] Chazelle, B.: The Soft Heap: An Approximate Priority Queue with Optimal Error Rate. J. ACM, ročník 47, 2000: str. 16. [7] Crane, C. A.: Linear lists and priority queues as balanced binary trees. Dizertační práce, Stanford University, Stanford, CA, USA, 1972, aAI7220697. [8] Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik, ročník 1, 1959: s. 269–271, ISSN 0029-599X, 10.1007/BF01386390. URL http://dx.doi.org/10.1007/BF01386390 [9] Center for Discrete Mathematics & Theoretical Computer Science (2005): 9th DIMACS Implementation Challenge - Shortest Paths. URL http://www.dis.uniroma1.it/~challenge9/download.shtml [10] Driscoll, J. R.; Gabow, H. N.; Shrairman, R.; aj.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM, ročník 31, November 1988: s. 1343–1354, ISSN 0001-0782, doi:http://doi.acm. org/10.1145/50087.50096. URL http://doi.acm.org/10.1145/50087.50096 [11] Elmasry, A.: Pairing Heaps with O(log log n) decrease Cost. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, editace C. Mathieu, 5B, 2009, s. 471–476. [12] Elmasry, A.: The violation heap: a relaxed Fibonacci-like heap. In Proceedings of the 16th annual international conference on Computing and combinatorics, COCOON’10, Berlin, Heidelberg: Springer-Verlag, 2010, ISBN 3-642-14030-0, 69

978-3-642-14030-3, s. 479–488. URL http://portal.acm.org/citation.cfm?id=1886811.1886872 [13] Elmasry, A.; Jensen, C.; Katajainen, J.: Two-tier relaxed heaps. In Proceedings of the 17th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 4288, Springer-Verlag, Springer-Verlag, 2006, s. 308–317. [14] Fredman, M.; Sedgewick, R.; Sleator, D.; aj.: The pairing heap: A new form of self-adjusting heap. Algorithmica, ročník 1, 1986: s. 111–129, ISSN 0178-4617, 10.1007/BF01840439. URL http://dx.doi.org/10.1007/BF01840439 [15] Fredman, M. L.: Pairing Heaps are Sub-optimal. Technická zpráva, Dept. of Computer Science, Rutgers University, 1997. [16] Fredman, M. L.: On the efficiency of pairing heaps and related data structures. J. ACM, ročník 46, July 1999: s. 473–501, ISSN 0004-5411, doi:http://doi.acm. org/10.1145/320211.320214. URL http://doi.acm.org/10.1145/320211.320214 [17] Fredman, M. L.; Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, ročník 34, July 1987: s. 596–615, ISSN 0004-5411, doi:http://doi.acm.org/10.1145/28869.28874. URL http://doi.acm.org/10.1145/28869.28874 [18] Goldreich, O.: Computational Complexity: Cambridge University Press, 2006.

A

Conceptual

Perspective.

[19] Hoare, C. A. R.: Quicksort. The Computer Journal, ročník 5, č. 1, 1962: s. 10– 16, doi:10.1093/comjnl/5.1.10. URL http://comjnl.oxfordjournals.org/content/5/1/10.abstract [20] Jain, R. K.: The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. New York, NY, USA: Wiley/Interscience, první vydání, Duben 1991, ISBN 978-0-471-50336-1. URL http://www.cse.wustl.edu/~{}jain/books/perfbook.htm [21] Johnson, D. B.: Priority queues with update and finding minimum spanning trees. Information Processing Letters, ročník 4, č. 3, 1975: s. 53–57, ISSN 0020-0190, doi:DOI:10.1016/0020-0190(75)90001-0. URL http://www.sciencedirect.com/science/article/pii/0020019075900010 [22] Kalibera, T.: Přednáška Vyhodnocování výkonnosti počítačových systémů. Karlova Univerzita, Matematicko-fyzikální fakulta, Praha, 2010. [23] Kaplan, H.; Tarjan, R. E.: Thin heaps, thick heaps. ACM Trans. Algorithms, ročník 4, March 2008: s. 3:1–3:14, ISSN 1549-6325, doi:http://doi.acm.org/10. 70

1145/1328911.1328914. URL http://doi.acm.org/10.1145/1328911.1328914 [24] Kaplan, H.; Zwick, U.: A simpler implementation and analysis of Chazelle’s soft heaps. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2009, s. 477–485. URL http://portal.acm.org/citation.cfm?id=1496770.1496823 [25] Koubek, V.; Koubková, A.: Datové struktury I. Praha: matfyzpress, 2011, ISBN 978-80-7378-166-8. [26] Lilja, D.: Measuring Computer Performance: A Practitioner’s Guide. Cambridge University Press, 2000. [27] Lukeš, J.; Malý, J.: Measure and Integral. matfyzpress, 2005, ISBN 80-8673268-1. [28] Pettie, S.: Towards a Final Analysis of Pairing Heaps. Foundations of Computer Science, Annual IEEE Symposium on, ročník 0, 2005: s. 174–183, doi:http:// doi.ieeecomputersociety.org/10.1109/SFCS.2005.75. [29] Ramachandran, V.: Lecture 16: Amortized analysis. 2006. URL http://www.cs.utexas.edu/~vlr/s06.357/notes/lec16.pdf [30] Stasko, J. T.; Vitter, J. S.: Pairing heaps: Experiments and Analysis. Communications of the ACM, ročník 30, March 1987: s. 111–129. [31] Tarjan, R. E.: Amortized Computational Complexity. SIAM Journal on Algebraic and Discrete Methods, ročník 6, č. 2, 1985: s. 306–318, doi:10.1137/ 0606031. URL http://link.aip.org/link/?SML/6/306/1 [32] Vuillemin, J.: A data structure for manipulating priority queues. Commun. ACM, ročník 21, April 1978: s. 309–315, ISSN 0001-0782, doi:http://doi.acm. org/10.1145/359460.359478. URL http://doi.acm.org/10.1145/359460.359478 [33] Walrand, J.: Lecture Notes on Probability Theory and Random Processes. University of California, 2004. [34] Williams, J. W. J.: Heapsort: Algorithm 232. Communications of the ACM, ročník 7, č. 6, June 1964: s. 347–348. [35] Zvára, K.; Štěpan, J.: Pravděpodobnost a matematická statistika. matfyzpress, 2006, ISBN 80-86732-71-7.

71

72