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.

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í.)

Stromové vyhledávací struktury

Binární stromy a jejich vyvažování

• wen:Binary search tree
• wen:Self-balancing binary search tree (AVL stromy, červenočerné stromy)

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.

Jednodussi verze

• Robert Sedgewick - jeden z autoru puvodniho paperu o Red-Black trees se k teto strukture po 30 letech vratil a vytvoril Left-leaning Red-Black-Trees.

 * Variantu vyzadujici k implementaci 1/4 zdrojaku
 * Vyrazne zjednodusuje rotace a zachovava ty slozitosti, ktere nas zajimaji
 * Pripomina myslenku stojici za vsemi "Red-black-trees" jsou zpusobem, jak zakodovat 2-3 nebo 2-3-4 strom do binarniho stromu. 
 * Primym dotazem na pana Koubka, zda je mohu pouzit u zkousky mi bylo receno, ze ano, ale musim o nich byt schopen dokazat a umet vse, co se uci/vyzaduje u Red Black Trees
 * Paper vcetne slozitosti zde: [1]

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

• wen:Heap (data structure), wcs:Halda (datová struktura)

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

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)
• B-stromy – (a,b)-stromy s fixním $ a=\lceil{}b/2\rceil $
• (B+)-stromy – B stromy který má klíče ve vnitřních uzlech, ale taky poslední (vnitřní) hladina ukazuje na pozici ve spojovém seznamu se všemi klíči (a ty typicky mají asociovaná nějaká data). 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. Prakticky B-strom ktery se chova k pameti trochu lepe - je z 2/3 zaplnena narozdil 1/2.
• (Ne)redundantnost:
  • Redundantni – klice ve smerovacich zaznamech i v listech
  • Neredundantni – klic bud v smerovacim zaznamu, nebo v listu

Hašování

• wen:Hash table

Řešení kolizí

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

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

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

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

(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.

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…)

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%

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, ...

Pořadí

pořadí metod dle počtu testů:

1. hašování s řetězci, hašování s přemísťováním
2. VICH/LICH, hašování se dvěma ukazateli
3. EICH
4. EISCH, LISCH
5. dvojité hašování
6. hašování s lineárním přidáváním

Zdroje

• http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/struktury.sxw
• http://mff.modry.cz/datovky/zapisky/Lenka/

Univerzální Hašování

wen:Universal hashing

• 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

$ c=\left(\left\lceil\cfrac{N}{m}\right\rceil\Big /\cfrac{N}{m}\right)^2 $

.. 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:

$ O\left(\cfrac{c n} {m}\right) $

.. 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:

$ \forall t>1 $ je pravděpodobnost, že je řetězec $ \geq \mu t $ menší než $ \cfrac{1}{t} $

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:

$ |I| > m \cfrac{\lceil (log_mN)-1\rceil}{c} $

Mno, podle mne to ma byt takto:

$ |I| > m \cfrac{\lceil {log_mN} \rceil -1}{c} $

Mno, a podle mne je $ \lceil X - 1 \rceil = \lceil X \rceil - 1 $ takze je to jedno.

Perfektní hašování

wen:Perfect hash function

• 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ž

$ \sum_{i=0}^{m-1} (b_k^i)^2 < n + 2 $

Existuje k takové, ze:

$ \sum_{i=0}^{m-1} (b_k^i)^2 \leq n + \cfrac{2n(n-1)}{m} $

.. 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:
  

$ \exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $ a k nalezneme v $ O(nN) $

• 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:
  

$ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $

