N2

2. 2.1.

˝ Hasítótáblák (Tördelotáblák) Halmaz

Értékhalmaz: Halmaz = { H : H ⊆ E} Muveletek: ˝

H : Halmaz, x : E, I : Iterator

{Igaz}

Letesit(H)

/ {H = 0}

{H = H} Megszuntet(H) {Hamis} {H = H}

Uresit(H)

{H = H}

Eleme(H, x)

{H = {a1 , . . . , an }}

Elemszam(H)

/ {H = 0} {Eleme = x ∈ Pre(H)} {Elemszam = n}

{H = H}

Bovit(H, x)

{H = Pre(H) ∪ {x}}

{H = H}

Torol(H, x)

{H = Pre(H) − {x}}

{H = H}

IterKezd(H, I)

{}

{I = I}

IterAd(I, x)

{}

{I = I}

IterVege(I)

{}

public interface Halmaz<E> extends Iterable<E>{ public int Elemszam(); public void Uresit(); public boolean Eleme(E x); public void Bovit(E x); public boolean Torol(E x); public E Keres(E x); } Ha a halmaz elemein alapértelmezett egy lineáris rendezési reláció, akkor az RHalmaz adattípust használjuk.

public interface RHalmaz<E extends Comparable<E>> extends Halmaz<E>, Iterable<E>{ } A Halmaz adattípus megvalósításai: HalmazB: bitvektor adatszerkezettel; E=1..n HalmazT: tömb adatszerkezettel, HalmazL: lánc adatszerkezettel, HalmazHL: hasítótábla (ütközésfeloldás láncolással) adatszerkezettel, HalmazHN: hasítótábla (ütközésfeloldás nyílt címzéssel) adatszerkezettel. Az RHalmaz adattípus megvalósításai: ˝ adatszerkezettel, HalmazBKF: AVL-kiegyensúlyozott bináris keresofa ˝ adatszerkezettel, HalmazAVL: AVL-kiegyensúlyozott bináris keresofa HalmazPFFa: piros-fekete fa adatszerkezettel. Diszkrét ismétléses vezérlés megvalósításai iterátorral.

Forall x in H Do M(x); java megvalósítás:

1

Iterator<E> I=H.iterator(); //IterKezd(H,I) while (I.hasNext()){ //!IterVege(I) x=I.next(); //IterAd(I,x) M(x); } vagy kiterjesztett for-ciklussal:

for (E x:H) M(x); Legyen U az Elemtip, univerzum,

H = {a1 , · · · , an } ⊆ U Vegyünk egy T:Array[0..M-1] of Elemtip tömböt, amelyben a H halmazt tárolni akarjuk. Válasszunk egy

h : U → {0, · · · , M − 1} függvényt, amely minden ai halmazelemre megadja azt a táblázat indexet, ahol az elemet tárolni akarjuk, T [h(ai )] := ai . Ha ai 6= a j és h(ai ) = h(a j ) ütközés.

2.2.

Ütközésfeloldás láncolással

Legyen T:Array[0..M-1] of Lanc, és legyen T [ j] a {x : x ∈ H ∧ h(x) = j} elemek lánca.

T ...

0

...

j

M−1

...

1. ábra. Adatszerkezet ütközésfeloldás láncolással módszerhez.

public class HasitoLanc<E>{ private Lanc<E>[] Tar; private int eszam; private int meret=100; public HasitoLanc(int m){ Tar=(Lanc<E>[])new Lanc[m]; meret=m; } protected int hf(E x){ //a hasító függvény return x.hashCode()%meret; } public boolean Eleme(E x){ int i=hf(x); Lanc<E> p=Tar[i]; while (p!=null && !x.equals(p.elem)) p=p.csat; 2

return p!=null; } public E Keres(E x){ int i=hf(x); Lanc<E> p=Tar[i]; while (p!=null && !x.equals(p.elem)) p=p.csat; if (p!=null) return p.elem; else return null; } public void Bovit(E x){ int i=hf(x); Tar[i]=new Lanc<E>(x, Tar[i]); ++eszam; } public boolean Torol(E x){ int i=hf(x); Lanc<E> p=Tar[i]; Lanc<E> pp=p; while (p!=null && !x.equals(p.elem)){ pp=p; p=p.csat; } if (p!=null){ if (pp==p) Tar[i]=p.csat; else pp.csat=p.csat; --eszam; return true; } else return false; }

2.3.

Ütközésfeloldás nyílt címzéssel

Pótvizsgálat (próbasorozat)

h : U × {0, · · · , m − 1} → {0, · · · , m − 1} hh(k, 0), · · · , h(k, m − 1)i h0, · · · , m − 1i egy permutációja minden k kulcsra. A k kulcsú elem helye a táblázatban az a j = h(k, i), amelyre Min{i : T [h(k, i)] = Szabad} Ekkor a próbák száma i + 1. ˝ ˝ Például, ha U = Integer, h(x, i) = (x + i) mod m. Ezt a tördelofüggvényt alkalmazva bovítsük a kezdetben üres táblát egymás ˝ után a 15, 30, 16, 35, 20, és 28 elemekkel. Majd töröljük a táblából a 16-os elemet. Ha ezt követoen a 28 elemet keressük a táblában, akkor a h2, 3, 4, 5, . . .i próbasorozat kell alkalmazni, de a keresés nem állhat meg a 3 indexu˝ törölt táblaelemnél. Tehát ˝ különbözo˝ Torolt konstans kulcs a táblában a törölt helyeket nem tekinthetjük üresnek. Választanunk kell egy Ures és egy ettol értéket az üres, illetve a törölt táblaelemek jelölésére.

3

T

0

1

3 4 5 6 15 16 30 28 2

7 8 20

9 10 11 12 35

˝ ˝ 2. ábra. Tördelotábla a 15, 30, 16, 35, 20, és 28 elemekkel való bovítés után.

T

0

1

2




3
 4 5 6





