Z kladn probl m: Reprezentace mno 0 6in a operace s nimi. V 0 0ad loh a algoritm 0 1 je tento

Datov´ e struktury ´ Uvod. Základn´ı problém: Reprezentace mnoˇzin a operace s nimi. V ˇradˇe u ´loh a algoritm˚ u je tento podproblém rozhoduj´ıc´ı pro sloˇzitost ˇreˇsen´ı, protoˇze tyto operace se mnohokrát opakuj´ı. Proto je tˇreba navrhnout pro tyto u ´lohy co nejefektivnˇejˇs´ı algoritmy (kaˇzd´ y uˇsetˇren´ y ˇcas mnohonásobn´ ym opakován´ım zaˇcne hrát d˚ uleˇzitou roli). To vede k detailn´ı anal´ yze sloˇzitosti v závislosti na vnˇejˇs´ıch okolnostech. Nelze ˇr´ıct, ˇze nˇekter´ y algoritmus je nejlepˇs´ı, protoˇze za urˇcit´ ych okolnost´ı m˚ uˇze b´ yt ‘ménˇe efektivn´ı’ algoritmus v´ yhodnˇejˇs´ı. ˇ s´ıme tzv. slovn´ıkov´ Reˇ y problém: Dáno univerzum U , máme reprezentovat S ⊆ U a navrhnout algoritmy pro následuj´ıc´ı operace MEMBER(x) – zjist´ı, zda x ∈ S, a nalezne jeho uloˇzen´ı INSERT(x) – kdyˇz x ∈ / S, pak vloˇz´ı x do struktury reprezentuj´ıc´ı S DELETE(x) – kdyˇz x ∈ S, pak odstran´ı x ze struktury reprezentuj´ıc´ı S. Efektivita algoritmu: ˇcasová sloˇzitost, prostorová sloˇzitost; ˇ v nejhorˇs´ım pˇr´ıpadˇe nebo v pr˚ vyˇsetˇrené bud umˇerném pˇr´ıpadˇe nebo amortizovanˇe. Literatura: K. Mehlhorn: Data Structures and Algorithms 1: Sorting and Searching, Springer 1984 http://www.mpi-sb.mpg.de/∼ mehlhorn/DatAlgbooks.html J. S. Vitter, W.-Ch. Chen: Design and Analysis of Coalesced Hashing, Oxford Univ. Press, 1987

1

2

´ n´ı Haˇ sova Pomoc´ı bitového pole m˚ uˇzeme rychle implementovat operace MEMBER, INSERT a DELETE. Nev´ yhoda: kdyˇz je velké univerzum, pak je prostorová sloˇzitost v nejlepˇs´ım pˇr´ıpadˇe ohromná, ve ˇspatném pˇr´ıpadˇe nelze pole zadat do poˇc´ıtaˇce. Haˇsován´ı chce zachovat rychlost operac´ı, ale odstranit pamˇeˇtovou nároˇcnost. Prvn´ı publikovan´ y ˇclánek o haˇsován´ı je od Dumney z roku 1956, prvn´ı anal´ yza haˇsován´ı poch´ az´ı od Petersona z roku 1957, ale existuje technická zpráva od IBM o haˇsován´ı z roku 1953. Základn´ı idea: Dáno univerzum U a mnoˇzina S ⊆ U tak, ˇze |S| << |U |. Máme funkci h:U − → {0, 1, . . . , m − 1} a mnoˇzinu S reprezentujeme tabulkou (polem) s m ˇrádky tak, ˇze s ∈ S je uloˇzen na ˇrádku h (s). Nev´ yhoda: mohou existovat r˚ uzná s, t ∈ S taková, ˇze h (s) = h (t) - tento jev se naz´ yv´ a kolize. Hlavn´ı problém: ˇreˇsen´ı koliz´ı. Základn´ı ˇreˇsen´ı: pouˇzijeme pole o velikosti [0..m − 1] a i-tá poloˇzka pole bude spojov´ y seznam obsahuj´ıc´ı vˇsechny prvky s ∈ S takové, ˇze h (s) = i. Toto ˇreˇsen´ı se naz´ yvá haˇsov´ an´ı se separovan´ ymi ˇretˇezci. Pˇr´ıklad: U = {1, 2, . . . , 1000}, S = {1, 7, 11, 53, 73, 141, 161} a funkce je h (x) = x mod 10. Pak P (0) = P (2) = P (4) = P (5) = P (6) = P (8) = P (9) = ∅,

P (7) =< 7 >,

P (3) =< 53, 73 >,

P (1) =< 1, 141, 11, 161 > .