(...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.

Vysvětlení

Myslím, že to co je výše jsou takové snippety z důkazu, ale vůbec v tom neni vidět jak to má fungovat. Idea je, že máme primární hashovací funkci $ h_k(x) = (k*x\ mod\ N)\ mod\ m $, která není perfektní, a pak zkonstruujeme sadu sekundárních, už perfektních. Nakonec je složíme, že dostaneme perfektní funkci. Ve skriptech Koubka je tohle zahrabané až na úplném konci a vůbec to neni zdůrazněné, že vlastně kvůli tomuhle sme všechno dokazovali. Pokud si nejste jistí tak doporučuju přečíst originální článek od Cormacka .

Def. $ b_k^i=\{x\in S|h_k(x)=i\} $

Takže jako shrnutí co umíme (viz. výše):

• umíme najít docela dobrou hashovací funkci rychle O(n), nebo trochu lepší ale zas to stojí víc času O(nN)
• umíme najít perfektní hashovací funkci do tabulky $ m=n(n-1)+1 $ v čase O(nN) (projdeme všechny možnosti a počítáme $ \sum (b_k^i)^2 $)
• umíme najít perfektní hashovací funkci do tabulky $ m=2n(n-1) $ v čase O(n) (náhodně procházíme možnosti)

Samozřejmě bychom mohli pustit rovnou hledání perfektní hash funkce v O(nN), ale tahle funkce by zabrala hodně paměti, takže to uděláme lépe. Takže konstrukce probíhá tak, že najdeme tu neperfektní, ale docela dobrou $ h_k $. O ní platí, že $ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $. Tuhle hashovací funkci pak použijeme k tomu, že rozhashujeme množinu S do disjunktních množin $ S_i=\{s\in S|h_k(s)=i\} $. A teď pro každou z nich najdeme perfektní hashovací funkci $ h_{k_i} $, do tabulky velké $ c_i:=m=n(n-1)+1 $.

Teď už máme všechno, co potřebujeme. Vytvoříme si primární soubor a uděláme si v něm značky, kam budeme ukládat $ S_i $. Řádek v primárním souboru kde začíná $ S_i $ bude $ d_i:=\sum_{j=0}^{i-1} c_i $. Perfektní hashovací funkce pak bude: $ h_k(x)=l; g(x)=d_l+h_{k_l}(x) $. Když sečteme jak dlouho nám vše trvalo dostaneme O(nN) za první hash funkci, pak zahashujem S do $ S_i $ v O(n) abychom spočítali kolik potřebujeme naalokovat na perfektní funkce. Perfektních funkcí bude m a každou budeme hledat v čase $ O(|S_i|N) $, což po sečtení vyjde O(nN). Takže teď jen potřebujeme ukázat, že jsme skutečně spotřebovali méně jak $ O(n^2) $ paměti. Pamět můžeme omezit pomocí $ d_m:=\sum_{j=0}^{m-1} c_i\leq \sum_{j=0}^{m-1} (b_k^i)^2<3n $, protože $ |S_i|(|S_i|-1)+1\leq |S_i|^2=(b_i^k)^2 $.

Tohle ještě není úplně stoprocentně perfektní hashovací funkce, ale už jsme dost blízko. Jeden z požadavků na perfektní funkci je, aby ji bylo jednoduché uložit (nejlépe analyticky), což zkonstruovaná funkce g(x) úplně není, což je asi dobré zmínit, i když se tohle hashování už označuje za perfektní. Alternativní metodu, která nám dá trochu hezčí analytickou hashovací funkci, popsali Fredman .

Možnosti dynamizace jednotlivých datových struktur (pouze I1,I4)

• wen:Dynamization
• slajdy o semidynamizaci a dynamizaci
• Kurt Mehlhorn - zda se puvodni zdroj

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í.

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á pomocná struktura T reprezentující A, kterou použijeme pro test $ x \in A $ před libovolnou operací (může to být třeba AVL strom, pro rychlé operace MEMBER a INSERT). Tady je důležité si uvědomit, že vyhledávací problém nemusí být MEMBER, pro INSERT ale potřebujeme pustit nejdřív MEMBER a proto máme tuhle pomocnou strukturu.
• Pro každé $ A_i \neq \emptyset $ máme S statickou strukturu. 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.

Vyčíslení f(x,A): f(x,A) se počítá pro každou množinu $ A_i $ zvlášt a pak se výsledky v konstantním čase spojí pomocí operace $ \oplus $.

INSERT: Zkontrolujeme pomocí pomocné struktury MEMBER(x,T), dál postupujeme jen pokud prvek ve struktuře není. Vložíme prvek x do pomocné struktury (INSERT(x,T)). Najdeme nejmenší i, pro které $ A_i=\emptyset $ do téhle zkolapsujeme všechny $ A_j, j<i $. Spojíme jejich spojové seznamy, přidáme x a vytvoříme novou statickou strukturu S která bude reprezentovat $ A_i $. Zároveň zapomeneme použité $ A_j $.

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.

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 $)

Když delete buduje strukturu $ A_j $, platí potom $ 2^{j-2}<=|A_j|<=2^{j-1} $

A je opět reprezentována nějakou dynamickou strukturou T, která umožňuje operace MEMBER, INSERT a DELETE v $ O(\log n) $.

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í (pouze I1,I4)

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
    1. omezení délky cesty v datové struktuře
    2. 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,

Statické metody organizace souborů

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.

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.

Dolní odhady pro uspořádání (rozhodovací stromy)

podle http://ksvi.mff.cuni.cz/~topfer/ppt/Progr-11.pdf

Třídíme-li s pomocí porovnávání, můžeme si výpočet znázornit binárním stromem. Začínáme v kořeni, v uzlech porovnáváme a větvíme, v listech máme setříděno. Pro každá vstupní data se výpočet někde odliší od ostatních, strom má $ n! $ listů (tolik je možných uspořádání množiny s $ n $ prvky.) Výška stromu je počet provedených porovnání při nejdelším výpočtu (v nejhorším případě) je alespoň $ \log_2(n!) $. (Úplný binární strom s $ k $ listy má výšku $ \log_2 k $, neúplný je vyšší.) Časová složitost třídícího algoritmu založeného na porovnávání proto nemůže být lepší než $ O(\log_2(n!)) = O(n\ \log n) $.