 15 30 28

7 8 20

9 10 11 12 35

˝ 3. ábra. Tördelotábla a 16 elem törlése után.

public class TordeloNyilt<E>{ private E[] Tar; private int eszam; private int meret=100; private final E TOROLT; private final boolean tobb; protected int proba(E x, int i){ return (x.hashCode()+i)%meret; } public TordeloNyilt(){ tobb=true; Tar=(E[])new Object[meret]; TOROLT= (E)new Object(); } public TordeloNyilt(int m){ tobb=true; meret=m; Tar=(E[])new Object[meret]; TOROLT= (E)new Object(); } public TordeloNyilt(boolean tobb){ this.tobb=tobb; Tar=(E[])new Object[meret]; TOROLT= (E)new Object(); } public TordeloNyilt(int m, boolean tobb){ this.tobb=tobb; meret=m; Tar=(E[])new Object[meret]; TOROLT= (E)new Object(); } public int Keres(E x){ //az x elem táblabeli helyének keresése int i=0; int j; do{ j=proba(x,i); if (Tar[j]!=null && x.equals(Tar[j])) return j; }while (++i<meret && Tar[j]!=null); 4

return -1; } public boolean Eleme(E x){ return Keres(x)>=0; } public void Bovit(E x){ int i=0; int j; if (!tobb && Eleme(x)) return; do{ j=proba(x,i); if (Tar[j]==null || Tar[j]==TOROLT){ Tar[j]=x; eszam++; return; } }while (++i<meret); throw new RuntimeException("A tábla megtelt"); } public boolean Torol(E x){ int j=Keres(x); if (j>=0){ Tar[j]=TOROLT; eszam--; return true; }else return false; } }

2.4.

Pótvizsgálatok (próbasorozatok).

Lineáris pótvizsgálat h(k, i) = (h0 (k) + i) mod m ,

h0 : U → {0, · · · , m − 1} Négyzetes pótvizsgálat

h(k, i) = (h0 (k) + c1 · i + c2 · i2 ) mod m , h0 : U → {0, · · · , m − 1} Dupla tördelés

h(k, i) = (h1 (k) + i · h2 (k)) mod m , h1 , h2 : U → {0, · · · , m − 1} A h2 (k) értékeknek relatív prímnek kell lenni a táblázat m méretéhez. Pl. h1 (k) = k mod m és h2 (k) = 1 + (k mod m0 ), ahol m0 = m − 1.

2.5.

˝ Tördelofüggvények

Tegyük fel, hogy a k kulcs egész számérték. Az osztás módszere: h(k) = k mod m Ha k = ck . . . c1 c0 string, akkor vegyük a b = 256-os számrendszerbeli értékét:

a = (ck . . . c1 c0 )b = ∑ki=0 bi ∗ |ci |

5

(ahol |c| a c karakter kódja) majd képezzük a h(k) = a mod m értéket. A modulus muveletre ˝ teljesül az alábbi két azonosság.

(a + b) mod m = (a mod m + b mod m) mod m (a ∗ b) mod m = ((a mod m) ∗ (b mod m)) mod m static int h(String S, int m){ int k=S.length(); int a=0; for (int i=k-1; i>=0; i--){ int c=Character.getNumericValue(S.charAt(i)); a=((a<<8)+c)%m; } return a; } A szorzás módszere: h(k) = bm(k · A mod 1)c ahol k · A mod 1 = k ·√ A − bk · Ac 0 < A < 1, pl. A = ( 5 − 1)/2 = 0.6180 · · ·

2.6.

˝ Tördelotáblák hatékonysági elemzése

˝ Legyen h : U → {0, . . . , m − 1} a tördelofüggvény. n ˝ a tábla telítettségi tényez oje. m Egyenletességi feltétel:

α=

∑

Pr(k) =

k:h(k)= j

1 m

( j = 0, · · · , m − 1)

˝ Feltesszük, hogy h(k) olcsó, azaz Θ(1) idoben kiszámítható. Ütközésfeloldás láncolással A B OVIT futási ideje legrosszabb esetben is O(1). A K ERES és TOROL futási ideje legrosszabb esetben O(n). (Minden elem egyetlen láncban van és a keresés szekvenciális.) Ha a T [ j] lánc hossza n j , akkor

n = n0 + n1 + · · · + nm−1 és n j várható értéke n/m = α. Így egy k kulcsú elem keresésének ideje lineárisan függ a T [h(k)] lánc nh(k) hosszától. A T [h(k)] lánc azon elemeinek számát tekintsük, amelyekkel a keresés során összehasonlítódik a keresett k kulcs. Két esetet kell tekintenünk, az elso˝ az, amikor a keresés sikeres, a másik pedig a sikertelen keresés. 2.1. tétel. Ha teljesül az egyenletességi feltétel, akkor láncolással történo˝ ütközésfeloldás esetén a sikertelen keresés átlagos ideje Θ(1 + α). Bizonyítás. Az egyenletességi feltétel miatt bármely k kulcsra, ami még nincs a táblában, egyforma valószínuséggel ˝ adódik bármely j = h(k) táblaindex. Ezért egy k kulcs sikertelen keresésének átlagos ideje megegyezik annak átlagos idejével, hogy a T [h(k)] láncot végigkeressük. Ennek a láncnak az átlagos hossza α, tehát h(k) kiszámításával együtt az átlagos futási ido˝ Θ(1 + α).  Sikertelen keresés esetén annak valószínusége, ˝ hogy egy adott láncban keresünk, azonos a lánc hosszával. 2.2. tétel. Ha teljesül az egyenletességi feltétel, akkor láncolással történo˝ ütközésfeloldás esetén a sikeres keresés átlagos ideje

Θ(1 + α). Bizonyítás. Az x elem sikeres keresése esetén megvizsgált elemek várható száma eggyel nagyobb, mint azoknak az elemeknek a ˝ ˝ o˝ elemeket x beszúrása után szúrtuk be, mivel várható száma, amelyek megelozik x-et az x-et tartalmazó láncban. Az x-et megeloz új elemet mindig a lánc elejéhez illesztünk. Tehát átlagolni kell a táblázat n elemére az 1+azon elemek várható száma értékeket,

6

amelyeket x után adtunk x láncához. Legyen xi a táblázatba i-edikként beszúrt elem és legyen ki = xi .kulcs. Az egyenletességi feltétel miatt Pr{h(ki ) = h(k j )} = 1/m. Ezért a sikeres keresés során vizsgált elemek számának várható értéke n 1 n 1 1+ ∑ ∑ n i=1 m j=i+1

! = 1+

1 n ∑ (n − i) nm i=1

1 = 1+ nm

n

n

i=1

i=1

!

∑n− ∑i

