Skupinové štěpení stránek
-
- 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:
Skupinové štěpení stránek
Mohl by někdo nějak srozumitelně vysvětlit skupinové štěpení stránek? Jakým způsobem probíhá expanze?
-
- 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:
Aha. No, já koukal do slidů, do sešitu, pak na nějaký jiný webový stránky a ani z jednoho jsem to nějak nepobral... a v jedněch otázkách jsem viděl
Kód: Vybrat vše
1)nacpání prvku 13 (jen kam patří) a pak 17ky do skupinového štěpení stránek s následnou expanzí. h(K)=K mod 4, h1(K)=K mod 3, h2(K)=(K div 3) mod 3
- Lada
- Donátor
- Příspěvky: 165
- Registrován: 9. 1. 2005 10:17
- Typ studia: Informatika Bc.
- Bydliště: Slaný / zácpa na Evropské
na fearu se to resilo a je tam nejaky castecny navod jak na to - aspon ja z nej i neco malo pochopil:)
http://mff.fear.cz/forum/viewtopic.php?t=843[/url]
http://mff.fear.cz/forum/viewtopic.php?t=843[/url]
Hail to you, champion:o)
- 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 jsem to MOZNA pochopil ... pripojuju okomentovany Zemlickuv algoritmus na vyhledani stranky pro prvek (ktery simuluje vsechna stepeni i reorganizace) ktery jsem si za tim ucelem napsal ... treba to pomuze ...
doporucuju copy & paste do neceho co umi syntax highlight pro pascal ...
Kód: Vybrat vše
const s0 = ...; { pocatecni pocet skupin stranek }
const g = ...; { pocet stranek v 1 skupine }
{
cisla stranek v 1 skupine nejdou za sebou, ale lisi se prave
o s, takze pokud je g = 3 a s = 5, tak stranky v 1. skupine maji
cisla 0, 5, 10 !
}
function pgAddr( k: key; reorgs, curPgs : integer ) : integer;
var j : integer; { pocitadylko pro for-cyklus, akt. provedeny pocet reorganizaci }
x : integer; { sem ukladam aktualni pozici zaznamu - cislo stranky,
na konci tam budu mit vysledek }
s : integer; { sem ukladam aktualni pocet stranek po reorganizacich }
begin;
{ pocatecni inicializace parametru }
x := hash( k ); { puvodni zahashovani do prostroru (s0 * g) stranek }
s := s0; { inicializace poctu stranek }
{ prepocitani pres vsechny provedene reorganizace }
for j := 0 to (reorgs - 1) do
begin
{ nova adresa zaznamu po akt. reorganizaci }
x := (x mod s ) { nova skupina stranek - meni se pri reorganizaci }
+ h_j( k ) * s; { nove cislo stranky ve skupine - prehashovani pri stepeni }
{ prepocitani noveho poctu stranek po akt. reorganizaci }
s := ceil( s * (g+1)/g );
end;
{ pokud uz v teto (reorgs.-te) iteraci stepeni prosla aktualni skupina
reorganizaci, musim prehashovat (z g do g+1 stranek) }
if (( x mod s ) < curPgs )
then x := (x mod s) + h_reorgs( k ) * s;
{ vraceni spocitane hodnoty }
pgAddr := x;
end;
Plug 'n' Pray.
-
- 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:
Diky moc, rano se na to kouknu, schvalne jestli rano moudrejsi vecera
EDIT: No, rano jsem spal, ale odpoledne jsem to pochopil, takze jeste jednou diky! Jen mensi oprava:
{ prepocitani noveho poctu stranek po akt. reorganizaci }
by podle me melo byt
{ prepocitani noveho poctu skupin po akt. reorganizaci }
A jeste pokud si pamatujete Zemlickovi obrazky z prednasky, tak "skupina" je radek, g je pocet sloupcu, g+1 je pocet sloupcu pokud skupina prosla castecnym stepenim.
EDIT: No, rano jsem spal, ale odpoledne jsem to pochopil, takze jeste jednou diky! Jen mensi oprava:
{ prepocitani noveho poctu stranek po akt. reorganizaci }
by podle me melo byt
{ prepocitani noveho poctu skupin po akt. reorganizaci }
A jeste pokud si pamatujete Zemlickovi obrazky z prednasky, tak "skupina" je radek, g je pocet sloupcu, g+1 je pocet sloupcu pokud skupina prosla castecnym stepenim.
- JJ
- Matfyz(ák|ačka) level II
- Příspěvky: 99
- Registrován: 28. 1. 2005 14:03
- Typ studia: Informatika Mgr.
Diky, ale porad mi to moc nepali, teda spis bych to potreboval vysvetlit na nejakem priklade. Moc mi neni jasne co se mysli pocatecnim poctem skupin (na zacatku budovani, pak by byla 1 nebo to je soucasny pocet a pocatecni je mysleno v ramci algoritmu). Zajimal by me hlavne lonsky priklad 1 ze skupiny C (zminovany kubou). V zadani mi chybi h0 a nejsem si jistej v jake fazi se nachazi, jestli se ma ted stepit nebo az po pridani prvku.
- Trupik
- Matfyz(ák|ačka) level III
- Příspěvky: 251
- Registrován: 3. 1. 2005 14:45
- Typ studia: Informatika Mgr.
- Kontaktovat uživatele:
k jiz zminenemu EDITU bych jeste nahradilJJ píše:Diky, ale porad mi to moc nepali, teda spis bych to potreboval vysvetlit na nejakem priklade. Moc mi neni jasne co se mysli pocatecnim poctem skupin (na zacatku budovani, pak by byla 1 nebo to je soucasny pocet a pocatecni je mysleno v ramci algoritmu). Zajimal by me hlavne lonsky priklad 1 ze skupiny C (zminovany kubou). V zadani mi chybi h0 a nejsem si jistej v jake fazi se nachazi, jestli se ma ted stepit nebo az po pridani prvku.
s : integer; { sem ukladam aktualni pocet stranek po reorganizacich }
s : integer; { sem ukladam aktualni pocet skupin po reorganizacich }
Jinak uz jsem to snad taky pochopil. V tom lonskem zadani C jsou podle me hi indexovane od jednicky misto od nuly a snad se maji nejprve vlozit prvky 13 a 17 a potom az provest reorganizace - s pak bude rovno 3
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Petice proti olympiádě http://olympiada.nazory.cz
Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
- Dawe
- Supermatfyz(ák|ačka)
- Příspěvky: 360
- Registrován: 12. 10. 2004 12:32
- Typ studia: Informatika Mgr.
- Bydliště: Doma a nebo na koleji
Jsme ve fázi, kdy jsem 2x2 roztáh na 3x2, hned pak by měla následovat reorganizace. Jestli nejdřív reorganizuju a nebo nejdřív vložím je jedno (pokud to udělám dobře).
Prvek 13 by se měl nacházet ve stránce 3 - jak na to - h(13) = 1, tedy v původní tabulce 2x2 by ležel ve spodním řádku, jelikož jsme ale už štěpily, je potřeba ještě udělat h1(13) = 1 a tak zařadím 13 do 1.pole na druhém řádku (číslováno od nuly).
Když chci vložit 17 je to podobný:
vložení před štěpením: h(17) = 1, vkládám do spodního řádku, je už rozštěpenej, takže musím ještě použít h1(17) = 2 - tedy 2. pozice na spodním řádku = 5.stránka
kdybych vkládal 17 až po štěpení: H(17)=1 ; 1mod2 + h1(17)*2 {obě 2 znamenají # str. před rozštěpením} = 5
A hle oba výsledky jsou stejný
Nejjednodušší, jak si otestovat, jestli to člověk chápe je, zkusit najít prvky který už tam jsou (jsou vloženy korektně). Nejlíp před reorganizací a znovu po ní...
Prvek 13 by se měl nacházet ve stránce 3 - jak na to - h(13) = 1, tedy v původní tabulce 2x2 by ležel ve spodním řádku, jelikož jsme ale už štěpily, je potřeba ještě udělat h1(13) = 1 a tak zařadím 13 do 1.pole na druhém řádku (číslováno od nuly).
Když chci vložit 17 je to podobný:
vložení před štěpením: h(17) = 1, vkládám do spodního řádku, je už rozštěpenej, takže musím ještě použít h1(17) = 2 - tedy 2. pozice na spodním řádku = 5.stránka
kdybych vkládal 17 až po štěpení: H(17)=1 ; 1mod2 + h1(17)*2 {obě 2 znamenají # str. před rozštěpením} = 5
A hle oba výsledky jsou stejný
Nejjednodušší, jak si otestovat, jestli to člověk chápe je, zkusit najít prvky který už tam jsou (jsou vloženy korektně). Nejlíp před reorganizací a znovu po ní...
- 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 ... preklep ... nebo se spis nedokazu vyzvejknout ... diky za opravuKuba píše: No, rano jsem spal, ale odpoledne jsem to pochopil, takze jeste jednou diky! Jen mensi oprava:
{ prepocitani noveho poctu stranek po akt. reorganizaci }
by podle me melo byt
{ prepocitani noveho poctu skupin po akt. reorganizaci }
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:
myslim ze je to dobre, ale je to pred a po REORGANIZACI, ne?Dawe píše: vložení před štěpením: h(17) = 1, vkládám do spodního řádku, je už rozštěpenej, takže musím ještě použít h1(17) = 2 - tedy 2. pozice na spodním řádku = 5.stránka
kdybych vkládal 17 až po štěpení: H(17)=1 ; 1mod2 + h1(17)*2 {obě 2 znamenají # str. před rozštěpením} = 5
A hle oba výsledky jsou stejný
Plug 'n' Pray.