Podle Stirlingovy formule:

$ n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n} $ (to je ona)

$ O(\log_2 n!) = O(\log_2{\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}}) = O(n \log n) $ (Logaritmus odmocniny bude asymptoticky $ O(\log n) $, $ (n/e)^n $ bude $ O(n \log n) $, a požere to.)

• Pro mne snazší odhad: nⁿ ≥ n! ≥ n^n/2
• k-tý prvek nelze s porovnanim ziskat driv nez v O(n): musim mit alespon retizek s n-1 hranami.
• konvexni obal nelze lepe nez O(n*log(n)): pro [x,x²] umim tridit

Třídění ve vnitřní a vnější paměti

Vnejsi pamet

• wen:External sorting
• Celkem pěkně popsané ve skriptech Pokorný, Žemlička k OZD (jsou dostupné na Studnici)

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)

Vnitrni pamet

Porovnavaci

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

Neporovnavaci

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

Samoupravující datové struktury (pouze I1,I4)

Wiki(en) - samoorganizujici seznamy

Wiki(en) - Splay stromy(samoorganizujici stromy)

Splay stromy(samoorganizujici stromy) - Cheruku Ravi Teja

Pointers to splay tree visualizations

Samoupravující seznamy

Zdroj: http://ktiml.mff.cuni.cz/teaching/files/materials/KoubekVaclav_BINVYHST.pdf str. 36 podkapitola 6

Předpoklady:

• Prvky jsou uložené ve spojovém seznamu.
• Vyhledává se lineárním průchodem.

Při vyhledávání se prvky přemísťují k začátku seznamu tak, aby se nejčastěji vyhledávané prvky byly na začátku. Nejlepší čas na vyhledání prvku se pak blíží konstatnímu. V nejhorším případě(hledaný prvek je na konci) ovšem stále $ O(n) $ jako u klasického spojáku.

Metody organizace(podrobněji viz wiki):

1. Move To Front(MTF) - vyhledaný prvek se prostě přepojí na začátek. Reaguje velmi rychle na změny ve vyhledávacích vzorů. Až moc rychle - občasné vyhledání jinak nepoužívaného prvku rozbije optimální strukturu seznamu.
2. Počítací metoda - každý uzel má počítadlo na počet vyhledávání. Uzly se udržují setřízené podle počtu vyhledání.Potřebuje navíc pamět pro počítadla. Reaguje pomaleji na změnu vyhledávacích vzorů, ale někdy zase až moc pomalu(viz příklad na wiki).
3. Transpoziční metoda - přehazuje prvek s předchůdcem, pokud existuje. Opět se přizpůsobuje vyhledávacím vzorům pomaleji než MTF.

Aplikace: V překladačích a interpretech se používají k uložení tabulky symbolů během kompilace/interpretace zdrojáku.

Splay stromy

Binární vyhledávací stromy. Při vyhledání prvku X se strom přeorganizuje tak, aby X byl v kořeni stromu.

Algoritmus operace splay pro uzel N [2]:

while N není kořen do
 1.Pokud rodič N(dále R) není kořen, proveď rotaci tak, aby N byl kořen a R jeho potomek.
 2.Pokud N a R mají stejnou orientaci(oba jsou levé nebo pravé děti). Rotuj R a potom N.
 3.Pokud N a R mají různou orientaci, rotuj dvakrát N. 
wend

Insert N:

1.Vlož N stejně jako v binárním stromě
2.Splay(N)

Delete N:

1.Stejně jako v binárním stromě
2.Splay(rodič N).

Amortizovaný odhad ceny splay operace

[3]

Výhody:

• Jednoduchá implementace.
• V průměrném případě stejně efektivní jako ostatní stromy.
• Nepotřebují paměť navíc.

Nevýhody:

• Může zdegenerovat na obyčený seznam, tj. hloubka stromu je lineární. Operace mají "dobrou" složitost amortizovanou.
• Problematické použití ve vícevláknovém prostředí. Vyhledání prvku(typická read-only operace) mění strom.

Relaxované vyhledávací stromy

Skripta Koubek str 16. podkapitola 3, Článek "Relaxed Balanced Red-Black Trees"

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.

Vícerozměrné datové struktury (asi zrušeno)

Dotazy na částečnou shodu a jejich optimalizace

see http://ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/

• 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

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

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: [4]
• Mareš M. a kol. Algoritmy a Datové struktury I a II: [5]
• Pokorny. Slajdy k prednasce Organizace a zpracovani dat: [6]
• Vizualizace datových struktur: [7]

Cormack, Gordon V., R. N. S. Horspool, and Matthias Kaiserswerth. "Practical perfect hashing." The Computer Journal 28.1 (1985): 54-58.

Fredman, Michael L., János Komlós, and Endre Szemerédi. "Storing a sparse table with 0 (1) worst case access time." Journal of the ACM (JACM) 31.3 (1984): 538-544