  n(n + 1) 1 2 n − = 1+ nm 2 n−1 = 1+ 2m α α = 1+ − . 2 2n Tehát a sikeres keresés futási ideje, beszámítva h(k) kiszámítását is

Ta (n) = Θ(2 +

α α − ) = Θ(1 + α) 2 2n



A nyílt címzés hatékonyságának elemzése A legjobb eset K ERES, B ÖVIT, TOROL : O(1) A legrosszabb eset B ÖVIT: O(n) K ERES, TOROL : O(n) Átlagos eset 1 2.3. tétel. Nyílt címzés esetén a sikertelen keresés során a próbák számának várható értéke ≤ 1−α .

Bizonyítás. pi = Pr{pontosan i táblaelem foglalt} azaz, i a legkisebb index, amelyre T [h(k, i)] = Szabad} Ekkor a próbák számának várható értéke: n

1 + ∑ i pi i=0

Jelölje qi annak valószínuségét, ˝ hogy legfeljebb i próbát kell végezni. Tehát n

n

n

i=0

i=0

i=0

n

n

∞

i=0

i=0

i=0

1 + ∑ i pi = ∑ i (qi − qi−1 ) = ∑ qi q1 = q2 =

n m n n−1 m m−1

qi =

n n−1 m m−1

n+1−i · · · m+1−i ≤ ( mn )i = αi . Tehát

1 + ∑ i pi ≤ ∑ αi ≤ ∑ αi ≤ A B OVIT algoritmus átlagos futási ideje :

1 1−α



1 O( 1−α ).

1 2.4. tétel. Nyílt címzés esetén a sikeres keresés során a próbák számának várható értéke ≤ α1 ln (1−α) .

Bizonyítás. Sikeres keresés ugyanazon próbasorozatot hajtja végre, mint amikor az elemet beraktuk a táblázatba. m Ha a k kulcsú elem i-edikként került a táblázatba, akkor a próbák száma m−i . Tehát a próbák számának várható értéke:

1 n−1 m m n−1 1 1 = ∑ = (Hm − Hm−n ), ∑ n i=0 m − i n i=0 m − i α 7

˝ így ahol Hi = ∑ij=1 1j az i. harmonikus szám. 1/x csökkeno,

1 (Hm − Hm−n ) = α 1 α

Z m

(1/x)dx m−n

=

m 1 1/k ≤ ∑ α k=m−n+1

1 m 1 1 ln = ln α m−n α 1−α

 1 ) O( α1 ln 1−α

Tehát a Torol algoritmus átlagos futási ideje (= sikeres keresés) Pl. ha α = 0.5 akkor 1.387, ha α = 0.9 akkor 2.559 próba kell átlagosan a törléshez.

8