Skupinové štěpení stránek

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:

Skupinové štěpení stránek

Příspěvek od Kuba »

Mohl by někdo nějak srozumitelně vysvětlit skupinové štěpení stránek? Jakým způsobem probíhá expanze?
Uživatelský avatar
Eubie
Matfyz(ák|ačka) level III
Příspěvky: 295
Registrován: 8. 10. 2005 15:35
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od Eubie »

Ahoj,
OZD mám za sebou z loňska a můžu říct, že tohle nikdo nechápal ( ani ti, co dávali stále pozor ) a u zkoušky se to ani okrajem nezmínilo, takže bych se toho příliš nebál.
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 »

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
pc
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 3. 10. 2004 21:44

Příspěvek od pc »

Eubie píše:Ahoj,
OZD mám za sebou z loňska a můžu říct, že tohle nikdo nechápal ( ani ti, co dávali stále pozor ) a u zkoušky se to ani okrajem nezmínilo, takže bych se toho příliš nebál.
Súhlasiť môžem iba s tou prvou časťou, na skúške ma to žiaľ stretlo...
Ale s vysvetlením pomôcť neviem :(
Uživatelský avatar
Lada
Donátor
Donátor
Příspěvky: 165
Registrován: 9. 1. 2005 10:17
Typ studia: Informatika Bc.
Bydliště: Slaný / zácpa na Evropské

Příspěvek od Lada »

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]
Hail to you, champion:o)
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 jsem to MOZNA :D 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 ...

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;
doporucuju copy & paste do neceho co umi syntax highlight pro pascal ...
Plug 'n' Pray.
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 »

Diky moc, rano se na to kouknu, schvalne jestli rano moudrejsi vecera :D

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.
Uživatelský avatar
JJ
Matfyz(ák|ačka) level II
Příspěvky: 99
Registrován: 28. 1. 2005 14:03
Typ studia: Informatika Mgr.

Příspěvek od JJ »

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.
Uživatelský avatar
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:

Příspěvek od Trupik »

JJ 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.
k jiz zminenemu EDITU bych jeste nahradil
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!
Uživatelský avatar
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

Příspěvek od Dawe »

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

Kuba 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 }
Jo pravda ... preklep ... nebo se spis nedokazu vyzvejknout :( :oops: ... diky za opravu :)
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 »

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ý :-)
myslim ze je to dobre, ale je to pred a po REORGANIZACI, ne?
Plug 'n' Pray.
Uživatelský avatar
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

Příspěvek od Dawe »

Tuetschek píše: myslim ze je to dobre, ale je to pred a po REORGANIZACI, ne?
Jo jasně, dík, už sem z toho všeho modulení, štěpení, reorganizaci, slučování, hešování ... uplně zblblej.
D
Matfyz(ák|ačka) level I
Příspěvky: 32
Registrován: 20. 12. 2006 17:42

Příspěvek od D »

A k comu je ta posledna hashovacia funkcia uvedena v tom priklade? h2(k)=( k div 3 ) mod 3
Uživatelský avatar
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

Příspěvek od Dawe »

na zmatení nepřítele? :-)
Odpovědět

Zpět na „2006“