Pratybos
Penkios užduotys.
1. Prasta maišos funkcija
Šeštame žingsnyje buvo pasakyta, kad kolizijas sukelia per mažai kibirų arba prasta maišos funkcija. Pamatuok antrąjį atvejį.
Parašyk dvi alternatyvas ir suleisk 10 000 įrašų į 16 384 kibirus, kaip
hashKey:
func lenHash(s string) uint64 { return uint64(len(s)) }
func sumHash(s string) uint64 { /* baitų suma */ }
Išspausdink, kiek kibirų panaudota ir kokia ilgiausia grandinėlė. Paaiškink, kodėl
lenHash naudoja tiek kibirų, kiek naudoja — skaičius nėra atsitiktinis.
Ir paaiškink, kodėl sumHash yra daug geresnis už lenHash, bet vis tiek daug
prastesnis už FNV-1a. Ką dar sugriauna sumavimas, ko FNV-1a nesugriauna?
(Užuomina: "ab" ir "ba".)
2. Delete
Pridėk func (h *HashIndex) Delete(title string, c *metrics.Counter) bool.
Įdėk 1 000 įrašų, ištrink 500, patikrink, kad Len() yra 500, kad ištrintų
neberandi, o likusius randi.
Tada atsakyk: ar Delete turėtų mažinti kibirų skaičių, kai apkrova nukrenta?
Kas nutiktų, jei programa nuolat prideda ir trina ties riba, o tavo lentelė
plečiasi ir traukiasi po kiekvieno veiksmo?
3. Atviras adresavimas prieš grandinėles
Antrame žingsnyje minėtas kitas kolizijų sprendimas: nesaugoti grandinėlės, o
ieškoti kito laisvo kibiro (i+1, i+2, …). Realizuok jį atskirai ir palygink
prie tos pačios apkrovos:
buckets load atviras adresavimas grandinėlės
16384 0.610 1.783 zondų 1.310 palyginimų
13000 0.769 2.927 1.381
11000 0.909 5.258 1.446
10500 0.952 12.249 1.486
10100 0.990 25.181 1.497
Grandinėlės nuo 0.610 iki 0.990 pablogėja 1.14 karto. Atviras adresavimas — 14 kartų.
Paaiškink kodėl. Kai kibirų beveik nebelieka laisvų, ko ieško zondavimo ciklas ir kiek ilgai?
4. Kiek kainuoja plėtimasis
Suskaičiuok, kiek įrašų iš viso buvo perskaičiuota per visus grow iškvietimus,
kol lentelė užaugo iki 10 000, ir padalink iš 10 000.
Palygink su antrosios pamokos rezultatu: append vidutiniškai nukopijuoja apie
4.5 elemento vienam elementui. Kodėl čia mažiau, jei plėtimosi taisyklė ta
pati — dvigubinimas?
5. Go map
Perrašyk algo index su map[string]Item vietoj savo HashIndex ir palygink
laikus per testing.B (ne per time.Since — 10 000 paieškų per greita, kad
laikrodis ką nors parodytų).
Tada perskaityk, ką grąžina Len(), ir paaiškink, kodėl negali parašyti
for k := range m ir tikėtis stabilios tvarkos — Go čia elgiasi griežčiau nei
tavo Keys(). Ką kalba kūrėjai apsisprendė padaryti ir kodėl būtent tai atitinka
aštuntą šios pamokos žingsnį?