Státnice - Informatika - Datové struktury: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Možnosti dynamizace jednotlivých datových struktur: wtf?)
(Semidynamizace: +spojový seznam)
Řádka 116: Řádka 116:
  
 
Postup: A si rozdělíme na sadu disjunktních množin <math>A_i</math>, pro které platí buď <math>A_i = \emptyset</math> nebo <math>|A_i| = 2^i</math>. Nová struktura reprezentující A je potom dynamická struktura reprezentující A (třeba AVL strom), pro každé <math>A_i \neq \emptyset</math> máme S strukturu propojenou s odpovídajícím prvkem ve stromě.
 
Postup: A si rozdělíme na sadu disjunktních množin <math>A_i</math>, pro které platí buď <math>A_i = \emptyset</math> nebo <math>|A_i| = 2^i</math>. Nová struktura reprezentující A je potom dynamická struktura reprezentující A (třeba AVL strom), pro každé <math>A_i \neq \emptyset</math> máme S strukturu propojenou s odpovídajícím prvkem ve stromě.
 +
 +
Zároveň si pro každou <math>A_i</math> pamatuji spojový seznam jejích prvků, protože při vkládání nového vyrábím novou statickou strukturu z menších <math>A_i</math>, 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 <math>\oplus</math>.
 
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 <math>\oplus</math>.

Verze z 24. 5. 2008, 18:33

Zdroje:

Stromové vyhledávací struktury

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

Haldy

Trie

B-stromy a jejich varianty

  • (a,b) - stromy - zakladni, pararelni INSERT/DELETE, A-Sort, hladinove propojene (a,b) s prstem
  • B - stromy - (a,b) stromy s fixnim a=ceil(b/2)
  • 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. 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.

Hašování

Řešení kolizí

  • hašování s přemisťováním + metoda se dvěma ukazateli
  • s separujícími řetězci -- při kolizi uložím do pole obě položky, oddělím nějakým separátorem
  • s uspořádanými separující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
  • srůstající hašování
    • s rozšířenou tabulkou (asi se to tak nejmenuje)

http://urtax.ms.mff.cuni.cz/~novap2am/poznamky/struktury.sxw

Univerzální Hašování

wen:Universal hashing

U normalnich hasovacich metod predpokladame rovnomerne rozdeleni vstupni mnoziny. To nejde zarucit a nerovnomernost a z ni vznikle zpozdeni by nam mohlo vadit. Proto pouzivame univerzalni hasovani jako rozsireni h. se separovanymi retezci. Pokud po insertu zjistime, ze je tabulka plna, tak prehasujem do dvojnasobne. Pokud po insertu zjistime, ze je delka retezce delsi nez nejaka konstanta d_i (kterou zatim neumime urcit optimalne), tak prehasujem jinou dostupnou fci.

H = soubor hasovacich fci (do tabulky vel. m)

Pro kazdou vstupni mnozinu ex. "hodne" fci z H, ktere se chovaji dobre(malo kolizi).

Def: Soubor fci z H (U -> {0, 1, ...m-1} se nazyva c-univerzalni, pokud $ \forall x<>y \in U;\ |{h \in H; h(x) = h(y)}| \leq\ \cfrac{c |H|}{m} $

Konstrukce H: Predpokladejme: U = (0, 1, ... N-1), N prvocislo (pro kazde prirozene cislo existuje prvocislo mezi tim cislem a dvounasobkem, takze prinejhorsim natahnem mnozinu na dvojnasobek, aby tohle platilo). $ H = {H_{a,b} (x) = ((ax + b)\ mod\ N)\ mod\ m: a,b = 0..N-1} $, tj. vsechny linearni fce.

Tvrzeni: takto zkonstruovane H je

$ \left\lceil\cfrac{N}{m}\right\rceil^2\Big /\left(\cfrac{N}{m}\right)^2 $ - univerzalni system

.. tim jsme ukazali, ze nejake c-univerzalni systemy existuji

Veta: necht H je c-univerzalni system, pak pro kazdou mnozinu $ S \subset U,\ |S| = n $ a pro kazde x je ocekavany cas operaci insert/member/delete(x) roven:

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

.. je to prumer pres vsechny fce z H, ne pres vsechny vstupy. Takze kdyz to pro jednu fci neni splneno, muzu nahodne vybrat jinou a mam slusnou sanci, ze pro ni to, na tom samem vstupu, splneno bude.

Veta: necht H je c-univerzalni system, pak pro kazdou mnozinu $ S \subset U,\ |S| = n $ a pro kazde x plati, pokud je $ \mu $ prumerna delka retezce pro prvky s hodnotou h(x), pak:

$ \forall t>1 $ je pravdepodobnost, ze je retezec $ \geq \mu t $ mensi nez $ \cfrac{1}{t} $

Veta: kdyz H je c-univerzalni system na universu U = {0,1,...N-1} hashujici do tabulky velikosti m, pak:

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

Perfektní hašování

wen:Perfect hash function
  • Hasovani takove, kde nejsou kolize.
  • Operace insert je bud zakazana, nebo se resi bufferem obcasne zahesovavanym do hlavni tabulky.

Chceme pro danou mnozinu S \subset U nalezt fci h: U -> {0, 1, ..m-1} takovou, ze

  • 1) h je perfektni vuci S
  • 2) h(x) je rychle spocitatelna
  • 3) m je srovnatelne s n
  • 4) h nevyzaduje prilis pameti

Konstrukce:
$ h_k(x) = (k*x\ mod\ N)\ mod\ m $
N = |U|

predpoklad: S pevne dana
$ b_k^i $ je pocet $ x \in S;\ h_k(x) = i $
pak existuje k takove, ze:

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

.. zkousim jednotlive fce tak dlouho, nez najdu parametr k, pro ktery je suma druhych mocnin delek retezcu < ten vyraz.

Dusledky:

  • 1) pokud m=n (my volime m), pak:
$ \exists k;\ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $ a k nalezneme v $ O(n*N) $
  • 2) pokud m= 1+n(n-1), pak exists k; h_k je perfektni (suma vyjde < n+2 a pokud by nebyla perfektni, tak je tam alespon jeden retez delky aspon dva, jeho mocnina je 4 a 4 + (n-1) jednoprvkovych retezu dava delku > n+2; spor). Tohle ale nevyhovuje pozadavku 3).
  • 3) Konstrukce do prostoru <3n. Vezmeme fci z dusledku 1) a rozdelime S do m mnozin podle h_k(s). Pro tyto mnoziny nalezneme perfektni fci podle dusledku dva. Tahle kombinace dvou fci pak tvori vyslednou perfektni fci. do <3n se to vleze, protoze pro ty male fce mam k dispozici druhou mocninu prostoru (vzhledem k poctu prvku) a:
$ \sum_{i=0}^{m-1} (b_k^i)^2 < 3n $
 :)

Stale to jeste nesplnuje podminku 4). Dalsi uprava se dela pomoci magie.

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

Semidynamizace

Máme rozložitelný vyhledávací problém f a pro něj statickou struturu, 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 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ě.

Dynamizace

Ještě přidáme falešný DELETE (škrtnutí prvku v čase O(n)).

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

Tato část je neúplná a potřebuje rozšířit. co přesně bude jako pak reprezentovat A? sada spojových seznamů?

Mapování datových struktur do stránek vnější paměti počítače

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

Časová složitost algoritmů vyjádřená v počtu I/O operací

- IMHO patri pod predchozi otazku

Vícerozměrné datové struktury

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

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

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

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)

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

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