Fagin

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Fagin

od Tuetschek » 7. 1. 2007 22:56

twoflower píše:Ja sourozeneckou stranku chapu tak, ze musi mit stejnou lokalni hloubku, jako ta druha stranka a zaroven maji stejnych prvnich (d' - 1) bitu, kde d' je jejich lokalni hloubka. Ale to je jen mozna blbe okoukane z toho jedineho prikladu, ktery na cviceni byl :)
Ja bych rekl ze to jinak byt nemuze, to chapu stejne :)

od twoflower » 7. 1. 2007 22:48

Petr píše:
Tuetschek píše:Pokud ten adresar slucujes, musis ho nacist cely -- pokud teda k zapisu potrebujes mit pripravenou celou 1 stranku (coz asi jo), jinak by to slo postupne po castech.
Za jakych podminek vlastne v rozsiritelnem hasovani dochazi ke slucovani stranek, pripadne "smrskavani" adresare? Ve slidech to neni a na cviceni jsem to moc nepochopil, tam to vypadalo, ze i kdyz se mi vyprazdni stranka, tak pokud ma lokalni hloubku < hloubku adresare, nedeje se vubec nic.

Pokud ma stejnou hloubku jako je hloubka adresare, tak i kdyz v ni zbyde jeste jeden prvek, tak ji sloucim. A to predpokladam tak, ze vezmu sourozeneckou stranku (coz taky presne nevim, co je, asi musi mit taky lokalni hloubku == hloubce adresare) a sloucim je, pricemz vysledna stranka ma lokalni hloubku zmensenou o 1?

Je to jen snuska mych pocitu :)
Ja sourozeneckou stranku chapu tak, ze musi mit stejnou lokalni hloubku, jako ta druha stranka a zaroven maji stejnych prvnich (d' - 1) bitu, kde d' je jejich lokalni hloubka. Ale to je jen mozna blbe okoukane z toho jedineho prikladu, ktery na cviceni byl :)

od Tuetschek » 7. 1. 2007 22:44

Petr píše:Za jakych podminek vlastne v rozsiritelnem hasovani dochazi ke slucovani stranek, pripadne "smrskavani" adresare? Ve slidech to neni a na cviceni jsem to moc nepochopil, tam to vypadalo, ze i kdyz se mi vyprazdni stranka, tak pokud ma lokalni hloubku < hloubku adresare, nedeje se vubec nic.

Pokud ma stejnou hloubku jako je hloubka adresare, tak i kdyz v ni zbyde jeste jeden prvek, tak ji sloucim. A to predpokladam tak, ze vezmu sourozeneckou stranku (coz taky presne nevim, co je, asi musi mit taky lokalni hloubku == hloubce adresare) a sloucim je, pricemz vysledna stranka ma lokalni hloubku zmensenou o 1?
Jj cely adresar slucujes, az kdyz v nem neni zadna stranka ktera by mela stejnou hloubku jako adresar ... aspon doufam ... mozna to neni definovany vubec ... cert vi :(.

od Petr » 7. 1. 2007 22:42

Tuetschek píše:Pokud ten adresar slucujes, musis ho nacist cely -- pokud teda k zapisu potrebujes mit pripravenou celou 1 stranku (coz asi jo), jinak by to slo postupne po castech.
Za jakych podminek vlastne v rozsiritelnem hasovani dochazi ke slucovani stranek, pripadne "smrskavani" adresare? Ve slidech to neni a na cviceni jsem to moc nepochopil, tam to vypadalo, ze i kdyz se mi vyprazdni stranka, tak pokud ma lokalni hloubku < hloubku adresare, nedeje se vubec nic.

Pokud ma stejnou hloubku jako je hloubka adresare, tak i kdyz v ni zbyde jeste jeden prvek, tak ji sloucim. A to predpokladam tak, ze vezmu sourozeneckou stranku (coz taky presne nevim, co je, asi musi mit taky lokalni hloubku == hloubce adresare) a sloucim je, pricemz vysledna stranka ma lokalni hloubku zmensenou o 1?

Je to jen snuska mych pocitu :)

od dr.Bik » 7. 1. 2007 22:41

Tuetschek píše:To nejak nechapu -- pokud bys mel od zacatku jen 2 stranky -- tu ze ktere odebiras a nejakou 1 dalsi, kde je jen 1 zaznam, tak je proste na 2xREAD + 1xWRITE slejes a zbytek dodelas v adresari, ne?
Ja to myslel tak, ze ty 2 stranky jsou jediny, ktery obsahujou nejaky data. Potom ty ostatni (prazdny) musim stejne precist, protoze nemam kristalovou kouli, abych to vedel. Nicmene mohl bych udelat neco ve stylu null pointeru (to bych v praxi asi udelal), ale tedka fakt nevim, jestli ta metoda neco takovyho zna a obavam se, ze pokud by neznala, tak by se nejspis moje kreativita nemusela setkat s kladnym ohlasem opravujiciho. Pokud zna, tak by opravdu stacilo slejvat jen jednou a vyresit si to v adresari

od Tuetschek » 7. 1. 2007 22:34

