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?

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.

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

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

Eubie wrote: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 :(

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]

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

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

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.

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.

JJ wrote: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

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

Kuba wrote: 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 :)

Dawe wrote: 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?

Tuetschek wrote: 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.

A k comu je ta posledna hashovacia funkcia uvedena v tom priklade? h2(k)=( k div 3 ) mod 3

na zmatení nepřítele? :-)

A kedy by sa teoreticky pouzila ta dalsia hashovacia funkcia?

D wrote:A k comu je ta posledna hashovacia funkcia uvedena v tom priklade? h2(k)=( k div 3 ) mod 3

Ja myslim ze neni jen na zmateni nepritele ... je tam napsano "vlozte 17 a provedte expanzi" -- tj. pred expanzi musis reorganizovat do 3 skupin po 2 strankach, pak tu expanzi provest - k 1. skupine pridat 1 stranku. Kdyz tu stranku pridavas, musis vsechny prvky ve skupine prehashovat pomoci teto funkce ze 2 stranek do 3.

Ja som skor pochopil ze ta prva funkcia sa pouziva po prvej reorganizacii ked vznikla druha skupina. Ta h2 sa bude pouzivat po druhej reorganizacii( ked uz budu 3 skupiny) ked dojde k rozdeleniu nejakej skupiny do troch stranok.

D wrote:Ja som skor pochopil ze ta prva funkcia sa pouziva po prvej reorganizacii ked vznikla druha skupina. Ta h2 sa bude pouzivat po druhej reorganizacii( ked uz budu 3 skupiny) ked dojde k rozdeleniu nejakej skupiny do troch stranok.

Ne pri reorganizaci se zadna hash-funkce nepouziva. To jenom vezmes ty stranky a prehazis je do jinych skupin, pripadne pridas nejakou prazdnou abys mel ve vsech skupinach stejne.

Hashovaci funkce h_x pouzivas jenom pri stepeni g stranek do g+1.

Ten priklad je tak trochu divny, protoze IMHO pocita s tim ze na zacatku byly 2 skupiny, takze doslo jenom ke stepeni obou skupin a k prvni reorganizaci dojde az pri tom vkladani sedmnactky ... jinak by totiz funkce h (hlavni hash-fce) nemohla davat hodnoty {0,1,2,3}. Ale prvku je v tech strankach vlozenych spousta ... to bych bral jako proste dany i kdyz to neodpovida postupu.

Je to zvlastne pretoze ked je g=2 a uz vsetky skupiny su rozstiepene tak by sa mala hned urobit reorganizace tak prve co by sme mali v tom priklade urobit je reorganizace. A ta globalna hashovacia funkcia ktora to rozdeluje do 0..3 nam prezradza ze sa zacalo s dvomi skupinami po dvoch strankach.

Takze moj nazor na vysledok je ze 13 by bola sla do stranky 3. A 17 sa ma vlozit do 5. Expanze sa rozdeli do 3 skupin.

A este otazka ako funguju oblasti pretecenia u skupinoveho stiepenia. Pride mi ze by kazda skupina mala mat svoju oblast a pri rozdeleni do g+1 by sa mal brat ohlad aj na zaznamy v oblasti pretecenia.

D wrote:A este otazka ako funguju oblasti pretecenia u skupinoveho stiepenia. Pride mi ze by kazda skupina mala mat svoju oblast a pri rozdeleni do g+1 by sa mal brat ohlad aj na zaznamy v oblasti pretecenia.

Ja jsem to vzdycky bral tak ze oblast preteceni je jenom jedna?