Fórum studentů MFF UK

D píše: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?

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.

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.

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.

D píše: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.

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 píše: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.

A kedy by sa teoreticky pouzila ta dalsia hashovacia funkcia?

na zmatení nepřítele?

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

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.

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?

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 ... diky za opravu

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

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