Fagin
Fagin
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!
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!
- 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:
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.
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ů.
Diky za odpoved.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.
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?
- 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:
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
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ů.
- 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:
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.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?
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ů.
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
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.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?
Plug 'n' Pray.
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
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?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
Plug 'n' Pray.
- 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:
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 adresariTuetschek 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?
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ů.
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.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.
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
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
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 .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?
Plug 'n' Pray.
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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 bylPetr 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.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.
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
- Tuetschek
- Supermatfyz(ák|ačka)
- Příspěvky: 657
- Registrován: 15. 6. 2005 13:54
- Typ studia: Nestuduji ale učím na MFF
- Login do SIS: duseo7af
- Kontaktovat uživatele:
Ja bych rekl ze to jinak byt nemuze, to chapu stejnetwoflower 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
Plug 'n' Pray.