Seznamy nemus´ı b´ yt uspoˇrádané. Algoritmy operac´ı. MEMBER(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif INSERT(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t 6= x then vloˇz´ıme x do i-tého seznamu endif

3

DELETE(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t 6= x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t = x then odstran´ıme x z i-tého seznamu endif

Předpoklad: Složitost v nejhorším případě:

V následuj´ıc´ı anal´ yze pˇredpokládáme, ˇze hodnota funkce h (x) je spoˇcitatelná v ˇcase O (1). V nejhorˇs´ım pˇr´ıpadˇe operace vyˇzaduj´ı ˇcas O (|S|) (vˇsechny prvky jsou v jednom seznamu). Poˇzadovaná pamˇeˇtová nároˇcnost O (m + |S|) (pˇredpokládáme, ˇze reprezentace prvku s ∈ S vyˇzaduje pamˇeˇt O (1)) pamˇeˇt nen´ı efektivnˇe vyuˇzitá

Předpoklady analýzy oček. délky řetězců:

Spoˇc´ıtáme oˇcekávanou délku ˇretˇezc˚ u za pˇredpoklad˚ u

Značení:

Pouˇzité znaˇcen´ı: |S| = n, m =poˇcet ˇretˇezc˚ u, |U | = N , n ` (i) =délka i-tého ˇretˇezce, α = m faktor naplnˇen´ı (load factor)

Důsledky předpokladů:

D˚ usledky pˇredpoklad˚ u:

(1) h je rychle spoˇcitatelná (tj. O (1)) a nemˇenná bˇehem v´ ypoˇctu; −1 (2) h rozdˇeluje univerzum U rovnomˇernˇe (tj. −1 ≤ |h (i) | − |h−1 (j) | ≤ 1 pro i, j ∈ {0, 1, . . . , m − 1}); (3) S je náhodnˇe vybraná z univerza U (tj. pro dané n = |S| jsou vˇsechny podmnoˇziny U o velikosti n reprezentovanou mnoˇzinou S se stejnou pravdˇepodobnost´ı); (4) kaˇzd´ y prvek z U má stejnou pravdˇepodobnost b´ yt argumentem operace; (5) velikost reprezentované mnoˇziny je v´ yraznˇe menˇs´ı neˇz velikost univerza.

1 m

pro vˇsechna x ∈ U a vˇsechna i = 0, 1, . . . , m − 1; 1 l 1 n−l Prob (` (i) = l) = pn,l = nl m 1− m pro vˇsechna i = 0, 1, . . . , m − 1.

Prob (h (x) = i) =

Vysvˇetlen´ı: i-t´ y ˇretˇezec má d´ a, ˇze elku l, právˇe kdyˇz existuje podmnoˇzina A ⊆ S takov´ |A| = l (tˇechto moˇznost´ı je nl ), pro kaˇzdé x ∈ A plat´ı h (x) = i (pravdˇepodobnost tohoto 1 l ) a pro kaˇzdé x ∈ S \ A plat´ı h (x) 6= i (pravdˇepodobnost tohoto jevu je jevu je m 1 n−l 1− m ). To znamená, ˇze jev má binomiáln´ı rozdˇelen´ı.

4

Oˇ cek´ avan´ a d´ elka ˇ retˇ ezc˚ u. n X

l n−l n X 1 1 n 1− = E (l) = lpn,l = l m m l l=0 l=0 l n−l n X 1 1 n! 1− = l l! (n − l)! m m l=0 l−1 n−l n n X 1 1 (n − 1)! 1− = m (l − 1)! (n − l)! m m l=1 l−1 (n−1)−(l−1) n 1 1 n X n−1 1− = l−1 m m m l=1 l n−1−l n−1 n X n−1 1 1 1− = l m m m l=0 n−1 n 1 n 1 = . [Tj. faktor naplnění +1− m m m m

\alpha]

Toto je standardn´ı elementárn´ı v´ ypoˇcet oˇcekávané hodnoty binomiáln´ıho rozdˇelen´ı. V´ ypoˇ cet druh´ eho momentu. E l2 =E (l (l − 1)) + E (l) , n−l l n X 1 1 n 1− = E(l(l − 1)) = l (l − 1) m m l l=0 (n−2)−(l−2) l−2 n n (n − 1) X n − 2 1 1 1− = m2 m m l−2 l=2 l n−2−l n−2 1 1 n (n − 1) X n − 2 1− = l m2 m m l=0

n (n − 1) Sečte se na 1 podle , 2 m n−1 n n n (n − 1) 2 1+ . + = E l = m2 m m m

binomické věty.

V´ ypoˇ cet rozptylu.

2 2 var (l) =E (l − E (l)) = E l2 − (E (l)) = n n−1 1 n n 2 1+ − 1− . = m m m m m

5

Shrneme v´ ysledky: n 1 n a rozptyl délky ˇretˇezc˚ u je m 1− m . Toto jsou standardn´ı Oˇcekávaná délka ˇretˇezc˚ u je m elementárn´ı odvozen´ı druhého momentu a rozptylu binomiáln´ıho rozdˇelen´ı. Oˇ cek´ avan´ y nejhorˇ s´ı pˇ r´ıpad. Spoˇc´ıtáme E (N P ) oˇcekávanou délku maximáln´ıho ˇretˇezce. Oznaˇcme ` (i) délku i-tého ˇretˇezce. Pak Prob max ` (i) = j = Prob max ` (i) ≥ j − Prob max ` (i) ≥ j + 1 . i

i

(#1)

i

Pak m˚ uˇzeme poˇc´ıtat: E (N P ) =

X j

(#1) j Prob max ` (i) = j = i

X j Prob max ` (i) ≥ j − Prob max ` (i) ≥ j + 1 = i

j

X j

X j

X j

X j

[Roztrhnu na dvě sumy]

i

X j Prob max ` (i) ≥ j + 1 = j Prob max ` (i) ≥ j − i

i

j

j Prob max ` (i) ≥ j − i

X j

(j − 1) Prob max ` (i) ≥ j =

(j − j + 1) Prob max ` (i) ≥ j =

i

[Přeindexoval jsem]

i

Prob max ` (i) ≥ j . i

Vysvˇetlen´ı: Pˇri ˇctvrté rovnosti se v druhé sumˇe zvˇetˇsil index, pˇres kter´ y sˇc´ıtáme, o 1, v p´ até rovnosti se k sobˇe daly koeficienty pˇri stejn´ ych pravdˇepodobnostech ve dvou sumách. Odtud Prob(max (` (i)) ≥ j) = i

Prob (` (1) ≥ j ∨ ` (2) ≥ j ∨ · · · ∨ ` (m − 1) ≥ j) ≤ j X 1 n Prob (` (i) ≥ j) ≤ m = j m i Qj−1 j−1 n j−1 1 1 k=0 (n − k) ≤n . j! m m j! Vysvˇetlen´ı: Prvn´ı nerovnost plyne z toho, ˇze pravdˇepodobnost disjunkce jev˚ u je menˇs´ı neˇz souˇcet pravdˇepodobnost´ı jev˚ u, druhá nerovnost plyne z toho, ˇze i-t´ y ˇretˇezec má délku alespoˇ n j, jakmile existuje podmnoˇzina A ⊆ S taková, ˇze |A| = j (tˇechto moˇznost´ı je nj ) 1 j a pro kaˇzdé x ∈ A plat´ı h (x) = i (pravdˇepodobnost tohoto jevu je m ).

6

D˚ usledek. n j−1 1 Prob max (` (i)) ≥ j ≤ min 1, n . i m j! Pˇredpoklad: α =

n m

(#2)

≤ 1. Ukáˇzeme, ˇze pro dostateˇcnˇe velká n pro

n j−1 1 j0 = min j | n ≤1 m j! plat´ı j0 ≤

8 log n log log n .

Z

n m

j 2

≤1az

2j

≤ j! plyne

( 2j ) n j−1 1 n j min j | n ≤ 1 ≤ min j | ≤ 1 ≤ min j | n ≤ m j! j! 2

Výraz zanedbáváme, protože <= 1.

(#3)

pro kaˇzdé n ≥ 1, kde j prob´ıhá pˇrirozená ˇc´ısla. Pro pevné n oznaˇcme 2j ) j k + 1 = min j | n ≤ , 2 (

pak k2 k+1 k k+1 2
Jde odhadout shora výrazem 2 log((k+1)/2)

Za pˇredpokladu, ˇze k ≥ 3, tak dostáváme, ˇze log log n < 2 log k log k2 k log n < < , k+1 8 4 log 2 log log n

k+1 2

, a odtud plyne

1/2 < ^^

protoˇze pro k ≥ 3 je

1 2

<

( )

log k 2 log k+1 2

. Pˇri sofistikovanˇejˇs´ı metodˇe, kdyˇz se pouˇzije Stirlingova ( ) aproximace log j!, lze dok´ azat, ˇze j0 < (1 + aj ) logloglogn n , kde limj7→∞ aj = 0.

7

Toto pouˇzijeme pˇri odhadu E (N P ). X

E (N P ) =

j

X j

[Počítáme stále očekávanou délku nejdelšího řetězce]

Prob max (` (i)) ≥ j ≤ i

n j−1 1 min 1, n = m j!

j0 X

∞ ∞ X X n n j−1 1 ≤ j0 + = n 1+ m j! j! j=j0 +1 j=1 j=j0 +1 ∞ X 1 j−j0 n X j0 ! j0 + = ≤ j0 + j0 ! j=j +1 j! j + 1 0 j=j +1 0

j0 +

1 j0 +1 − j01+1 +

0

1

= j0 +

1 = O (j0 ) . j0

n ≤ 1, pˇri tˇret´ı nerovnosti jsme pouˇzili, Vysvˇetlen´ı: Pˇri druhé nerovnosti jsme pouˇzili, ˇze m n ˇze j0 ! ≤ 1 a j−j0 1 j0 ! 1 . = Qj ≤ j! j0 + 1 k=j0+1 k

Shrneme z´ıskan´ y v´ ysledek

n m

≤ 1 je pˇri haˇsov´ ymi ˇretˇezci horn´ı odhad an´ı se separovan´ log n oˇcek´ avané délky maxim´ aln´ıho ˇretˇezce O log log n . Kdyˇz 0.5 ≤ α ≤ 1, je to z´ aroveˇ n i doln´ı odhad. [Bez důkazu] Vˇ eta. Za pˇredpokladu α =

Oˇ cek´ avan´ y poˇ cet test˚ u. Def:

Test je porovnán´ı argumentu operace s prvkem na daném m´ıstˇe ˇretˇezce nebo zjiˇstˇen´ı, ˇze vyˇsetˇrovan´ y ˇretˇezec je prázdn´ y. Budeme rozliˇsovat dva pˇr´ıpady: u ´spˇeˇsné vyhledáván´ı – argument operace je mezi prvky reprezentované mnoˇziny, ne´ uspˇeˇsné vyhledáván´ı – argument operace nen´ı mezi prvky reprezentované mnoˇziny. Ne´ uspˇ eˇ sn´ e vyhled´ av´ an´ı. Oˇcekávan´ y poˇcet test˚ u: E (T ) = Prob (` (i) = 0) +

X

l Prob (` (i) = l) =

l

pn,0 +

X

lpn,l =

l

n n 1 + ≈ e−α + α. 1− m m

8

Vysvˇetlen´ı: Zjiˇstˇen´ı, zda ˇretˇezec je prázdn´ y, vyˇzaduje jeden test, tj. Prob (` (i) = 0) nen´ı s koeficientem 0, ale 1. Protoˇze pravdˇepodobnosti jsou stejné pro P vˇsechny ˇretˇezce, nemus´ıme specifikovat ˇretˇezec, kter´ y vyˇsetˇrujeme, staˇc´ı ps´ at obecnˇe i. c´ıtali pˇri l lpn,l jsme spoˇ v´ ypoˇctu oˇcekávané délky ˇretˇezce. ´ eˇ Uspˇ sn´ e vyhled´ av´ an´ı. Zvolme jeden ˇretˇezec prvk˚ u o délce l. Poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v tomto ˇretˇezci je l+1 . 1+2+···+l = 2 Oˇcekávan´ y poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v nˇejakém ˇretˇezci je X l + 1 X l+1 pn,l . Prob (` (i) = l) = 2 2 l

l

Oˇcekán´ y poˇcet test˚ u pˇri vyhledán´ı vˇsech prvk˚ u v tabulce je m

P

l+1 l 2

Oˇcekávan´ y poˇcet test˚ u pro vyhledán´ı jednoho prvku je ! n n n X m X 2 mX l+1 pn,l = l pn,l + lpn,l = 2 n 2n l=0

m 2n

l=0 n X l=1

pn,l .

l=0

l (l − 1) pn,l + 2

n X l=1

lpn,l

!

=

n−1 n (n − 1) 2n = + +1≈ 2 m m 2m α 1 1+ . 2 Jin´ y postup: Poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı prvku x ∈ S je 1+poˇcet porovn´ an´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı x v operaci INSERT(x). Poˇcet porovnán´ı kl´ıˇc˚ u je délka ˇretˇezce, a proto oˇcekávan´ y poˇcet porovnán´ı kl´ıˇc˚ u je oˇcekávaná délka ˇretˇezce. Tedy oˇcek´ avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı x je 1+oˇcekávaná délka ˇretˇezce v okamˇziku vkl´ ad´ an´ı x, neboli n−1 i 1X n−1 1+ =1+ . n i=0 m 2m m 2n

Vˇ eta. Pˇri haˇsov´ an´ı se separovan´ ymi ˇretˇezci je oˇcek´ avan´ y poˇcet test˚ u pˇri ne´ uspeˇsném vyhled´ avan´ı pˇribliˇznˇe e−α + α a pˇri u ´spˇeˇsném vyhled´ av´ an´ı pˇribliˇznˇe 1 + α2 . Následuj´ıc´ı tabulka dává pˇrehled oˇcekávaného poˇctu test˚ u pro r˚ uzné hodnoty α α ne´ usp. u ´spˇeˇs. α ne´ usp. u ´spˇeˇs.

vyh. vyh. vyh. vyh.

0 0.1 0.2 0.3 0.4 0.5 0.6 1 1.005 1.019 1.041 1.07 1.107 1.149 1 1.05 1.1 1.15 1.2 1.25 1.3 0.7 0.8 0.9 1 2 3 1.196 1.249 1.307 1.368 2.135 3.05 1.35 1.4 1.45 1.5 2 2.5

9

Příklad:

Volba \alpha:

Vˇsimnˇete si, ˇze oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı je menˇs´ı neˇz oˇcek´ avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı, kdyˇz α ≤ 1. Na prvn´ı pohled vypadá tento v´ ysledek nesmyslnˇe, ale d˚ uvod je, ˇze poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı pr˚ umˇerujeme proti n, kdeˇzto pˇri ne´ uspˇeˇsném vyhledáván´ı proti m. Ilustrujeme to na následuj´ıc´ım pˇr´ıkladu: ˇ Nechˇt n = m azdn´ ych ˇretˇezc˚ u má délku 1 a polovina má délku 2. 2 a necht polovina nepr´ Oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledávan´ı: 1 test pro prázdné ˇretˇezce a ˇretˇezce délky 1 – tˇechto pˇr´ıpad˚ u je 5m 6 m 2 testy pro ˇretˇezce délky 2 – tˇechto pˇr´ıpad˚ u je 6 . 7 1 m Oˇcekávan´ y poˇcet test˚ u je m 1 5m 6 + 2 6 = 6. Oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı: 1 test pro prvky na prvn´ım m´ıstˇe ˇretˇezce – tˇechto pˇr´ıpad˚ u je 2n 3 2 testy pro prvky, které jsou na druhém m´ıstˇe ˇretˇezce – tˇechto pˇr´ıpad˚ u je n3 . n 4 Oˇcekávan´ y poˇcet test˚ u je n1 1 2n 3 + 2 3 = 3. Velikost α je doporuˇcována menˇs´ı neˇz 1, ale nemá b´ yt hodnˇe mal´ a, protoˇze by pamˇeˇt nebyla efektivnˇe vyuˇzita. ´ n´ı s uspor ˇa ´ dany ´ mi separovany ´ mi r ˇetˇ Haˇ sova ezci Vylepˇsen´ı metody: haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci. Rozd´ıl proti p˚ uvodn´ı metodˇe – ˇretˇezce jsou uspoˇrádané ve vzr˚ ustaj´ıc´ım poˇrad´ı. Protoˇze ˇretˇezce obsahuj´ı tytéˇz prvky, je poˇcet oˇcekávan´ ych test˚ u pˇri u ´spˇeˇsném vyhledáván´ı stejn´ y jako u neuspoˇrádan´ ych ˇretˇezc˚ u. Pˇri ne´ uspˇeˇsném vyhledáván´ı konˇc´ıme, kdyˇz argument operace je menˇs´ı neˇz vyˇsetˇrovan´ y prvek v ˇretˇezci, tedy konˇc´ıme dˇr´ıv. Následuj´ıc´ı vˇeta (bez d˚ ukazu) uvád´ı oˇcekavan´ y poˇcet test˚ uv ne´ uspˇeˇsném pˇr´ıpadˇe. Vˇ eta. Oˇcek´ avan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhled´ av´ an´ı pro haˇsov´ an´ı s uspoˇra ´dan´ ymi avan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhˇretˇezci je pˇribliˇznˇe e−α + 1 + α2 − α1 (1 − e−α ). Oˇcek´ led´ av´ an´ı pro haˇsov´ an´ı s uspoˇra ´dan´ ymi ˇretˇezci je pˇribliˇznˇe 1 + α2 . [bez důkazu] Uvedeme algoritmy pro operace s uspoˇrádan´ ymi ˇretˇezci. Algoritmy. MEMBER(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t = x then x ∈ S else x ∈ / S endif INSERT(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu

10

while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t 6= x then if x < t then [Může se stát jen když t je poslední prvek] vloˇz´ıme x do i-tého seznamu pˇred prvek t else vloˇz´ıme x do i-tého seznamu za prvek t endif endif DELETE(x): Spoˇc´ıtáme i := h (x), t := N IL if i-t´ y seznam je neprázdn´ y then t :=prvn´ı prvek i-tého seznamu while t < x a t 6=posledn´ı prvek i-tého seznamu do t :=následuj´ıc´ı prvek i-tého seznamu enddo endif if t = x then odstran´ıme x z i-tého seznamu endif Nev´ yhody haˇsovan´ı se separovan´ ymi ˇretˇezci – nevyuˇzit´ı alokované pamˇeti (nehospodárné) pouˇz´ıván´ı ukazatel˚ u (cache). ˇ Reˇsen´ı: vyuˇz´ıt pro ˇretˇezce p˚ uvodn´ı tabulku. Poloˇzky tabulky: key, odkaz na uloˇzená data, poloˇzky pro práci s tabulkou. Předpoklad o datech:

Druhy hašování:

Pˇredpokládáme, ˇze data jsou velká, v tom pˇr´ıpadˇe se ukládaj´ı mimo tabulku. V tabulce je jen odkaz na uloˇzená data. Pˇri popisu práce s tabulkou tuto ˇcást budeme vynechávat (tj. data budou pouze kl´ıˇc). Podle ˇreˇsen´ı kolize dˇel´ıme dál haˇsován´ı: haˇsován´ı s pˇrem´ısˇtován´ım, haˇsován´ı s dvˇema ukazateli, sr˚ ustaj´ıc´ı haˇsován´ı, dvojité haˇsován´ı a haˇsován´ı s lineárn´ım pˇridáván´ım. ´ n´ı s pr ˇ em´ıst ˇova ´ n´ım Haˇ sova Poloˇzky pro práci s tabulkou: next, previous poloˇzka next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı poloˇzku seznamu poloˇzka previous – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı pˇredcházej´ı poloˇzku seznamu. Pˇr´ıklad: U = {1, 2, . . . , 1000}, h (x) = x mod 10, uloˇzená mnoˇzina S = {1, 7, 11, 53, 73, 141, 161},

11

ˇretˇezce: P (1) = (1, 141, 11, 161), P (3) = (73, 53), P (7) = (7). Haˇsovac´ı tabulka: ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next previous

1

9

73

6

161 53 7 11 141

[Jednotlivé seznamy]

8 3 5 8

9 1

Tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(161). Algoritmy. MEMBER(x): Spoˇc´ıtáme i := h (x) if i.previous 6=prázdné nebo i.key =prázdné then V´ ystup: x ∈ / S, stop endif while i.next 6=prázdné a i.key 6= x do i := i.next enddo if i.key = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif DELETE(x): Spoˇc´ıtáme i := h (x) if i.previous 6=prázdné nebo i.key =prázdné then stop endif [Nejsem na začátku seznamu] while i.next 6=prázdné a i.key 6= x do i := i.next enddo [Hledám prvek x] if i.key = x then [Nalezl jsem prvek x] if i.previous 6=prázdné then (i.previous) .next := i.next [Můj předchůdce musí ukazovat na mého následníka] if i.next 6=prázdné then (i.next) .previous := i.previous endif [Můj následník musí ukazovat x po sobě smaže na mého předchůdce] i.key := i.next := i.previous := prázdné [Prvek svůj řádek v tabulce] else [Předchůdce prvku x není, takže x je první prvek v seznamu] if i.next 6=prázdné then i.key := (i.next) .key, i.next := (i.next) .next [Zkopíruju následníka na řádek, kde je nyní x] if ((i.next) .next) 6=prázdné then ((i.next) .next) .previous := i endif [Po přesunutí následníka na (i.next) .key := (i.next) .next := (i.next) .previous := prázdné pozici x by mohl mít následník else následníka špatnou i.key := prázdné [Prvek x nemá ani předchůdce ani následníka, mažu klíč] hodnotu previous] endif endif endif

12

INSERT(x): Spoˇc´ıtáme i := h (x) if i.previous 6= N IL nebo i.key = N IL then [Prázdný seznam nebo neprázdný předek] if i.key = N IL then i.key := x [Do prázdného seznamu jen přidám klíč a hotovo] mám již nějaký prvek v seznamu nebo hůř: do mého seznamu else [Buď prorostl jiný seznam] if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky j.key := i.key, j.previous := i.previous, j.next := i.next (j.previous) .next := j if j.next 6= N IL then (j.next) .previous := j endif i, .key := x, i.next := i.previous :=prázdné endif endif stop endif while i.next 6= N IL a i.key 6= x do i := i.next enddo if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky i.next := j, j.key := x, j.previous := i, stop endif endif endif V pˇr´ıkladu provedeme INSERT(28), nov´ y ˇrádek je 4. ˇrádek – v´ ysledná haˇsovac´ı tabulka

ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next previous

1

9

73 11 161 53 7 28 141

6 5

4

9 4 3

1

První případ. Všimněte si příkazu STOP, tedy toto je jedna větev algritmu. Z nějakého důvodu není použito ELSE, což by bylo přehlednější.

[Přemísťujeme prvek i, protože patří do jiného seznamu, musíme tedy udělat místo pro prvek našeho nového jednoprvkového seznamu.]

[Dojedu si na konec seznamu /nebo najdu vkládaný prvek a končím.]

13 Očekávaný počet testů:

Oˇcekávan´ y poˇcet test˚ u je stejn´ y jako pro haˇsován´ı se separovan´ ymi ˇretˇezci: α + 1 ≈ 1 + u ´spˇeˇsné vyhledáván´ı: n−1 2m 2 1 n n ne´ uspˇeˇsné vyhledáván´ı: 1 − m +m ≈ e−α + α, kde m = velikost tabulky, n = velikost S tj. poˇcet uloˇzen´ ych prvk˚ u, α = zaplnˇen´ı.

n m

= faktor

´ n´ı s dvˇ Haˇ sova ema ukazateli Nevýhoda hašování s přemísť. je přemístování:

Nev´ yhoda haˇsován´ı s pˇrem´ısˇtován´ım je krok 5) v operaci INSERT. Vyˇzaduje v´ıce ˇcasu – operace s pˇrem´ıstˇen´ım poloˇzky. Toto odstraˇ nuje dalˇs´ı implementace haˇsován´ı se separuj´ıc´ımi ˇretˇezci.

: )

Poloˇzky pro práci s tabulkou – next, begin Poloˇzka next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı poloˇzku seznamu Poloˇzka begin – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı prvn´ı poloˇzku seznamu s touto adresou Stejná data jako v minulém pˇr´ıpadˇe Haˇsovac´ı tabulka:

Pozn:


key

next begin

1

9

1

73

7

3

161 7 53 11 141

6 5 8

Tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(161). Algoritmy. MEMBER(x): Spoˇc´ıtáme i := h (x) if i.begin = prázdné then V´ ystup: x ∈ / S, stop else i := i.begin endif while i.next 6= prázdné a i.key 6= x do i := i.next enddo if i.key = x then

14

V´ ystup: x ∈ S else V´ ystup: x ∈ /S endif DELETE(x): Spoˇc´ıtáme i := h (x) if i.begin =prázdné then stop else j := i, i := i.begin endif [j je jakýsi předchozí prvek pro while i.next 6=prázdné a i.key 6= x do j := i, i := i.next enddo [Hledám klíč x] if i.key = x then if i = j.begin then [Chceme správně nastavit hodnotu begin, pokud by byla smazáním prvku i ovlivněna] if i.next 6=prázdné then j.begin := i.next else j.begin :=prázdné endif else j.next := i.next endif i.key := i.next :=prázdné [Promažeme řádku i] endif INSERT(x): Spoˇc´ıtáme i := h (x) if i.begin =prázdné then Přidáváme do prázdného if i.key =prázdné then i.key := x, i.begin := i else if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky j.key = x, i.begin := j endif endif else i := i.begin while i.next 6=prázdné a i.key 6= x do i := i.next enddo if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky, i.next := j, j.key := x, stop endif endif endif

seznamu.

i]

15 Příklad:

V pˇr´ıkladu provedeme INSERT(28), nov´ y ˇrádek je 4. ˇrádek – v´ ysledná haˇsovac´ı tabulka ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key

next begin

1

9

1

73 28 161 7 53 11 141

7

3

5 8

6 4

Algoritmus pˇri práci s poloˇzkami je rychlejˇs´ı neˇz pˇri haˇsován´ı s pˇrem´ısˇtován´ım, ale zaˇc´ atek ˇretˇezce v jiném m´ıstˇe tabulky pˇridává jeden test. V´ ysledek bez odvozován´ı: Oˇcekávan´ y poˇcet test˚ u: 2 u ´spˇeˇsn´ y pˇr´ıpad: 1 + (n−1)(n−2) + n−1 ≈ 1 + α6 + α2 6m2 2m 2 ne´ uspˇeˇsn´ y pˇr´ıpad: ≈ 1 + α2 + α + e−α (2 + α) − 2. ´ n´ı Sr˚ ustaj´ıc´ı haˇ sova Terminologie:

Sr˚ ustaj´ıc´ı haˇsován´ı se dˇel´ı podle práce s pamˇet´ı na standardn´ı a na sr˚ ustaj´ıc´ı haˇsov´ an´ı s pomocnou pamˇet´ı (které se naz´ yva jen sr˚ ustaj´ıc´ı haˇsován´ı) a podle zp˚ usobu pˇrid´ av´ an´ı dalˇs´ıho prvku. Pop´ıˇseme metody: Standardn´ı sr˚ ustaj´ıc´ı haˇsován´ı: LISCH, EISCH, Sr˚ ustaj´ıc´ı haˇsován´ı: LICH, VICH, EICH. Vˇsechny metody pro práci s tabulkou pouˇz´ıvaj´ı jen poloˇzku next – ˇc´ıslo ˇrádku tabulky obsahuj´ıc´ı následuj´ıc´ı poloˇzku seznamu. Základn´ı idea: ˇretˇezec zaˇc´ıná na svém m´ıstˇe, ale pokud uˇz tam byl uloˇzen nˇejak´ yu ´daj, pak ˇretˇezec tohoto u ´daje sroste s ˇretˇezcem zaˇc´ınaj´ıc´ım na tomto ˇrádku. To znamená, ˇze prvky ˇretˇezce, kter´ y zaˇc´ıná na tomto m´ıstˇe budou uloˇzeny v ˇretˇezci, kter´ y uˇz je uloˇzen na tomto m´ıstˇe, ale jen od tohoto m´ısta dál. Metody EISCH a LISCH. EISCH – early-insertion standard coalesced hashing LISCH – late-insertion standard coalesced hashing. Organizace tabulky je stejná jako v pˇredchoz´ıch pˇr´ıpadech. Základn´ı ideje: LISCH pˇridává nov´ y prvek na konec ˇretˇezce, EISCH pˇridává nov´ y prvek x do ˇretˇezce za ˇrádkem h (x).

16 Příklad:

Pˇr´ıklad: U = {1, 2, . . . , 1000}, h (x) = x mod 10 mnoˇzina S = {1, 7, 11, 53, 73, 141, 171} je uloˇzena v haˇsovac´ı tabulce ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key next 1

9

73

6

7 53 161 11 141

5 7 8

Tabulka pro metodu LISCH vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(141), INSERT(11), INSERT(73), INSERT(53), INSERT(161), INSERT(7). Pro metodu EISCH tabulka vznikla následuj´ıc´ı posloupnost´ı operac´ı: INSERT(1), INSERT(161), INSERT(11), INSERT(73), INSERT(53), INSERT(7), INSERT(141). Provedeme INSERT(28), pˇridáváme do ˇcvrtého rádku, v´ ysledná tabulka vlevo je pro metodu LISCH, vpravo pro metodu EISCH. ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9)

key next 1

9

73 28 7 53 161 11 141

6 4 5 7 8


key next 1

9

73 28 7 53 161 11 141

6 7

Algoritmy. Algoritmus operace MEMBER je pro obˇe metody stejn´ y. MEMBER(x): Spoˇc´ıtáme i := h (x) while i.next 6=prázdné a i.key 6= x do i := i.next enddo if i.key = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif

5 4 8

17

Metoda LISCH – INSERT(x): Spoˇc´ıtáme i := h (x) while i.next 6=prázdné a i.key 6= x do i := i.next enddo [Dojedu na konec seznamu] if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je prázdn´ y ˇrádek, j.key := x, i.next := j [Přidám prvek na konec seznamu] endif endif Metoda EISCH – INSERT(x): Spoˇc´ıtáme k := i := h (x) while i.next 6=prázdné a i.key 6= x do i := i.next enddo [Dojedu na konec seznamu] if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then V´ ystup: pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky j.next := k.next, k.next := j, j.key := x [Posledním prvkem je nyní druhý prvek a prvkem je vkládaný prvek x] endif endif Operace DELETE:

druhým

Efektivn´ı operace DELETE nen´ı známá, ale i primitivn´ı algoritmy pro operaci DELETE maj´ı rozumnou oˇcekávanou ˇcasovou sloˇzitost. Anal´ yza sloˇ zitosti tˇ echto algoritm˚ u.. Popis situace: Uloˇzena mnoˇzina S = {s1 , s2 , . . . , sn } do tabulky velikosti m, je dán prvek sn+1 a máme zjistit, zda sn+1 ∈ S. Oznaˇcme ai = h (si ) pro i = 1, 2, . . . , n + 1, kde h je pouˇzitá haˇsovac´ı funkce. Pˇredpoklad: vˇsechny posloupnosti a1 , a2 , . . . , an+1 jsou stejnˇ e pravdˇ epodobn´ e. V´ ybˇer prázdného ˇrádku je pevnˇe dan´ y, to znamená, ˇze pˇri stejnˇe obsazen´ ych ˇradc´ıch dostaneme vˇzdy stejn´ y prázdn´ y ˇrádek. Ne´ uspˇ eˇ sn´ e vyhled´ av´ an´ı (sn+1 ∈ / S)..

Oznaˇcen´ı: C (a1 , a2 , . . . , an ; an+1 ) oznaˇcuje poˇcet test˚ u pro zjiˇstˇen´ı, ˇze sn+1 ∈ / S. Plat´ı: oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı v mnoˇzinˇe S je P Def:

C (a1 , a2 , . . . , an ; an+1 ) , mn+1

kde se sˇc´ıtá pˇres vˇsechny posloupnosti a1 , a2 , . . . , an+1 – a tˇech je mn+1 . ˇ ezec délky l v mnoˇzinˇe S je maximáln´ı posloupnost adres (b1 , b2 , . . . , bl ) takov´ Retˇ a, ˇze bi .next = bi+1 pro i = 1, 2, . . . , l − 1. Kdyˇz adresa an+1 je i-t´ y prvek v ˇ r etˇ e zci, pak poˇ cet P test˚ u je l − i + 1. Proto ˇretˇezec délky C (a1 , a2 , . . . , an ; an+1 ) celkem l pˇrispˇel k souˇctu l [Součet aritmetické posloupnosti: L/2 (1+L) = (L over 2) poˇctem test˚ u 1+2+···+l = l + 2 .

+ L]

Pozn: l = L, jen rozdíl mezi l a 1 není vidět, tak používám L.

18 Def: Výpočet pro počet testů v neúsp. př.

cn (l) = poˇcet vˇsech ˇretˇezc˚ u délky l ve vˇsech reprezentac´ıch n-prvkov´ ych mnoˇzin (ztotoˇzn ˇujeme dvˇe mnoˇziny, které mˇely stejnou posloupnost adres pˇri ukládan´ı prvk˚ u), pak n X X l cn (l) C(a1 , a2 , . . . , an ; an+1 ) = cn (0) + l+ [Rozdělím na dvě 2 l=1 n n X X l cn (l) , = cn (0) + lcn (l) + Počet testů pro 2 délky l. l=1

sumy]

řetězec

l=1

kde cn (0) je poˇcet prázdn´ ych ˇrádk˚ u ve vˇsech reprezentac´ıch. Reprezentace S má m − n prázdn´ ych ˇrádk˚ u, [Nemůžu mít n > m prvků, protože by se mi do tabulky nevešly] n [m^n je počet možností, jak se mohou prvky S vˇsech posloupnost´ı n-adres je m , proto zahašovat do tabulky, každá taková tabulka má cn (0) = (m − n) mn .

Pn

m n prázdných řádků; to že se prázdné řádky opakují nám nevadí, protože počítáme stále součet (SUMU) a ne průměr.]

lcn (l) je celková délka vˇsech ˇretˇezc˚ u ve vˇsech tabulkách reprezentuj´ıc´ıch vˇsechny nprvkové mnoˇziny a proto n X lcn (l) = nmn . l=1

l=1

Pn

l

Spoˇc´ıtáme Sn = l=1 2 cn (l). Nejprve rekurentn´ı vztah pro cn (l). Pˇridáváme prvek s adresou an+1 . Pak ˇretˇezec délky l v reprezentaci S z˚ ustal stejn´ y, kdyˇz adresa an+1 neleˇzela v tomto ˇretˇezci, v opaˇcném pˇr´ıpadˇe se délka ˇretˇezce zvˇetˇsila na l + 1. Proto pˇridán´ı jednoho prvku vytvoˇrilo z ˇretˇezce délky l celkem m − l ˇretˇezc˚ u délky l a l ˇretˇezc˚ u délky l + 1. Vysˇc´ıtán´ım pˇres vˇsechny n-prvkové posloupnosti adres dostáváme cn+1 (l) = (m − l) cn (l) + (l − 1) cn (l − 1) . Odtud

Poslední člen první

n X l cn (l) = Sn = 2 l=1 n X l l (l − 1) cn−1 (l − 1) = [Použili jsme rekurentní vztah] (m − l) cn−1 (l) + 2 2 l=1 ! ! n−1 n X l + 1 X l lcn−1 (l) = [Rozdělili jsme na dvě sumy] (m − l) cn−1 (l) + 2 2 l=0 l=1 n (m − n) cn−1 (n) + první člen druhé sumy 2 0 sumy ! n−1 X l 1 l+1 0cn−1 (0) = l cn−1 (l) + (m − l) + 2 2 2 l=1 n−1 n−1 X X l (m + 2) cn−1 (l) + lcn−1 (l) = 2 l=1

l=1 n−1

(m + 2) Sn−1 + (n − 1) m

,

19

kde jsme pouˇzili, ˇze cn−1 (n) = 0, a identitu 1 l+1 l = l2 m − lm − l3 + l2 + l3 + l2 = +l (m − l) 2 2 2 1 2 l m − lm + 2l2 = 2 1 2 l m − lm + 2 l2 − l + l = 2 l + l. (m + 2) 2 Rekurence pro Sn dává Sn = (m + 2) Sn−1 + (n − 1) mn−1 = 2

(m + 2) Sn−2 + (m + 2) (n − 2) mn−2 + (n − 1) mn−1 = 3

2

(m + 2) Sn−3 + (m + 2) (n − 3) mn−3 + (m + 2) (n − 2) mn−2 + (n − 1) mn−1 = n−1

0

(m + 2)

S0 +

n−1 X i=0

n−1

(m + 2)

n−1 X

(n − 1 − i)

i=0

n−1

(m + 2)

i

(m + 2) (n − 1 − i) mn−1−i =

n−1 X

i

i=1

m m+2

i

m m+2

(c −

=cTcn

−

Tcn

ncn+1 +

=

n+1 X

i=2 n X i=2

ncn+1 +

n X i=2

ncn+1 − n+2

nc

n X i=1

=

[Je jedno zda suma pojede od "začátku" či "od konce".]

,

kde jsme ˇze S0 = 0. Spoˇc´ıtáme souˇcet Tcn = Pnvyuˇzili, n i+1 plyne cTc = i=1 ic 1) Tcn

n−1−i

Pn

i=1

i

ici pro n = 1, 2, . . . a c 6= 1. Z

(i − 1) c −

n X

ici =

i=1

! −c= (i − 1) ci − ici

−ci

!

Sečetl jsem pár členů geom. řady

−c=

ci = ncn+1 −

− (n + 1) cn+1 + c . c−1

cn+1 − c = c−1

20

Tedy plat´ı Tcn = Protoˇze

m m+2

2

(c − 1)

6= 1, dostáváme, ˇze

Sn = (m + 2)

n−1

(n − 1) "

Výsledný odhad počtu testů při neúspěšném vyhledávání:

ncn+2 − (n + 1) cn+1 + c

m m+2

n+1

−n

m m+2

m m+2 2

−1 n+1

n

.

+

m m+2

= [Zůstalo stejné]

n

m m 1 n+1 −n (m + 2) (n − 1) 4 m+2 m+2 1 n (n − 1) mn+1 − n (m + 2) mn + m (m + 2) = 4 1 n m (m + 2) − mn+1 − 2nmn . 4

# m = + m+2

Oˇcekávan´ y poˇcet test˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı je

n m (m + 2) − mn+1 − 2nmn = mn+1 n mn+1 + 41 m (m + 2) − mn+1 − 2nmn = mn+1 n 2 2n 1 2α 1 1+ −1− ∼1+ e − 1 − 2α . 1+ 4 m m 4 (m − n) mn + nmn +

1 4

Tento odhad je stejn´ y pro obˇe metody – LISCH i EISCH, protoˇze maj´ı stejné posloupnosti adres (liˇs´ı se jen poˇrad´ım prvk˚ u v jednotliv´ ych ˇretˇezc´ıch). ´ eˇ Uspˇ sn´ y pˇ r´ıpad (sn+1 ∈ S). Oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhledáván´ı v modelu LISCH spoˇc´ıtáme stejnou metodou jako pro haˇsován´ı se separuj´ıc´ımi ˇretˇezci. Pro vyhledán´ı prvku sn+1 ∈ S je poˇcet test˚ u roven 1+poˇcet porovnán´ı kl´ıˇc˚ u pˇri operaci INSERT(sn+1 ). Kdyˇz sn+1 je vloˇzen na m´ısto h (sn+1 ), nebyl porovnáván ˇzádn´ y kl´ıˇc a test bude 1, kdyˇz h (sn+1 ) byl na na i-tém m´ıstˇe v ˇretˇezci délky l, pak bylo pˇri operaci INSERT(sn+1 ) pouˇzito l − i + 1 porovnán´ı kl´ıˇc˚ ua ˇ se pouˇzije l − i + 2 test˚ ted u. Podle pˇredchoz´ı ˇcásti anal´ yzy dostaneme, ˇze oˇcekávan´ y poˇcet porovnán´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı je ! n X 1 l cn (l) = l+ mn+1 2 l=1 1 1 n n+1 n n m (m + 2) − m − 2nm = nm + mn+1 4 n 2 2n 1 1+ . −1+ 4 m m

21 Očekávaný počet testů v úspěšném případě pro metodu LISCH:

Tedy oˇcekávan´ y poˇcet test˚ u pˇri u ´spˇeˇsném vyhled´ aván´ı v n-prvkové mnoˇzinˇe je podle pˇredchoz´ı anal´ yzy roven 1 + n-tina souˇctu oˇcekávaného poˇctu porovnán´ı kl´ıˇc˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı v i-prvkové mnoˇzinˇe, kde i prob´ıhá ˇc´ısla 0, 1, . . . , n − 1. Podle pˇredchoz´ıch v´ ysledk˚ u je hledan´ y souˇcet n−1 X i=0

i 1 2i 2 −1 + ] = [ 1+ 4 m m m 1+ 8

n 2 n −1 n 1 1+ m 2 − + = 2 4 1+ m 4 2m −1 n 2 n2 − n 2n + −1− . m m 4m

Tedy oˇcekávan´ y poˇcet test˚ uvu ´spˇeˇsném pˇr´ıpadˇe pro n-prvkovou mnoˇzinu je m 1+ 8n Dtto pro metodu EISCH:

n α 2 n−1 2n 1 1+ + e2α − 1 − 2α + . −1− ∼1+ m m 4m 8α 4

Pro metodu EISCH je oˇcekáván´ y poˇcet test˚ uvu ´spˇeˇsném pˇr´ıpadˇe m n

1 1+ m

n

−1

∼

1 α (e − 1) . α

V´ ypoˇcet je ale komplikovanˇejˇs´ı mus´ı se pouˇz´ıt sloˇzitˇejˇs´ı metoda (metoda EISCH dáv´ a nov´ y 1 prvek hned za m´ısto, kde má b´ yt uloˇzen). Chyba aproximace pro tyto odhady je O m .

Metody LICH, EICH, VICH.

LICH – late-insertion coalesced hashing EICH – early-insertion coalesced hashing VICH – varied-insertion coalesced hashing. Základn´ı idea: Metody pouˇz´ıvaj´ı pomocnou pamˇeˇt. Tabulka je rozdˇelená na adresovac´ı ˇc´ ast ˇ a na pomocnou pamˇet, která nen´ı dostupná pomoc´ı haˇsovac´ı funkce, ale pomáhá pˇri ˇreˇsen´ı koliz´ı. Metody se liˇs´ı operac´ı INSERT. Vˇsechny metody pˇri kolizi nejprve pouˇzij´ı ˇr´ adek tabulky z pomocné ˇcásti a teprve, kdyˇz je pomocná ˇcást zaplnˇena, pouˇz´ıvaj´ı adresovac´ı ˇc´ ast. Metoda LICH: pˇri INSERTu vkládá prvek vˇzdy na konec ˇretˇezce. Metoda EICH: pˇri INSERTu vkládá prvek x do ˇretˇezce vˇzdy na m´ısto hned za ˇr´ adkem h (x). Metoda VICH: Pˇri INSERTu, kdyˇz nov´ y ˇrádek je z pomocné ˇcásti, tak je vloˇzen s nov´ ym prvkem na konec ˇretˇezce, kdyˇz je pomocná ˇcást pamˇeti vyˇcerpána, tak se ˇrádek s nov´ ym prvkem vkládá do ˇretˇezce za posledn´ı ˇrádek z pomocné ˇcásti tabulky. Kdyˇz ˇretˇezec neobsahuje ˇzádn´ y ˇrádek z pomocné pamˇeti, tak se ˇrádek s nov´ ym prvkem x vkládá hned za ˇr´ adek h (x). Idea: pomocn´ a ˇcást má zabránit rychlému sr˚ ustán´ı ˇretˇezc˚ u. DELETE:

Tyto metody nepodporuj´ı pˇrirozené efektivn´ı algoritmy pro operaci DELETE.

22

Pˇr´ıklad: U = {1, 2, . . . , 1000}, h (x) = x mod 10, S = {1, 7, 11, 53, 73, 141, 161}. Tabulka má 12 ˇrádk˚ u a má tvar

ˇrádek P(0) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11)

key next 1

10

73

11

7 161 11

5 7

141 53

8

Nepřístupná oblast pro hashovací fci: x mod 10

Haˇsovac´ı tabulka vznikla posloupnostmi operac´ı: Pro metodu LICH: INSERT(1), INSERT(73), INSERT(141), INSERT(53), INSERT(11), INSERT(161), INSERT(7). Pro metodu EICH: INSERT(1), INSERT(73), INSERT(161), INSERT(53), INSERT(11), INSERT(141), INSERT(7), ale nedodrˇzovalo se, ˇze se nejdˇr´ıv zaplˇ nuj´ı ˇrádky z pomocné ˇcásti. Pˇri dodrˇzován´ı tohoto pravidla takováto tabulka nem˚ uˇze vzniknout. Pro metodu VICH: INSERT(1), INSERT(73), INSERT(141), INSERT(53), INSERT(161), INSERT(11), INSERT(7). Aplikujeme operace INSERT(28) a INSERT(31), nové ˇrádky budou ˇrádky ˇc´ıslo 4 a 9. Tabulka vytvoˇrená pomoc´ı metody LICH je na levé stranˇe, metodou VICH je v prostˇredku a metodou EICH je na pravé stranˇe.

23 LICH


VICH

key next 1

10

73 28 7

11 9 4

161 11 31 141 53

5 7 8


EICH

key next 1

10

73 28 7

11 7

161 11 31 141 53

5 4 8 9


key next 1

9

73 28 7

11 7

161 11 31 141 53

5 4 10 8

Algoritmy. Algoritmus operace MEMBER je pro tyto metody stejn´ y jako pro LISCH a EISCH MEMBER(x): Spoˇc´ıtáme i := h (x) while i.next 6=prázdné a i.key 6= x do i := i.next enddo if i.key = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif Algoritmus operace INSERT je pro metodu LICH stejn´ y jako pro metodu LISCH a pro metodu EICH je stejn´ y jako pro metodu EISCH s jedin´ ym doplˇ nkem, pokud existuje pr´ azdn´ y ˇrádek v pomocné ˇcásti, tak j-t´ y ˇrádek je z pomocné ˇcásti. Tento pˇredpoklad je i pro algoritmus INSERT pro metodu VICH. Metoda LICH – INSERT(x): Spoˇc´ıtáme i := h (x) if i.next = N IL then i.next = x, stop endif while i.next 6= N IL a i.key 6= x do i := i.next enddo if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then pˇreplnˇen´ı, stop else nechˇt j je prázdn´ y ˇrádek, j.key := x, i.next := j endif endif Metoda EICH – Insert(x): Spoˇc´ıtáme k := i := h (x) if i.next = N IL then i.next = x, stop endif while i.next 6= N IL a i.key 6= x do i := i.next enddo if i.key 6= x then if neexistuje prázdn´ y ˇrádek tabulky then

24

pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek tabulky j.next := k.next, k.next := j, j.key := x endif endif Metoda VICH – INSERT(x): Spoˇc´ıtáme i := h (x) if i.next = N IL then i.next = x, stop endif while i.next 6= N IL a i.key 6= x do [Zapamatuju si prvek, který není v if k nen´ı definováno a i.next < m then k := i endif pomocné části. ] Poznámka: Podm´ınka pro k je splnˇena, kdyˇz jsme byli na zaˇcátku nebo v pomocné ˇca´sti, podm´ınka na i.next je splnˇena, kdyˇz i.next nen´ı v pomocné ˇcásti. i := i.next enddo if i.key 6= x then if neexistuje prázdn´ y ˇrádek then pˇreplnˇen´ı, stop else nechˇt j je voln´ y ˇrádek, j.key := x if k nen´ı definováno then [Když poslední prvek seznamu je v pomocné části] i.next := j else j.next := k.next, k.next := j endif endif endif Sloˇzitost algoritm˚ u pro sr˚ ustaj´ıc´ı haˇsován´ı. Znaˇcen´ı: n – velikost uloˇzené mnoˇziny, m – velikost adresovac´ı ˇcásti tabulky, m0 – velikost tabulky, α = mn0 – faktor zaplnˇen´ı, m ı faktor, β=m 0 – adresovac´ λ – jediné nezáporné ˇreˇsen´ı rovnice e−λ + λ =

1 . β

Oˇcekávan´ y poˇcet test˚ u pro metodu LICH ne´ uspˇeˇsn´ y pˇr´ıpad: α e− β + αβ , kdyˇz α ≤ λβ, α 2( β −λ) 1 1 1 α 2 e + + 2λ − − λ , kdyˇz α ≥ λβ − 1 3 − β 4 β 2 β u ´spˇeˇsn´ y pˇr´ıpad: α , kdyˇz α ≤ λβ, 1 + 2β α 1+ β e2( β −λ) − 1 − 2 α − λ 3 − 2 + 2λ + 1 α + λ + λ 1 − 8α

β

β

4

β

4

λβ α

, kdyˇz α ≥ λβ.

25

Oˇcekávan´ y poˇcet test˚ u pro metodu EICH ne´ uspˇeˇsn´ y pˇr´ıpad: α e− β + αβ , kdyˇz α ≤ λβ, α α 1 α 1 e2( β −λ) 34 + λ2 − 2β + e β −λ β1 − 1 + 14 − 2β , kdyˇz α ≥ λβ + 2β u ´spˇeˇsn´ y pˇr´ıpad: α , kdyˇz α ≤ λβ, 1 + 2β α α α e β −λ − 1 (1 + λ) − αβ − λ ), kdyˇz α ≥ λβ. + αβ 1 + λ2 + 2β 1 + 2β Oˇcekávan´ y poˇcet test˚ u pro metodu VICH ne´ uspˇeˇsn´ y pˇr´ıpad: −α β e + αβ , kdyˇz α ≤ λβ, α 2( β −λ) 1 1 α 2 1 − 1 3 − β + 2λ − 2 β − λ , kdyˇz α ≥ λβ β + 4 e u ´spˇeˇsn´ y pˇr´ıpad: α , kdyˇz α ≤ λβ, 1 + 2β α α α 1 + 2β e β −λ − 1 (1 + λ) − αβ − λ )+ + αβ 1 + λ2 + 2β kdyˇz α ≥ λβ. 0 Chyba aproximace pro tyto odhady je O log √mm0 .

1−β α

α β

α − λ − e β −λ + 1 ,

´ n´ı s linea ´ rn´ım pr ˇ ida ´ va ´ n´ım Haˇ sova Tabulka má jedinou poloˇzku – key Základn´ı idea: Pˇri operaci INSERT(x) vloˇz´ıme x na ˇrádek h (x), kdyˇz je prázdn´ y, v opaˇcném pˇr´ıpadˇe nalezneme nejmenˇs´ı i takové, ˇze ˇrádek h (x) + i mod m je prázdn´ y, a tam vloˇz´ıme x. Tato metoda byla motivována snahou o co nejvˇetˇs´ı vyuˇzit´ı pamˇeti. Komentáˇr: Metoda vyˇzaduje minimáln´ı velikost pamˇeti. V tabulce se vytváˇrej´ı shluky pouˇzit´ ych ˇrádk˚ u, a proto pˇri velkém zaplnˇen´ı metoda vyˇzaduje velké mnoˇzstv´ı ˇcasu. Metoda nepodporuje efektivn´ı implementaci operace DELETE. Pˇri vyhledáván´ı je tˇreba testovat, zda nevyˇsetˇrujeme podruhé prvn´ı vyˇsetˇrovan´ y ˇrádek a pro zjiˇstˇen´ı pˇreplnˇen´ı je vhodné m´ıt uloˇzen poˇcet vyplnˇen´ ych ˇrádk˚ u v tabulce. Pro standarn´ı pamˇeti nen´ı v´ yhodná. Pˇri pouˇziti cache-pamˇeti se v´ yraznˇe mˇen´ı jej´ı ohodnocen´ı, protoˇze minimalizuje poˇcet pˇrechod˚ u mezi r˚ uzn´ ymi typy pamˇet´ı. Proto se tato metoda doporuˇcuje pro poˇc´ıtaˇce s cache-pamˇet´ı. MEMBER(x): Spoˇc´ıtáme i := h (x), h := i if i.key = x then V´ ystup x ∈ S, stop endif if i.key =prázdn´ y then V´ ystup: x ∈ / S, stop endif i := i + 1 while i.key 6=prázdn´ y a i.key 6= x a i 6= h do i := i + 1 mod m enddo if i.key = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif INSERT(x): Spoˇc´ıtáme i := h (x), j := 0

26

while i.key 6=prázdn´ y a i.key 6= x a j < m do i := i + 1 mod m, j := j + 1 enddo if j = m then V´ ystup: pˇreplnˇen´ı, stop endif if i.key =prázdn´ y then i.key := x endif Pˇr´ıklad: Máme universum U = {1, 2, . . . , 1000}, haˇsovac´ı funkci h (x) = x mod 10 a mnoˇzinu S = {1, 7, 11, 53, 73, 141, 161}. Tato mnoˇzina je uloˇzena v levé tabulce. Provedeme operaci INSERT(35). V´ ysledek je uloˇzen v pravé tabulce. Insert 35


key 1 11 73 141 161 53 7


key 1 11 73 141 161 53 7 35

Tabulka vznikla posloupnost´ı operac´ı: INSERT(1), INSERT(11), INSERT(73), INSERT(141), INSERT(161), INSERT(53), INSERT(7). Na závˇer uvedeme sloˇzitost Oˇcekávan´ y poˇcet test˚ u: této metody. 2 1 ne´ uspˇeˇsn´ y pˇr´ıpad: ≈ 21 1 + 1−α , 1 . u ´spˇeˇsn´ y pˇr´ıpad: ≈ 21 1 + 1−α ´ n´ı Dvojit´ e haˇ sova

Nevýhoda lin. haš.:

Tabulka:

Pozn:

Základn´ı nev´ yhoda pˇredchoz´ı metody je zp˚ usob v´ ybˇeru dalˇs´ıho ˇrádku. Je velmi determinován a d˚ usledkem je vznik shluku ˇrádk˚ u, kter´ y vede k v´ yraznému zpomalen´ı metody. Idea jak odstranit tuto nev´ yhodu: Pouˇzijeme dvˇe haˇsovac´ı funkce h1 a h2 a pˇri operaci INSERT(x) nalezneme nejmenˇs´ı i = 0, 1, . . . takové, ˇze ˇrádek (h1 (x) + ih2 (x)) mod m je prázdn´ y, a tam uloˇz´ıme prvek x. Tabulka má jedinou poloˇzku – key. Poˇzadavky na korektnost: Pro kaˇzdé x mus´ı b´ yt h2 (x) a m nesoudˇelné (jinak prvek x nem˚ uˇze b´ yt uloˇzen na libovolném ˇrádku tabulky). m−1 Pˇredpoklad pro v´ ypoˇcet oˇcekavaného poˇctu test˚ u: posloupnost {h1 (x) + ih2 (x)}i=0 je náhodná permutace mnoˇziny ˇrádk˚ u tabulky. Nev´ yhoda: Uvedená metoda nepodporuje operaci DELETE. Pˇreplnˇen´ı se ˇreˇs´ı stejn´ ym zp˚ usobem jako v metodˇe haˇsován´ı s lineárn´ım pˇridáván´ım. Poznámka: Metoda haˇsován´ı s lineárn´ım pˇridáván´ım je speciáln´ı pˇr´ıpad dvojitého haˇsov´ an´ı, kde h2 (x) = 1 pro kaˇzdé x ∈ U .

27

Algoritmy. MEMBER(x): Spoˇc´ıtáme i := h1 (x), h := h2 (x), j := 0 while i.key 6=prázdn´ y a i.key 6= x a j < m do i := i + h mod m, j := j + 1 enddo if i.key = x then V´ ystup: x ∈ S else V´ ystup: x ∈ / S endif INSERT(x): Spoˇc´ıtáme i := h1 (x), h := h2 (x), j := 0 while i.key 6=prázdn´ y a i.key 6= x a j < m do i := i + h mod m, j := j + 1 enddo if j = m then V´ ystup: pˇreplnˇen´ı, stop endif if i.key =prázdn´ y then i.key := x endif Komplik. předpis funkce h_2:

Pˇr´ıklad: Mˇejme universum U = {1, 2, . . . , 1000}. Haˇsovac´ı funkce jsou h1 (x) = x mod 10 a h2 (x) = 1 + 2 (x mod 4), kdyˇz x mod 4 ∈ {0, 1}, h2 (x) = 3 + 2 (x mod 4), kdyˇz x mod 4 ∈ {2, 3}. Mnoˇzina je S = {1, 7, 11, 53, 73, 141, 161}. Tato mnoˇzina je uloˇzena v levé tabulce. Aplikujme INSERT(35). Pak h2 (35) = 9, tedy posloupnost pro x = 35 je (5, 4, 3, 2, 1, 0, 9, 8, 7, 6) . V´ ysledek je uloˇzen v pravé tabulce. Insert 35


key 11 1 73 141 7 53 161


key 11 1 35 73 141 7 53 161

Tabulka vznikla posloupnost´ı operac´ı: INSERT(1), INSERT(73), INSERT(53), INSERT(141), INSERT(161), INSERT(11), INSERT(7). Anal´ yza vyhledáván´ı v dvojitém haˇsován´ı. Ne´ uspˇ eˇ sn´ y pˇ r´ıpad. Znaˇcen´ı: qi (n, m) – kdyˇz tabulka má m ˇrádk˚ u a je v n´ı obsazeno n ˇrádk˚ u, tak je to pravdˇepodobnost, ˇze pro kaˇzdé j = 0, 1, . . . , i − 1 je ˇrádek h1 (x) + jh2 (x) obsazen. Pak n(n−1) n , q2 (n, m) = m(m−1) a obecnˇe q0 (n, m) = 1, q1 (n, m) = m Qi−1

j=0

qi (n, m) = Qi−1

(n − j)

j=0 (m − j)

.

28

C (n, m) – oˇcekávan´ y poˇcet test˚ u v ne´ uspˇeˇsném vyhledáv´ an´ı, kdyˇz tabulka má m ˇrádk˚ ua n jich je obsazeno. Podle definice plat´ı: C (n, m) =

n X j=0

(j + 1) (qj (n, m) − qj+1 (n, m)) =

n X

qj (n, m) .

j=0

n Dále plat´ı C (0, m) = 1 pro kaˇzdé m a qj (n, m) = m qj−1 (n − 1, m − 1) pro vˇsechna j, n > 0 [q_{j 1}(n 1,m 1) ... nějak je závorka uskočená a m > 1. Odtud   n−1 n X X n n  qj (n − 1, m − 1) = 1 + C (n − 1, m − 1) . C (n, m) = qj (n, m) = 1 + m j=0 m j=0

m+1 m+1 Indukc´ı ukáˇzeme, ˇze C (n, m) = m−n+1 . Kdyˇz n = 0, pak C (0, m) = m−0+1 = 1 a tvrzen´ı plat´ı. Pˇredpokládáme, ˇze tvrzen´ı plat´ı pro n − 1 ≥ 0 a pro kaˇzdé m ≥ n − 1 a dok´ aˇzeme tvrzen´ı pro n a m ≥ n. Plat´ı n C (n, m) =1 + C (n − 1, m − 1) = m n ((m − 1) + 1) 1+ = m ((m − 1) − (n − 1) + 1) m+1 n = . 1+ m−n+1 m−n+1

Oˇcekávan´ y poˇcet dotaz˚ u pˇri ne´ uspˇeˇsném vyhledáván´ı v tabulce s m ˇrádky, z nichˇz n je m+1 . obsazeno, je m−n+1

´ eˇ Uspˇ sn´ y pˇ r´ıpad. Pouˇzijeme metodu ze separuj´ıc´ıch ˇretˇezc˚ u. Poˇcet dotaz˚ u pˇri vyhledáván´ı x pro x ∈ S je stejn´ y jako byl poˇcet dotaz˚ u pˇri vkládán´ı x do tabulky. Tedy oˇcekávan´ y poˇcet dotaz˚ u pˇri u ´spˇeˇsném vyhledáván´ı v tabulce s m ˇrádky, z nichˇz n je obsazeno, je n−1 n−1 1X 1 X m+1 C (i, m) = = n i=0 n i=0 m − i + 1   m+1 m−n+1 X 1 m + 1 X 1 ≈ − n j j j=1 j=1 1 1 m+1 1 ≈ ln . ln α m−n+1 α 1−α

Následuj´ıc´ı tabulka ukazuje tyto hodnoty v závislosti na velikosti α. hodnota α 1 α

1 1−α

1 ln( 1−α )

0.5 2 1.38

0.7 3.3 1.70

0.9 10 2.55

0.95 20 3.15

0.99 0.999 100 1000 4.65 6.9

: ( ]

29

´ n´ı efektivity Porovna Poˇrad´ı metod haˇsován´ı podle oˇcekávaného poˇctu test˚ u: Ne´ uspˇ eˇ sn´ e vyhled´ av´ an´ı. Haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci, Haˇsovan´ı s ˇretˇezci=Haˇsován´ı s pˇrem´ısˇtován´ım, Haˇsován´ı s dvˇema ukazateli, VICH=LICH, EICH, LISCH=EISCH, Dvojité haˇsován´ı, Haˇsován´ı s lineárn´ım pˇridáván´ım. ´ eˇ Uspˇ sn´ e vyhled´ av´ an´ı. Haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci=Haˇsován´ı s ˇretˇezci=Haˇsován´ı s pˇrem´ısˇtován´ım, Haˇsován´ı s dvˇema ukazateli, VICH, LICH, EICH, EISCH, LISCH, Dvojité haˇsován´ı, Haˇsován´ı s lineárn´ım pˇridáván´ım. Poznámka: Metoda VICH pˇri ne´ uspˇeˇsném vyhledáván´ı pro α < 0.72 a pˇri u ´spˇeˇsném vyhledáván´ı pro α < 0.92 vyˇzaduje menˇs´ı oˇcekávan´ y poˇcet test˚ u neˇz metoda s dvˇema ukazateli. Pˇri ne´ uspˇeˇsném vyhledáván´ı jsou metody VICH a LICH stejné a jsou o 8% lepˇs´ı neˇz EICH a o 15% neˇz metody LISCH a EISCH. Pˇri u ´spˇeˇsném vyhledáván´ı je VICH nepatrnˇe lepˇs´ı neˇz LICH a EICH o 3% lepˇs´ı neˇz EISCH a o 7% lepˇs´ı neˇz LISCH. Oˇ cek´ avan´ y poˇ cet test˚ u pˇ ri u ´ plnˇ e zaplnˇ en´ e tabulce. ˇ Metoda s pˇrem´ıstován´ım: ne´ uspˇeˇsné vyhledáván´ı 1.5, u ´spˇeˇsné vyhledáván´ı 1.4. Metoda s dvˇema ukazateli: u ´spˇeˇsné i ne´ uspˇeˇsné vyhledáván´ı 1.6. VICH: ne´ uspˇeˇsné vyhledáván´ı 1.79, u ´spˇeˇsné vyhledáván´ı 1.67. LICH: ne´ uspˇeˇsné vyhledáván´ı 1.79, u ´spˇeˇsné vyhledáván´ı 1.69. EICH: ne´ uspˇeˇsné vyhledáván´ı 1.93, u ´spˇeˇsné vyhledáván´ı 1.69. EISCH: ne´ uspˇeˇsné vyhledáván´ı 2.1, u ´spˇeˇsné vyhledáván´ı 1.72. LISCH: ne´ uspˇeˇsné vyhledáván´ı 2.1, u ´spˇeˇsné vyhledáván´ı 1.8. Metodu s lineárn´ım pˇridáván´ım je dobré pouˇz´ıt jen pro α < 0.7, metodu s dvojit´ ym haˇsován´ım pro α < 0.9, pak ˇcas pro ne´ uspˇeˇsné vyhledáván´ı rychle nar˚ ustá. m Vliv β = m ri sr˚ ustaj´ıc´ım haˇsován´ı. 0 pˇ Pˇri u ´spˇeˇsném vyhledáván´ı je optimáln´ı hodnota β = 0.85, pˇri ne´ uspˇeˇsném vyhledáv´ an´ı je optimáln´ı hodnota β = 0.78. V praxi se doporuˇcuje pouˇz´ıt hodnotu β = 0.86 (uvedené v´ ysledky byly pro tuto hodnotu β).

30

Komentáˇr: Metody se separuj´ıc´ımi ˇretˇezci a sr˚ ustaj´ıc´ı haˇsován´ı pouˇz´ıvaj´ı v´ıce pamˇeti (pˇri sr˚ ustaj´ıc´ım haˇsován´ı souˇcet adresovac´ı a pomocné ˇcásti). Metoda s pˇrem´ısˇtován´ım a metoda dvojitého haˇsován´ı vyˇzaduji v´ıce ˇcasu – na pˇrem´ıstˇen´ı prvku a na v´ ypoˇcet druhé haˇsovac´ı funkce. ´ zky Dalˇ s´ı ota Jak nalézt voln´ y ˇrádek. Za nejlepˇs´ı metodu se povaˇzuje m´ıt seznam (zásobn´ık) voln´ ych ˇrádk˚ u a z jeho vrcholu brát voln´ y ˇrádek a po u ´spˇeˇsné operaci DELETE tam zase ˇrádek vloˇzit (pozor pˇri operaci DELETE ve strukturách které nepodporuj´ı DELETE). Jak ˇreˇsit pˇreplnˇen´ı. Standardn´ı model: Dána základn´ı velikost tabulky m a pracuje se s tabulkami s 2i m ˇr´ adky 1 pro vhodné i = 0, 1, . . . . Vhodné i znamená, ˇze faktor zaplnˇen´ı α je v intervalu < 4 , 1 > (s vyj´ımkou i = 0, kde se uvaˇzuje pouze horn´ı mez). Pˇri pˇrekroˇcen´ı meze se zvˇetˇs´ı nebo zmenˇs´ı i a vˇsechna data se pˇrehaˇsuj´ı do nové tabulky. V´ yhoda: Po pˇrehaˇsován´ı do nové tabulky, poˇcet operac´ı, které vedou k novému pˇrehaˇsov´ aván´ı, je alespoˇ n polovina velikosti uloˇzené mnoˇziny. Praktické pouˇzit´ı: Nedrˇzet se striktnˇe mez´ı, pouˇz´ıvat malé pomocné tabulky pˇri pˇreplnˇen´ı a posunout velké pˇrehaˇsován´ı na dobu klidu (aby systém nenechal uˇzivatele v normáln´ı dobˇe ˇcekat). Jak ˇreˇsit DELETE v metodách, které ho nepodporuj´ı. Pouˇz´ıt ideu tzv. ‘faleˇsného DELETE’. Odstranit prvek, ale ˇrádek neuvolnit (i v kl´ıˇci nechat nˇejakou hodnotu, která bude znamenat, ˇze ˇrádek je prázdn´ y, poloˇzky podporuj´ıc´ı pr´ aci s ˇ adek nebude v seznamu voln´ tabulkami nemˇenit). R´ ych ˇrádk˚ u, ale operace INSERT, kdyˇz testuje tento ˇrádek, tak tam m˚ uˇze vloˇzit nov´ y prvek. Kdyˇz je alespoˇ n polovina pouˇzit´ ych ˇrádk˚ u takto blokována, je vhodné celou strukturu pˇrehaˇsovat. Pravdˇepodobnostn´ı anal´ yzu tohoto modelu neznám. Otevˇ ren´ e probl´ emy. Jak vyuˇz´ıt ideje z haˇsován´ı s uspoˇrádan´ ymi ˇretˇezci pro ostatn´ı metody ˇreˇsen´ı koliz´ı (jmenovitˇe pro sr˚ ustaj´ıc´ı haˇsován´ı). Jakou metodu pouˇz´ıt pro operaci DELETE ve sr˚ ustaj´ıc´ım haˇsován´ı (problém je zachovat náhodnost uloˇzené mnoˇziny a t´ım platnost odhadu na sloˇzitost operac´ı). Jak nalézt druhou haˇsovac´ı funkci pro metodu dvojitého haˇsován´ı, aby vzniklé posloupnosti adres pˇri operaci INSERT se chovaly jako náhodné? Z´ avˇ er. Pˇripomeˇ nme si pˇredpoklady pro pˇredchoz´ı uvedené v´ ysledky o haˇsován´ı: (1) Haˇsovac´ı funkce se rychle spoˇc´ıtá (v ˇcase O (1)); (2) Haˇsovac´ı funkce rovnomˇernˇe rozdˇeluje univerzum (to znamená, ˇze pro dvˇe r˚ uzné hodnoty i a j haˇsovac´ı funkce plat´ı −1 ≤ |h−1 (i) | − |h−1 (j) | ≤ 1); (3) Vstupn´ı data jsou rovnomˇernˇe rozdˇelená.

31

Diskutujme splnitelnost tˇechto pˇredpoklad˚ u. Pˇredpoklad 1) je jasn´ y. Pˇredpoklad 2) – je v´ yhodné, kdyˇz rozdˇelen´ı univerza haˇsovac´ı funkc´ı kop´ıruje známé rozdˇelen´ı vstupn´ıch dat. Pouˇzilo se pˇri návrhu pˇrekladaˇce pro FORTRAN (Lum 1971). V následuj´ıc´ı tabulce jsou uvedené spoˇc´ıtané a namˇeˇrené v´ ysledky. Pouˇzila se metoda separovan´ ych ˇretˇezc˚ u. Byly teoreticky spoˇc´ıtané za naˇsich pˇredpoklad˚ u. Experiment byl provádˇen pomoc´ı haˇsovac´ı funkce, která preferovala obvyklé názvy identifikátor˚ u. V´ ysledky byly mˇeˇreny, kdyˇz se pˇrekladaˇc FORTRANu pouˇzil pro standardn´ı v´ ypoˇcet. Porovnán´ı v´ ysledku:

hodnota α experiment teorie

0.5 1.19 1.25

0.6 1.25 1.30

0.7 1.28 1.35

0.8 0.9 1.34 1.38 1.40 1.45

Závˇer: Podm´ınky 1) a 2) m˚ uˇzeme splnit, kdyˇz známe rozloˇzen´ı vstupn´ıch dat, m˚ uˇzeme dosáhnout jeˇstˇe lepˇs´ıch v´ ysledk˚ u. Nev´ yhoda: Rozloˇzen´ı vstupn´ıch dat nem˚ uˇzeme ovlivnit a obvykle ho ani neznáme. Je reálné, ˇze rozdˇelen´ı vstupn´ıch dat bude nevhodné pro pouˇzitou haˇsovac´ı funkci. D˚ usledek – na poˇcátku 70. let se zaˇcalo ustupovat od haˇsován´ı. Hledal se postup, kter´ y by se vyhnul uvedenému problému s bodem 3). Nalezenému ˇreˇsen´ı je vˇenován následuj´ıc´ı text. ´ ln´ı haˇ ´ n´ı Univerza sova ˇ sen´ı navrhli Carter a Wegman (1977), kdyˇz pˇriˇsli s metodou univerzáln´ıho haˇsován´ı, kter´ Reˇ a obcház´ı poˇzadavek 3). To vedlo k novému rozsáhlému pouˇz´ıván´ı haˇsován´ı. Základn´ı idea: M´ısto jedné funkce máme mnoˇzinu H funkc´ı z univerza do tabulky velikosti m takov´ ych, ˇze pro kaˇzdou mnoˇzinu S ⊆ U , |S| ≤ m se vˇetˇsina funkc´ı chová dobˇre v˚ uˇci S (tj. S splˇ nuje poˇzadavek 3)). Haˇsovac´ı funkci zvol´ıme náhodnˇe z H (s rovnomˇern´ ym rozdˇelen´ım) a haˇsujeme pomoc´ı takto zvolené funkce.

Def:

Modifikace ideje. Ovˇeˇrován´ı vlastnost´ı vyˇzaduje znalost velikosti mnoˇziny H. Rychl´ a vyˇc´ıslitelnost h (x) vyˇzaduje analytické zadán´ı funkc´ı v H, ale zjiˇstˇen´ı rovnosti dvou analyˇ sen´ım problému je pouˇzit´ı inticky zadan´ ych funkc´ı na univerzu U je problematické. Reˇ dexové mnoˇziny. To znamená, ˇze H = {hi | i ∈ I} a dvˇe funkce jsou r˚ uzné, kdyˇz maj´ı r˚ uzné indexy. Pak velikost systému bude velikost indexové mnoˇziny. M´ısto zvolen´ı haˇsovac´ı funkce budeme volit náhodnˇe index s rovnomˇern´ ym rozloˇzen´ım a kdyˇz zvol´ıme index i, pak budeme pracovat s haˇsovac´ı funkc´ı hi . Oˇcekávan´ P a hodnota náhodné promˇenné f z mnoˇziny I do f (i) i∈I . reáln´ ych ˇc´ısel bude pr˚ umˇer pˇres I, tj. |I| Formálnˇe: Nechˇt U je univerzum. Soubor funkc´ı H = {hi | i ∈ I} z univerza U do mnoˇziny {0, 1, . . . , m − 1} se naz´ yvá c-univerzáln´ı (c je kladné reálné ˇc´ıslo), kdyˇz ∀x, y ∈ U, x 6= y plat´ı | {i ∈ I | hi (x) = hi (y)} | ≤

c|I| . m

32 Ekviv. def:

Jako ekvivalentn´ı definici lze pouˇz´ıt toto tvrzen´ı: systém funkc´ı H z univerza U do mnoˇziny {0, 1, . . . , m − 1} je c-univerzáln´ı, kdyˇz vyb´ıráme funkci h ∈ H s rovnomˇern´ ym rozdˇelen´ım, pak pro kaˇzdé dvˇe r˚ uzná x, y ∈ U , plat´ı c Prob (h (x) = h (y)) ≤ . m Problémy: existence c-univerzáln´ıch systém˚ u, vlastnosti c-univerzáln´ıch systém˚ u (zda splˇ nuj´ı poˇzadované ideje).

Def. mn. hašovacích funkcí:

Existence univerz´ aln´ıch syst´ em˚ u. Univerzum U = {0, 1, . . . , N − 1} pro prvoˇc´ıslo N , H = {ha,b | (a, b) ∈ U × U }, kde ha,b (x) = ((ax + b) mod N ) mod m (tj. indexová mnoˇzina je U × U a jej´ı velikost je N 2 ). V´ yhoda: funkce z mnoˇziny H um´ıme rychle vyˇc´ıslit. Zvolme x, y ∈ U taková, ˇze x 6= y. Chceme nalézt (a, b) ∈ U ×U takové, ˇze ha,b (x) = ha,b (y). − 1 tak, ˇze plat´ı Mus´ı existovat i ∈ {0, 1, . . . , m − 1} a r, s ∈ 0, 1, . . . , N m (ax + b ≡ i + rm) mod N (ay + b ≡ i + sm) mod N

Kdyˇz x, y, i, r a s jsou konstanty a a a b jsou promˇenné, je to systém lineárn´ıch rovnic v tˇelese Z/ mod N , kde Z jsou celá ˇc´ısla. Matice soustavy Zn Dle Frobeniovy věty x 1 y 1 je regulárn´ı, protoˇze x 6= y. Tedy existuje jediné ˇreˇsen´ı této soustavy pro fixovaná x, y, i, r hodnot. a s. Pro daná x a y, i nab´ yvá m hodnot, r a s nab´ yvaj´ı N m N 2 Závˇer: pro kaˇzd´ a x, y ∈ U taková, ˇze x 6= y, existuje m m dvojic (a, b) ∈ U × U takov´ ych, ˇze ha,b (x) = ha,b (y). Vˇ eta. Mnoˇzina H je c-univerz´ aln´ı pro c=

N 2 m N 2 m

.

Skuteˇcnˇe, pro kaˇzdé x, y ∈ U , x 6= y, je poˇcet (a, b) ∈ U × U takov´ ych, ˇze ha,b (x) = ha,b (y), nejv´ yˇse roven N 2 N 2 2 N2 |I| N m = = m 2 . m 2 N N m m m m

m

Závˇer: Dokázali jsme existenci c-univerzáln´ıch systém˚ u pro c bl´ızké 1. Staˇc´ı si uvˇedomit, ˇze kaˇzdé univerzum m˚ uˇzeme povaˇzovat za univerzum tvaru {0, 1, . . . , N − 1} pro nˇejaké N a ˇze mezi ˇc´ısly N a 2N vˇzdy existuje nˇejaké prvoˇc´ıslo.

33

Vlastnosti univerz´ aln´ıho haˇ sov´ an´ı. Def:

Pˇredpoklad: H = {hi | i ∈ I} je c-univerzáln´ı systém funkc´ı Oznaˇcen´ı: Pro i ∈ I a prvky x, y ∈ U oznaˇcme δi (x, y) =

Def:

1 0

stejné hašovací kdyˇz x 6= y a hi (x) = hi (y) , [Na kolize mezi x a y] kdyˇz x = y nebo hi (x) 6= hi (y) .

funkci

Pro mnoˇzinu S ⊆ U , x ∈ U a i ∈ I definujme δi (x, S) =

X

δi (x, y) .

y∈S

Pro fixovanou mnoˇzinu S ⊆ U a pro fixované x ∈ U seˇcteme δi (x, S) pˇres vˇsechna i ∈ I: X

δi (x, S) =

i∈I

XX

δi (x, y) =

XX

δi (x, y) =

i∈I y∈S

y∈S i∈I

X

| {i ∈ I | hi (x) = hi (y)} | ≤

X

|I| c = m

y∈S,y6=x

y∈S,y6=x

(

(|S| − 1) c |I| m |S|c |I| m

kdyˇz x ∈ S, kdyˇz x ∈ / S.

Protoˇze δi (x, S) dává odhad na velikost ˇretˇezce hi (x) pˇri reprezentaci mnoˇziny S pomoc´ı funkce hi , dostáváme, ˇze oˇcekávaná délka ˇretˇezce pro fixovanou mnoˇzinu S ⊆ U a fixované x ∈ U pˇres i ∈ I s rovnomˇern´ ym rozdˇelen´ım je nejv´ yˇse 1 X δi (x, S) ≤ |I| i∈I

(

c |S|−1 m

kdyˇz

c |S| kdyˇz m Jen vydělím |I|

x ∈ S, x∈ / S.

Vˇ eta. Oˇcek´ avan´ y ˇcas operac´ı MEMBER, INSERT a DELETE pˇri c-univerz´ aln´ım |S| haˇsov´ an´ı je O (1 + cα), kde α je faktor naplnˇen´ı (tj. α = m ). Oˇcek´ avan´ y ˇcas pro pevnou posloupnost n operac´ı MEMBER, INSERT a DELETE apn likovan´ ych na pr´ azdnou tabulku pro c-univerz´ aln´ı haˇsov´ an´ı je O 1 + 2c α n , kde α = m .

V´ yznam v´ ysledku: Vzorec se jen o multiplikativn´ı konstantu c liˇs´ı od vzorce pro haˇsov´ an´ı se separovan´ ymi ˇretˇezci. Pˇritom c m˚ uˇze b´ yt jen o málo menˇs´ı neˇz 1 a ve vˇsech znám´ ych pˇr´ıkladech je c ≥ 1. Takˇze, co jsme dosáhli? Rozd´ıl je v pˇredpokladech. Zde je pˇredpoklad 3) nahrazen pˇredpokladem, ˇze index i ∈ I je vybrán s rovnomˇern´ ym rozdˇelen´ım, a nen´ı ˇz´ adn´ y pˇredpoklad na vstupn´ı data. V´ ybˇ er indexu i m˚ uˇ zeme ovlivnit, ale v´ ybˇ er vstupn´ıch dat nikoliv. M˚ uˇzeme zajistit rovnomˇerné rozdˇelen´ı v´ ybˇeru i z I nebo se k tomuto rozdˇelen´ı hodnˇe pˇribl´ıˇzit.

34

Markovova nerovnost. Pˇredpoklady: Je dána mnoˇzina S ⊆ U , prvek x ∈ U . Oˇcekávaná velikost δi (x, S) je µ, a t ≥ 1. Ukáˇzeme pro t > 1, ˇze pravdˇepodobnost, ˇze δi (x, S) ≥ tµ pro i ∈ I, je menˇs´ı neˇz (pˇredpokladáme, ˇze i je z I vybráno s rovnomˇern´ ym rozdˇelen´ım). Oznaˇcme I 0 = {i ∈ I | δi (x, S) ≥ tµ}. Pak plat´ı P P P |I 0 | 0 tµ i∈I δi (x, S) i∈I 0 δi (x, S) µ= > ≥ i∈I = tµ |I| |I| |I| |I| Odtud |I 0 | <

1 t

Kratím µ na obou stranách rovnice.

|I| . t

Závˇer: Pravdˇepodobnost, ˇze δi (x, S) ≥ tµ, je menˇs´ı neˇz tvrzen´ı.

1 t,

a odtud plyne poˇzadované

Poznámka: Toto tvrzen´ı plat´ı obecnˇe a naz´ yvá se Markovova nerovnost. Uveden´ y d˚ ukaz ilustruje jednoduché tvrzen´ı pro koneˇcn´ y pˇr´ıpad. Probl´ emy. Hlavn´ı problém: Zajiˇstˇen´ı rovnomˇerného rozdˇelen´ı v´ ybˇeru i z I. Proveden´ı v´ ybˇeru: Zakódovat indexy z mnoˇziny I do ˇc´ısel 0, 1, . . . , |I| − 1. Zvolit náhodnˇe ˇc´ıslo i z tohoto intervalu s rovnomˇern´ ym rozdˇelen´ım a pak pouˇz´ıt funkci s indexem, jehoˇz kód je i. Abychom vybrali i, nalezneme nejmenˇs´ı j takové, ˇze 2j − 1 ≥ |I| − 1. Pak ˇc´ısla v intervalu 0, 1, . . . , 2j − 1 jednoznaˇcnˇe koresponduj´ı s posloupnostmi 0 a 1 délky j. Budeme vyb´ırat náhodnˇe posloupnost 0 a 1 délky j. K v´ ybˇeru posloupnosti pouˇzijeme náhodn´ y generátor rovnomˇerného rozdˇelen´ı. Závada: Skuteˇcn´ y náhodn´ y generátor pro rovnomˇerné rozdˇelen´ı je prakticky nedosaˇziteln´ y (nˇekteré fyzikáln´ı procesy). K dispozici je pouze pseudogenerátor. ˇ ım je j vˇetˇs´ı, t´ım je posloupnost pravidelnˇejˇs´ı (tj. ménˇe náhodná). Jeho nev´ yhoda: C´ D˚ usledky: Nalézt co nejmenˇs´ı c-univerzáln´ı systémy. Nalézt doln´ı odhady na jejich velikost. Doln´ı odhady na velikost. Pˇredpoklady: Nechˇt U je universum velikosti N a nechˇt H = {hi | i ∈ I} je c-univerz´ aln´ı systém funkc´ı haˇsuj´ıc´ıch do tabulky velikosti m. M˚ uˇzeme pˇredpokládat, ˇze I = {0, 1, . . . , |I| − 1} . Indukc´ı definujme mnoˇziny U0 , U1 , . . . tak, ˇze: U0 = U . Nechˇt U1 je nejvˇetˇs´ı podmnoˇzina U0 vzhledem k poˇctu prvk˚ u taková, ˇze h0 (U1 ) je jednoprvková mnoˇzina. Nechˇt U2 je nejvˇetˇs´ı podmnoˇzina U1 vzhledem k poˇctu prvk˚ u taková, ˇze h1 (U2 ) je jednoprvková mnoˇzina.

35

Nechˇt U3 je nejvˇetˇs´ı podmnoˇzina U2 vzhledem k poˇctu prvk˚ u taková, ˇze h2 (U3 ) je jednoprvková mnoˇzina. Obecnˇe, nechˇt Ui je nejvˇetˇs´ı podmnoˇzina Ui−1 vzhledem k poˇctu prvk˚ u taková, ˇze hi−1 (Ui ) je jednoprvková mnoˇzina. l m i−1 | Protoˇze haˇsujeme do tabulky velikosti m, plat´ı |Ui | ≥ |Um . Protoˇze |U0 | = N , indukc´ı N dostaneme, ˇze |Ui | ≥ mi pro kaˇzdé i. Zvolme i = dlogm N e− 1. Pak i je nejvˇetˇs´ı pˇrirozené N ˇc´ıslo takové, ˇze m a aspoˇ n dva prvky, zvolme x, y ∈ Ui taková, ˇze x 6= y. i > 1. Tedy Ui m´ Pak hj (x) = hj (y) pro j = 0, 1, . . . , i − 1. Tedy c|I| (#1) . i ≤ | {j ∈ I | hj (x) = hj (y)} | ≤ m Vˇ eta. Kdyˇz H = {hi | i ∈ I} je c-univerz´ aln´ı systém pro univerzum U o velikosti N haˇsuj´ıc´ı do tabulky s m ˇra ´dky, pak m |I| ≥ (dlogm N e − 1) . c Posloupnosti 0 a 1 pˇri n´ ahodné volbˇe i z I mus´ı m´ıt délku alespoˇ n d(log m − log c + log log N − log log m)e

(zde vˇsechny logaritmy jsou o z´ akladu 2).

Def:

Mal´ y univerz´ aln´ı syst´ em. Zkonstruujeme c-univerzáln´ı systém takov´ y, ˇze logaritmus z velikosti jeho indexové mnoˇziny pro velká univerza je aˇz na aditivn´ı konstantu menˇs´ı neˇz 4 (log m + log log N ), kde N je velikost univerza a m je poˇcet ˇrádk˚ u v tabulce. Nechˇt p1 , p2 , . . . je rostouc´ı posloupnost vˇsech prvoˇc´ısel. Mˇejme velikost tabulky m a univerzum U = {0, 1, . . . , N − 1} pro nˇejaké pˇrirozené ˇc´ıslo N (nemus´ı b´ yt prvoˇc´ıslo). Nechˇt t je nejmenˇs´ı ˇc´ıslo takové, ˇze t ln pt ≥ m ln N . Definujme H1 = {gc,d (h` ) | t < ` ≤ 2t, c, d ∈ {0, 1, . . . , p2t − 1}} ,

kde h` (x) = x mod p` a gc,d (x) = ((cx + d) mod p2t ) mod m. Ukáˇzeme, ˇze kdyˇz m (ln m + ln ln m) < N , pak H1 je 3.25-univerzáln´ı systém. Pozn:

Nejprve si pˇripomeneme známou vˇetu o velikosti prvoˇc´ısel (zde ln je pˇrirozen´ y logaritmus, tj. o základu e). Vˇ eta. Pro kaˇzdé i = 1, 2, . . . plat´ı pi > i ln i a pro i ≥ 6 plat´ı pi < i (ln i + ln ln i).

Tedy pro i ≥ 6 plat´ı pi < 2i ln i.

(#2)

Velikost indexové mnoˇziny H1 . Indexová mnoˇzina H1 je (#3) Tedy

I = {(c, d, `) | c, d ∈ {0, 1, . . . , p2t − 1,} t < ` ≤ 2t}} .

|I| = tp22t . Odtud plyne |I| ≤ 16t3 ln2 2t a tedy

log (|I|) ≤ 4 + 3 log t + 2 log log t.

Pro dostateˇcnˇe velké t (takové, ˇze log t ≥ 2 log log t, tj. t ≥ 16) plat´ı, ˇze log (|I|) ≤ 4+4 log t. Z definice t plyne, ˇze t ≤ m ln N , kdyˇz ln pt ≥ 1 (tj. pt ≥ 3). Závˇer: log (|I|) ≤ 4 + 4 (log m + log log N ).

36

Univerzalita mal´ eho syst´ emu. Zvolme r˚ uzná x a y z univerza U . Oznaˇc´ıme G1 = {(c, d, `) | gc,d (h` (x)) = gc,d (h` (y)) , h` (x) 6= h` (y)} , G2 = {(c, d, `) | gc,d (h` (x)) = gc,d (h` (y)) , h` (x) = h` (y)}

a odhadneme velikost G1 a G2 . Odhad velikosti G1 . Kdyˇz (c, d, `) ∈ G1 , pak existuj´ı r, s ∈ {0, 1, . . . , m − 1} taková, ˇze

0, 1, . . . ,

p2t m

−1

a i ∈

(c (x mod p` ) + d ≡ i + rm) mod p2t

(c (y mod p` ) + d ≡ i + sm) mod p2t .

Kdyˇz c a d povaˇzujeme za nezn´ amé, pak je to soustava lineárn´ıch rovnic s regulárn´ı matic´ı (protoˇze x mod p` 6= y mod p` ), a tedy pro kaˇzdé `, i, r a s existuje nejv´ yˇse jedna dvojice (c, d). Proto |G1 | ≤ tm

l p m2 2t

m

tp2 ≤ 2t m

2 2 m |I| m 1+ = 1+ . p2t m p2t

Q Odhad velikosti G2 . Oznaˇcme L = {` | t < ` ≤ 2t, x mod p` = y mod p` } a P = `∈L p` . Protoˇze P dˇel´ı |x − y|, dostáváme, ˇze P ≤ N . Protoˇze pt < p` pro kaˇzdé ` ∈ L, dostáv´ ame, |L| t ln N ˇze P > pt . Tedy |L| ≤ ln pt ≤ m z definice t. Protoˇze (c, d, `) ∈ G2 , právˇe kdyˇz ` ∈ L a c, d ∈ {0, 1, . . . , p2t − 1}, shrneme, ˇze |G2 | ≤ |L|p22t ≤ Abychom odhadli 1 +

m p2t

2

tp22t |I| = . m m

, ukáˇzeme si nejdˇr´ıv pomocné lemma.

Lemma. Kdyˇz t ≥ 6 a m (ln m + ln ln m) < N , pak m <

pt ln t .

D˚ ukaz. Pˇredpokládejme, ˇze tvrzen´ı neplat´ı. pak m ≥ lnptt . Z Vˇety o velikosti prvoˇc´ısel pak plyne m ≥ lnptt > tlnlntt = t. Kdyˇz pouˇzijeme, ˇze m (ln m + ln ln m) < N , tak dostaneme, ˇze ln m + ln (ln m + ln ln m) < ln N,

a odtud plyne, ˇze t ln pt < t ln (t (ln t + ln ln t)) ≤ m (ln m + ln (ln m + ln ln m)) < m ln N a to je spor s definic´ı t. Tedy m <

pt ln t .

Definice t

Nyn´ı zkombinujeme Vˇetu o odhadu velikosti prvoˇc´ısel, pˇredchoz´ı Lemma a fakt, ˇze ln 2t ≥ ln t ≥ ln ln t

pro vˇsechna t ≥ 1

37

Odhadujeme (1+m/p_{2t})^2

a dostaneme, ˇze p

t m t (ln t + ln ln t) 1 ≤ ln t < < p2t 2t ln 2t 2t ln t ln 2t ln 2t

ln ln t 1+ . ln t

zanedbame

1 2

Je zˇrejmé, ˇze tento v´ yraz je menˇs´ı neˇz a kdyˇz konverguje k +∞ pak tento v´ yraz konverguje k 0. 2 Z toho plyne, ˇze 1 + pm2t ≤ 1.52 = 2.25 a tedy |{i ∈ I | hi (x) = hi (y)}| = |G1 | + |G2 | ≤ 2 |I| m |I| |I| |I| 1+ + ≤ (1 + 2.25) = 3.25 . m p2t m m m Shrnut´ı: Kdyˇz t ≥ 6 a m ln m ln ln m < N , pak H1 je 3.25-univerzáln´ı. Bez jak´ ychkoliv pˇredpoklad˚ u lze ukázat, ˇze H1 je 5-univerzáln´ı. Odhad na velikost c. Vˇ eta. Kdyˇz H je c-univerz´ aln´ı systém univerza U o velikosti N haˇsuj´ıc´ı do tabulky s m m ˇra ´dky, pak c ≥ 1 − N . Nejprve dokáˇzeme technické lemma. Lemma. Mˇejme re´ aln´ a ˇc´ısla bi pro i = 0, 1, . . . , m − 1 a nechˇt b = m−1 X

bi (bi − 1) ≥ b

i=0

b −1 . m

Pm−1 i=0

bi . Pak

D˚ ukaz lemmatu. Z Cauchyho-Schwarzovy nerovnosti

b^2

plyne Pm−1 i=0

P

m−1 i=0 bi

2

b2i . Odtud m−1 X i=0

m−1 X i=0

= b2 ≤ m

bi (bi − 1) =

a lemma je dokáz´ ano.

xi y i

!2

≤

P

m−1 X i=0

m−1 2 i=0 bi

b2i

−

m−1 X i=0

m−1 X

x2i

i=0

!

m−1 X i=0

yi2

!

nasčítáme m, protože každý člen je 1

, staˇc´ı poloˇzit xi = bi a yi = 1, a tedy

bi =

m−1 X i=0

b2i

b2 −b≥ −b =b m

b −1 m

b2 m

≤

38

D˚ ukaz Vˇety. Mˇejme funkci f : U − → S, kde U má velikost N a S má velikost m. Oznaˇcme A mnoˇzinu uspoˇrádan´ ych dvojic u, v ∈ UPtakov´ ych, ˇze u 6= v a f (u) = f (v). Kdyˇz pro −1 s ∈ S oznaˇc´ıme ks = |f (s) |, pak |A| = s∈S ks (ks − 1). Z lemmatu plyne, ˇze |A| =

X

s∈S

ks (ks − 1) ≥ N

N −1 m

=N

N −m m

,

P protoˇze s∈S ks = N . Kdyˇz H = {hi | i ∈ I} je c-univerzáln´ı systém funkc´ı z univerza U o velikosti N do tabulky o velikosti m, pak pomoc´ı lemmatu dostáváme

N −m m

|I|N ≤ X | {(x, y) ∈ U × U | hi (x) = hi (y) , x 6= y} | = i∈I

X

| {i ∈ I | hi (x) = hi (y)} | ≤

X

c

(x,y)∈U×U, x6=y

(x,y)∈U×U,x6=y

|I| |I| = N (N − 1) c . m m

Odtud plyne, ˇze N − m ≤ c (N − 1), a tedy c≥

Porovnavame pouze obe strany nerovnice

N −m N −m m > =1− . N −1 N N

Probl´ emy univerz´ aln´ıho haˇ sov´ an´ı. Pouˇz´ıt jiné metody na ˇreˇsen´ı koliz´ı neˇz separované ˇretˇezce. Jak to ovlivn´ı pouˇzitelnost univerzáln´ıho haˇsován´ı? Plat´ı podobné vztahy jako pro pevnˇe danou haˇsovac´ı funkci? Jak´ y vliv na efektivnost má nepˇr´ıtomnost operace DELETE? Existuje c-univerzáln´ı haˇsovac´ı systém pro c < 1? Jak´ y je vztah mezi velikost´ı c-univerz´ aln´ıho haˇsovac´ıho systému a velikost´ı c? Lze zkonstruovat mal´ y c-univerzáln´ı systém pro c < 3.25? Zde hraje roli fakt, ˇze pˇri c = 3.25 se oˇcekávaná délka ˇretˇezce m˚ uˇze pohybovat aˇz kolem hodnoty 7. ˇ Pouˇzit´ı Cebyˇ sevovy nerovnosti m´ısto Markovovy nerovnosti dáv´ a kvadratick´ y odhad pravdˇepodobnosti, ˇze délka ˇretˇezce je o t vˇetˇs´ı neˇz oˇcekávaná hodnota. Za jak´ ych okolnost´ı d´ av´ a lepˇs´ı odhad? Lze pouˇz´ıt i vyˇsˇs´ıch moment˚ u?

Jiny model:

Jak pouˇz´ıt Markovou nerovnost a oˇcekávanou délku maximáln´ıho ˇretˇezce pro odhad oˇcek´ avaného poˇctu voleb haˇsovac´ı funkce? Pro jaké parametry lze pouˇz´ıt následuj´ıc´ı model? Je dána základn´ı velikost tabulky m a dále pro j = 0, 1, . . . ˇc´ısla (parametry) lj a c-univerzáln´ı haˇsovac´ı systémy Hj = {hi | i ∈ Ij } z univerza do tabulky s m2j ˇrádky. Mnoˇzina S ⊆ U je reprezentována následovnˇe: je dáno j takové, ˇze kdyˇz j > 0, pak

39

m2j−2 ≤ |S| ≤ m2j , kdyˇz j = 0, pak |S| ≤ m, a je zvolen index i ∈ Ij . Dále m´ ame prosté ˇretˇezce r0 , r1 , . . . , rm2j −1 , jejichˇz délky jsou nejv´ yˇse lj , a ˇretˇezec rk obsahuje prvky {s ∈ S | hi (s) = k}. Operace INSERT(x) prohledá ˇretˇezec rhi (x) a kdyˇz tento ˇretˇezec neobsahuje prvek x, pak ho pˇridá. Kdyˇz m2j−2 ≤ |S| ≤ m2j a délka ˇretˇezce rhi (x) je nejv´ yˇse lj , pak operace konˇc´ı. j Kdyˇz |S| > m2 , tak se nejdˇr´ıve zvˇetˇs´ı j o 1. Pak se náhodnˇe zvol´ı i ∈ Ij a zkonstruuj´ı se ˇretˇezce reprezentuj´ıc´ı S. Kdyˇz nˇekter´ y z nich má délku vˇetˇs´ı neˇz lj , tak se volba a konstrukce ˇretˇezc˚ u opakuje tak dlouho, dokud se nepovede zvolit i ∈ Ij takové, ˇze vˇsechny zkonstruované ˇretˇezce maj´ı délku nejv´ yˇse lj . Operace DELETE se ˇreˇs´ı analogicky. Problém: Jak volit parametry li ? V pˇr´ıpadˇe ˇreˇsen´ı koliz´ı dvojit´ ym haˇsován´ım nebo haˇsován´ım s lineárn´ım pˇridáván´ım je tˇreba dát silnˇejˇs´ı podm´ınky na velikost |S|. V posledn´ı dobˇe se této tématice vˇenuje pozornost a byla dosaˇzena ˇrada zaj´ımav´ ych v´ ysledk˚ u. ´ n´ı Perfektn´ı haˇ sova Jiné ˇreˇsen´ı koliz´ı je perfektn´ı haˇsován´ı. Idea je nalézt pro danou mnoˇzinu haˇsovac´ı funkci, která nevytv´ aˇr´ı kolize. Nev´ yhoda: Metoda nepˇripouˇst´ı operaci INSERT (pro nov´ y vstup nem˚ uˇzeme zaruˇcit, ˇze nevznikne kolize). Metodu lze prakticky pouˇz´ıt pro u ´lohy, kde lze oˇcekávat hodnˇe operac´ı MEMBER a operace INSERT se témˇeˇr nevyskytuje (kolize se ˇreˇs´ı pomoc´ı malé pomocné tabulky, kam se ukládaj´ı koliduj´ıc´ı data). Tato metoda se pouˇz´ıvá pˇri navrhován´ı kompilátor˚ u. Zadán´ı u ´lohy: Pro danou mnoˇzinu S ⊆ U chceme nalézt haˇsovac´ı funkci h takovou, ˇze

(1) pro s, t ∈ S takové, ˇze s 6= t, plat´ı h (s) 6= h (t) (tj. h je perfektn´ı haˇsovac´ı funkce pro S); (2) h haˇsuje do tabulky s m ˇrádky, kde m je pˇribliˇznˇe stejnˇe velké jako |S| (nen´ı praktické haˇsovat do pˇr´ıliˇs velk´ ych tabulek – ztrác´ı se jeden ze základn´ıch d˚ uvod˚ u pro haˇsován´ı); (3) h mus´ı b´ yt rychle spoˇcitatelná – jinak haˇsován´ı nen´ı rychlé; (4) uloˇzen´ı h nesm´ı vyˇzadovat moc pamˇeti, nejv´ yhodnˇejˇs´ı je analytické zadán´ı (kdyˇz zadán´ı h bude vyˇzadovat moc pamˇeti, napˇr. kdyˇz by byla dána tabulkou, pak se ztrác´ı d˚ uvod k pouˇzit´ı stejnˇe jako v bodˇe 2).

Kompenzace: Nalezen´ı haˇsovac´ı funkce m˚ uˇze spotˇrebovat v´ıce ˇcasu. Provád´ı se jen na zaˇcátku u ´lohy. Def:

Uvedené poˇzadavky motivuj´ı zaveden´ı následuj´ıc´ıho pojmu. Mˇejme univerzum U = {0, 1, . . . , N − 1}. Soubor funkc´ı H z U do mnoˇziny {0, 1, . . . , m − 1) se naz´ yvá (N, m, n)-perfektn´ı, kdyˇz pro kaˇzdou S ⊆ U takovou, ˇze |S| = n, existuje h ∈ H perfektn´ı pro S (tj. h (s) 6= h (t) pro kaˇzdá dvˇe r˚ uzná s, t ∈ S). Protoˇze nev´ıme, zda taková h existuj´ı, nejprve vyˇsetˇr´ıme mnoˇziny perfektn´ıch haˇsovac´ıch funkc´ı. Vyˇsetˇr´ıme vlastnosti (N, m, n)-perfektn´ıch soubor˚ u funkc´ı.

40

Doln´ı odhady na velikost (N, m, n)-perfektn´ıho souboru. Pˇredpokládejme, ˇze H je (N, m, n)-perfektn´ı systém pro U = {0, 1, . . . , N − 1} a nejprve nalezneme doln´ı odhady na velikost |H|.

Mˇejme funkci h z U do mnoˇziny {0, 1, . . . , m − 1}. Nalezneme poˇcet mnoˇzin S ⊆ U takov´ ych, ˇze h je perfektn´ı funkce pro S a |S| = n. Funkce h je perfektn´ı pro S ⊆ U , právˇe kdyˇz pro kaˇzdé i = 0, 1, . . . , m − 1 je |h−1 (i) ∩ S| ≤ 1. Odtud poˇcet tˇechto mnoˇzin je    X n−1 Y −1 |h (ij ) | | 0 ≤ i0 < i1 < · · · < in−1 < m .   j=0

Vysvˇetlen´ı: h (S) = {ij | j = 0, 1, . . . , n − 1}.

zdé i. Tedy h m˚ uˇze b´ yt perfektn´ı nejv´ yˇse Toto ˇc´ıslo je maxim´ aln´ı, kdyˇz |h−1 (i) | = N m pro kaˇ N n m m pro n m mnoˇzin (ˇc´ıslo n urˇcuje poˇcet posloupnost´ı 0 ≤ i0 < i1 < · · · < in−1 < m). Protoˇze n-prvkov´ ych podmnoˇzin universa je N , dostáváme, ˇze n N |H| ≥

m n

n N n . m

Jin´ y odhad velikosti (N, m, n)-perfektn´ıho souboru.

Induktivní definice množin U_i: t je počet hashovacích funkcí.

Pˇredpokládejme, ˇze H = {h1 , . . . , ht } je (N, m, n)-perfektn´ı soubor funkc´ı. Definujme indukc´ı soubor mnoˇzin Ui : U0 = U a pro i > 0 je Ui nejvˇetˇs´ı podmnoˇzina Ui−1 , co do poˇctu prvk˚ u, taková, ˇze hi |Ui−1 | N je konstantn´ı na Ui . Pak |Ui | ≥ m pro vˇsechna i > 0. Z |U0 | = N plyne |Ui | ≥ m i. Pro kaˇzdé i = 1, 2, . . . , t je hj (Ui ) jednobodová mnoˇzina pro kaˇzdé j ≤ i. Proto ˇz´ adn´ a hj pro j ≤ i nen´ı perfektn´ı pro mnoˇzinu S ⊆ U takovou, ˇze |S ∩ Ui | ≥ 2. Protoˇze H je log N N (N, m, n)-perfektn´ı, mus´ı b´ yt |Ut | ≤ 1, a tedy m t ≤ 1. Proto t ≥ log m . Vˇ eta. Kdyˇz H je (N, m, n)-perfektn´ı soubor funkc´ı, pak ( ) N log N nN n , |H| ≥ max . m log m n m

Existence (N, m, n)-perfektn´ıho souboru. Mˇejme univerzum U = {0, 1, . . . , N − 1} a soubor funkc´ı H = {h1 , h2 , . . . , ht } z univerza U do mnoˇziny {0, 1, . . . , m − 1}. Reprezentujeme tento soubor pomoc´ı matice M (H) typu N × t s hodnotami {0, 1, . . . , m − 1} tak, ˇze pro x ∈ U a i = 1, 2, . . . , t je v x-tém ˇr´ adku a i-tém sloupci matice M (H) hodnota hi (x). Pak ˇzádná funkce z H nen´ı perfektn´ı pro mnoˇzinu S = {s1 , s2 , . . . , sn } ⊆ U , právˇe kdyˇz podmatice M (H) tvoˇrená ˇrádky s1 , s2 , aˇz sn a vˇsemi sloupci nemá prost´ y sloupec. Takov´ ych matic je nejv´ yˇse !t t (pocet hash. n−1 Y n (N−n)t (m − i) m . m − i=0

fci)

h_i(x) prvky, kde

N

x \in U i \in {1,..,t}

Doplneni matice na matici typu N x n

41

Qn−1 Vysvˇetlen´ı: mn je poˇcet vˇsech funkc´ı z S do {0, 1, . . . , m − 1}, cet i=0 (m − i) je poˇ prost´ ych funkc´ı z S do {0, 1, . . . , m − 1}, a tedy poˇcet vˇsech podmatic s n ˇrádky takov´ ych, t Qn−1 ˇze ˇzádn´ y jejich sloupec nen´ı prost´ y, je mn − i=0 (m − i) . Tyto podmatice m˚ uˇzeme libovolnˇe doplnit na matici typu N × n a pro kaˇzdou matici je tˇechto doplnˇen´ı m(N−n)t . Podmnoˇzin U velikosti n je N , tedy poˇcet vˇsech matic, které nereprezentuj´ı (N, m, n)n perfektn´ı systém, je menˇs´ı nebo rovno !t n−1 Y N (m − i) m(N−n)t . mn − n i=0 Vˇsech matic je mNt a kdyˇz !t n−1 Y N mn − (m − i) m(N−n)t < mNt , n

(*)

i=0

Vyraz (*)

pak nutnˇe existuje (N, m, n)-perfektn´ı systém. Následuj´ıc´ı v´ yrazy jsou ekvivalentn´ı s nerovnost´ı (∗) !t Qn−1 ln N (m − i) N n i=0 . Qn−1 <1 ⇔ t≥ 1− (m−i) mn n vydeleny m^{Nt} i=0 − ln 1 − mn Protoˇze ln

N n

≤ n ln N a protoˇze − ln (1 − x) ≥ x pro x ∈ (0, 1) dostáváme

− ln 1 −

Qn−1

i=0 (m − i) mn

!

≥

n−1 Y i=0

i 1− m

Rn ln 1− x dx e 0 ( m)

Pn−1 i = e i=0 ln(1− m ) ≥

kde integrál m˚ uˇzeme odhadnout m

h

1−

i h i > n2 n n n n 1 − ln 1 − −1 ≥m 1− 1+ −1 =− , m m m m m n2

dostáváme, ˇze kdyˇz t ≥ n (ln N ) e m , pak (*) plat´ı, a tedy existuje (N, m, n)-perfektn´ı soubor funkc´ı. Existence (N, m, n)-perfektn´ıho souboru funkc´ı ale nezaruˇcuje splnˇen´ı poˇzadavk˚ u 2), 3) a 4). Abychom uspˇeli, pouˇzijeme ideu z metody univerzáln´ıho haˇsován´ı.

42

Hash. fce:

Konstrukce perfektn´ı haˇ sovac´ı funkce. Pˇredpoklady: U = {0, 1, . . . , N − 1}, kde N je prvoˇc´ıslo. Mˇejme S ⊆ U o velikosti n. Budeme uvaˇzovat funkce pro k = 1, 2, . . . , N − 1.

hk (x) = (kx mod N ) mod m Hodnoty b_i^k:

(#1)

Pro i = 0, 1, . . . , m − 1 a k = 1, 2, . . . , N − 1 oznaˇcme bki = | {x ∈ S | (kx mod N ) mod m = i} |. h_k(x) = i

V´ yznam bki : Hodnoty bki lze povaˇzovat za veliˇciny, které ukazuj´ı odchylku od perfektnosti. Vˇsimnˇeme si, ˇze 2 kdyˇz bki ≥ 2, pak bki − bki ≥ 2, protoˇze a2 − a ≥ 2, kdyˇz a ≥ 2. Na druhou stranu bki ≤ 1 implikuje bki Tedy z

Pm−1 i=0

bki = n plyne

2

− bki = 0.

2 Pm−1 Vˇ eta. Funkce hk je perfektn´ı, pr´ avˇe kdyˇz i=0 bki − n < 2. PN−1 Pm−1 k 2 Nyn´ı odhadneme v´ yraz k=1 b − n . i i=0 N−1 X k=1

(

m−1 X i=0

N−1 X

k=1

bi

!

m−1 X i=0

k=1

N−1 X

k 2

− n) =

| {x ∈ S | hk (x) = i} |2

!

−n

!

=

| {(x, y) | x, y ∈ S, x 6= y, hk (x) = hk (y)} | =

X

x,y∈S,x6=y

| {k | 1 ≤ k < N, hk (x) = hk (y)} |.

x, y ∈ S taková, ˇze x 6= y. Pak hk (x) = hk (y), právˇe kdyˇz existuje i = 0, 1, . . . , m−1 N a r, s = 0, 1, . . . , b m c taková, ˇze kx ≡ i+rm mod N a ky ≡ i+sm mod N a i+rm, i+sm < N . Odtud dostáváme, ˇze hk (x) = hk (y) implikuje kx − ky ≡ (r − s) m mod N . Protoˇze 0 < k < n a x 6= y, dostáváme, ˇze kx − ky 6= 0, a tedy hk (x) = hk (y) implikuje existenci N N q = −b N eho, ˇze kx−ky ≡ qm mod N , a to je ekvivam c, −b m c+1, . . . , −1, 1, 2, . . . , b m c takov´ N N lentn´ı s t´ım, ˇze k (x − y) ≡ qm mod N pro nˇejaké q = −b N c, −b m c+1, . . . , −1, 1, 2, . . . , b m c. m

Rozebirame Zvolme h_k(x)=h_k(y):

N c existuje právˇe jedno k takové, ˇze k (x − y) ≡ qm mod Pro x > y a pro jedno q = 0, 1, . . . , b m N N , protoˇze ZN je tˇeleso (tato rovnice má jediné ˇreˇsen´ı). Protoˇze pro q = −b m c, . . . , −1, 0

43

je rovnice k (x − y) ≡ qm mod N ekvivalentn´ı s rovnic´ı k (x − y) ≡ N + qm mod N , tak N−1 dostáváme, ˇze pro x, y ∈ S, x < y existuje nejv´ yˇse 2b N uzn´ ych k = 1, 2, . . . , N − m c = 2b m c r˚ 1, ˇze hk (x) = hk (y) (nen´ı pravda, ˇze kdyˇz k splˇ nuje rovnici k (x − y) ≡ qm mod N pro N N nˇejaké q = −b m c, . . . , −1, 1, . . . , b m c, pak hk (x) = hk (y)). Stejn´ y odhad analogicky dostaneme, kdyˇz x < y (ale dostáváme jiná ˇreˇsen´ı). Odtud ! ! N−1 m−1 X X X n (n − 1) N −1 2 k ≤ 2 (N − 1) . bi −n ≤ 2 m m i=0 x,y∈S,x6=y

k=1

Pocet dvojic {x,y}, kde x =/= y

Tedy existuje k takové, ˇze

Pm−1

≤

bki

2

bi

i=0

Ukáˇzeme, ˇze existuje v´ıce neˇz

k 2

N−1 4 m−1 X

2 n(n−1) m

+ n.

(#3)

takov´ ych k, ˇze plat´ı

i=0

<3

n (n − 1) + n. m

V opaˇcném pˇr´ıpadˇe dostáváme, ˇze N−1 X k=1

m−1 X i=0

k 2

bi

!

−n

!

≥

3 (N − 1) 3n (n − 1) = 4 m 9 (N − 1) n (n − 1) > 4m 2 (N − 1) n (n − 1) , m

a to je spor s pˇredchoz´ım v´ ysledkem. Tedy pˇri náhodném rovnomˇerném v´ ybˇeru k je (m−1 ) X 3n (n − 1) 1 2 bki < Prob + n | k ∈ {1, 2, . . . , N − 1} ≥ . m 4 i=0 Tvrzen´ı. Kdyˇz n = m, pak (a) existuje deterministick´ y algoritmus, jenˇz v ˇcase O (nN ) nalezne k takové, ˇze m−1 X i=0

bki

2

< 3n;

2 Pm−1 (b) existuje pravdˇepodobnostn´ı algoritmus, kter´ y nalezne takové k, ˇze i=0 bki < 4n v ˇcase O (n) – oˇcek´ avan´ y poˇcet iterac´ı v´ ypoˇctu je nejv´ yˇse 4. D´ ale (c) existuje deterministick´ y algoritmus, jenˇz v ˇcase O (nN ) pro m = n (n − 1)+1 nalezne takové k, ˇze hk je perfektn´ı; (d) existuje pravdˇepodobnostn´ı algoritmus, kter´ y pro m = 2n (n − 1) v ˇcase O (n) nalezne k takové, ˇze hk je perfektn´ı – oˇcek´ avan´ y poˇcet iterac´ı v´ ypoˇctu je nejv´ yˇse 4.

44

a)

Pm−1 k 2 D˚ ukaz. Mˇejme n = m. Protoˇze spoˇc´ıtán´ı bi pro pevné k vyˇzaduje ˇcas O (n), i=0 prohledán´ım vˇsech moˇznost´ı nalezneme k takové, ˇze m−1 X

bki

i=0

b)

2

2n (n − 1) + n = 3n − 2 < 3n, n

≤

Viz #3 z min. str., navic n = m.

v ˇcase O (nN ). T´ım je dok´ azáno a). Pravdˇepodobnostn´ı algoritmus dokazuj´ıc´ı b) vol´ı 2 Pm−1 náhodnˇe k a v ˇcase O (n) ovˇeˇr´ı, zda i=0 bki ≤ 3 n(n−1) + n = 4n − 3 < 4n. Tuto akci n opakuje dokud poˇzadavek nen´ı splnˇen. Protoˇze pravdˇepodobnost, ˇze k splˇ nuje poˇzadavek, y poˇcet iterac´ı akce je nejv´ yˇse je alespoˇ n 41 , tak oˇcekávan´ ∞ i−1 X 3 1 1 1 i = =4 4 4 4 1− 3 2 i=0 4

c)

a odtud plyne b). Kdyˇz m = n (n − 1) + 1, pak prohledán´ım vˇsech moˇznost´ı nalezneme k takové, ˇze m−1 X i=0

bki

2

≤

2n (n − 1) + n < n + 2, n (n − 1) + 1

v ˇcase O (nN ) a c) plyne z pˇredchoz´ı vˇety. Kdyˇz m = 2n (n − 1), pak pro náhodnˇe zvolené k plat´ı s pravdˇepodobnost´ı ≤ 14 , ˇze m−1 X i=0

bki

2

≤

3n (n − 1) + n < n + 2. 2n (n − 1)

Algoritmus splˇ nuj´ıc´ı tvrzen´ı d) je stejn´ y jako v pˇr´ıpadˇe b) (jen m = 2n (n − 1)).

Pozn:

Def c_i:

Takto zkonstruované perfektn´ı haˇsovac´ı funkce nesplˇ nuj´ı poˇzadavek 2) (plat´ı m = Θ n2 ). Pouˇzijeme následuj´ıc´ı postup. 2 2 Pm−1 Pm−1 1) Nalezneme k takové, ˇze pro m = n plat´ı i=0 bki < 3n (respektive i=0 bki < 4n). Pro i = 0, 1, . . . , m − 1 nalezneme mnoˇziny Si = {s ∈ S | hk (s) = i}; 2) Pro kaˇzdé i = 0, 1 . . . , m − 1 takové, ˇze Si 6= ∅, nalezneme pro m = 1 + |Si | (|Si | − 1) (respektive m = 1 + 2|Si | (|Si | − 1)) takové ki , ˇze hki je perfektn´ı na Si . Definujme ci = 1 + |Si | (|Si | − 1) (respektive ci = 2|Si | (|Si | − 1)), kdyˇz Si 6= ∅, a ci = 0, kdyˇz Si = ∅. Pi−1 3) Pro i = 0, 1, . . . , m definujme di = cme hk (x) = l. Pak j=0 cj a pro x ∈ U oznaˇ poloˇz´ıme g (x) = dl + hkl (x). Vˇ eta. Zkonstruovan´ a funkce g je perfektn´ı, hodnota g (x) se pro kaˇzdé x ∈ U spoˇc´ıt´ a v ˇcase O (1), v deterministickém pˇr´ıpadˇe haˇsuje do tabulky velikosti < 3n a je nalezena v ˇcase O (nN ), v pravdˇepodobnostn´ım pˇr´ıpadˇe haˇsuje do tabulky velikosti < 6n a je nalezena v ˇcase O (n). Pro jej´ı zak´ odov´ an´ı jsou tˇreba hodnoty k a ki pro i = 0, 1, . . . , m − 1. Tyto hodnoty jsou v rozmez´ı 1, 2, . . . , N − 1, a tedy vyˇzaduj´ı O (n log N ) pamˇeti.

45

D˚ ukaz. Protoˇze g (Si ) pro i = 0, 1, . . . , m − 1 jsou navzájem disjunktn´ı a hki je perfektn´ı na Si , dostáváme, ˇze g je perfektn´ı. Pro v´ ypoˇcet hodnoty g (x) jsou tˇreba dvˇe násoben´ı, dvoj´ı v´ ypoˇcet zbytku pˇri dˇelen´ı a jedno sˇc´ıtán´ı (hodnoty di jsou uloˇzeny v pamˇeti). Proto v´ ypoˇcet g (x) vyˇzaduje ˇcas O (1). Dále dm je horn´ı odhad na poˇcet ˇradk˚ u v tabulce. Protoˇze pro 2 Si 6= ∅, máme |Si | (|Si | − 1)+1 ≤ |Si |2 = bki , dostáváme v deterministickém pˇr´ıpadˇe dm = Pm−1 Pm−1 k 2 bi < 3n a k nalezneme v ˇcase O (nN ). v ˇcase i=0 ci ≤ i=0 Protoˇ ze ki nalezneme Pm−1 Pm−1 O (|Si |N ), lze g zkonstruovat v ˇcase O nN + i=0 |Si |N = O nN + N i=0 |Si | = O (2nN ) = O (nN ). V pravdˇepodobnostn´ım pˇr´ıpadˇe je dm =

m−1 X i=0

ci ≤

m−1 X i=0

2

2|Si | − 2|Si | = 2

m−1 X i=0

2 bki

−2

m−1 X i=0

bki < 8n − 2n = 6n

Pm−1 (protoˇze |Si | = bki a i=0 bki = n). Protoˇze k nalezneme v ˇcase O (n) a ki v ˇcase O (|Si |) dostaneme, ˇze ˇze g nalezneme v ˇcase O (n). Zbytek je jasn´ y. Pozn:

Tedy zkonstruovaná haˇsovac´ı funkce splˇ nuje poˇzadavky 1), 2) a 3), ale poˇzadavek 4) nen´ı splnˇen. Mˇejme pˇrirozené ˇc´ıslo m a nechˇt q je poˇcet vˇsech prvoˇc´ısel dˇel´ıc´ıch m (p1 , p2 , . . . je rostouc´ı posloupnost vˇsech prvoˇc´ısel). Pak m≥

q Y

i=1

Rq Pq q q ln xdx ln i q ln( eq )+1 i=1 1 pi > q! = e ≥e =e ≥ . e

Proto existuje konstanta c, ˇze q ≤ c lnlnlnmm . Plat´ı tedy Vˇ eta. Nechˇt δ (m) =poˇcet prvoˇc´ısel, kter´ a dˇel´ı m. Pak δ (m) = O

Def φ_p(x):

log m log log m

.

Mˇejme S = {s1 < s2 < · · · < sn } ⊆ U . Oznaˇcme di,j = sj − si pro 1 ≤ i < j ≤ n. Pak Q 2 si mod p 6= sj mod p, právˇe kdyˇz di,j 6= 0 mod p. Oznaˇcme D = 1≤i<j≤n di,j ≤ N (n ) . Pak poˇcet prvoˇc´ıseln´ ych dˇelitel˚ u ˇc´ısla D je nejv´ yˇse c lnlnlnDD , a tedy mezi prvn´ımi 1 + c lnlnlnDD prvoˇc´ısly existuje prvoˇc´ıslo p takové, ˇze si mod p 6= sj mod p pro kaˇzdé 1 ≤ i < j ≤ n. To znamená, ˇze funkce φp (x) = x mod p je perfektn´ı pro S. Podle vˇety o velikosti prvoˇc´ısel pt ≤ 2t ln t pro kaˇzdé t ≥ 6, tedy ln D ln D p ≤2 1 + c ln 1 + c ≤ ln ln D ln ln D ln D ln D ≤ ln 2c 4c ln ln D ln ln D ln D ln D ln D = + 4c ln 4c (ln 2c) ln ln D ln ln D ln ln D 4c ln D + o (ln D) = O (ln D) = O n2 ln N .

(#1)

46

Vˇ eta. Pro kaˇzdou n-prvkovou mnoˇzinu S ⊆ U existuje prvoˇc´ıslo p o velikosti O n2 ln N takové, ˇze funkce φp (x) = x mod p je perfektn´ı pro S. Složitost determinist. algoritmu:

Krok pstního algoritmu:

Test, zda funkce φp (x) = x mod p je perfektn´ı pro S, vyˇzaduje ˇcas O (n log n). Tedy systematické hledán´ı nejmenˇs´ıho p, ˇze φp je perfektn´ı pro S, vyˇzaduje ˇcas O n3 log n log N . Nejmenˇs´ı p takové, ˇze φp je perfektn´ı pro S, je prvoˇc´ıslo. Navrhneme pravdˇepodobnostn´ı algoritmus pro nalezen´ı p. Pro dostateˇcnˇe velké n mezi prvn´ımi 9c ln D prvoˇc´ısly je alespoˇ n polovina takov´ ych prvoˇc´ısel p, ˇze φp je perfektn´ı pro S. Algoritmus pak opakuje následuj´ıc´ı krok, dokud nenalezne perfektn´ı funkci vyberme náhodnˇe ˇc´ıslo p mezi prvn´ımi 9cn2 ln N ˇc´ısly a otestujme, zda p je prvoˇc´ıslo a φp je perfektn´ı Odhad oˇcekávaného poˇctu ne´ uspˇeˇsn´ ych krok˚ u. 2 Náhodnˇe zvolené ˇc´ıslo p ≤ 9cn ln N je prvoˇc´ıslo s pravdˇepodobnost´ı Θ ln(9cn12 ln N) a pro prvoˇc´ıslo p je φp perfektn´ı s pravdˇepodobnost´ ı ≥

1 . 2

Tedy náhodnˇe zvolené ˇc´ıslo , a proto oˇcekávan´ y poˇcet

1 ln(9cn2 ln N)

2

p ≤ 9cn ln N splˇ nuje test s pravdˇepodobnost´ı Θ ne´ uspˇeˇsn´ ych test˚ u je O ln 9cn2 ln N . Tedy oˇcekávan´ y ˇcas algoritmu je Ocekavan pocet neuspesnych testu

ma byt log n^2??

O (n log n (log n + log log N )) . Otestovani vybraneho p

Vˇ eta. Pro danou mnoˇzinu S ⊆ U takovou, ˇze |S| = n, deterministick´ y algoritmus nalezne 2 prvoˇc´ıslo p = O n log N takové, ˇze φp (x) = x mod p je perfektn´ı pro S, a pracuje v 3 2 ˇcase O n log n log N . Pravdˇepodobnostn´ı algoritmus nalezne prvoˇc´ıslo p = O n log N takové, ˇze φp je perfektn´ı, v oˇcek´ avaném ˇcase O (n log n (log n + log log N )). Výsledná p pro deter. a nedeter. algoritmus:

Deterministick´ y algoritmus nalezne nejmenˇs´ı prvoˇc´ıslo s poˇzadovanou vlastnost´ı. Pravdˇepodobnostn´ı algoritmus nalezne prvoˇc´ıslo, které m˚ uˇze b´ yt podstatnˇe vˇetˇs´ı, ale jeho velikost 2 je omezena 9cn log N . Nyn´ı navrhneme postup na konstrukci perfektn´ı haˇsovac´ı funkce pro mnoˇzinu S ⊆ U . (1) Nalezneme prvoˇc´ıslo q0 ∈ O n2 log N takové, ˇze φq0 (x) = x mod q0 je perfektn´ı funkce pro S. Poloˇzme S1 = {φq0 (s) | s ∈ S}. (2) Nalezneme prvoˇc´ıslo q1 takové, ˇze n (n − 1) < q1 ≤ 2n (n − 1). Pak existuje l ∈ {1, 2, . . . , q0 − 1} takové, ˇze hl (x) = ((lx) mod q0 ) mod q1 je perfektn´ı pro S1 ⊆ {0, 1, . . . , q0 − 1}. Poloˇzme S2 = {hl (s) | s ∈ S1 }. (3) Dále zkonstruujme perfektn´ı haˇsovac´ı funkci g pro mnoˇzinu S2 ⊆ {0, 1, . . . , q1 − 1} do tabulky s ménˇe neˇz 3n ˇrádky. Poloˇzme f (x) = g (hl (φq0 (x))). Konstruovan´ a haˇsovac´ı funkce je f . V´ ysledek: f je perfektn´ı haˇsovac´ı funkce pro S, protoˇze sloˇzen´ı perfektn´ıch haˇsovac´ıch funkc´ı je zase perfektn´ı funkce, a tedy poˇzadavek 1) je splnˇen. f haˇsuje S do tabulky s ménˇe neˇz 3n ˇrádky, a tedy splˇ nuje poˇzadavek 2). Protoˇze kaˇzd´ a z funkc´ı g, hl , φq0 se vyˇc´ısl´ı v ˇcase O (1), i vyˇc´ıslen´ı funkce f vyˇzaduje ˇcas O (1) a poˇzadavek 3) je splnˇen. Funkce φq0 je jednoznaˇcnˇe urˇcena ˇc´ıslem q0 ∈ O n2 log N . Funkce hl je urˇcena ˇc´ısly

47

q1 ∈ O n2 a l ∈ O (q0 ). Funkce g je urˇcena n + 1 ˇc´ısly velikosti O (q1 ). Tedy zad´ an´ı f vyˇzaduje pamˇeˇt o velikosti O (log n + log log N + n log n) = O (n log n + log log N ) . Lze ˇr´ıct, ˇze poˇzadavek 4) je splnˇen. V´ ypoˇcet φq0 vyˇzaduje ˇcas O n3 log n log N . V´ ypoˇcet hl vyˇzaduje ˇcas O n n2 log N = O n3 log N (pouˇzité univerzum je {0, 1, . . . , q0 }). V´ ypoˇcet g vyˇzaduje ˇcas O nn2 = 3 O n (zde univerzum je {0, 1, . . . , q1 }). Celkovˇe, v´ ypoˇcet f vyˇzaduje ˇcas O n3 log n log N .

Lze pouˇz´ıt i pravdˇepodobnostn´ı algoritmy pro nalezen´ı g, hl a φq0 . Pak haˇsujeme do tabulky s ménˇe neˇz 6n ˇrádky, ale oˇcekávan´ y ˇcas pro nalezen´ı f je O (n log n (log n + log log N )). Tuto metodu navrhli Fredman, Koml´ os a Szemerédi. Dynamick´ e perfektn´ı haˇ sov´ an´ı. Jedna z velk´ ych nev´ yhod perfektn´ıho haˇsovan´ı je neznalost efektivn´ıch aktualizaˇcn´ıch operac´ı. Existuj´ı sice obecné metody na dynamizaci deterministick´ ych operac´ı – viz letn´ı pˇrednáˇska, ale tato metoda v tomto pˇr´ıpadˇe neposkytuje efektivn´ı dynamizaˇcn´ı operace, protoˇze deterministick´ y algoritmus pro ˇreˇsen´ı perfektn´ıho haˇsován´ı je pro aktualizaˇcn´ı operace pˇriliˇs pomal´ y. To vedlo k návrhu, kter´ y kombinuje pravdˇepodobnostn´ı algoritmus pro perfektn´ı haˇsován´ı s obecnou metodou dynamizace a tyto metody jsou upraveny pro konkrétn´ı situaci. Nejprve uvedeme modifikaci v´ ysledk˚ u z pˇredchoz´ı ˇcásti, na kter´ ych je tato metoda zaloˇzena. Pˇredpokládáme, ˇze U = {0, 1, . . . , N − 1} je univerzum, kde N je prvoˇc´ıslo, a ˇze je dáno ˇc´ıslo s < N . Oznaˇcme Hs = {hk | k = 1, 2, . . . , N − 1} mnoˇzinu funkc´ı z U do {0, 1, . . . , s − 1}, kde hk (x) = (kx mod N ) mod s pro kaˇzdé x ∈ U . Kdyˇz zvol´ıme náhodnˇe k = 1, 2, . . . , N −1, pak s pravdˇepodobnost´ı alespoˇ n 12 plat´ı s−1 X i=0

bki

2

<

8n2 + 2n. s

Budeme pˇredpokládat, ˇze takové k máme, a pak pro kaˇzdé i = 0, 1, . . . , s−1 pˇredpoklád´ ame, ˇze náhodnˇe zvol´ıme ji ∈ H2(bk )2 takové, ˇze hji je prostá na mnoˇzinˇe Si = {s ∈ S | hk (s) = i} i

(z pˇredchoz´ıho textu v´ıme, ˇze kdyˇz zvol´ıme náhodnˇe ji = 0, 1, . . . , N − 1, pak hji je prost´ a na Si s pravdˇepodobnost´ı alespoˇ n 21 ). Pro jednoduchost pˇredpokládáme, ˇze mnoˇziny Si pro i = 0, 1, . . . , s − 1 uloˇz´ıme do tabulek Ti a tabulky T0 , T1 , . . . , Ts−1 budou uloˇzeny v tabulce T . Kdyˇz s = O (|S|), pak tato metoda vyˇzaduje O (|S|) prostoru. Abychom urˇcili s, √ zvolme c > 1 a poloˇzme s = σ (|S|), kde σ (n) = 43 6 (1 + c) n pro kaˇzdé n. Nyn´ı pop´ıˇseme algoritmy.

48

Algoritmy. INSERT(x): n := n + 1 if n ≤ m then j := h (x), |Sj | := |Sj | + 1 if |Sj | ≤ m (j) a pozice hj (x) v Tj je prázdná then vloˇz´ıme x do tabulky Tj na pozici hj (x) else if |Sj | ≤ m (j) a pozice hj (x) v Tj je obsazená then vytvoˇr´ıme seznam Sj prvk˚ u v tabulce Tj vyprázdn´ıme tabulku Tj Volíme funkci h_j zvol´ıme náhodnˇe funkci hj ∈ H2m(j)2 while hj nen´ı prostá na mnoˇzinˇe Sj do zvol´ıme náhodnˇe funkci hj ∈ H2m(j)2 enddo for every y ∈ Sj do vloˇz´ıme y do Tj na pozici hj (y) enddo else [Platí |S_j| > m(j)] [Zdvojnásobíme prostor pro tabulku T_j] m (j) := 2m (j) if nen´ı dost prostoru pro tabulku Tj nebo σ(m)−1

X i=0

[Přehashujeme prvky]

8m2 + 2m 2 (m (i)) ≥ σ (m) 2

then RehashAll else alokujeme prostor pro novou prázdnou tabulku Tj vytvoˇr´ıme seznam Sj prvk˚ u ze staré tabulky Tj a zruˇs´ıme ji zvol´ıme náhodnˇe funkci hj ∈ H2m(j)2 Volíme náhodně funkci while hj nen´ı prostá na mnoˇzinˇe Sj do zvol´ıme náhodnˇe funkci hj ∈ H2m(j)2 enddo for every y ∈ Sj do vloˇz´ıme y do Tj na pozici hj (y) enddo endif endif else RehashAll endif endif

h_j

[Přehashujeme prvky]

RehashAll: projdeme tabulku T a tabulky Ti a vytvoˇr´ıme seznam prvk˚ u z mnoˇziny S m := (1 + c) |S| zvolme náhodnˇe h ∈ Hσ(m)

49

for every i = 0, 1, . . . , σ (m) − 1 do Si := {x ∈ S | h (x) = i} enddo Pσ(m)−1 2 8m2 while i=0 2 (|Si |) < σ(m) + 2m do (#1) zvolme náhodnˇe h ∈ Hσ(m) for every i = 0, 1, . . . , σ (m) − 1 do Si := {x ∈ S | h (x) = i} enddo enddo Komentáˇr: zde Si jsou mnoˇziny vytvoˇrené náhodnˇe zvolenou funkci h n := 0 for every i = 0, 1, . . . , σ (m) − 1 do m (i) := |Si | zvol´ıme náhodnˇe hi ∈ H2m(i)2 Volíme funkci h_i while hi nen´ı prostá na mnoˇzinˇe Si do zvol´ıme náhodnˇe hi ∈ H2m(i)2 enddo enddo for every x ∈ S do INSERT(x) enddo

Dokud neni splnena podminka #1, tak pomoci nahodne hash. funkce rozdeluju do mnozin S_i.

DELETE(x): j := h (x), n := n − 1, |Sj | := |Sj | − 1 odstran´ıme x z pozice hj (x) v tabulce Tj , pozice bude prázdná m then RehashAll endif if n < 1+2c MEMBER(x): j := h (x) if x je na hj (x)-té pozici v tabulce Tj then V´ ystup: x je prvek S else V´ ystup: x nen´ı prvkem S endif Algoritmy pˇedpokládaj´ı, ˇze pˇri operaci INSERT(x) prvek x nepatˇr´ı do S a pˇri operaci DELETE(x) x je prvkem S. Pak n znamená velikost reprezentované mnoˇziny. Uvedu sloˇzitost této metody bez d˚ ukazu. Vˇ eta. Popsan´ a metoda vyˇzaduje line´ arn´ı pamˇeˇt (neuvaˇzuje se pamˇeˇt potˇrebn´ a pro zak´ odov´ an´ı haˇsovac´ıch funkc´ı), operace MEMBER v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas O (1) a oˇcek´ avan´ a amortizovan´ a sloˇzitost operac´ı INSERT a DELETE je také O (1). Toto zobecnˇen´ı Fredman-Komlós-Szemerédiho metody navrhli Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert a Tarjan. Dalˇs´ı nev´ yhoda Fredman-Komlós-Szemerédiho metody: Navrˇzená metoda pracuje pro m < 3n, ale nezajist´ı m = n. Lze ˇr´ıct, ˇze pamˇeˇt je efektivn´ı vyuˇzitá? Existuje metoda, která by umoˇznila návrh perfektn´ı haˇsovac´ı funkce pro m = n? Z v´ ysledk˚ u pro (N, m, n)-perfektn´ı soubory funkc´ı plyne existence (N, n, n)-perfektn´ıho souboru pro nN > en+ln(n) ln (N ). Zm´ın´ıme se orientaˇcnˇe o parametrizované metodˇe, kter´ a

50

Def:

navrhuje perfektn´ı haˇsovac´ı funkci pro S ⊆ U a pro |S| = n. Parametr bude pˇrirozené ˇc´ıslo r, které urˇcuje, jaké hypergrafy jsou uˇzity pˇri konstrukci funkce. Proto nejdˇr´ıve pˇripomeneme nˇekolik definic. Dvojice (X, E), kde X je mnoˇzina a E je systém r-prvkov´ ych podmnoˇzin X, se naz´ yv´ a r-hypergraf. Prvky v E se naz´ yvaj´ı hrany r-hypergrafu. Cyklus je hypergraf (X, E), kde kaˇzd´ y vrchol leˇz´ı alespoˇ n ve dvou r˚ uzn´ ych hranách. Naopak r-hypergraf (X, E) se naz´ yv´ a y jeho podhypergraf nen´ı cyklus. acyklick´ y, kdyˇz ˇzádn´ Nyn´ı pop´ıˇseme metodu, která je rozdˇelena do dvou krok˚ u. Je dáno S ⊆ U takové, ˇze |S| = n. Krok 1) Mˇejme r-hypergraf (V, E), kde |E| = n. Nalezneme zobrazen´ı g:V − → {0, 1, . . . , n − 1} Pr takové, ˇze funkce h : E − → {0, 1, . . . , n − 1} definovaná h (e) = i=1 g (vi ) mod n, kde e = {v1 , v2 , . . . , vr }, je prostá (m´ısto sˇc´ıtán´ı modulo n m˚ uˇzeme pouˇz´ıt libovolnou grupovou operaci na mnoˇzinˇe {0, 1, . . . , n − 1}). Pro acyklick´ y r-hypergraf lze funkci g zkonstruovat následuj´ıc´ım postupem. Zvol´ıme bijekci h : E − → {0, 1, . . . , n − 1} a pak definujeme g následovnˇe: kdyˇz e = {v1 , v2 , . . . , vr } a g (vi ) je definováno pro i = 2, 3, . . . , r, pak g (v1 ) = h (e) −

r X

g (vi ) mod n.

i=2

Protoˇze pro kaˇzd´ y acyklick´ y r-hypergraf existuje vrchol, kter´ y leˇz´ı v jediné hranˇe, lze tento postup pouˇz´ıt ke konstrukci g pomoc´ı indukce (a tedy máme algoritmus pro konstrukci g). Krok 2) Nalezneme r funkc´ı f1 , f2 , . . . , fr : U − → V takov´ ych, ˇze (V, E), kde E = {{f1 (x) , f2 (x) , . . . , fr (x)} | x ∈ S} , je acyklick´ y r-hypergraf. Pak haˇsovac´ı funkce f je definována f (x) = kaˇzdé x ∈ U . Z konstrukce vypl´ yvá, ˇze je perfektn´ı na mnoˇzinˇe S.

Pr

i=1

g (fi (x)) pro

Autoˇri dokázali, ˇze nejvhodnˇejˇs´ı alternativa je, kdyˇz zobrazen´ı f1 , f2 , . . . , fr jsou náhodnˇe zvolená náhodná zobrazen´ı. Bohuˇzel taková zobrazen´ı neum´ıme zkonstruovat, ale autoˇri ukázali, ˇze pro tyto u ´ˇcely lze pouˇz´ıt náhodn´ y v´ ybˇer funkc´ı z nˇejakého c-univerz´ aln´ıho souboru funkc´ı. Autoˇri ukázali, ˇze jejich algoritmus vyˇzaduje O (rn + |V |) ˇcasu a O (n log n + r log |V |) pamˇeti. Tento metapostup navrhli Majewski, Wormald, Havas a Czech (1996). Pro praktické pouˇzit´ı je problematická reprezentace r-hypergrafu a i náhodná volba funkc´ı f1 , f2 , . . . , fr (viz pˇredchoz´ı diskuze o c-univerzalitˇe). Z poˇzadavk˚ u na perfektn´ı haˇsovac´ı funkci je opˇet problémem splnˇen´ı poˇzadavku 4). Nev´ım, jak je uvedená metoda prakticky pouˇzitelná a zda se nˇekde pouˇz´ıvá.

51

´ n´ı Extern´ı haˇ sova Navrˇzen´ y postup je také znám pod názvem Fagin˚ uv algoritmus. T´ımto problémem se prvn´ı asi zab´ yval Larsson. ˇ s´ıme jin´ Reˇ y problém – uloˇzen´ı dat na extern´ı pamˇeˇt. Hlavn´ı problém – minimalizovat poˇcet pˇr´ıstup˚ u na extern´ı pamˇeˇt. Pˇredpoklady: Extern´ı pamˇeˇt je rozdˇelena na stránky, kaˇzdá stránka obsahuje b poloˇzek (dat) (pˇredpokládáme, ˇze b > 1, jinak to nemá smysl). Vˇzdy v jednom kroku naˇcteme celou stránku do intern´ı pamˇeti nebo celou stránku v intern´ı pamˇeti v jednom kroku zap´ıˇseme na extern´ı medium. Tyto operace jsou ˇrádovˇe pomalejˇs´ı neˇz oprace v intern´ı pamˇeti. Náˇs c´ıl: Nalézt zp˚ usob ukládán´ı dat do stránek extern´ı pamˇeti, aby se minimalizoval poˇcet operac´ı s extern´ı pamˇet´ı. ∗

Def:

Pˇredpokládejme, ˇze h : U − → {0, 1} je prosté zobrazen´ı takové, ˇze délka h (u) je stejn´ a pro vˇsechny prvky univerza U . Oznaˇcme k délku h (u) pro u ∈ U . Pak h je haˇsovac´ı funkce. Nechˇt S ⊆ U , pak pro slovo α délky menˇs´ı neˇz k definujme h−1 S (α) = {s ∈ S | α je prefix h (s)} .

Def:

ˇ zd´ y vlastn´ı prefix α0 slova α Rekneme, ˇze α je kritické slovo, kdyˇz 0 < |h−1 S (α) | ≤ b a pro kaˇ 0 zdé s ∈ S existuje právˇe jedno kritické slovo α, které je prefixem plat´ı |h−1 S (α ) | > b. Pro kaˇ h (s). Definujme d (s) pro s ∈ S jako délku kritického slova, které je prefixem h (s) a d (S) = max {délka (α) | α je kritické slovo} = max {d (s) | s ∈ S} . Mnoˇzinu S reprezentujeme tak, ˇze je jednoznaˇcná korespondence mezi kritick´ ymi slovy a stránkami extern´ı pamˇeti slouˇz´ıc´ımi k reprezentaci S. Na stránce pˇr´ısluˇsej´ıc´ı kritickému slovu α je reprezentován soubor h−1 S (α). Problém: jak nalézt stránku kritického slova α? ˇ sen´ı: Adresáˇr je funkce, která kaˇzdému slovu α o délce d (S) pˇriˇrad´ı adresu str´ Reˇ anky pˇredpisem kdyˇz kritické slovo β je prefixem α, pak k α je pˇriˇrazena stránka koresponduj´ıc´ı s β, jinak je k α pˇriˇrazena stránka N IL – speciáln´ı prázdná stránka. −1 zdé Korektnost: Pro r˚ uzná kritická slova β a γ plat´ı h−1 S (β) ∩ hS (γ) = ∅, a tedy pro kaˇ slovo α délky d (S) existuje nejv´ yˇse jedno kritické slovo, které je prefixem α. Kdyˇz α je slovo délky d (S), pak nastane jeden z tˇechto tˇr´ı pˇr´ıpad˚ u: −1 avˇe jedno kritické slovo β, které je (1) h−1 S (α) 6= ∅, pak 0 < |hS (α) | ≤ b a existuje pr´ prefixem α; 0 0 y, ˇze 0 < |h−1 (2) h−1 S (α ) | ≤ b, pak existuje S (α) = ∅ a existuje prefix α slova α takov´ 0 právˇe jedno kritické slovo, které je prefixem α (a tedy také prefixem α); ˇ h−1 (α0 ) = ∅ nebo |h−1 (α0 ) | > b zd´ y prefix α0 slova α plat´ı bud (3) h−1 S S S (α) = ∅ a pro kaˇ (pak k α je pˇriˇrazena stránka N IL. Mˇejme slovo α o délce d (S). Oznaˇcme c (α) nejkratˇs´ı prefix α0 slova α takov´ y, ˇze str´ anka 0 pˇriˇrazená slovu β o délce d (S), které má α za prefix, je stejná jako stránka pˇriˇrazen´ a α.

52

Vˇsimnˇeme si, ˇze kdyˇz hS−1 (α) 6= ∅, pak c (α) je kritické slovo. Plat´ı silnˇejˇs´ı tvrzen´ı, které tvrd´ı, ˇze následuj´ıc´ı podm´ınky jsou ekvivalentn´ı: (1) stránka pˇriˇrazená slovu α je r˚ uzná od N IL; (2) c (α) je kritické slovo; (3) nˇejak´ y prefix α je kritické slovo. Vˇsimnˇeme si, ˇze znalost adresáˇre umoˇzn ˇuje nalézt slovo c (α) pro kaˇzdé slovo o délce d (S). Lineárn´ı uspoˇrádán´ı na slovech délky n nazveme lexikografické, kdyˇz α < β, právˇe kdyˇz α = γ0α0 a β = γ1β 0 pro nˇejaká slova γ, α0 a β 0 . Lexikografické uspoˇrádán´ı vˇzdy existuje a je jednoznaˇcné. Reprezentace adresáˇre: Je to seznam adres stránek o délce 2d(S) takov´ y, ˇze adresa na i-tém m´ıstˇe odpov´ıdá i-tému slovu délky d (S) v lexikografickém uspoˇrádán´ı. Pˇr´ıklad: U je mnoˇzina vˇsech slov nad {0, 1} o délce 5, h je identická funkce a b = 2. Reprezentujme mnoˇzinu S = {00000, 00010, 01000, 10000}. Pak d (00000) = d (00010) = d (01000) = 2, d (10000) = 1, kritická slova jsou 00, 01 a 1 a adresáˇr je (m´ısto adresy str´ anky uvedeme mnoˇzinu, která je na této stránce uloˇzena) 00 7→ {00000, 00010} ,

01 7→ {01000} ,

10 7→ 11 7→ {10000} .

Tedy c (00) = 00, c (01) = 01 a c (10) = c (11) = 1. Kdyˇz odstran´ıme prvek 10000, pak 1 pˇrestane b´ yt kritické slovo a adresáˇr bude m´ıt tvar 00 7→ {00000, 00010} ,

01 7→ {01000} ,

10 7→ 11 7→ N IL.

Opˇet plat´ı c (00) = 00, c (01) = 01 a c (10) = c (11) = 1. V adresáˇri je také uloˇzeno d (S). Algoritmy. Slovn´ı popis operac´ı. Pˇredpokládáme, ˇze adresáˇr je uloˇzen v extern´ı pamˇeti na jedné str´ ance. MEMBER(x): 1) Spoˇc´ıtáme h (x) a naˇ cteme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h (x) o délce d (S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α. Kdyˇz je to stránka N IL, pak x ∈ /S a konec, jinak pokraˇcujeme krokem 2). 2) Naˇ cteme stránku pˇr´ısluˇsej´ıc´ı k α do intern´ı pamˇeti. Prohledáme ji a pokud neobsahuje x, pak x ∈ / S a konec. Kdyˇz obsahuje x, pak provedeme poˇzadované zmˇeny a str´ anku uloˇ z´ıme do extern´ı pamˇeti na jej´ı p˚ uvodn´ı m´ısto. Konec. INSERT(x): 1) Spoˇc´ıtáme h (x) a naˇ cteme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h (x) o délce d (S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α a slovo c (α). Kdyˇz stránka pˇriˇrazen´ a k α je N IL, pokraˇcujeme krokem 3), v opaˇcném pˇr´ıpadˇe pokraˇcujeme krokem 2). 2) Naˇ cteme stránku pˇriˇrazenou slovu α. Kdyˇz x je uloˇzeno na této stránce, pak skonˇc´ıme. Kdyˇz x nen´ı na této stránce, pak tam pˇridáme slovo x. Pokud na stránce je nejv´ yˇse b prvk˚ u, pak uloˇ z´ıme stránku na jej´ı p˚ uvodn´ı m´ısto a skonˇc´ıme. Kdyˇz na stránce je v´ıce neˇz b prvk˚ u, pak nalezneme nová kritická slova, která nám stránku rozdˇel´ı, a vytvoˇr´ıme dvˇe stránky – jednu uloˇ z´ıme na m´ısto p˚ uvodn´ı stránky a druhou uloˇ z´ıme na novou str´ anku.

53

Pokraˇcujeme krokem 4). 3) Vytvoˇr´ıme v intern´ı pamˇeti novou stránku, která obsahuje x, nalezneme novou stránku v extern´ı pamˇeti a tam uloˇ z´ıme vytvoˇrenou stránku (vˇsem slov˚ um, která maj´ı c (α) za prefix, bude pˇriˇrazena tato stránka) a pokraˇcujeme krokem 4). 4) Naˇ cteme opˇet adresáˇr do intern´ı pamˇeti, aktualizujeme adresy pˇriˇrazen´ ych str´ anek a pˇr´ıpadnˇe zvˇetˇs´ıme adresáˇr (to nastane, kdyˇz nˇejaké nové kritické slovo má délku vˇetˇs´ı neˇz d (S), pak nové d (S) je právˇe délka tohoto slova – obˇe kritická slova vzniklá v kroku 2) maj´ı stejnou délku). Aktualizovan´ y adresáˇr uloˇ z´ıme do extern´ı pamˇeti. Konec. DELETE(x): 1) Spoˇc´ıtáme h (x) a naˇ cteme adresáˇr do intern´ı pamˇeti. Vezmeme prefix α slova h (x) o délce d (S) a nalezneme adresu stránky pˇr´ısluˇsej´ıc´ı k α a slovo c (α). Kdyˇz stránka pˇriˇrazen´ a 0 k α je N IL, pak skonˇc´ıme. Oznaˇcme β slovo, které má stejnou délku jako c (α) a liˇs´ı se od c (α) pouze v posledn´ım bitu. Kdyˇz existuje slovo β délky d (S) takové, ˇze c (β) = β 0 , pak stránka pˇriˇrazená k β je kandidát. 2) Naˇ cteme stránku pˇr´ısluˇsnou k slovu α do intern´ı pamˇeti. Kdyˇz tato stránka neobsahuje x, pak skonˇc´ıme. Kdyˇz tato stránka obsahuje x, pak odstran´ıme x z této stránky. Kdyˇz neexistuje kandidát nebo kdyˇz nová stránka a stránka kandidáta dohromady obsahuj´ı v´ıce neˇz b prvk˚ u, pak novou stránku uloˇ z´ıme na jej´ı p˚ uvodn´ı m´ısto a skonˇc´ıme. 3) Kdyˇz nová stránka a stránka kandidáta maj´ı dohromady b prvk˚ u, pak naˇ cteme str´ anku kandidáta do intern´ı pamˇeti. V intern´ı pamˇeti tyto stránky spoj´ıme do jedné a tuto str´ anku pak uloˇ z´ıme do extern´ı pamˇeti. 4) Naˇ cteme adresáˇr, kde zaktualizujeme adresy stránek. Pokud jsme slouˇcili dvˇe str´ anky, mus´ıme nalézt nové c (α) (je to nejkratˇs´ı prefix α0 slova α takov´ y, ˇze ke kaˇzdému slovu β o délce d (S), které má α0 za prefix, je pˇriˇrazena jedna z tˇechto adres: adresa stránky pˇriˇrazen´ a k α, adresa stránky kandidáta, N IL) a kaˇzdému slovu o délce d (S), které má nové c (α) za prefix, bude pˇriˇrazena adresa nové (spojené) stránky. Otestujeme, zda se adresáˇr nem˚ uˇze zkrátit (to nastane, kdyˇz adresy stránek pˇriˇrazené (2i + 1)-´ımu slovu a (2i + 2)-ému slovu o délce d (S) jsou stejné pro vˇsechna i, pak se tato slova spoj´ı a d (S) se zmenˇs´ı o 1). Upraven´ y adresáˇr uloˇ z´ıme. Konec.

Následuj´ıc´ı vˇeta ukazuje, ˇze jsme náˇs hlavn´ı c´ıl splnili. Pro jednoduchost pˇredpoklád´ ame, ˇze adresáˇr je také uloˇzen na extern´ı pamˇeti a ˇze v intern´ı pamˇeti nem˚ uˇze b´ yt uloˇzen spolu s nˇejakou jinou stránkou. Vˇ eta. Operace MEMBER vyˇzaduje nejv´ yˇse tˇri operace s extern´ı pamˇet´ı. Operace INSERT a DELETE vyˇzaduj´ı nejv´ yˇse ˇsest operac´ı s extern´ı pamˇet´ı. V naˇsem pˇr´ıkladu provedeme operaci INSERT(00001). Po pˇridán´ı prvku stránka p˚ uvodnˇe pˇriˇrazená k slovu 00 vypadá takto {00000, 00001, 00010}. Tuto stránku rozdˇel´ıme na str´ anky {00000, 00001} a {00010}. Pˇritom kritické slovo prvn´ı stránky je 0000 a druhé str´ anky

54

je 0001. Takˇze d (S) = 4 a adresáˇr vypadá 0000 7→ {00000, 00001} , 0001 7→ {00010} , 0010 7→ 0011 7→ N IL,

0100 7→ 0101 7→ 0110 7→ 0111 7→ {0100} ,

1000 7→ 1001 7→ 1010 7→ 1011 7→ {10000} ,

1100 7→ 1101 7→ 1110 7→ 1111 7→ {10000} .

To znamená, ˇze kromˇe adresy 00 se ostatn´ı slova rozdˇelila na ˇctyˇri slova, ale adresy z˚ ustaly stejné. Jen u slova 00 vzniklá slova dostala r˚ uzné adresy. V p˚ uvodn´ım pˇr´ıkladu provedeme operaci DELETE(01000). Pak kandidát je 00 a po odstranˇen´ı prvku 01000 nastane spojen´ı tˇechto dvou stránek. Po aktualizaci adres dostane adresáˇr tvar 00 7→ 01 7→ {00000, 00010} , 10 7→ 11 7→ {10000} , tj. k prvn´ımu a druhému slovu je pˇriˇrazena stejná stránka a stejnˇe tak k tˇret´ımu a ˇctvrtému slovu. Takˇze m˚ uˇzeme adresáˇr zmenˇsit. Pak d (S) = 1 a adresáˇr má podobu 0 7→ {00000, 00010} , 1 7→ {10000} . Vzniká ot´ azka, jak je tato metoda efektivn´ı. Hlavnˇe jak efektivnˇe vyuˇz´ıvá pamˇeˇt. Plat´ı Vˇ eta. Kdyˇz velikost reprezentované mnoˇziny je n, pak oˇcek´ avan´ y poˇcet pouˇzit´ ych str´ anek e n 1+ 1b avan´ a velikost adres´ aˇre je b ln 2 n . je b ln 2 a oˇcek´ Prvn´ı tvrzen´ı ˇr´ıká, ˇze oˇcekávan´ y poˇcet prvk˚ u na stránce je b ln 2 ≈ 0.69b. Tedy zaplnˇeno je asi 69% m´ıst. Tento v´ ysledek nen´ı pˇrekvapuj´ıc´ı a je akceptovateln´ y. Horˇs´ı je to s adres´ aˇrem, jak ukazuje následuj´ıc´ı tabulka

velikost S 2 10 50 100

105 6.2 · 107 1.2 · 105 9.8 · 103 4.4 · 103

106 1.96 · 108 1.5 · 106 1.0 · 106 4.5 · 104

108 1.96 · 1011 2.4 · 108 1.1 · 108 4.7 · 106

1010 1.96 · 1014 3.9 · 1010 1.2 · 1010 4.9 · 108

kde jednotlivé ˇrádky odpov´ıdaj´ı hodnotám b uveden´ ych v prvn´ım sloupci. Protoˇze oˇcek´ avan´ a 1 avat, velikost adresáˇre se zvˇetˇsuje rychleji neˇz lineárnˇe (exponent u n je 1+ b ), tak nelze oˇcek´ ˇze tuto metodu lze vˇzdy pouˇz´ıt. V´ ypoˇcty i experimenty ukazuj´ı, ˇze pouˇzitelná je do velikosti |S| = 1010 , kdyˇz b ≈ 100. V tomto rozmez´ı je nár˚ ust adresáˇre jen kolem 5%. Pro vˇetˇs´ı n je tˇreba, aby b bylo jeˇstˇe vˇetˇs´ı.

Z kladn probl m: Reprezentace mno 0 6in a operace s nimi. V 0 0ad loh a algoritm 0 1 je tento

Recommend Documents