Fagin

Petr

Fagin

Příspěvek od Petr »

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!
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 9. 6. 2005 14:13
Typ studia: Informatika Bc.
Bydliště: Prágl
Kontaktovat uživatele:

Příspěvek od dr.Bik »

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.
Jednou z hlavních příčin zániku Římského imperia bylo, že bez nuly nemohli Římané ohlásit úspěšné ukončení svých céčkových programů.
Petr

Příspěvek od Petr »

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?
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 9. 6. 2005 14:13
Typ studia: Informatika Bc.
Bydliště: Prágl
Kontaktovat uživatele:

Příspěvek od dr.Bik »

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 :)
Jednou z hlavních příčin zániku Římského imperia bylo, že bez nuly nemohli Římané ohlásit úspěšné ukončení svých céčkových programů.
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 9. 6. 2005 14:13
Typ studia: Informatika Bc.
Bydliště: Prágl
Kontaktovat uživatele:

Příspěvek od dr.Bik »

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.
Jednou z hlavních příčin zániku Římského imperia bylo, že bez nuly nemohli Římané ohlásit úspěšné ukončení svých céčkových programů.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

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.
Plug 'n' Pray.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

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?
Plug 'n' Pray.
Uživatelský avatar
dr.Bik
Matfyz(ák|ačka) level II
Příspěvky: 73
Registrován: 9. 6. 2005 14:13
Typ studia: Informatika Bc.
Bydliště: Prágl
Kontaktovat uživatele:

Příspěvek od dr.Bik »

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
Jednou z hlavních příčin zániku Římského imperia bylo, že bez nuly nemohli Římané ohlásit úspěšné ukončení svých céčkových programů.
Petr

Příspěvek od Petr »

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 :)
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

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 :(.
Plug 'n' Pray.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

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 :)
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Příspěvek od Tuetschek »

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 :)
Plug 'n' Pray.
Odpovědět

Zpět na „2006“