Vísbendingar um Verkefni 2

Uppbygging tölva, haust 2001

Í verkefninu á að útfæra Quick-find aðferðina fyrir Union-Find verkefnið. Við það er notaður vektorinn id. Á hverjum tíma mun gilda um hann:

Ef id[p] = id[q] þá eru stökin p og q í sama mengi.

Find-aðgerðin verður þá mjög hraðvirk, því aðeins þarf að bera saman innihald tveggja staka í vektornum id. Union-aðgerðin er hins vegar mun dýrari, því það þarf að fara í gegnum allan vektorinn og uppfæra gildi.

Hvert stak í vektornum id er tvö bæti. Þetta þýðir að tvöfalda verður vísagildið áður en það er lagt við grunnbendi vektorsins. Við höfum í upphafi að DS:SI bendir á id[0] og segjum að BX sé vísirinn p í forritinu. Til að ná í id[p] þarf fyrst að tvöfalda BX, t.d. með hliðrun, leggja það síðan við SI og loks helminga BX aftur, til að viðhalda því sem p. Hér að neðan er forritsbútur sem gerir þetta:

              ...
           shl     bx, 1             ; Tvöfalda BX til að vísa í vektor
           mov     ax, [si+bx]       ; Ná í A[p]
           shr     bx, 1             ; Breyta BX aftur í p
              ...
Athugið að ætlast er til að QF-fallið sé sjálfstætt, án víðværra breyta. Það er því ætlast til þess að ekki séu skilgreindar breytur í gagnasegmenti fyrir QF-fallið. Að sjálfsögðu þarf að skilgreina minnipláss fyrir vektorinn, en hann er skilgreindur í aðalforritinu og bendir á hann sendur niður í fallið. Ef þið þurfið að nota aukaminni í fallinu, notið þá staflann (með push og pop), en þið ættuð að geta komist af með bara gistu. Nota má gistun, AX, BX, CX (sem er viðfang), DX (sem er viðfang), DI, SI (sem er viðfang) og BP (ath. að ef BP er notað sem bendir þá þarf að setja DS: á undan því). Munið bara eftir því að forða þeim gistum sem þið breytið í upphafi fallsins og setjið síðan gildin aftur í þau í lok fallsins.

Hér er mun betra slembitölufall: slembi16.asm, fyrir þá sem hafa áhuga á slíku. Þetta fall er að vísu aðeins hægvirkara og notar bæði AX og DX fyrir upphafsgildi (sæði).


hh (hja) hi.is, 10. október, 2001.