31 (733)

A : sicwr.i):) : inzeęar;

function2    [x : s2cvc; v*r

b«gir*

if A( szu.k^j (x,A) ) * x then

return(Crue);

•tre-Ł

i p    c ć? ipb-c/Li-

‘ŁłJc?- <-c

alfę

return (fa 1 se) ;

endif;

end;

procedurę WSTAW(x : słowc; var. 2 : slownik) ; var kubełek :

begin

if A( szuka j (x,A) } ^Ł x tihen*

return;    (x jest w tablicy]

endi f;

kubełek : * szukaj2tx,A);

if(A ikubełek} =■ pusca) or (A[kubełex] = usunięće) then A(kubełek)    x;

else

bi*d( 'błać w procedurze ffsrAtf: rebiica jest pezr.a' ) ;

endif;

end;

procedura L^r5L?!^r(x : siowc; var A ; sicuTii/C) ; var Jrur-eiaJt : 0..a-i;

begin

kubełek := czulej (x, A); if [kubełe.<] — x then

A • kubeł ek] - u a urJ. e z e;

endi f;

end;

42. Podać wymagania, jakte powinna spełniać podstawowa funkcja mieszająca. Wymienić i ot7tóvtTĆ cząctc otOocwana podstawowe funkcje mieszające.

Liczba funkcji fr.iesaajecych, które można wykorzystać do wyznaczenia pozycji n elementów w tablicy' o m komórkach (dla u < ;n), jest równa mⁿ. (Liczbo doskonałych funkcji mieszających to zarazem liczba różnych rozmieszczeń tych elementów w tablicy, czyli m\ ! (m - n)\ [1]

•u

Ideełne funkcje mieszająca powinna być łatwo odliczaina i losowa. Każdy indeks [0..m - 1) powinien by jednakowo prawdopodobny >ako wartość funkqi - nie oznacza to. ze w każdym kubełku jest jeden element! Jeżeli zanalizujemy rozkład naturalny Z2 pomocą rozkładu Porssooa, to otrzymamy prawdopodobieństwa:

k	0	1	^2	^2	■i	^5	^5 i
PU»*0	3S.7S2%	36.792%	TS.396%	6.132%	1.533%	0.3307%	0.051%
pfavrriccH5do6tcr!srłYo. ze:	kUbete* worry	1 dementw fcuoe&u	2 dementy w	3 elementy w fcubfrftciJ	4 eiementy w fcuc-ttoj	5 ełememow w tajotfcu	6 eiementcb* w tajbeflnj

Uwaga: jeżeli analizujemy za pomocą rczkJadu dwumianowego — Ib. kubełków pustych - 32,7%!

Tśąh) = 0\1 + n / a), a - rozmiar tablicy, n - Ib.elementów

Metoda dzielenia HI;

Funkcja mieszająca powinna być znormalizowana, tj, zwracana przez nią liczba jest poprawnym adresem jednej z komórek tablicy. Najprościej osiągnąć to biorąc resztę mod TSize (TStza ■= rozmiar tablicy).

Oznacza to, że h(k) ~ k mcd TSize. Najlepiej, gdy TSize jest liczbą pierwszą. W przeciwnym wypadku można przyjąć, że    (jctiiód p) rrrcci TSize, -dla liczby pierwszej p > TSize. Jednakże podobno dzielniki ziożone są

•równie dobre jak pierwszo, jeśli nie mają czynników mniejszych¹ niż 20. Metoda dzielenia zapewnia zwykle mj\epszy wybór f. mieszającej tam, gdzie o kluczach wiadomo bardzo niewiele.

31

1

Lum, Yuen, Dood, Key-Zoaddress f/ansfo/rnabor? technioues: A fundamenta! performance study on large existino formatted fi/es