N11

11.

Az UnioHolvan adattípus megvalósítása

Az UnioHolvan absztrakt adattípus. / Értékhalmaz: UnioHolvan = {{H1 , . . . , Hk } : Hi ⊆ E, i = 1, . . . , k, i 6= j ⇒ Hi ∩ H j = 0} Muveletek: ˝

S : UnioHolvan, x, y : Elemtip, n1, n2 : NevTip

{Igaz}

Letesit(S, n)

{S = {}}

{Igaz}

Letesit(S)

/ {S = 0}

{S = S}

Megszuntet(S)

{Igaz}

{S = S}

Uresit(S)

/ {S = 0}

{S = {H1 , . . . , Hk } ∧ x ∈ ∪Hi }

Holvan(S, x)

}{= y ∧ (x ∈ Hi ∧ y ∈ Hi )}

{S = {H1 , . . . , Hk } ∧ x ∈ / ∪Hi }

Holvan(S, x)

{= x ∧ S = Pre(S) ∪ {{x}}

{S = {H1 , . . . , Hk } ∧ n1 ∈ Hi ∧ n2 ∈ H j }

Unio(S, n1, n2)

{S = {H1 , . . . , Hk }}

Elemszam(S)

{S = {H1 , . . . , Hk }}

ReszElemszam(S, x)

{S = S} {S = {H1 , . . . , Hk } ∧ (∃i)(x ∈ Hi )}

{S = Pre(S) − Hi − H j ∪ {Hi ∪ H j }} {= k = |S| ∧ S = Pre(S)} {= |Hi | ∧ x ∈ Hi ∧ S = Pre(S)}

Iterator(S)

{}

ReszIterator(S, x)

{}

Adatszerkezet választása. A diszjunkt részhalmazok ábrázolhatók olyan Rep : {1, . . . , n} → {1, . . . , n} függvénnyel, hogy bármely x, y ∈ {1, . . . , n}-re Rep(x) = Rep(y) akkor és csak akkor, ha x és y ugyanazon részhalmazhoz tartozik. Ezt szemlélteti a 4. ábra. Ekkor a H OLVAN muvelet ˝ ˝ konstans idoben megvalósítható, az U NIO azonban az egyik részhalmaz elemszámával arányos ideju˝ lesz. lehetséges adatszer-

1. ábra. Egyszeru˝ adatszerkezet az UnioHolvan adattípushoz.

2. ábra. Az U NIO muvelet ˝ megvalósítása egyszeru˝ adatszerkezet esetén.

˝ kezet a megvalósításhoz a kétdimenziós lánc, amit a a 6. ábra mutat. Ekkor az U NIO muvelet ˝ konstans idoben megvalósítható, a ˝ H OLVAN muvelet ˝ azonban csak O(n) idoben. Tehát egymásnak ellentmondó követelményeket kellene kielégíteni, amelyik adatszerkezet jó a H OLVAN muvelethez, ˝ az nem jó az U NIO-hoz. Kevesebbet követeljünk a H OLVAN hatékony, azaz konstans ideju˝ megvalósításánál. Ábrázoljuk a részhalmazokat ˝ fával, mint azt a 7. ábra mutatja. Ekkor az U NIO konstans idoben megvalósítható. A H OLVAN futási idejének felso˝ korlátja a fa magassága, tehát arra kell törekedni, hogy fa magassága ne legyen nagy. Két heurisztikát használunk ennek elérésére: 1.Egyesítés a nagyobbikhoz: Az U NIO muvelet ˝ mindig a nagyobb elemszámú részhalmaz gyökeréhez kapcsolja a kisebb elemszámú részhalmaz gyökerét. 2. Úttömörítés: Minden H OLVAN muvelet ˝ során a fának mindazon pontjait, amelyen a keresés áthalad a gyökérhez kapcsoljuk.

1

3. ábra. Kétdimenziós lánc az U NIO H OLVAN típus megvalósításához.

4. ábra. Halmazerdo˝ adatszerkezet az U NIO H OLVAN adattípus megvalósításához.

x

x

5. ábra. Úttömörítés H OLVAN muvelet ˝ során.

2

Az iterátor muveletek ˝ hatékony megvalósításához ábrázoljuk a részhalmazokat körláncban (, esetleg kétirányú körláncban a részhalmazok gyökereit). Tehát az adatszerkezet: (M, Adat, R); ahol az R szerkezeti kapcsolatok: R = {Apa,Csat, Elore,Vissza}, Apa,Csat(, Elore,Vissza) : M → M . Az Apa kapcsolat fa, a Csat kapcsolat körlánc, az (Elore,Vissza) kapcsolatpár pedig kétirányú körlánc. A részhalmazok elemszámát nem tároljuk, hanem Apa(x) = −E legyen, ha x gyökér és az x-gyökeru˝ részhalmaz elemszáma E . ˝ ˝ amit a 10. ábra mutat. Két körlánc konstans idoben egyesítheto,

6. ábra. Adatszerkezet az U NIO H OLVAN adattípus megvalósításához.

p1

p2

q1

7. ábra. Két körlánc egyesítése:q1 := Csat(p1);Csat(p1) := Csat(p2);Csat(p2) := q1 .

public class UnioHolvan implements Iterable{ private static int[] apa; private static int[] csat; private int eszam; private int n; public UnioHolvan(int n){ apa=new int[n+1]; csat=new int[n+1]; eszam=0; this.n=n; for (int x=1; x<=n; x++){ apa[x]=0; } } public int Holvan(int x){ if (x<1 || x>n ) throw new NoSuchElementException("Nincs ilyen elem: "+x); if (apa[x]==0){ 3

apa[x]=-1; csat[x]=x; ++eszam; return x; } int Nx=x; while (apa[Nx]>0) Nx=apa[Nx]; int y=x; while (x!=Nx){ //úttömörítés y=apa[x]; apa[x]=Nx; x=y; } return Nx; } public void Unio(int Nx, int Ny){ if (Nx<=0 || Nx>n || Ny<=0 || Ny>n || apa[Nx]>=0 || apa[Ny]>=0) throw new NoSuchElementException("Nincs ilyen részhalmaz"); if (Nx==Ny) return; if (apa[Nx]>apa[Ny]){ //egyesítés a nagyobbikhoz int z=Nx; Nx=Ny; Ny=z; } apa[Nx]+=apa[Ny]; apa[Ny]=Nx; int kovet=csat[Nx]; csat[Nx]=csat[Ny]; csat[Ny]=kovet; --eszam; } public int Elemszam(){ return eszam; } public int ReszElemszam(int Nx){ if (Nx<=0 || Nx>n || apa[Nx]==0) throw new NoSuchElementException("Nincs ilyen részhalmaz"); if (apa[Nx]>0) Nx=this.Holvan(Nx); return Math.abs(apa[Nx]); } class PontIter implements Iterator{ int aktp, indulo; PontIter(){ aktp=0; do{ aktp++; }while(aktp<=n && apa[aktp]>=0); indulo=aktp; } public boolean hasNext(){ return aktp<=n; } public Integer next(){ 4

int ad=aktp; do{ aktp++; }while(aktp<=n && apa[aktp]>=0); return ad; } public void remove(){} } public Iterator iterator(){ return new PontIter(); } class ReszIter implements Iterator{ int aktp, indulo; ReszIter(int Nx){ if (Nx<=0 || Nx>n || apa[Nx]==0) throw new NoSuchElementException("Nincs ilyen részhalmaz"); aktp=Nx; indulo=Nx; } public boolean hasNext(){ return aktp!=-1; } public Integer next(){ int ad=aktp; aktp=csat[aktp]; if (aktp==indulo) aktp=-1; return ad; } public void remove(){ } } public Iterator ReszIterator(int Nx){ return new ReszIter(Nx); } } public static void main (String[] args)throws IOException { int x,y,nx,ny; Scanner bef = new Scanner(new File("parok.be")); int n=bef.nextInt(); int m=bef.nextInt(); bef.nextLine(); UnioHolvan H=new UnioHolvan(n); for (int i=0; i<m; i++){ x=bef.nextInt(); y=bef.nextInt(); nx=H.Holvan(x); ny=H.Holvan(y); if (nx!=ny) H.Unio(nx,ny); } bef.close(); System.out.println("A bandák száma: "+H.Elemszam()); for (int b:H){ Iterator iterb=H.ReszIterator(b); while (iterb.hasNext()){ 5

System.out.print(iterb.next()+", "); } System.out.println(); } } Az U NIO H OL adattípus megvalósításának hatékonysági elemzése. Összesítéses elemzés. Egy muveletegyüttes, ˝ mint az absztrakt adattípusok hatékonysági elemzését megadhatjuk úgy is, hogy nem külön-külön vizsgáljuk az egyes muveletek ˝ futási idejét, hanem muveletsorok ˝ összesített futási idejét mérjük. Ha egy P = P1 ; . . . ; Pm muveletsor ˝ összesített futási ideje T (P), akkor a T (P)/m hányadost az egyes muveletek ˝ amortizált futási idejének nevezzük.  ha i = 0 ,  n lg(i) n = lg(lg(i−1) n) ha i > 0 és lg(i−1) n > 0,  nemdef egyébként

lg∗ n = min{i ≥ 0 : lg(i) n ≤ 1} P = P1 ; · · · ; Pm muveletsorozat, ˝ ahol Pi ∈ {U NIO, H OLVAN} és n azon H OLVAN muveletek ˝ száma, amelyek új elemet adnak a halmazrendszerhez, azaz a részhalmazok elemszámának összege a muveletsor ˝ végén n, akkor a muveletsor ˝ futási ideje: T (P) = O(m lg∗ n) ˝ lg∗ n minden gyakorlatban eloforduló n-re ≤ 5, mivel lg∗ (265536 ) = 5. Tehát az H OLVAN muveletek ˝ amortizált futási ideje praktikusan konstans.

6