From 531276c1a45482cb12d1ec6b1752da4bd1cee296 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 10 Sep 2007 14:34:09 +0200 Subject: [PATCH] Prvni rozumna verze zapisu o hashovani. --- 13-hash/{13-hash.latex => 13-hash.tex} | 139 +++++++++++-------------- 13-hash/Makefile | 3 + 2 files changed, 63 insertions(+), 79 deletions(-) rename 13-hash/{13-hash.latex => 13-hash.tex} (55%) create mode 100644 13-hash/Makefile diff --git a/13-hash/13-hash.latex b/13-hash/13-hash.tex similarity index 55% rename from 13-hash/13-hash.latex rename to 13-hash/13-hash.tex index 1165c0a..0609629 100644 --- a/13-hash/13-hash.latex +++ b/13-hash/13-hash.tex @@ -1,120 +1,97 @@ -\documentclass[12pt]{article} -\usepackage[czech]{babel} -\usepackage[latin2]{inputenc} -\begin{document} +\input lecnotes.tex +\prednaska{13}{Hashování}{(zapsal Martin Francù a Bohdan Maslowski)} -{\large \bf Tøídìní} +\h{Tøídìní} -Víme-li nìco o hodnotách, mù¾eme najít lep¹í tøídící algoritumus, napø. v lineárním èase. +V kapitole 5 jsme si ukázali, ¾e tøídìní pomocí porovnávání se dá zvládnout nejlépe v èase $O(n)$. Víme-li v¹ak nìco o hodnotách, mù¾eme najít lep¹í tøídící algoritumus, který pracuje napø. v lineárním èase. -Na mno¾inì máme tyto operace: +\>Na mno¾inì máme tyto operace: -\medskip - -Insert(x) +\itemize\ibull +\:Insert(x) +\:Delete(x) +\:Find(x) +\endlist -Delete(x) - -Find(x) +\>Víme-li, ¾e je mno¾ina uspoøádaná, mù¾eme pou¾ít vyhledávací strom, tedy $\Theta(\log n)$ na operaci. \medskip -Víme-li, ¾e je uspoøádaná - vyhledávací strom: $\Theta(\log n)$ na operaci +\>Znaèíme -\medskip +\itemize\ibull +\:$n$ ... Poèet prvkù +\:$U$ ... Velikost universa (mno¾ina ze které prvky vybíráme) +\:$[U] = {0, 1, 2,\ldots,U-1}$ +\endlist -$n$ ... poèet prvkù - -$U$ ... velikost universa (mno¾ina ze které prvky vybíráme) - -$[U] = {0, 1, 2,\ldots,U-1}$ \bigskip -{\bf 1. Pole indexované $0..U-1$} +\h{1. Pole indexované $0$ a¾ $U-1$} -\medskip - -Insert/Delete/Find v èase $O(1)$ - -\medskip - -pamì» $O(U)$ - -\bigskip +Insert, Delete i Find pracují v èase $O(1)$, pamì»ová slo¾itost je $O(U)$. -{\bf 2. Èíslicový strom (radix tree) } -Zvolíme $b$ základ soustavy +\h{2. Èíslicový strom (radix tree) } -prvky $U$ zapisujeme jako $k$-tice èíslic +Zvolíme základ soustavy $b$, prvky universa zapisujeme jako $k$-tice èíslic. Èili: -èili $x\in U \mapsto [b]^{k}, k=[\log_b U]$ +$$x\in U \mapsto [b]^{k}, k=[\log_b U]$$ -Tedy vznikne strom (hloubka $k$), na $k$-té úrovni podle $k$-té èíslice +Tedy vznikne strom (s hloubkou $k$), na $k$-té úrovni podle $k$-té èíslice \medskip + Find: $O(\log_b U)$ Insert, Delete: $O(b \log_b U)$ -pamì»: $O(nb\log_b U)$ +Pamì»ová nároènost: $O(nb\log_b U)$ \medskip -$b$ malá - lep¹í pamì», hor¹í èasová slo¾itost a obrácenì - -$\Rightarrow$ vy¾aduje peèlivé nastavení parametrù - +Èím bude základ $b$ men¹í, tím lep¹í pamì»ová a hor¹í èasová slo¾itost, a obrácenì. Èíslicový strom tedy vy¾aduje peèlivé nastavení parametrù. \bigskip -{\bf 3. Pro øetìzce } - -Za $b$ zvolíme abecedu +\h{3. Písmenkový strom } -$|x|$ ... délka øetìzce +Pou¾ívá se pro øezìzce, za základ soustavy $b$ zvolíme abecedu. \medskip -Find, Insert, Delete: $O(|x|)$ +$\vert x\vert $...délka øetìzce -pamì»: $O(\sum_{i} |x|)$ +Find, Insert, Delete: $O(\vert x\vert )$ + +Pamì»: $O(\sum_{i} \vert x\vert )$ \bigskip -{\bf 4. Hashování } +\h{4. Hashování } -$h: [U] \rightarrow [m]$ hashovací funkce +$h$ ... hashovací funkce $[U] \rightarrow [m]$ -Perfektní hashovací funkce - do ka¾dé z $n$ pøihrádek jediný prvek z $[U]$ +$m$ ... poèet pøihrádek, v ka¾dé pøihrádce spojový seznam. -Pøíklad: 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: $m = cn^2$) +\medskip -$m$ ... poèet pøihrádek +Perfektní hashovací funkce pøiøadí do ka¾dé z $m$ pøihrádek jediný prvek z $[U]$. -$h$ ... hashovací funkce $[U] \rightarrow [m]$ +\s{Pøíklad:} 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$ -v ka¾dé pøihrádce spoják -\medskip -Find: pou¾ít hashovací funkci k urèení pøihrádky a projít spojákem -Insert -\medskip -{\bf Hashování se separovými øetezci} +\h{Hashování se separovými øetezci} \medskip -Insert, Delete, Find pracují v èase $O(|x|)$ - -pamì»: $O(m+n)$ +Insert, Delete i Find pracují v èase $O(\vert x\vert )$, pamì»ová slo¾itost je $O(m+n)$ \medskip vlo¾ili jsme $x_1 \ldots x_n \in [U]$ @@ -133,20 +110,24 @@ $N_{i,p} := 1$ pokud $h(x_i)= p$ $N_p = \sum_{i=1}^n N_{i,p}$ -$E N_{i,p} = Pr[h(x_i)=p] = \frac{1}{m} $ +$E N_{i,p} = Pr[h(x_i)=p] = {1 \over m} $ -$E N_p = n \frac{1}{m} = \frac{n}{m} $ +$E N_p = n {1\over m} = {n \over m} $ \medskip -Za pøedpokladu, ¾e hash pøidìluje náhodnou pøihrádku, je v ka¾dé pøihrádce $\frac{n}{m}$ prvkù. +Za pøedpokladu, ¾e hash pøidìluje náhodnou pøihrádku, je v ka¾dé pøihrádce ${n \over m}$ prvkù. \bigskip + +\h{Druhá pùlka} + + \noindent {\sc Vìta:} {\it Pokud jsme do hashovací tabulky vlo¾ili hodnoty $x_1,\dots,x_m$ tak, ¾e $h_{x_i}$ jsou v¹echny stejnì pravdìpodobné, pak následující Insert, Delete, Find pracují v èase -${\cal O}\,(\frac{n}{m}+1)$. (Za pøedpokladu, ¾e výpoèet $h$ trvá +${\cal O}\,({n \over m}+1)$. (Za pøedpokladu, ¾e výpoèet $h$ trvá ${\cal O}\,(1)$.)} \medskip @@ -172,8 +153,8 @@ odstran na poèátku: $n=0;m=4$ -v ka¾dém okam¾iku budeme udr¾ovat pomìr $\frac{n}{m}\in \langle -\frac{1}{2},1)$ +v ka¾dém okam¾iku budeme udr¾ovat pomìr ${n\over m}\in \langle +{1\over 2},1)$ tedy: (pokud nastane) $$n=4 \Rightarrow m:=8 $$ @@ -182,28 +163,28 @@ P v tabulce ulo¾ené znovu "zhashovat". Nafukování trvá ${\cal O}\, (n)$, ale mezi dvìma nafouknutími je -minimálnì $ \frac {n}{2} $ Insertù. +minimálnì $ {n\over 2} $ Insertù. Pokud tedy ka¾dý Insert pøispìje konstantou, tak to máme zadarmo! \bigskip PROBLÉM: Jak udìlat funkci Delete? Jednoduché zmen¹ování tabulky pøi pomìru -$\frac{n}{m}=\frac{1}{2}$ není dostaèující, nebo» by se mohlo stát, ¾e bychom nafukovali a +${n\over m}={1\over 2}$ není dostaèující, nebo» by se mohlo stát, ¾e bychom nafukovali a zfukovali hned po sobì. \bigskip {\bf Verze s Insert a Delete} -Udr¾ujeme $\frac{n}{m}\in \langle \frac{1}{4},1)$ +Udr¾ujeme ${n\over m}\in \langle {1\over 4},1)$ pøi zfukování tabulku pùlíme, pøi nafukování zdvojnásobujeme \medskip -Po pøehashování je pomìr $\frac{n}{m}=\frac{1}{2} \Rightarrow$mezi dvìma pøehashováními -nastane minimálnì $\frac{m}{2}$ Insertù èi $\frac{m}{4}$ Deletù, tedy alespoò $\frac{m}{4}$ +Po pøehashování je pomìr ${n\over m}={1\over 2} \Rightarrow$mezi dvìma pøehashováními +nastane minimálnì ${m\over 2}$ Insertù èi ${m\over 4}$ Deletù, tedy alespoò ${m\over 4}$ operací. Zároveò zabereme v¾dy lineárnì prostoru vzhledem k $n$. @@ -234,12 +215,11 @@ $x \in{\sc N}$ pak $\alpha x $ $ mod (1)$ se chov \medskip b) $h(x)=\lfloor m(\alpha x $ $mod(1))\rfloor$ - $$ \frac {A}{W} \sim \alpha \Rightarrow h(x)= \lfloor m(Ax \ mod(W)) \rfloor $$ + $$ {A\over W} \sim \alpha \Rightarrow h(x)= \lfloor m(Ax \ mod(W)) \rfloor $$ \medskip - Jako velmi výhodné se jeví pou¾ívat $\alpha = \frac {\sqrt{5} -1} - {2} $ - pøevrácená hodnota zlatého øezu. + Jako velmi výhodné se jeví pou¾ívat $\alpha = {{\sqrt{5} -1}\over{2}} $ - pøevrácená hodnota zlatého øezu. \medskip @@ -267,8 +247,9 @@ Pokud plat $\overrightarrow{a}$ je prvkem ortogonálního doplòku k $(x-y)$, ten má $ dim (W^\bot) = (k-1)$ -$$ p= \frac{W^\bot}{Z_p^k}= \frac{p^{k-1}}{p^k} = \frac {1}{p}=\frac{1}{m}$$ +$$ p= {{W^\bot}\over{Z_p^k}}= {{p^{k-1}}\over{p^k}} = {1\over p}={1\over m}$$ kde $m$ je poèet pøihrádek. Co¾ je dostaèující. -\end{document} +\bye + diff --git a/13-hash/Makefile b/13-hash/Makefile new file mode 100644 index 0000000..fc04eaf --- /dev/null +++ b/13-hash/Makefile @@ -0,0 +1,3 @@ +P=13-hash + +include ../Makerules -- 2.39.2