Namų darbas

Ką atiduoti

Veikiantį algo projektą su gen ir find komandomis, praeinantį go test ./..., ir vieno puslapio matavimų ataskaitą.

1. Pasirink temą ir pritaikyk Item

Muzika, filmai, žaidimai ar knygos. Pervadink Artist į tai, kas tinka tavo temai (Director, Studio, Author), ir pritaikyk generatorių.

Year ir Rating palik su rėžiais. Rėžius gali pakeisti (žaidimams 1970–2030 prasmingiau), bet jie turi likti.

2. Išmatuok augimo kreivę

Sugeneruok bibliotekas po 1 000, 10 000, 100 000 ir 1 000 000 įrašų su tuo pačiu -seed. Kiekvienai išmatuok blogiausio atvejo paiešką (ieškok pavadinimo, kurio nėra) ir surašyk į lentelę:

n	palyginimai	palyginimai ÷ n
1 000
10 000
100 000
1 000 000

Paskutinis stulpelis turi būti pastovus. Paaiškink vienu sakiniu, kodėl.

3. Kur laikrodis nustoja meluoti

Tą patį pamatuok laikrodžiu (time.Since). Rask mažiausią n, kuriam tavo kompiuteris parodo ne nulį.

Užsirašyk tą n ir savo procesorių. Palygink su bendraklausiu — skaičiai skirsis, o palyginimų skaičius bus toks pat. Tai ir yra visa šios pamokos mintis viename sakinyje.

4. Prognozė

Neatlikdamas matavimo, užsirašyk, kiek palyginimų kainuos blogiausio atvejo paieška, kai n = 5 000 000. Tada pamatuok.

Jei nepataikei — klydai ne skaičiuodamas, o kažko nesupratai apie O(n). Parašyk, ką.

5. Kam O(n) pakanka

Vienas pastraipos atsakymas: kada tiesinė paieška yra teisingas pasirinkimas, nepaisant to, kad kitos struktūros greitesnės? Duok konkretų pavyzdį su skaičiais.

(Užuomina: 6 pamokoje pamatysi, kad tiesinė paieška kartais laimi prieš dvejetainę — ir ne dėl to, kad kas nors suklydo.)