Namų darbas
Ką pateikti
algo su index ir ordered, praeinantis go test ./..., plius ataskaita.
1. Trys paieškos, viena biblioteka
n = 1 000 / 10 000 / 100 000, ieškant kiekvieno pavadinimo:
| n | tiesinė (1 pam.) | dvejetainė (6 pam.) | maišos indeksas |
|---|
Palyginimai vienam ieškojimui, ne laikas.
Kuris stulpelis auga su n ir kuris ne? Dvejetainė reikalauja surikiuotų
duomenų — pridėk rikiavimo kainą prie jos stulpelio ir pasakyk, nuo kelinto
ieškojimo ji atsiperka.
2. Riba
Penktame žingsnyje riba buvo 1.0 ir ji duoda ~1.3 palyginimo vienam ieškojimui.
Pakeisk ją į 0.5, 2.0 ir 4.0. Kiekvienai pamatuok palyginimus vienam ieškojimui,
kibirų skaičių ir sunaudotą atmintį (len(buckets) × rodyklės dydis, plius
įrašai).
Kuri riba tau atrodo teisinga ir kokį klausimą reikia atsakyti pirma, kad šis sprendimas apskritai turėtų prasmę?
3. Sandoris, savais žodžiais
Trys sakiniai:
- ką maišos lentelė nusiperka;
- kuo už tai sumoka;
- kokį klausimą apie savo biblioteką turėtum atsakyti prieš ją pasirinkdamas.
Tada įvardyk du dalykus savo algo programoje, kuriuos jau dabar darytum per
maišos indeksą, ir vieną, kurio nedarytum — ir kodėl ne.
4. Baitai ir runos
Septintas žingsnis parodė, kaip transit sulaužo lietuvišką paiešką.
Tavo hashKey irgi dirba su baitais. Ar tai klaida? Atsakyk taip arba ne ir
pagrįsk vienu sakiniu.
Tada parašyk Get, kuris randa įrašą nepaisant registro ("bamila" randa
"Bamila"). Kur turi būti atliktas normalizavimas — prieš maišos funkciją ar jos
viduje? Ir kas nutinka, jei normalizuoji ieškant, bet ne dedant?
5. Kada medis, kada lentelė
Aštuntas žingsnis surašė klausimus, į kuriuos indeksas neatsako.
Sugalvok tris realias funkcijas, kurias norėtum turėti savo bibliotekos programoje, ir kiekvienai pasakyk, ar jai užtenka maišos indekso.
Bent viena iš trijų turi būti tokia, kuriai neužtenka. Aprašyk, ką tokiu atveju tektų daryti su dabartine struktūra ir kiek tai kainuotų.
(Vienuolikta pamoka pradės nuo šito.)
Kurso darbo pasirinkimas
Norintiems — prefiksų indeksas: struktūra, atsakanti „kurie pavadinimai prasideda šiomis raidėmis". Septintas žingsnis parodė ir kainą, ir vieną būdą jį sugadinti.
Tai nėra šios pamokos reikalavimas.