Pratybos
Penkios užduotys.
1. ExactFind(items []Item, title string, c *metrics.Counter) (int, bool)
Tiksli paieška, pastatyta ant LowerBound.
Kiek papildomų palyginimų jai reikia? Kodėl negalima daryti atvirkščiai —
iš tikslios paieškos gauti LowerBound?
2. UpperBound(items []Item, title string, c *metrics.Counter) int
Grąžina indeksą už paskutinio sutampančio įrašo.
Turėdamas LowerBound ir UpperBound, suskaičiuok, kiek kartų pavadinimas
pasitaiko, per O(log n). Patikrink su algo gen -dup-rate 0.3.
3. Sulaužyk paiešką keturiais būdais
Padaryk keturias LowerBound kopijas, kiekvienoje po vieną klaidą:
hi := len(items) - 1lo = midvietojlo = mid + 1hi = mid - 1vietojhi = midfor lo <= hivietojfor lo < hi
Kiekvienai paleisk 3 žingsnio testą ir užrašyk, kuris atvejis ją pagavo. Kuri klaida sukelia amžinąjį ciklą?
4. Rask savo lūžio tašką tiksliai
algo sweep naudoja pastovius dydžius. Parašyk Crossover() int, kuris pats
susiaurina intervalą ir grąžina mažiausią n, kuriam dvejetainė greitesnė.
Paleisk penkis kartus. Ar gauni tą patį skaičių? Jei ne — ką tai sako apie matavimo tikslumą?
5. Nuspėjamumas
5 žingsnyje sakoma, kad tiesinė paieška greitesnė iš dalies dėl to, kad procesorius nuspėja šuolius.
Sugalvok matavimą, kuris tai parodo: ta pati tiesinė paieška, tie patys palyginimai, bet nenuspėjama tvarka.
(Užuomina: eik per masyvą atsitiktine indeksų tvarka, o ne iš eilės. Palyginimų skaičius nepasikeis.)