pocet pristupu s indexovymi souboy s bitovou mapou
- Hugo
- Donátor
- Příspěvky: 233
- Registrován: 2. 6. 2005 13:31
- Typ studia: Informatika Mgr.
- Bydliště: treti kontejner zleva
- Kontaktovat uživatele:
pocet pristupu s indexovymi souboy s bitovou mapou
asi nejsem jediny, koho by zajimala spravna odpoved na otazku 3 z 30.1.06
Zvlaste druha a treti otazka - mrazi me trochu v zadech, kdyz vidim, jak to je obodovane..
Zvlaste druha a treti otazka - mrazi me trochu v zadech, kdyz vidim, jak to je obodovane..
- Hugo
- Donátor
- Příspěvky: 233
- Registrován: 2. 6. 2005 13:31
- Typ studia: Informatika Mgr.
- Bydliště: treti kontejner zleva
- Kontaktovat uživatele:
jeste poslu presne zadani - Mejme indexovany soubor s b = 6, v nem je 597 ulozenych zaznamu. Indexy jsou tvoreny B+ stromem (m=60, primarni klic) a bitovou mapou (prislusny atribut nabyva 6 hodnot). Predpokladejme, ze zadna data nejsou nactena do pameti.
a) spoctete kolik pristupu na disk je potreba pro vyhledani zaznamu dle primarniho klice.
b) kolik nejmene pristupu na disk pro ulozeni noveho zaznamu do souboru
c)Predpokladejme, ze uvedeny soubor je umisten na disku s parametry s=8.5ms, r=4.2ms, btt = 0.2ms. Kolik casu budeme prinejhorsim potrebovat na pridani zaznamu?
Trochu na hlavu je, ze kdyz student vubec nevedel, co s timhle nahore, a vse ostatni mel bez chyby, tak uz mel za 4. To neni moc vyvazene..
a) spoctete kolik pristupu na disk je potreba pro vyhledani zaznamu dle primarniho klice.
b) kolik nejmene pristupu na disk pro ulozeni noveho zaznamu do souboru
c)Predpokladejme, ze uvedeny soubor je umisten na disku s parametry s=8.5ms, r=4.2ms, btt = 0.2ms. Kolik casu budeme prinejhorsim potrebovat na pridani zaznamu?
Trochu na hlavu je, ze kdyz student vubec nevedel, co s timhle nahore, a vse ostatni mel bez chyby, tak uz mel za 4. To neni moc vyvazene..
-
- Matfyz(ák|ačka) level II
- Příspěvky: 92
- Registrován: 2. 6. 2005 22:55
- Typ studia: Informatika Mgr.
- Login do SIS: klimj4bm
- Bydliště: Praha - Dejvice
- Kontaktovat uživatele:
Nevim jestli je to spravne, ale muj tip je nasledujici
a) primarni klic - pouzivam B+ strom.
m = 60
vyska = log60(597) = 1,56, horni cela cast = 2
takze 2 na nacteni adresy v primarnim souboru + 1 za nacteni zaznamu v prim. souboru, dohromady 3
b) nejlepsi pripad pridani prvku: zadne stepeni v B strome
2 cteni cesty k prvku v Bstrome, 1 zapis do listu
1 cteni bloku, kam pridam zaznam
1 zapis bloku do primarniho souboru
1 cteni bit. mapy
1 zapis bit. mapy
celkem 7 pristupu na disk
c) nejhorsi pripad pridani zaznamu ma navic jeste zapsani druhe urovne Bstromu a zapsani noveho listu.
Teď ještě jde o to, zda update bloku mohu počítat jako (s + r + btt + 2r + btt) nebo 2*(s + r + btt)
Takze:
2x update v Bstromu, 1x zapsat novy list
1x update v prim. souboru
1x update bit. mapy
a) primarni klic - pouzivam B+ strom.
m = 60
vyska = log60(597) = 1,56, horni cela cast = 2
takze 2 na nacteni adresy v primarnim souboru + 1 za nacteni zaznamu v prim. souboru, dohromady 3
b) nejlepsi pripad pridani prvku: zadne stepeni v B strome
2 cteni cesty k prvku v Bstrome, 1 zapis do listu
1 cteni bloku, kam pridam zaznam
1 zapis bloku do primarniho souboru
1 cteni bit. mapy
1 zapis bit. mapy
celkem 7 pristupu na disk
c) nejhorsi pripad pridani zaznamu ma navic jeste zapsani druhe urovne Bstromu a zapsani noveho listu.
Teď ještě jde o to, zda update bloku mohu počítat jako (s + r + btt + 2r + btt) nebo 2*(s + r + btt)
Takze:
2x update v Bstromu, 1x zapsat novy list
1x update v prim. souboru
1x update bit. mapy
- Hugo
- Donátor
- Příspěvky: 233
- Registrován: 2. 6. 2005 13:31
- Typ studia: Informatika Mgr.
- Bydliště: treti kontejner zleva
- Kontaktovat uživatele:
Tady bude asi nejlepsi rozepisovat odpoved stromovite, abychom pokryli vsechny mozne varianty zadani:)
Ale protoze je jen indexovy soubor a ne indexsekvencni (neni to usporadane), tak si myslim, ze si musi nekde drzet stav naplnenosti posledniho bloku, do ktereho zapisoval (aby vedel, zda nedat offset na nove zapisovany blok uz pri vkladani do B-stromu).. Urcite by to bylo rychlejsi nez to vzdy kontrolovat ctenim:)
Ale protoze je jen indexovy soubor a ne indexsekvencni (neni to usporadane), tak si myslim, ze si musi nekde drzet stav naplnenosti posledniho bloku, do ktereho zapisoval (aby vedel, zda nedat offset na nove zapisovany blok uz pri vkladani do B-stromu).. Urcite by to bylo rychlejsi nez to vzdy kontrolovat ctenim:)
- 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 myslim ze to je dobre ... s tou naplnenosti bloku nevim, asi bych nepredpokladal ze si to nekde drzim ...
Akorat bych dodal ze vyska stromu nemusi byt vzdy dana tim logaritmem -- da se spocitat min. a max. pocet prvku pro B-strom s danym m a vyskou (h): min = 2([m/2]-1)([m/2])^(h-2) ([] je horni cela cast) a max. = (m-1)m^(h-1) -- a rozsahy min. - max. se pro jednotliva h kryji - napr. B-strom pro m=60 s 2000 prvky muze mit vysku 2 i 3 protoze 1740 (min. pro 3) < 2000 < 3540 (max. pro 2).
No ale pro 597 to opravdu muze byt jenom 2.
Jeste muze byt otazka, zda se bitova mapa vejde do 1 bloku. Ale myslim ze pro (597/8 )*6 = 448 bajtu by to melo byt v poradku.
Pro to vkladani zaznamu bych asi rewrite pouzival (nebo jim napsal obe verze at si vyberou ), takze by mi to vyslo:
2(s+r+btt) + 2r + (s+r+btt) na update stromu
+ (s+r+btt) + 2r na update bloku v prim. souboru
+ (s+r+btt) + 2r na update bitmapy.
Celkem 5(s+r+btt) + 6r = 95.2 ms.
Akorat bych dodal ze vyska stromu nemusi byt vzdy dana tim logaritmem -- da se spocitat min. a max. pocet prvku pro B-strom s danym m a vyskou (h): min = 2([m/2]-1)([m/2])^(h-2) ([] je horni cela cast) a max. = (m-1)m^(h-1) -- a rozsahy min. - max. se pro jednotliva h kryji - napr. B-strom pro m=60 s 2000 prvky muze mit vysku 2 i 3 protoze 1740 (min. pro 3) < 2000 < 3540 (max. pro 2).
No ale pro 597 to opravdu muze byt jenom 2.
Jeste muze byt otazka, zda se bitova mapa vejde do 1 bloku. Ale myslim ze pro (597/8 )*6 = 448 bajtu by to melo byt v poradku.
Pro to vkladani zaznamu bych asi rewrite pouzival (nebo jim napsal obe verze at si vyberou ), takze by mi to vyslo:
2(s+r+btt) + 2r + (s+r+btt) na update stromu
+ (s+r+btt) + 2r na update bloku v prim. souboru
+ (s+r+btt) + 2r na update bitmapy.
Celkem 5(s+r+btt) + 6r = 95.2 ms.
Plug 'n' Pray.
- MyS
- Donátor
- Příspěvky: 178
- Registrován: 22. 9. 2004 00:13
- Typ studia: Informatika Bc.
- Bydliště: The city of Dobříš
- Kontaktovat uživatele:
...IMHO se zapisuje jeste extra ten novy list a koren, cili 2(s+r+btt) + 2r + 2*(s+r+btt)2(s+r+btt) + 2r + (s+r+btt) na update stromu
To podle me vyplyva z toho, ze 597:6=99.5,cili posledni blok neni cely, cili RW je nutnyTo si taky myslim, jenze asi musis zjistit, ze ten co nactes je plny
We don't need no education!
- 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:
Jo pravda ... chybicka se vloudila ... a to s tim poctem zaznamu a zaplnenosti je dobry ... jedine nevim jestli muzes predpokladat ze primarni soubor je souvisly ... po nejakych deletech a tak by nemusel ?MyS píše:...IMHO se zapisuje jeste extra ten novy list a koren, cili 2(s+r+btt) + 2r + 2*(s+r+btt)
...
To podle me vyplyva z toho, ze 597:6=99.5,cili posledni blok neni cely, cili RW je nutny
Plug 'n' Pray.
Asi mi to ted vubec nepali, ale nechapu, jak by mohl mit ten strom vysku 2. Pokud m = 60, tak krome korene musi mit kazdy uzel minimalne 30 potomku, tedy v jakemsi "minimalnim" pripade bude mit koren dva potomky a kazdy z nich 30 potomku => to mame 60 uzlu na listove urovni (pokud vyska = 2) a kazdy z techto uzlu ma minimalne 29 klicu => nas strom ma 1740 klicu.
Podle mne by mel mit vysku 1..
Podle mne by mel mit vysku 1..
-
- Matfyz(ák|ačka) level I
- Příspěvky: 34
- Registrován: 10. 11. 2006 20:41
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
A taky pozor na ty bitmapy. Na nasem cviceni tenhle tyden nam vyucujici potvrdil tohle... Ta bitmapa se sklada z tolika vektoru, kolik hodnot ma. A kazdy ten vektor se umistuje obvykle zvlast (jsou tak drazsi inserty, ale je levnejsi vyhledavani) - tudiz na insert bude treba prave tolik cteni a prave tolik zapisu, kolik je moznych hodnot daneho atributu. Pokud by se ty bitmapy umistovaly prokladane (pro kazdy vektor vyhradit v kazdem bloku vyhradit stejnou cast), pak pro jedno vyhledavani je nutne nacitat uplne celou bitmapu... Vzhledem k tomu, ze insert je vetsinou mene castejsi nez select, tak je asi lepsi ten prvni pristup. Ale kdyz se to specifikuje, ze berete takove a takove usporadani, tak by to projit melo i tim druhym.
Takove ty metody typu "to ma pet hodnot, to se vejde do tri bitu" uz nejsou tak docela bitmapa, ale index podle hodnot - na nejake jednoduche and/or operace se uz neda ani myslet. Tudiz to asi ne.
Takove ty metody typu "to ma pet hodnot, to se vejde do tri bitu" uz nejsou tak docela bitmapa, ale index podle hodnot - na nejake jednoduche and/or operace se uz neda ani myslet. Tudiz to asi ne.
- 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:
No ale kdyz koren ma potomky a ty maji potomky, tak uz je to 3 .JirkaL píše:Asi mi to ted vubec nepali, ale nechapu, jak by mohl mit ten strom vysku 2. Pokud m = 60, tak krome korene musi mit kazdy uzel minimalne 30 potomku, tedy v jakemsi "minimalnim" pripade bude mit koren dva potomky a kazdy z nich 30 potomku => to mame 60 uzlu na listove urovni (pokud vyska = 2) a kazdy z techto uzlu ma minimalne 29 klicu => nas strom ma 1740 klicu.
Podle mne by mel mit vysku 1..
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:
No a kdyz mas bitmapu, kde se ti vektory pro vsechny mozne hodnoty vejdou do 1 bloku (na 1 zaznam pro 1 hodnotu potrebujes 1 bit)?fissie píše:A taky pozor na ty bitmapy. Na nasem cviceni tenhle tyden nam vyucujici potvrdil tohle... Ta bitmapa se sklada z tolika vektoru, kolik hodnot ma. A kazdy ten vektor se umistuje obvykle zvlast
...
Napr. tech 597 zaznamu * 6 hodnot = 3582 bitu = cca 450 bajtu ...
Plug 'n' Pray.
Ne, to je 2, vyska je nejdelsi cesta od korene do listu..Tuetschek píše:No ale kdyz koren ma potomky a ty maji potomky, tak uz je to 3 .JirkaL píše:Asi mi to ted vubec nepali, ale nechapu, jak by mohl mit ten strom vysku 2. Pokud m = 60, tak krome korene musi mit kazdy uzel minimalne 30 potomku, tedy v jakemsi "minimalnim" pripade bude mit koren dva potomky a kazdy z nich 30 potomku => to mame 60 uzlu na listove urovni (pokud vyska = 2) a kazdy z techto uzlu ma minimalne 29 klicu => nas strom ma 1740 klicu.
Podle mne by mel mit vysku 1..
-
- Matfyz(ák|ačka) level II
- Příspěvky: 51
- Registrován: 30. 5. 2005 19:26
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
Celkom uspesne ma tu zamotavate. Ak som dobre pochopil, tak hore co je uvedene vyska dva vlastne nie je vyska dva ale jedna (koren sa do vysky nezapocitava). Dva z toho pohladu, ze potrebujes dva pristupy. Takze ak ma koren potomkov a ti maju potomkov, to je v skutocnosti vyska dva, nie tri. Takze tvoje vypocty su dobre a myslene to bolo rovnako, len nie podla definicie:) Alebo aj ja to vidim inak?JirkaL píše:Asi mi to ted vubec nepali, ale nechapu, jak by mohl mit ten strom vysku 2. Pokud m = 60, tak krome korene musi mit kazdy uzel minimalne 30 potomku, tedy v jakemsi "minimalnim" pripade bude mit koren dva potomky a kazdy z nich 30 potomku => to mame 60 uzlu na listove urovni (pokud vyska = 2) a kazdy z techto uzlu ma minimalne 29 klicu => nas strom ma 1740 klicu.
Podle mne by mel mit vysku 1..