pocet pristupu s indexovymi souboy s bitovou mapou

Uživatelský avatar
Hugo
Donátor
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

Příspěvek od Hugo »

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..
Uživatelský avatar
Hugo
Donátor
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:

Příspěvek od Hugo »

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..
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Příspěvek od Kuba »

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
Uživatelský avatar
Hugo
Donátor
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:

Příspěvek od Hugo »

diky moc,
ja bych radsi uz nemel nic psat, protoze dneska perlim (no proste Hugo :D )
Ale u toho b) -> mi neni jasne, jak to je, kdyz bych zacal zapisovat novy blok do primarniho souboru - to prece nemusim nacitat zadny nynejsi, takze by bylo o jeden pristup na disk mene?
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Příspěvek od Kuba »

To si taky myslim, jenze asi musis zjistit, ze ten co nactes je plny... si myslim. Nevim :)
Uživatelský avatar
Hugo
Donátor
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:

Příspěvek od Hugo »

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:)
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 »

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.
Plug 'n' Pray.
Uživatelský avatar
MyS
Donátor
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:

Příspěvek od MyS »

2(s+r+btt) + 2r + (s+r+btt) na update stromu
...IMHO se zapisuje jeste extra ten novy list a koren, cili 2(s+r+btt) + 2r + 2*(s+r+btt)
To si taky myslim, jenze asi musis zjistit, ze ten co nactes je plny
To podle me vyplyva z toho, ze 597:6=99.5,cili posledni blok neni cely, cili RW je nutny
We don't need no education!
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 »

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
Jo pravda ... chybicka se vloudila :oops: ... 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 ?
Plug 'n' Pray.
JirkaL

Příspěvek od JirkaL »

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..
fissie
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 10. 11. 2006 20:41
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od fissie »

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.
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 »

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..
No ale kdyz koren ma potomky a ty maji potomky, tak uz je to 3 :).
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 »

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
...
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)?
Napr. tech 597 zaznamu * 6 hodnot = 3582 bitu = cca 450 bajtu ...
Plug 'n' Pray.
JirkaL

Příspěvek od JirkaL »

Tuetschek píše:
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..
No ale kdyz koren ma potomky a ty maji potomky, tak uz je to 3 :).
Ne, to je 2, vyska je nejdelsi cesta od korene do listu..
qwyxyo
Matfyz(ák|ačka) level II
Příspěvky: 51
Registrován: 30. 5. 2005 19:26
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od qwyxyo »

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..
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?
Odpovědět

Zpět na „2006“