dr.Bik píše:S IO operacema to bude horsi:
Urcite budu potrebovat 2xRead na nacteni adresare. Potom 1xRead na stranku, ze ktery chci mazat. Martyrium nastane pri slejvani. Urcite potrebuju jeden Read na zjisteni, jak je zaplnena sousedni (musi bejt stejne velka) stranka.
Prinejhorsim se mi muze stat, ze ze stranky s |S| zaznamy mazu a sousedni ma 1 zaznam a jinak neni nic (to se stat muze, kdyz vsechny klice maj stejne zacinajici hashe), pak se mi to vsechno smrskne do jedny stranky a ja nactu n stranek, kde n je to cislicko, ktery urcuje, podle kolika prvnich bitu hashe se to rozhazuje.
Suma sumarum
(3+n) krat Read a 3 krat Write (2 stranky na adresar a jedna nova stranka, ale v tech ostatnich strankach necham bordel)

pozn. |S| je pocet zaznamu ve strance
To nejak nechapu -- pokud bys mel od zacatku jen 2 stranky -- tu ze ktere odebiras a nejakou 1 dalsi, kde je jen 1 zaznam, tak je proste na 2xREAD + 1xWRITE slejes a zbytek dodelas v adresari, ne?

od Tuetschek » 7. 1. 2007 22:31

Petr píše:Nestacil by pro nacteni adresare jen jeden buffer? Nevim, jestli to neni kravina, ale kdyz zahashuji klic, ktery chci odstranit, vim hned, kde v adresari se nachazi pointer na prislusny zaznam a tak by mi mozna stacilo nacist jen relevantni stranku s adresarem, nebo ne?
Pokud ten adresar slucujes, musis ho nacist cely -- pokud teda k zapisu potrebujes mit pripravenou celou 1 stranku (coz asi jo), jinak by to slo postupne po castech.

od dr.Bik » 7. 1. 2007 22:28

Petr píše:Nestacil by pro nacteni adresare jen jeden buffer? Nevim, jestli to neni kravina, ale kdyz zahashuji klic, ktery chci odstranit, vim hned, kde v adresari se nachazi pointer na prislusny zaznam a tak by mi mozna stacilo nacist jen relevantni stranku s adresarem, nebo ne?
Ja bych rekl, ze je rozumny nechat si celej adresar v pameti, protoze je mozny, ze ho pak budes celej prepisovat po vymazu, takze by clovek usetril trosku pameti, ale zase by ho to stalo 2x Read navic.

od dr.Bik » 7. 1. 2007 22:25

S IO operacema to bude horsi:
Urcite budu potrebovat 2xRead na nacteni adresare. Potom 1xRead na stranku, ze ktery chci mazat. Martyrium nastane pri slejvani. Urcite potrebuju jeden Read na zjisteni, jak je zaplnena sousedni (musi bejt stejne velka) stranka.
Prinejhorsim se mi muze stat, ze ze stranky s |S| zaznamy mazu a sousedni ma 1 zaznam a jinak neni nic (to se stat muze, kdyz vsechny klice maj stejne zacinajici hashe), pak se mi to vsechno smrskne do jedny stranky a ja nactu n stranek, kde n je to cislicko, ktery urcuje, podle kolika prvnich bitu hashe se to rozhazuje.
Suma sumarum
(3+n) krat Read a 3 krat Write (2 stranky na adresar a jedna nova stranka, ale v tech ostatnich strankach necham bordel)

pozn. |S| je pocet zaznamu ve strance


Prosim, zkontrolujte to nekdo, nejsem si timto jisty - kritiku vitam, jelikoz mi zejtra muze prinest body navic :)

od Petr » 7. 1. 2007 22:17

dr.Bik píše:Prvni bych resil takto:
2 stranky potrebuji na nacteni adresare, potom nactu stranku, ze ktery mazu. Dokud je zaplneni takove, ze muzu sloucit se sousedni strankou, tak slevam, tzn. musim ji nacist taky - tzn. pohodlne by to slo s 4 strankama v pameti

Je otazka, jestli se mysli, kolik minimalne, nebo kolik rozumne je potreba, slo by to i se dvema, za predpokladu neustalyho zonglovani, ale pak me to bude stat vic IO operaci, takze bych byl pro 4.
Diky za odpoved.

Nestacil by pro nacteni adresare jen jeden buffer? Nevim, jestli to neni kravina, ale kdyz zahashuji klic, ktery chci odstranit, vim hned, kde v adresari se nachazi pointer na prislusny zaznam a tak by mi mozna stacilo nacist jen relevantni stranku s adresarem, nebo ne?

od dr.Bik » 7. 1. 2007 22:11

Prvni bych resil takto:
2 stranky potrebuji na nacteni adresare, potom nactu stranku, ze ktery mazu. Dokud je zaplneni takove, ze muzu sloucit se sousedni strankou, tak slevam, tzn. musim ji nacist taky - tzn. pohodlne by to slo s 4 strankama v pameti

Je otazka, jestli se mysli, kolik minimalne, nebo kolik rozumne je potreba, slo by to i se dvema, za predpokladu neustalyho zonglovani, ale pak me to bude stat vic IO operaci, takze bych byl pro 4.

Fagin

od Petr » 7. 1. 2007 21:59

Ahoj,

nevite, jak se resi tohle?

Rušíme záznam v souboru organizovaném v rozšířitelném (Faginově) hašování
s adresářem ve dvou stránkách na disku.
· Kolik bufferů (1 buffer = 1 stránka) je třeba alokovat ve vnitřní paměti?
· Kolik I/O operací je třeba v nejhorším případě (zkracuje se adresář)?

Diky moc!

Nahoru