Namų darbas

Ką atiduoti

algo su sweep ir std, praeinantį go test ./..., ir savo lūžio taško ataskaitą.

1. Tavo lūžio taškas

Paleisk algo sweep visomis trimis konfigūracijomis ir užpildyk:

konfigūracija	tavo lūžio taškas
-ints gretimai
-ints -scattered
eilutės, gretimai

Palygink su pamokoje pateiktais (≈6, ≈6, ≈3) ir su transit (≈50 ir >127).

Jei tavo skaičiai kitokie — tai rezultatas, ne klaida. Paaiškink, kuris iš trijų mechanizmų labiausiai paaiškina skirtumą tavo atveju.

2. Procesorius

Nurodyk savo procesoriaus modelį ir L1 atmintinės dydį.

Suskaičiuok, kiek int32 telpa į tavo L1. Susiek šį skaičių su tuo n, ties kuriuo tavo lentelėje dvejetainė pradeda ryškiai laimėti.

3. Kur riba nustoja galioti

Prie kokio n tiesinė paieška tampa nepriimtina tavo bibliotekai, jei paieška turi tilpti į 16 ms (vienas kadras 60 Hz ekrane)?

Skaičiuok su savo lin ns/op reikšmėmis. Nurodyk n.

4. Prielaidos kaina

Dvejetainei paieškai reikia surikiuotų duomenų. Rikiavimo dar nerašei — bet sort.Slice jau turi.

Pamatuok: kiek kainuoja vienas rikiavimas 100 000 įrašų, ir kiek dvejetainių paieškų reikia atlikti, kad tas rikiavimas atsipirktų prieš tiesinę paiešką?

Šis skaičius yra 7 pamokos motyvas.

5. Sprendimas

Vienas pastraipos atsakymas: tavo bibliotekos paieškai pagal pavadinimą — tiesinė, ranka rašyta dvejetainė ar sort.Search?

Nurodyk savo n, savo lūžio tašką ir kaip dažnai biblioteka keičiasi. Jei keičiasi po kiekvienos paieškos, atsakymas gali būti „tiesinė" — ir tai bus teisinga.