From 7ebf5f52638de639c7601c4660e5c9ab3cb45616 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 19 May 2009 17:01:53 +0200 Subject: [PATCH] Nulta verze hashovani. --- 12-hash/12-hash.tex | 84 +++++++++++++++++++++++++++++++++++++++++++++ 12-hash/Makefile | 3 ++ 2 files changed, 87 insertions(+) create mode 100644 12-hash/12-hash.tex create mode 100644 12-hash/Makefile diff --git a/12-hash/12-hash.tex b/12-hash/12-hash.tex new file mode 100644 index 0000000..b56df1d --- /dev/null +++ b/12-hash/12-hash.tex @@ -0,0 +1,84 @@ +\input lecnotes.tex + +\prednaska{10}{Hashování}{} + +V pøedchozích kapitolách jsme se zabývali tøídìním prvkù a zjistili jsme, ¾e v obecném pøípadì (kdy¾ smíme prvky pouze porovnávat a prohazovat) nelze tøídit rychleji ne¾ v èase $\Theta(n\log n)$. Zároveò jsme do¹li k tomu, ¾e pokud víme o prvcích nìco více (napø. jejich rozsah), tak jsme v nìkterých pøípadech schopni tøídit i s lineární èasovou slo¾itostí. + +V praxi nicménì vìt¹inou netøídíme samotná èísla, ale spí¹e nìjaké polo¾ky, napø. urèené uspoøádanou dvojicí (klíè, hodnota), kde klíèe jsou unikátní a existuje na nich lineární uspoøádání. Ukázali jsme si, jak takovouto mno¾inu udr¾ovat (aby se v ní dalo rychle vyhledávat, zaøazovat i mazat) ve vyhledávacích stromech. Dokázali jsme si, ¾e pokud budeme udr¾ovat strom dostateènì vyvá¾ený, tak budou jednotlivé operace (\, \ a \) trvat $\Theta(\log n)$. + +Ne¹lo by to ale rychleji? Odpovìï je jak kdy. Podívejme se na dal¹í mo¾nosti. Nejdøíve si ale pøipomeòme základní pojmy, které budeme pou¾ívat. + +Klíèe budou prvky universa, co¾ je mno¾ina $\{ 0, \dots, U-1 \}$, kterou budeme oznaèovat $[U]$. Tuto mno¾inu budeme chtít udr¾ovat v nìjaké ¹ikovné datové struktuøe, abychom v ní mohli rychle vyhladávat, zaøazovat i mazat. Dále $n$ bude znaèit (maximální) poèet prvkù, které si budeme v jednu chvíli pamatovat. + + +\h{1. Pole {\it indexované od $0$ do $U-1$}} + +Pokud bude velikost universa dostateènì malá, tak si mù¾eme polo¾ky pamatovat v poli o velikosti universa. Operace \, \ i \ pracují v~èase $\O(1)$, ale platíme za~to pamì»ovou slo¾itostí $\O(U)$. Kdy¾ uvá¾íme, ¾e si budeme pamatovat mnohem ménì prvkù, ne¾ je velikost universa, tak je to velké plýtvání. + +\h{2. Èíslicový strom} + +Zvolíme vhodný základ soustavy $b$, klíè zapí¹eme v soustavì o základu $b$ a zápis ulo¾íme do stromu. Tímto nám vznikne \uv{$b$-ární strom}, tedy strom, jeho¾ ka¾dý vrchol má a¾ $b$ synù. + +Vrcholy na první hladinì pak znaèí první èíslici, na druhé druhou, atd. Na poslední hladinì bude tedy $n$ listù. Hloubka tohoto stromu je $\lceil\log_b U\rceil$. + +Operace \ bude trvat $O(\log_b U)$ (najití jednoho klíèe odpovídá projití jedné cesty ve stromì od koøene do listu). Stejný èas budou trvat i operace \ a \. (Pøi vkládání zakládáme vrcholy, které odpovídají na¹emu klíèi a které je¹tì nejsou zalo¾ené. Pøi mazání sma¾eme list a následnì vrcholy, ze kterých nic nevede. Pro tuto operaci je výhodné si ve vrcholech udr¾ovat jejich stupnì.) Strom zabere prostor velikosti $O(nb\log_b U)$. + + +Èím bude základ $b$ men¹í, tím bude lep¹í pamì»ová a hor¹í èasová slo¾itost +a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù. + +\s{Pøíklad:} Pøedstavme si, ¾e klíèe budou IP-adresy, tedy 32-bitová èísla. Jak zvolit $b$, aby byla èasová i pamì»ová slo¾itost pøijatelná? Zkusme rozdìlit IP-adresu na 4 kusy, $b$ bude tedy 256. Strom bude mít hloubku 4. Èas bude v poødáku, ale po¾adavky na prostor jsou dost vysoké. Výhodnìj¹í bude rozdìlit IP-adresu na 8 èástí, $b$ bude tedy 16, hloubka stromu 8 a nároky na èas i pamì» jsou pøijatelné. + + +\h{4. Hashování } + +Mìjme $m$ pøihrádek a v ka¾dé z nich spojový seznam. Dále $h$ bude hashovací funkce, která libovolnému prvku z universa pøiøadí právì jednu pøihrádku. + +Kdyby $h$ fungovala \uv{rovnomìrnì } (ka¾dému prvku by pøiøadila jinou pøihrádku, tedy ka¾dý spojový seznam by mìl jen jeden prvek), tak bychom umìli vyhledávat, pøidávat i mazat prvky v konstantním èase. To je ov¹em samozøejmì pøíli¹ krásné na to, aby to byla pravda. + +Problém je, ¾e pokud bude $m$ výraznì men¹í ne¾ $U$ (co¾ chceme, jinak se jedná o normální (obrovské) pole a funkce je identita -- tento pøípad jsme ji¾ vyøe¹ili), tak urèitì budou existovat prvky, kterým funkce pøiøadí stejnou hodnotu. Takovému pøípadu se øíká {\it kolize}. Prvky se pak zaøadí do spojového seznamu. Kdyby byla naopak funkce hodnì ne¹ikovná a namapovala by nám v¹echny prvky do jedné pøihrádky, tak budeme v¾dy muset projít (v nejhor¹ím pøípadì celý) dlouhý spojový seznam. + +Jak se dá tedy kolizím bránit? Nejvýhodnìj¹í by bylo mít dobrou hashovací funkci, která by mapovala prvky pokud mo¾no rovnomìrnì. Ale nìkdy staèí i prùmìrnì dobrá funkce a dostateènì náhodné klíèe. + + +\s{Vsuvka:} Jaká je pravdìpodobnost, ¾e 2 z k lidí mají narozeniny ve stejný den? Staèí 23 lidí, aby nastala kolize s pravdìpodobností vìt¹í ne¾ jedna polovina. Aby nenastala, potøebovali bychom vìt¹í poèet pøihrádek: $p = cm^2$. + +\h{Praktické hashovací funkce} + +\s{První pøíklad} + +Tato hashovací funkce $h: [U] \rightarrow [m]$ je definovaná pøedpisem: $h(x) = x \mod m$. Pro dostateènì náhodné hodnoty bude fungovat, ale v mnoha pøípadech mù¾e být nevhodná. Napøíklad je zøejmé, ¾e pro sudé $m$ zachovává paritu. V pøípadì, ¾e sudých, resp. lichých klíèù bude mnohem více, vznikne mnoho zbyteèných kolizí. Pro takovouto hashovací funkci je nejlep¹í zvolit za $m$ nìjaké prvoèíslo. + +\s{Druhý pøíklad} + +Zvolme si iracionální $\alpha$ z intervalu $(0,1)$. Funkce bude definovaná následovnì: $$h(x) = \lfloor m (x \cdot \alpha \mod 1) \rfloor.$$ Tato funkce by mìla na $x$ záviset velmi málo, ale nebudeme si to dokazovat. + +\s{Implementace} Reálná èísla se samozøejmì implementují dosti nároènì (resp. to vùbec nejde), tak¾e v praxi se tento postup aproximuje celoèíselnì. Místo reálné $\alpha$ si zvolme $A = \lfloor \alpha \cdot 2^w \rfloor$, kde $2^w$ je ¹íøka slova ($w$ je napø. poèet bitù integeru). Potom místo výrazu $(x \cdot \alpha \mod 1)$, který je z intervalu $(0,1)$, budeme poèítat s výrazem $(x \cdot A \mod 2^w)$. Potom na¹e funkce vyjde následovnì: + +$$h(x) = \lfloor { m(x \cdot A \mod 2^w) \over 2^w } \rfloor$$ + + +Zbývá jen otázka, jak volit $\alpha$? Osvìèená hodnota je ${1 \over \tau }$, co¾ je pøibli¾nì 0,618. ($\tau$ je hodnota zlatého øezu.) Takto zvolené $\alpha$ dobøe rozbíjí aritmetické posloupnosti, ale i toto je pouze pøedstava a nebudeme si to dokazovat. + +\h{Hashování øetìzcù} + +Vzhledem k tomu, ¾e hashování nijak speciálnì nepotøebuje, aby byly prvky èísla, tak se mohou hashovat i øetìzce. Uka¾me si jeden pøíklad funkce pro hashování øetìzcù. +Prázdnému øetìzci pøiøaïme nulu: $h(\epsilon) = 0$. Øetìzci znakù $x_1, \dots, x_n$ pøiøaïme hodnotu: +$$h(x_1, \dots, x_n) = (h(x_1, \dots, x_{n-1}) \cdot + x_n) \mod m.$$ +$A$ je zde nìjaká konstanta. Aby se vyu¾ily v¹echny pøihrádky, tak je vhodné zvlit $A$ tak, aby $A^{{\bb E}[\]} >> m$. Tato funkce vyu¾ívá podobných vlastností jako lineární konkurenèní generátor náhodných èísel, který pomocí vhodných konstant $A$ a $B$ a ¹íøky slova $2^w$ vyrábí nové náhodné èíslo $x'$ z minulého èísla $x$ jako $$x' = (x \cdot A + B) \mod 2^w.$$ + + +\s{Vìta} Pokud jsou $h(x_1), \dots, h(x_n)$ rovnomìrnì náhodné, pak $$\forall i: {\bb E}[\] = {n \over m}.$$ + +\proof +Poèet prvkù v $i$-té pøihrádce si oznaème $N_i$. Definujme si indikátor $P_{ij}$, který je roven 1, pokud $x_j$ padlo do $i$-té pøihrádky, jinak je roven 0. +Vidíme, ¾e poèet prvkù v $i$-té pøihrádce je souèet $P_{ij}$ pøes v¹echny $j$. +$$N_i = \sum_{j} P_{i,j}.$$ +Teï ji¾ staèí upravit následující výrazy. Vyu¾ijeme mimo jiné vìtu o linearitì støední hodnoty. +$${\bb E}[P_{ij}] = {1 \over m} \cdot 1 + (1 - {1 \over m}) \cdot 0 = {1 \over m}.$$ +$${\bb E}[N_i] = {\bb E}[\sum_{j} P_{i,j}] = \sum_{j} {\bb E}[P_{i,j}] = {n \over m}.$$ +\qed + +\s{Dùsledek:} Pokud bude $n$ pøibli¾nì stejnì velké jako $m$, tak v ka¾dé pøihrádce bude prùmìrnì jeden prvek. + +\bye diff --git a/12-hash/Makefile b/12-hash/Makefile new file mode 100644 index 0000000..e0cfe0f --- /dev/null +++ b/12-hash/Makefile @@ -0,0 +1,3 @@ +P=12-hash + +include ../Makerules -- 2.39.2