Namų darbas

Ką pateikti

algo su top ir pq, praeinantis go test ./..., plius ataskaita.

1. Abstrakcijos taisyklė, patikrinta ketvirtu atveju

Septintas žingsnis davė taisyklę ir tris matavimus po ja. Rask ketvirtą atvejį savo algo programoje ir patikrink taisyklę juo.

Kandidatai: sort.Slice (uždarinys) prieš sort.Sort (sąsaja) tiems patiems duomenims; strings.Builder prieš +=; tavo LinearFind prieš slices.IndexFunc.

Pirma nuspėk, naudodamas tris septinto žingsnio klausimus. Tada pamatuok. Spėjimą pateik net jei jis buvo neteisingas — ypač tada.

2. Ko skaitiklis nemato, sudėta į vieną vietą

Riba jau rasta penkiose pamokose: 4, 6, 11, 12, 13.

Kiekvienai po eilutę: kas buvo matuojama, ką pasakė skaitiklis ir ką pasakė laikrodis.

Tada suformuluok taisyklę, kada imti skaitiklį, o kada laikrodį. Vienas sakinys, tinkantis visiems penkiems atvejams.

3. Eilė, kurios reikės Dijkstrai

Keturioliktoje ir penkioliktoje pamokose tavo krūvos klausinės „kuris nelankytas mazgas artimiausias?". Tavo MinHeap raktas yra Rating.

Kas turi pasikeisti? Užrašyk sąsają, kurios Dijkstrai prireiks — įskaitant vieną operaciją, kurios nerealizavai ir kurios prireiks. (Užuomina: kas nutinka, kai randi trumpesnį kelią iki mazgo, jau esančio eilėje?)

Nerealizuok. Aprašyk, kiek tai kainuotų, ir nurodyk vieną būdą apskritai išvengti tokios operacijos.

4. Dešimtukas nuo pradžios iki galo

Pridėk algo chart: dešimt geriausiai įvertintų knygų kiekvienam dešimtmečiui.

Tai dešimt atskirų top-k uždavinių, po vieną dešimtmečiui. Du sprendimai:

• vienas praėjimas per duomenis, dešimt krūvų greta;
• dešimt praėjimų, po vieną krūvą.

Nuspėk, kuris laimės ir kiek. Pamatuok abu. Paaiškink rezultatą per tai, ką kiekvienas sprendimas liečia atmintyje — vienuolikta pamoka tą patį efektą pamatavo iš kitos pusės.

5. Kada rašyti pačiam

Iki šiol ranka parašei sąrašą, paiešką, keturis rikiavimus, maišos indeksą, du medžius ir krūvą. Lygiai dviem atvejais standartinė biblioteka buvo lėtesnė.

Viena pastraipa: ko iš tikrųjų imtumeisi darbe ir kas turėtų būti tiesa, kad rašytum savo? Įvardyk matavimą, kurį atliktum prieš apsispręsdamas.

Atsakymas nėra „visada standartinė biblioteka" ir nėra „visada ranka". Jei tavo pastraipa skamba kaip vienas iš šitų, septinto žingsnio taisyklės nepanaudojai.