Státnice - Informatika - Datové struktury
Tento souhrn slouží pro přípravu k magisterským státnicím. Detailní informace o předmětu hledej na stránkách Datové struktury I a Datové struktury II.
[edit] Rozsah látky
Seznam oficiálních státnicových otázek:
- Stromové vyhledávací struktury: binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty. Hašování: řešení kolizí, univerzální hašování, perfektní hašování. Mapování datových struktur do stránek vnější paměti počítače. Třídění ve vnitřní a vnější paměti.
(Co ubylo a teď to na této stránce najdete "navíc": Možnosti dynamizace jednotlivých datových struktur. Časová složitost algoritmů vyjádřená v počtu I/O operací.)
[edit] Stromové vyhledávací struktury
[edit] Binární stromy a jejich vyvažování
- wen:Binary search tree
- wen:Self-balancing binary search tree (AVL stromy, červenočerné stromy)
[edit] R-B stromy
- nejefektivnější variantou vyvážených binárních stromů
- narozdíl od AVL jim stačí pouze 1 bit na uložení stavu uzlu (červená/černá)
- DELETE volá maximálně 2x rotaci nebo 1x rotaci a 1x dvojitou rotaci (AVL až log|S|) - při tom ale může projít celou cestu až ke kořeni!
- INSERT = maximálně 1x rotaci nebo 1x dvojitou rotaci - při tom ale může projít celou cestu až ke kořeni!
R-B stromy lze obecně definovat různými ekvivalentními definicemi, jedna z nich je:
- Barva vrcholu je buď červená, nebo černá
- Cesta do všech vrcholů, které jsou buď listem a nebo mají jednoho potomka je stejně dlouhá (počtem přechodu přes černé vrcholy).
- na cestě za sebou nesmí být dva červené vrcholy (černé ano)
- vyska(T) <= 4 + 2 log |s|
- Insert - po vlozeni u a obarveni otce u na cerveno (syny cerne). pokud rotace, tak hrana R-R pokud ukazeje ven ze stromu, bude LL resp. RR rotace, pokud dovnitr tak LR resp. RL.
- Delete - po odstraneni u, nahrazeni synem a obarvenim na cerno. pokud rotace, tak cerveny uzel urcuje co. Pokud bratr, nebo vzdalenejsi synovec, tak LL resp. RR rotace, pokud blizsi synovec, tak LR resp. RL rotace. Pozn. -Detaily a ostani (napr. prebarveni) uz tu neni!
Pokud má R-B strom T na cestě z kořene do listu k černých vrcholů, pak platí k <= vyska(T) <= 2k.
[edit] Haldy
d-regularni d=3-4: minimalizace porovnani, d=6: rychle
- Lokální (otec reprezentuje prvek menší než syni) a strukturální kriterium (např. strom, kde každý vnitřní uzel má d synů, až na poslední v level-order (tj. jako BFS), který může mít pouze 1 ≤ k ≤ d synů).
- d-regulární (snadný find min (vždy kořen), umim make heap v O(n), težký merge)
- leftist(snadný find min (vždy kořen), umím merge)
- binomiální(+líná) (lze merge, ale find min horší (mam víc stromů)) Slajdy Složitost I
- fibonacciho (jako líná binomiální a navíc umím decrease key). Slajdy Složitost I, wen:Fibonacci_heap, Fibonačiho haldy - slajdy ČVUT
[edit] Trie
- Pozn.: Jdou použít i ke zjišťování množiny slov s podobností určenou editační vzdáleností a omezenou prahem - jdu více větvemi, pokud jdu přes jiný znak, tak ++podobnost v podstromu.
- wen:Trie
[edit] B-stromy a jejich varianty
- (a,b)-stromy
- Základní
- INSERT: štěpí zdola nahoru příliš velké vnitřní uzly
- DELETE: postupně, zdola nahoru, slévá rodiče se sousedem, nebo (když je soused moc velký na slití) si z nej přesuneme krajní prvek.
- Paralelní INSERT/DELETE – uzpůsobení operací, aby se nemusel zamykat celý strom. Štěpí/slučuje uzlu preventivně (proto se zde nevoli $ 2a>b $ tj. napr. $ 2a-1=b $, ale treba $ 2a=b $) již při sestupu, aby nebylo potřeba se vracet.
- A-Sort – třídící algoritmus, který naskládá posloupnost do (2,3)-stromu a pak přečte (listy jsou spojeny). Respektuje předtřídění. O(n*log(F/n)).
- Hladinově propojené (a,b)-stromy s prstem (využívají zobecnění vyhledávání použitého v A-Sortu)
- Základní
- B-stromy – (a,b)-stromy s fixním $ a=\lceil{}b/2\rceil $
- (B+)-stromy – B stromy s listy propojenymi obousmernym spojakem, umoznuje intervalove dotazy v DB, dalsi pouziti ve FS
- (B*)-stromy – varianta s podminkou, ze nekorenove nelistove uzly musi byt alespon 2/3 plne ($ a\ge\lceil{}2/3\times{}b\rceil $). Pri pridavani uzel sdili potomky se svym sousedem misto toho aby se delil. Az kdyz je i soused plny, tak se tyto dva uzly rozdeli na 3. Lze take dovolit podteceni/preteceni.
- (Ne)redundantnost:
- Redundantni – klice ve smerovacich zaznamech i v listech
- Neredundantni – klic bud v smerovacim zaznamu, nebo v listu
[edit] Hašování
[edit] Řešení kolizí
[edit] Hašování se separovanými řetězci
- při kolizi uložím do pole tabluky obě položky, každé políčko má [separátní] seznam (řetězec) položek, které tam dle hašovací funkce patří
- očekávaná délka řetězců = n/m
- očekávaný počet testů v úspěšném případě = 1 + α/2
- očekáváný počet testů v neúspěšném případě je 1,37 a 2,14 pro α = 1 resp. 2
[edit] Hašování s uspořádanými separovanými řetězci
- trochu lepší, protože když hledám v políčku prvek, nemusím jet až na konec ale stačí k první větší položce
- očekáváný počet testů v neúspěšném případě je 1,24 a 1,70 pro α = 1 resp. 2
[edit] Hašování s přemisťováním
- každé políčko má dva ukazatele (předchůdce, následník), jejichž pomocí tvoří kolizní položky řetězec
- pokud kolizní položka zabírá místo položce, co na místo dle haše patří, je přemístěna
- nevýhoda: přemísťování při INSERTu zpomaluje
[edit] Metoda se dvěma ukazateli
- podobné, políčko má ukazatele následník a začátek řetězce
- prvky se nepřemisťují, místo toho může být začátek přesměrován pomocí druhého ukazatele
- očekávaný počet testů v úspěšném případě = 1 + α/2 + α^2/6
- očekáváný počet testů v neúspěšném případě je 1,66 pro zaplněnou tabulku (α = 1)
- nevýhoda: tři položky v paměti zabírají příliš paměti
[edit] (Standardní) srůstající hašování
- Podobné jako předchozí, kolizní řetězce srůstají s prvky, co na zabraná políčka patří
- Nelze jednoduše mazat položky
- Varianty
- LISCH (Late Insertion Standard Coalescing Hashing) – přidává na konec řetězce
- EISCH (Early Insertion Standard Coalescing Hashing) – přidává na druhé místo řetězce
Varianty se liší v očekávaném počtu testů při úspěšném vyhledávání, pro neúspěšné je odhad pro obě metody stejný, protože posloupnosti se liší jen pořadím prvků v jednotlivých řetězcích.
[edit] Obecné srůstající hašování
- Tabulka má pomocnou část, jejíž políčka se přednostně používají pro kolizní řetězce
- Varianty: LICH (Late Insertion…), EICH (Early Insertion…), VICH (Variable Insertion…)
[edit] Hašování s lineárním přidáváním
- tabulka má jen klíč, kolizní prvky se dávají na první volné místo
- použitelné do zaplnění 75%
[edit] Dvojité hašování
- zobecnění předchozího, přidávám na první volné místo v posloupnosti h1(x) + k*h2(x) pro k = 0, 1, 2, ...
[edit] Pořadí
pořadí metod dle počtu testů:
- hašování s řetězci, hašování s přemísťováním
- VICH/LICH, hašování se dvěma ukazateli
- EICH
- EISCH, LISCH
- dvojité hašování
- hašování s lineárním přidáváním
[edit] Zdroje
- http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/struktury.sxw
- http://mff.modry.cz/datovky/zapisky/Lenka/
[edit] Univerzální Hašování
- Zdroje
- skripta Vidner-Kotal, kapitola 4.1 (strana 26)
- skripta Petr Hošek (pro Jana Hrice), kapitola 7.4 (strana 17)
U normálních hašovacích metod předpokládáme rovnoměrné rozdělení vstupní množiny. To nejde zaručit a nerovnoměrnost a z ní vzniklé zpoždění by nám mohlo vadit. Proto používáme univerzální hašování jako rozšíření hašování se separovanými řetezci. Pokud po insertu zjistíme, že je tabulka plná, tak přehašujeme do tabulky o dvojnasobné velikosti. Pokud po insertu zjistíme, že je délka řetězce delší než nějaká konstanta $ d_i $ (kterou zatím neumíme určit optimálně), tak přehašujeme jinou dostupnou funkcí.
H = soubor hašovacích funkcí (do tabulky velikosti m)
Pro každou vstupní množinu existuje "hodně" funkcí z H, které se chovají dobře (málo kolizí).
Def: Soubor funkcí z H (U -> {0, 1, ...m-1}) se nazývá c-univerzální, pokud $ \forall x \neq y \in U;\ | \{ h \in H: h(x) = h(y) \}| \leq\ \cfrac{c |H|}{m} $
Konstrukce H: Předpokládejme: U = (0, 1, ... N-1), N prvočíslo (pro každé přirozené číslo existuje prvočíslo mezi tím číslem a dvojnásobkem, takže přinejhorším natáhnem množinu na dvojnasobek, aby tohle platilo). $ H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1} $, tj. všechny lineární funkce.
Tvrzení: takto zkonstruované H je c-univerzální systém pro
.. tím jsme ukázali, že nějaké c-univerzální systémy existují
Věta: Nechť H je c-univerzální systém, pak pro každou množinu $ S \subset U,\ |S| = n $ a pro každé x je očekávaný čas operací insert/member/delete(x) roven:
.. je to průměr přes všechny funkce z H, ne přes všechny vstupy. Takže když to pro jednu funkci není splněno, můžu náhodně vybrat jinou a mám slušnou šanci, že pro ni to, na tom samem vstupu, splněno bude.
Věta: Nechť H je c-univerzální systém, pak pro každou množinu $ S \subset U,\ |S| = n $ a pro každé x platí, pokud je $ \mu $ průměrná délka řetězce pro prvky s hodnotou h(x), pak:
Věta: Když H je c-univerzální systém na universu U = {0,1,...N-1} hašující do tabulky velikosti m, pak:
Mno, podle mne to ma byt takto:
[edit] Perfektní hašování
- Hašování takové, kde nejsou kolize.
- Operace insert je buď zakazaná, nebo se řeší bufferem občasně zahašovávaným do hlavní tabulky.
Chceme pro danou množinu $ S \subset U $ nalézt funkci h: U -> {0, 1, ..m-1} takovou, že
- 1) h je perfektní vůči S
- 2) h(x) je rychle spočitatelná
- 3) m je srovnatelné s n
- 4) h nevyžaduje příliš paměti
Konstrukce:
$ h_k(x) = (k*x\ mod\ N)\ mod\ m $
N = |U|
předpoklad:
S pevně daná
$ b_k^i $ je počet $ x \in S;\ h_k(x) = i $
Význam $ b_k^i $: Tyto hodnoty ukazují odchylku od perfektnosti.
pokud $ b_k^i \geq 2 $, potom $ (b_k^i)^2 - b_k^i \geq 2 $
naopak $ b_k^i \leq 1 $, implikuje $ (b_k^i)^2 - b_k^i = 0 $
Věta: Funkce $ h_k $ je perfektní, právě když
Existuje k takové, ze:
.. zkouším jednotlivé funkce tak dlouho, než najdu parametr k, pro který je suma druhých mocnin délek řetězců menší, než ten výraz. (to plyne nějak z vlastností univerzálního hešování!)
Důsledky:
- 1) pokud m = n (my volíme m), pak:
- 2) pokud $ m = 1+n(n-1) $, pak $ \exists k; h_k $ je perfektní (suma vyjde < n+2 a pokud by nebyla perfektní, tak je tam alespoň jeden řetězec délky alespoň dva, jeho mocnina je 4 a $ 4 + (n-1) $ jednoprvkových řetězců dává délku > $ n+2 $; spor). Tohle ale nevyhovuje požadavku 3).
- 3) Konstrukce do prostoru < 3n. Vezmeme funkci z důsledku 1) a rozdělíme S do m množin podle $ h_k(s)=i $ (množiny kolidujících prvků pro každé i). Pro tyto množiny nalezneme perfektní funkci podle důsledku dva. Tahle kombinace dvou funkcí pak tvoří výslednou perfektní funkci. Do <3n se to vleze, protože pro ty malé funkce mám k dispozici druhou mocninu prostoru (vzhledem k počtu prvků) a:
(...kolizní řetězce se rozprostřou tak, že se najde perfektní hašovací funkce pro každý z nich, a díky tomu, že těch řetězců je málo, se to celé vedje do 3n :-)
Stále to ještě nesplňuje podmínku 4). Další úprava se dělá pomocí magie.
[edit] Možnosti dynamizace jednotlivých datových struktur
Máme obecnou statickou strukturu (neumožňující INSERT a DELETE) a zkoumáme jak do ní toto přidat. Chceme, aby se f(x,A) (vyhledání a tak) v nové struktuře počítalo přibližně stejně rychle jako v té původní. Dále, když vytvoření původní struktury pro n-prvkovou množinu trvalo t, pak operace INSERT by měla vyžadovat čas t/n.
- vyhledávací problém
- je funkce $ f : U_1 \times 2^{U_2} \to U_3 $, kde $ U_1 $, $ U_2 $ a $ U_3 $ jsou univerza.
- řešení vyhledávacího problému
- pro $ x \in U_1, A \subseteq U_2 $ je nalezení hodnoty f(x,A).
Klasický vyhledávací problém má $ U_1 = U_2 = U $ (univerzum prvků), $ U_3 = \{0,1\} $, $ A \subseteq U_2 $. f(x,A) pak vrací 0/1 podle toho, je-li $ x \in A $.
- rozložitelnost problému
- Vyhledávací problém je rozložitelný, když existuje operace $ \oplus $ spočitatelná v konstantním čase, a platí: když $ x \in U_1 $ a A a B jsou disjunktní podmnožiny $ U_2 $, pak $ f(x, A \cup B) = f(x,A) \oplus f(x,B) $
- Pozn.: Vyhledávací problém není chápán jen jako dotaz MEMBER(x)! Ale jako hledání řešení nějaké obecné úlohy, kterou lze řešit pouze (nebo dostatečně efektivně) nad statickou strukturou, resp. pro rozložitelný problém i nad její parcelací.
[edit] Semidynamizace
Máme rozložitelný vyhledávací problém f a pro něj statickou strukturu, která ho řeší v čase Q(n), vyžaduje S(n) paměti a vytvoří se v čase P(n), kde Q(n), P(n)/n a S(n)/n jsou neklesající funkce. Pak existuje semidynamická datová struktura D, řešící f v čase O(Q(n) log n), vyžadující O(S(n)) paměti a umožňující INSERT s amortizovanou složitostí O(P(n)/n * log n).
Postup: A si rozdělíme na sadu disjunktních množin $ A_i $, pro které platí buď $ A_i = \emptyset $ nebo $ |A_i| = 2^i $. Nová struktura reprezentující A je potom dynamická struktura reprezentující A (třeba AVL strom, pro rychlé operace MEMBER), pro každé $ A_i \neq \emptyset $ máme S strukturu propojenou s odpovídajícím prvkem ve stromě.
Zároveň si pro každou $ A_i $ pamatuji spojový seznam jejích prvků, protože při vkládání nového vyrábím novou statickou strukturu z menších $ A_i $, a dostávat seznamy prvků ze statických struktur by mohlo trvat.
f(x,A) se počítá pro každou menší množinu zvlášt a pak se výsledky v konstantním čase spojí pomocí operace $ \oplus $.
Pak existuje ještě varianta optimalizující INSERT v nejhorším případě. V něm se budují množiny velikosti $ 2^i $ postupně. Po vložení prvních dvou prvků x,y učiním polovinu kroků stavby {x,y} atd.
[edit] Dynamizace
Ještě přidáme falešný DELETE (škrtnutí prvku v čase O(n)).
- Pozn.: Falešný DELETE je nový požadavek! Statická struktura ho musí podporovat.
A rozložíme na disjunktní množiny $ A_j, j = 0, 1, ..., \log {|A|+3} $ takové, že buď $ A_j = \emptyset $ nebo $ 2^{j-3} < |A_j| \leq 2^j $. Každá množina $ A_j $ je reprezentována strukturou, která před škrtáním měla velikost $ \leq 2^j $. Pak máme pro každou neprázdnou $ A_j $ spojový seznam prvků v ní, provázaný se strukturou reprezentující $ A_j $. Amortizovaně INSERT v O(log(n)*P(n)/n), DELETE v O(D_s(n) + log n + P(n)/n)), pokud P(n) je $ n^{\epsilon} $, tak to vychází O(P(n)/n). DELETE naplní A_j jen do půlky, takže to sice stačí, ale nekazí to složitost INSERTu získanou v semidynamické kapitole.
- INSERT
- $ |\bigcup_{i=0}^{j}A_i|<2^j $
- $ A_j $=build($ \bigcup_{i=0}^{j}A_i|\cup\{x\} $)
- destroy(0,j-1,$ A_i $)
- Když insertbuduje $ A_j $, platí potom $ 2^{j-1}<=|A_j|<=2^{j} $
- DELETE
- $ |A_j|=1 $…destroj($ A_j $)
- $ |A_j|>2^{j-3}+1 $…fake_delete(x)
- $ |A_j|=2^{j-3}+1 $
- |$ A_{j-1}|=0 $…$ A_{j-1} $=build($ A_j\smallsetminus\{x\} $), destroy($ A_j $)
- $ |A_{j-1}|>=2^{j-2} $…swap($ A_{j-1} $, $ A_j $), $ A_{j-1} $=build($ A_{j-1}\smallsetminus\{x\} $) //po swapu
- $ |A_{j-1}|<2^{j-2} $
- if $ |A_j|-1+| A_{j-1}|>2^{j-2} $ then
- $ A_j $=build($ (A_j\smallsetminus\{x\})\cup A_{j-1} $), destroy($ A_{j-1} $)
- else
- $ A_{j-1} $=build($ (A_j\smallsetminus\{x\})\cup A_{j-1} $), destroy($ A_j $)
- if $ |A_j|-1+| A_{j-1}|>2^{j-2} $ then
- Když delete buduje strukturu $ A_j $, platí potom $ 2^{j-2}<=|A_j|<=2^{j-1} $
[edit] Mapování datových struktur do stránek vnější paměti počítače & Časová složitost algoritmů vyjádřená v počtu I/O operací
[edit] Schéma organizace souborů (SOS)
- fyzické soubory
- délka fyzického záznamu R, délka stránky B, blokovací faktor B/R=b
- blokované, neblokované, přerostlé záznamy
- logické soubory
- logické stránky (bloky) konstantní délky
- primární soubor (velikosti N)
- dotazy nad soubory
- dotaz na úplnou shodu, na částečnou shodu, dotaz na úplnou intervalovou shodu, dotaz na částečnou intervalovou shodu
- vyváženost struktury (rozlišují se podle ní statické a dynamické SOS
- omezení délky cesty v datové struktuře
- naplněnost logických stránek (faktor naplnění stránky λ), štěpení stránky, slévání stránky
- fyzické nosiče souborů
- magentická páska
- sekvenční čtení, využívá se buffer (velikosti jedné stránky), páska obsahuje meziblokové mezery
- magnetický disk
- stopy, cylindry, bloky, parametry: s - seek, r - rotation (rovno polovině) doby otáčky, btt - block transfer time,
[edit] Statické metody organizace souborů
[edit] Počty I/O operací - základní přehled
Rozhoduje kolik se přečte stránek z disku, kolik se jich zapíše a jak dlouho to trvá
- Fetch
- čas pro načtení jedné stránky $ T_F = s+r+btt $, pro další stránky na stejném cylindru se nemusí hlavičky přesouvat ($ T_F = r+btt $)
- Rewrite
- přepsání stránky na disku (tj. přenos stránky do vnější paměti, změnu ve vnější paměti a přenos zpět na disk), lze vyřešit v době, než se plotna disku jednou otočí, tedy $ T_RW = 2r - btt + btt = 2r $
- Insert
- vložení zánamu (je nejprve zapotřebí načíst stránku, do které se bude zapisovat, do paměti) $ T_I $
- Delete
- smazání stráky (obvykle prohlášení za neplatnou) $ T_D $
- Update
- změna záznamu ve stránce $ T_U $
- Reorganizace
- $ T_Y $
Pro jednotlivé typy organizace souborů bude úvaha nad jejich počty IO operací uvedena u jejich popisu.
Dlouhodobe9 půjčky, americke9 hypote9ky a psaeikdtnloke9 favěry se ze1stavou nemovitosti v cele9 ČR. Nabedzedme konsolidace, oddlužened a refinance s nebankovnedch sektoru. Vyple1cedme nevfdhodne9 ze1stavy, dražby, exekuce a vyčistedme LV s veškerfdm pre1vnedm servisem. Finance jsou u ne1s poskytove1ny od 1 30 let a kdykoliv můžete půjčku předčasně splatit. Bez zkoume1ned předjmů a registrů. Bez poplatků předem! Milan Karička608192902
[edit] Sekvenční soubor
- neuspořádaný - oproti hromadě záznamy pevné délky
- uspořádaný - podle jednoho klíče
Odhady pro uspořádaný sekvenční soubor:
- $ T_F = log_{2} (N/\lfloor b \rfloor)(s+r+btt) $ - nalezení záznamu metodou půlení intervalů
- $ T_I = s+r+btt + T_RW + T_Y/o $ - načte se stránka kam se bude vkládat, přepíše se a připočte se poměrný čas potřebný pro reorganizaci souboru (až k ní dojde).
- update
- Tato část je neúplná a potřebuje rozšířit. Dopsat, doporučuju skripta Pokorný-Žemlička - Základy implementace souborů a databází
(prosim doplnujte co si myslite ze sem patri nebo primo vite ze se zkouselo, nejlepe i s info kde to najit)
- schema organizace souboru (hromada, sekv, index-sekv.) - zkouselo se (Zemlicka), skripta Zaklady implementace souboru a databazi (stare vydani str. 15-30) (viz též ČVUT wiki
- ja myslim ze sem patri aj Externe hashovanie (skripta na DS) - je to asi totez co Fagin z OZD, ale sloziteji popsany :)
- staticke hasovani - Cormack, Larson+Kalja (Pok97 31-35)
- dynamicke hasovani - Fagin, Litwin, skupinova stepeni stranek (Pok97 41-47)
- Externy mergesort? Je to sice uz v triedeni vo vonkajsej pamati, ale ked je tu aj ext. hashovanie...
- Majerech akceptoval rozpravanie o externom MergeSorte, B+ stromoch.
[edit] Vícerozměrné datové struktury
[edit] Dotazy na částečnou shodu a jejich optimalizace
- v hasovacich schematech - Pokorny 35-40 (stare vydani) - optimalizace prumerneho poctu I/O operaci pro specialni variantu dotazu na 1 atribut ze znamych pravdepodobnosti atributu; deskriptory stranek a 2urovnove vrstvene kodovani; Grayovy kody
- ve vicerozmernych B-stromech - Pok. 71-73
- vicerozmerna mrizka - Pok. 73-75
[edit] Signaturové metody
Rozdělím si text na logické bloky, ty nějak zakóduju do signatur (řetězce bitů). Dotaz (konjunkci termů) pak taky zakóduju si signatury, a porovnáním se signaturami jednotlivých bloků vyloučím část dokumentů, které dotazu určitě nevyhovují.
- máme funkci h, která zobrazuje termy na bitové řetězce; OR binárních reprezentací termů je signatura dokumentu
- signatura bloku SD vyhovuje signatuře dotazu SQ, pokud SQ & SD == SQ (nebo taky SQ & ~SD == 0)
http://kocour.ms.mff.cuni.cz/~pokorny/vyuka/pokorny6/
http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/07/dis07_v1.html
[edit] Třídění ve vnitřní a vnější paměti
[edit] Vnejsi pamet
Merge sort jak je popsan v pokornem: Hlavni rozdil je nacitani po blocich (obsahuje typicky vice zaznamu najednou) a pomalost disku, takze optimalizace na co nejmensi pocet nacteni.
1. nactu a setridim skupiny bloku, ktere se mi vlezou do operacni pameti (OP)
2. nactu z m setrizenych skupinbloku 1. blok do OP, tridim do bloku m+1. Kdyz je m+1 plny, tak ho zapisu a uvolnim, kdyz se nejaky vstupni blok vyprazdni, tak nactu dalsi blok te skupiny (pokud existuje).
Tak ziskam setrizenou skupinu bloku m nasobne velikosti. a opakuju. Pokud se mi do pameti vejde vice nez odmocnina z celkoveho poctu bloku, tak lze provest na dva pruchody (obecne M - pocet bloku, co se vejdou do OP, N pocet vsech bloku zabranych mnozinou, tak to setridim na log_M N pruchodu)
- Behy pro trideni (resp. externi trideni) lze delat pomoci 2 hald. Udelam jednu pres celou pamet. Trham minimum a novy nacitany prvek: pokud je vetsi nez odeslane min tak zatridim do haldy, jinak ulozim do pameti na volne misto (stavim 2. haldu)
[edit] Vnitrni pamet
[edit]
buble sort - prochazim seznamem a kdyz najdu dva sousedni prvky, ktere jsou v opacnem poradi nez maji byt, tak je prehodim. Pruchody zacinam do doby, nez jsem pri pruchodu nic nezmenil - je setrizeno. O(n2), nejhorsi
insert sort - pri nacteni noveho prvku jej zatridi do mnoziny jiz setrizenych porovnavanim se sousedem. Worst: O(n2), Avg O(n2), O (n+ počet transpozic), ale lepsi konstanta nez bubblesort
A-sort - ma podobonou vlastnost jako insert sort: pri malem poctu transpozic je rychly. I jeho myslenka je podobna. Pouze pri zatrizovani ma misto jednoducheho pole setrizenych prvku nejaky stromecek (napr. 2,3-strom nebo AVL strom), do ktereho nove prvky vklada. Takto je mozne opravit k transpozic na pouhych log(k) kroku.
selection sort - najde nejmensi prvek, vynda ho a da na vystup (v in-place verzi vymeni s prvnim v posl.), opakuje se zbytkem - O(n2) nejhorsi i ocekavany
shell sort - zdokonaleny insert sort. Pri zatrizovani neporovnavam se sousedem, ale s nekym o vice indexu vzdalenym - treba 5. Pote, co skoncim, tak opakuju se skakanim o 3 a naposledy skacu o 1 (=insert sort). Pri dobre k - vzdalenosti dvou porovnavanych prvku, lze slozitost stlacit (v soucasnosti, zlepseni je otevreny problem) az na O(n log^2(n))
merge sort - rozdelim posloupnost na pulky rekurzivne az na jednotlive prvky. Pak skladam vzdy dve setrizene casti (pocinaje dvema samostatnymi prvky a konce polovinami posloupnosti) - O(n logn) best, worst i avg; jina verze - "prirozeny merge" nejdriv projde posl. O(n) a najde rostouci behy, nahaze je do fronty; pak dokud ve fronte vic jak 1 posl. zmerguje prvni dve a vysledek hodi na konec fronty - tato verze je optimalni vzhledem k poctu porovnani, adaptuje se na predtridene posloupnosti; pokud je pocet behu konstatni tak bezi v O(n)
quicksort(+vyber dobreho pivota) - zvolim pivota a prvky mensi nez on dam do jedne casti, prvky vetsi nez on do druhe. Rekurzivne az po trivialni ulohy a pak zpetne skladam jiz setrizenou posloupnost. Avg O(n logn), Worst O(n2), O (n log n , i kdybych pivota vybral vzdycky tak blbe, ze 1% bude mensi a 99% vetsi nez on).
heap sort - postavim d-regularni haldu (jde O(n)), n krat extractmin - O(n logn) celkem; da se delat in-place (primo v poli s tridenymi prvky) - ulozeni haldy v poli jasne; pouzijeme dualni podminku (otec > syn) a DELETEMAX misto DELETEMIN - DELETEMAX vymeni koren s poslednim v halde (a DOWN na koren) + zmensi haldu o 1 - tim MAX vypadne, vpravo od haldy se vytvari setridena posloupnost
[edit]
bogo sort - srovnej vstupni posloupnost nahodne a zkus, jestli je setrizena :))
radix sort - rozdelim do kastliku 0-9 (a-z, ..., podle abecedy v klicich) podle nejmene duleziteho znaku. Znovu postavim celou posloupnost serazenim kastliku za sebe dle jejich (znameho) poradi. Udelam to same pro 2. nejmene dulezity znak a dokola az po nejdulezitejsi.
hybrid sort - trideni n realnych cisel v rozsahu (0-1] - k=alfa*n prihradek, prvek a_i zatridim do prihradky ceil(k*a_i) , kolize sortuju heap sortem (misto "separovanych retezcu" ma kazda prihradka svuj heap) -> slozitost nejhur O(nlogn), za predpokladu nezavisleho rovnomerneho rozlozeni vstupu O(n)
bucket sort, counting sort ..
Stabilni trizeni - pokud zachova poradi prvku se stejnym klicem takove, jake bylo na vstupu
Dlhsi seznam viz wikipedia
[edit] Relaxované vyhledávací stromy
Co se stane se stromy, kde po přidání/odebrání nevyvažujeme. Rychlejší operace, více uživatelů zároveň, vyvažování necháme na později. Tyto stromy nazýváme relaxované.
- Možná degenerace stromu - delší vyhledávání
- Lze jednoduše nevyvážený strom vyvážit bez přebudování celé struktury?
Požadavek
- v - vrchol černý a v podstromu vrcholu chybí jeden černý uzel
- b - vrchol i jeho otec červené, exkluzivní, s vrcholem nesmí být svázán žádný jiný požadavek
Příklad na RB stromech, lze analogicky pro ostatní. Máme frontu vyvažovacích požadavků, pokud prázdná, strom je vyvážený. Nad daty pracuje několik procesů najednou:
- uživatelský - provádí vyhledávání, přidávání a odebírání. Pokud po aktualizaci vznikne požadavek na vyvážení, přidá ho do fronty
- správcovký - bere vhodné požadavky z fronty a provádí je. Požadavky mohou být buď zcela ošetřeny nebo transformovány v jiný požadavek blíže kořeni.
[edit] Další materiály
- Základ přebrán z Majklových státnicových výcucků
- Skripta Vidner-Kotal – neoficiální skripta
- Václav Koubek, Alena Koubková: Datové struktury I, II (ktiml) – dost obsáhlé
- Melhorn K., Data Structures and Algorithms: [1]
- Mareš M. a kol. Algoritmy a Datové struktury I a II: [2]
- Pokorny. Slajdy k prednasce Organizace a zpracovani dat: [3]
