From: Doni Pracner Date: Tue, 19 Nov 2019 18:38:29 +0000 (+0100) Subject: Hash, doterivanje tekstualnog materijala X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain Hash, doterivanje tekstualnog materijala --- diff --git a/Hash/primeri/hash.pdf b/Hash/primeri/hash.pdf index 5b8cd5a..f698c1a 100644 Binary files a/Hash/primeri/hash.pdf and b/Hash/primeri/hash.pdf differ diff --git a/Hash/primeri/hash.txt b/Hash/primeri/hash.txt index dbad695..6834106 100644 --- a/Hash/primeri/hash.txt +++ b/Hash/primeri/hash.txt @@ -1,6 +1,6 @@ % Hash funkcije - pripremni materijal -% SPA2, DMI-PMF-UNS, www.dmi.rs -% 2016 +% SPA2, DMI-PMF-UNS, www.dmi.uns.ac.rs +% 2019 Heš kod i jednakost u programskom jeziku Java ============================================= @@ -42,6 +42,10 @@ Klasa `String` ima redefinisana oba ova metoda. Heš kod koji se dobija za ovu klasu je veoma kvalitetan i uglavnom se vredi osloniti na njega za polja ovog tipa. +Nažalost, nizovi nemaju nijednu od ove dve funkcije definisane kako +treba, pa kada se radi sa njima, mora se uložiti napor da se +pojedinačni elementi u nizu porede, odnosno hešuju. + Ocene kvaliteta funkcije ======================== @@ -71,28 +75,9 @@ Osim ovog podatka se ispisuje i dužina najdužeg lanca u skupu, koja daje predstavu o tome koliko je pretraživanje u najgorem slučaju. Ovaj broj takođe treba da je što manji. - -Nešto komplikovanija mera je $\chi^2$ \emph{(hi-kvadrat)} test. -\begin{equation} - \chi ^2 = \sum_{i=1}^{n} \frac{(K_i - E)^2}{E} -\end{equation} - -gde je $K_i$ - broj elemenata u podskupu $i$, a $E$ - očekivan broj -elemenata u podskupu, odnosno idealna vrednost koja je jednaka -količniku ukupnog broja elemenata i broja skupova. - -Iako deluje relativno komplikovano, ovo nam zapravo daje dobru ocenu -koliko su (ne)ravnomerno raspoređeni elementi. U idealno slučaju bi -sve $K_i$ vrednosti bile jednake sa $E$ i imali bi da je vrednost -testa nula. U opštem slučaju se naravno javljaju odstupanja od -proseka, a pošto kvadriramo udaljenosti, $\chi^2$ brzo raste ukoliko -ima većih anomalija. - -Program daje vrednosti za ovaj test i u odnosu na idealan -slučaj kada je broj lanaca/podskupova jednak sa brojem -elemenata, kao i za realan broj podskupova (tj različitih -vrednosti elemenata). - +Program ispisuje i vrednosti $chi^2$ testa, o čemu postoji još +komentara na kraju ovog dokumenta, ali se inače neće dublje +razmatrati, nego se ostavlja zainteresovanima da pogledaju. Primeri ======= @@ -145,8 +130,6 @@ Number of elements: 4885 Different values: 100 ( 2.05 %) Avg. search chain len.: 48.85 +- 2.99 Longest search chain: 56 -Chi square (no. of el): 229,855.00 -Chi square (diff el.): 18.28 ``` Budući da ima samo 100 soba, može biti i samo 100 različitih heš vrednosti, te @@ -176,8 +159,6 @@ Number of elements: 4885 Different values: 61 ( 1.25 %) Avg. search chain len.: 80.08 +- 3.96 Longest search chain: 89 -Chi square (no. of el): 382,448.00 -Chi square (diff el.): 11.95 ``` Očigledno je potrebno kombinovati ove dve vrednosti, odnosno @@ -202,8 +183,6 @@ Number of elements: 4885 Different values: 4885 (100.00 %) Avg. search chain len.: 1.00 +- 0.00 Longest search chain: 1 -Chi square (no. of el): 0.00 -Chi square (diff el.): 0.00 ``` @@ -235,7 +214,9 @@ pitanju baš ista klasa kao naša (moguće da je neki naslednik koji tehnički ne mora biti isti), te da tu uzme u obzir i da je moguće da nam je prosleđen `null` što nikako ne može biti isto kao i naš objekat. Dalje se može ubrzati postupak proverom da li su u pitanju -pokazivači na isto mesto pošto nema potrebe za proverama onda. +pokazivači na isto mesto pošto nema potrebe za proverama onda. Takođe +se preporučuje da se polja porede jedno po jedno, pošto je kod +pregledniji i lakše se menja, nego kad se kombinuju upiti kao gore. Potpuna verzija bi izgledala ovako: @@ -317,6 +298,11 @@ puta, u podacima će biti nizovi različitih dužina. U skladu sa tim je i format za unos takav da je prvi broj u redu zapravo broj gađanja, koji određuje veličinu niza. +Na početku je već bilo napomenuto da nizovi nemaju `hashCode` i +`equals` implementirane na načine koji bi odgovarao ovoj situaciji, +tako da se mora implentirati pojedinačno poređenje elemenata, naročito +kod ovakvih situacija sa dodatnim značenjima elemenata. + Funkcija jednakosti bi izgledala ovako: ```Java @@ -335,23 +321,31 @@ Funkcija jednakosti bi izgledala ovako: } Gadjanje o2 = (Gadjanje) o; - // proveravamo da li je polje null pre dalje provere + + // proveravamo da li su polja null pre dalje provere + if (rezultati == null && o2.rezultati != null) { + return false; + } + if (rezultati != null && o2.rezultati == null) { + return false; + } + + // ako u obe instance nije null, poredimo delove if (rezultati != null && o2.rezultati != null) { - if (o2.rezultati.length == rezultati.length) { - for (int i = 0; i < rezultati.length; i++) { - if (o2.rezultati[i] != rezultati[i]){ - // cim je nesto razlicito nisu isti - return false; - } + // proverimo duzinu. + if (o2.rezultati.length != rezultati.length) { + return false; + } + // ako je ista duzina proveravamo elemente + for (int i = 0; i < rezultati.length; i++) { + if (o2.rezultati[i] != rezultati[i]) { + // cim je nesto razlicito nisu isti + return false; } - // ako se sve vrednosti slazu isti su - return true; } - return false; - } else { - // vracamo da li su oba null, tj da li su jednaki - return (rezultati == null && o2.rezultati == null); } + // ako nije bilo razlika, vracamo da je sve ok + return true; } ``` @@ -366,8 +360,6 @@ Number of elements: 9049 Different values: 139 ( 1.54 %) Avg. search chain len.: 65.10 +- 37.98 Longest search chain: 118 -Chi square (no. of el): 771,638.00 -Chi square (diff el.): 3,079.85 ``` U ovakvoj strukturi, pozicija u nizu bi trebalo da bude značajna za @@ -398,8 +390,6 @@ Number of elements: 9049 Different values: 1411 (15.59 %) Avg. search chain len.: 6.41 +- 3.89 Longest search chain: 20 -Chi square (no. of el): 62,736.00 -Chi square (diff el.): 3,335.34 ``` Problem je zapravo što brojevi nisu dovoljno različiti. Pošto znamo da su @@ -419,8 +409,6 @@ Number of elements: 9049 Different values: 8911 (98.47 %) Avg. search chain len.: 1.02 +- 0.14 Longest search chain: 4 -Chi square (no. of el): 176.00 -Chi square (diff el.): 171.21 ``` Možemo uočiti i sledeće - ako na početku nekog niza stoje 0, one će biti ignorisane @@ -446,8 +434,6 @@ Number of elements: 9049 Different values: 9049 (100.00 %) Avg. search chain len.: 1.00 +- 0.00 Longest search chain: 1 -Chi square (no. of el): 0.00 -Chi square (diff el.): 0.00 ``` @@ -536,8 +522,6 @@ Number of elements: 4424 Different values: 18 ( 0.41 %) Avg. search chain len.: 245.78 +- 253.74 Longest search chain: 674 -Chi square (no. of el): 2,237,400.00 -Chi square (diff el.): 4,715.27 ``` Efikasnost se u ovakvoj strukturi dobija davanjem "težine" @@ -555,7 +539,73 @@ sa vrednostima polja. Jedan način da se ovo uradi u konkretnom slučaju je da se pri računanju heša vrednosti u matrici sabiraju sa 2, pa time imamo 1,2,3 umesto -1,0,1, što dovodi do veće različitosti. -Kombinovanjem ovih ideja se mogu napraviti `hashCode` metodi koji će -rezultovati sa hi kvadrat vrednostima manjim od broja podskupova -("kolona"), što se ostavlja za samostalnu vežbu. +Jedno od mogućih rešenja koje daje dobre rezultate je zapravo jako +slično onome viđeno kod niza - ako stalno množimo sa brojem koji je +veći od mogućih vrednosti jednog elementa, automatski su sva mesta +pomnožena različitim koeficijentom. Ovo možemo kombinovati sa +pomeranjem pojedinačnih elemenata na pozitivne vrednosti, mada se +dobri rezultati mogu postići i bez toga. + +```Java + public int hashCode() { + int rez = 0; + int koef = 3; + for (int i = 0; i < DIM; i++) { + for (int j = 0; j < DIM; j++) { + rez = koef * (rez + (tabla[i][j] + 2)); + } + } + return rez; + } +``` + +``` +Number of elements: 4424 +Different values: 4424 (100.00 %) +Avg. search chain len.: 1.00 +- 0.00 +Longest search chain: 1 +``` + + +Dodatne napomene +================ + +Hi kvadrat ocena kvaliteta heš funkcije +----------------------------------- + +Nešto komplikovanija mera je $\chi^2$ \emph{(hi-kvadrat)} test. +\begin{equation} + \chi ^2 = \sum_{i=1}^{n} \frac{(K_i - E)^2}{E} +\end{equation} + +gde je $K_i$ - broj elemenata u podskupu $i$, a $E$ - očekivan broj +elemenata u podskupu, odnosno idealna vrednost koja je jednaka +količniku ukupnog broja elemenata i broja skupova. + +Iako deluje relativno komplikovano, ovo nam zapravo daje dobru ocenu +koliko su (ne)ravnomerno raspoređeni elementi. U idealno slučaju bi +sve $K_i$ vrednosti bile jednake sa $E$ i imali bi da je vrednost +testa nula. U opštem slučaju se naravno javljaju odstupanja od +proseka, a pošto kvadriramo udaljenosti, $\chi^2$ brzo raste ukoliko +ima većih anomalija. + +Program daje vrednosti za ovaj test i u odnosu na idealan +slučaj kada je broj lanaca/podskupova jednak sa brojem +elemenata, kao i za realan broj podskupova (tj različitih +vrednosti elemenata). + +Ispitivanje različitosti dobijenih podataka +------------------------------------------- + +Kada se dobiju nepoznati podaci koje treba obraditi i za njih odrediti +heš funkcije, nekad vredi prvo probati saznati više o različitostima +dobijenih podataka. + +Kod primera za korišćenje kancelarija, na primer, definisali smo da je +`hashCode` zavistan samo od jednog od polja, i samim tim kad smo +pokrenuli program smo saznali tačno koliko ima različitih imena i +koliko ima različitih brojeva. +Isti pristup se može iskoristiti i u drugim situacijama, što nam može +dati bolje ideje kako da postavimo različite koeficijente i na koja +polja možda ima smisla staviti više "težine" u samom hešu.