Vienodas raktas nėra kolizija
Pirmoje pamokoje gen gavo vėliavėlę -dup-rate: dalis pavadinimų
pakartojami. Atrodo akivaizdu, ką ji padarys maišos lentelei — vienodi
pavadinimai, daugiau kolizijų, ilgesnės grandinėlės.
Spėk prieš skaitydamas toliau
10 000 įrašų, -dup-rate 0.9. Ar palyginimų vienam ieškojimui bus daugiau, ar
mažiau nei prie -dup-rate 0?
Matavimas
$ for r in 0 0.3 0.5 0.9; do algo gen -n 10000 -seed 7 -dup-rate $r -o dup.jsonl; algo index -in dup.jsonl; done
dup-rate stored buckets resizes load longest cmps/lookup
0 10000 16384 10 0.610 5 1.310
0.3 6994 8192 9 0.854 7 1.474
0.5 4999 8192 9 0.610 5 1.308
0.9 972 1024 6 0.949 5 1.722
Grandinėlės nepailgėjo. Ilgiausia svyruoja tarp 5 ir 7 — tiksliai taip pat, kaip be pakartojimų. Palyginimų skaičius juda tarp 1.31 ir 1.72, ir juda kartu su apkrovos koeficientu, ne su pakartojimų dalimi (0.9 dalmuo yra 0.949 — aukščiausias lentelėje, todėl ir 1.722 yra aukščiausias).
Pasikeitė stored: 10 000 → 972.
Kodėl
Antrame žingsnyje šis skirtumas jau buvo pasakytas, o dabar jis pamatuotas:
- kolizija — skirtingi raktai tame pačiame kibire. Grandinėlę ilgina;
- vienodas raktas — tas pats pavadinimas antrą kartą.
Putjį pakeičia, ir įrašas lieka vienas.
-dup-rate 0.9 gamina vienodus raktus. Indeksas juos sulydo, todėl jame lieka
972 skirtingi pavadinimai vietoj 10 000. Lentelė ne prisipildo — ji
susitraukia: 1024 kibirai vietoj 16384, šeši plėtimaisi vietoj dešimties.
Kolizijos priklauso nuo apkrovos koeficiento, o ne nuo to, kiek tavo duomenyse yra pasikartojančių pavadinimų. Vienodi raktai indekso neapkrauna — jie jį mažina.
Kolizijų iš tikrųjų pridės du kiti dalykai: per mažai kibirų (tai pamatavai penktame žingsnyje) ir prasta maišos funkcija. FNV-1a tokia nėra; pirmoje pratyboje pamatysi, kokia atrodo prasta.
Ir dar viena vieta, kur -dup-rate dabar reikšminga
Aštuntoje pamokoje pakartojimai buvo įdomūs dėl stabilumo: vienodi raktai, kurių tarpusavio tvarką rikiavimas gali sugriauti. Čia jie visai kitokie — vienodas raktas maišos lentelėje negali turėti dviejų vietų, nes visa struktūros esmė yra „vienas raktas, viena vieta".
Ta pati vėliavėlė, du visiškai skirtingi klausimai. Todėl ji ir buvo padaryta pirmoje pamokoje, o ne devintoje.