Nazdar ludia,
po fiasku, ktore som zazil na poslednej skuske som bol nuteny poriadne pozriet tomu Fagin hashovaniu na zub.
Na cvikach to sice bolo fajn, skoda ze moje zapisky su smutne a ja si nepamatam delikatne situacie.
Na wikipedii je jeden clanok, ktory je ale uplne odveci a nepochopil som z toho nic.
V knihe Základy Implementace souborů a databazí je to fajn, az na nejasnosti, ktore ma doteraz sprevadzaju.
Teraz sa mi konecne podarilo najst nieco, co vyzera pomerne slusne. Je to subor (.pdf), ktory som vlozil do prilohy. Jedna sa o akysi clanok, ktoreho odkaz som nasiel na wikipedii. Nechal som ho nepozmeneny (su tam aj ine zaujimave veci) a Fagin tam zacina od strany 20. Je to pekne popisane s obrazkami a vysvetleniami krokov, ale POZOR, je tam jedna drobna chybicka. Na str. 25, posledny odsek, ma tam byt i3 namiesto i1. Aspon myslim, ine chybicky som si nevsimol.
Otazka je, v com sa ten clanok hlavne lisi od knihy ?
Napriklad v knihe (str. 51) je "dosahnuti maxima" hlbky stranky vyjadrene ako lambda=beta. Dodnes tomu nerozumiem, ale po skuske som si isty, ze je to dolezite. Podla clanku to vyzera, ze to "dosahnuti maxima" je dosiahnutie maximalnej velkosti stranky (pravdepodobne staticky zadana). Podla knihy som ani len netusil, ze tie stranky su obmedzene velkostou.
Dalej je tam napisane, ze po vlozeni do stranky, ktorej lokalna hlbka je rovna hlbke adresara, nastava zdvojnasobenie adresara. Podla clanku to sice je pravda, ale stranka musi byt navyse plna ! Naozaj neviem, ktore z toho je spravne, ale to s tou plnou strankou sa mi to paci viac .
Mohli by ste prosim niekto, kto mate chut, pripadne to riesite, alebo je vam to cele davno jasne, do tychto zalezitosti vniest trochu svetla ?
Budem nesmierne vdacny za akukolvek radu .
Rozšiřitelné hašování - Fagin
- DZuXO
- Matfyz(ák|ačka) level I
- Příspěvky: 11
- Registrován: 20. 1. 2009 11:28
- Typ studia: Informatika Bc.
- Login do SIS: 55020672
Rozšiřitelné hašování - Fagin
- Přílohy
-
- lecture.extendible.hashing.pdf
- (85.09 KiB) Staženo 384 x
UIRA — UIRA Isn't a Recursive Acronym.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 86
- Registrován: 21. 1. 2009 20:08
- Typ studia: Informatika Bc.
Re: Rozšiřitelné hašování - Fagin
Nazdar Martine, zkusim to sem hodit, aspon si v tom sam udelam jasno =)DZuXO píše: Mohli by ste prosim niekto, kto mate chut, pripadne to riesite, alebo je vam to cele davno jasne, do tychto zalezitosti vniest trochu svetla ?
Budem nesmierne vdacny za akukolvek radu .
Zakladem je adresar. To je struktura, kterou si drzis vetsinou v operacni pameti. Pokud by se tam nevesel, musi se to brat z disku, ale pak by cely algoritmus rapidne ztratil na efektivite. Adresar je tabulka (predstavuj si ho treba jako asociativni pole), kde kazdy radek obsahuje dve informace.
- prefix - oznacme d delku toho prefixu (pro vsechny zaznamy v adresari je stejna)
- pointer na prislusnou stranku
Kdyz hledas prvek s klicem K, spocitas h(K) (zahashujes klic) a vezmes prvnich d bitu z te hodnoty (ono by nevadilo ani brat je odzadu, ale tak uz nam to nadefinoval). Tenhle prefix vyhledas v adresari a dostanes pointer na stranku, kde se zaznam nachazi. Tu nactes do operacni pameti a pak ji (zanedbatelne rychle) prohledas.
Insert probiha nasledovne. Stejne jako pri hledani zjistis pointer na stranku, kam zaznam patri. Pokud se tam zaznam vejde, vlozis ho tam. Pokud ne, musi se stranka rozstepit. U kazde stranky si drzis hodnotu d', ktera rika, podle kolika bitu jsou rozlisovany zaznamy ve strance (tyhle hodnoty si drzis v operacni pameti). Pokud d' < d, tak urcite na stranku vedou z adresare aspon 2 pointery. V tom pripade staci naalokovat novou stranku, prevest na ni prislusny pointer v adresari, a pak vezmes zaznamy z pretecene stranky a ty rozdelis mezi ty dve stranky podle toho, kteremu prefixu odpovidaji. Pak obema strankam zvysis d'. V pripade, ze d = d', na stranku vede jen jeden pointer. Ted prichazi chvile na stepeni adresare. Zvetsis d o jednicku (prodlouzis prefixy v adresari). Kazdy zaznam v adresari zduplikujes (velikost adresare se zdvojnasobi), vzdycky udelas jeden radek, kde k prefixu pridas 0, a druhemu pridas k prefixu 1. Tim docilis, ze na kazdou stranku ukazujou aspon 2 pointery a muzes postupovat podle pripadu d' < d.
Delete je celkem easy, proste zaznam oznacis za neplatny (nebo ho fyzicky smazes). Problem muze byt, pokud by melo dojit ke slucovani stranek. Po delete se ujistis, jestli by nesla ta stranka spojit se sesterskou (tj. tou, jejiz prefix konci na opacny bit). Pokud by sla (tj. dohromady ty stranky obsahuji min prvku nez b), pak je sloucis. Po slouceni se jeste podivas na d' vsech stranek. Pokud by vsechna byla ostre mensi nez d, pak muzes sloucit adresar - tj. zmensit d o jednicku a provest opacnou operaci ke stepeni adresare. U delete je dobre pouzit nejaky treshold pro slucovani stranek/adresare, aby ti po sobe jdouci inserty a delety stejnych prvku nezpusobily caste "pulzovani" adresare nebo slucovani a rozdelovani stranek.
Mne samotneho by zajimaly pocty IO operaci, tak se je pokusim nacrtnout.
- fetch - vzdycky staci precist 1 stranku (adresar je v pameti), tedy TF = r + s + btt
- insert - pokud nestepis, tak staci TF + 2r (nactes stranku, pockas, az se plotna otoci, a zapises zpatky); pokud stepis (a je jedno, jestli jen stranku, nebo cely adresar!), tak TF + 2r + s + r (jednu stranku prectes, zapises ji zpatky, a pak zapises novou stranku - ta muze byt na disku uplne jinde)
- delete - stejne jako insert (pri slucovani stranek u te smazane musis poznacit, ze je neplatna, takze do ni stejne musis zapsat).
-
- Matfyz(ák|ačka) level I
- Příspěvky: 33
- Registrován: 13. 12. 2008 16:29
- Typ studia: Informatika Bc.
Re: Rozšiřitelné hašování - Fagin
Ještě bych dodal, že insert/delete to může být trochu složitější.
U deletu lze teoreticky slučovat opakovaně (třeba až do chvíle, kdy se adresář zmenší na velikost 1), pseudokód ve skriptech tuhle možnost neobsahuje a v odstavci pod ním je jenom napsáno něco jako, že pro zjednodušení neuvažujeme opakované slučování. Když jsem před zkouškou zkoumal, jak vlastně ten delete má fungovat, vygooglil jsem tenhle dokument
http://www.site.uottawa.ca/~lucia/cours ... /lect19.ps
(pozor: narozdíl od toho, jak se to učíme my, tady berou bity od konce, ale jinak by to mělo být stejné.) Tam je příklad, kdy delete vyvolá hned několik slučování.
U insertu se může stát, že vkládaný záznam se do stránky nejenže nevejde, ale s ostatními záznamy ve stránce nelze rozlišit podle (d+1) bitu, ale třeba až podle (d+3) bitu, tím pádem musíme adresář rozšířit hned 3x, abychom ty problematické záznamy mohli rozhodit do dvou stránek.
U deletu lze teoreticky slučovat opakovaně (třeba až do chvíle, kdy se adresář zmenší na velikost 1), pseudokód ve skriptech tuhle možnost neobsahuje a v odstavci pod ním je jenom napsáno něco jako, že pro zjednodušení neuvažujeme opakované slučování. Když jsem před zkouškou zkoumal, jak vlastně ten delete má fungovat, vygooglil jsem tenhle dokument
http://www.site.uottawa.ca/~lucia/cours ... /lect19.ps
(pozor: narozdíl od toho, jak se to učíme my, tady berou bity od konce, ale jinak by to mělo být stejné.) Tam je příklad, kdy delete vyvolá hned několik slučování.
U insertu se může stát, že vkládaný záznam se do stránky nejenže nevejde, ale s ostatními záznamy ve stránce nelze rozlišit podle (d+1) bitu, ale třeba až podle (d+3) bitu, tím pádem musíme adresář rozšířit hned 3x, abychom ty problematické záznamy mohli rozhodit do dvou stránek.