Namų darbas

Ką pateikti

algo su balance, rotate ir reload, praeinantis go test ./..., plius ataskaita. Tai paskutinis paieškos lanko namų darbas, tad jis apžvelgia visas tris pamokas.

1. Trys indeksai, viena lentelė

Užpildyk ją savo matavimais prie n = 10 000:

	maiša (10)	BST (11)	AVL (12)
paieška, maišyta įvestis
paieška, -sorted įvestis
pastatymas, maišyta
atmintis visai struktūrai
surikiuotas sąrašas

Palyginimai ten, kur jie prasmingi; testing.B ten, kur ne. Nurodyk, kuriuos langelius pildai laiku ir kodėl.

2. Kada AVL neverta

Šeštame žingsnyje surašytos trys sąlygos, kurioms esant balansavimas atsiperka.

Aprašyk konkrečią programą, kuriai netinka nė viena, ir pasakyk, kurią struktūrą jai rinktumeisi. Tada aprašyk antrą, kuriai tinka visos trys.

Nė viena iš dviejų negali būti bibliotekos katalogas.

3. Riba prieš matavimą

TestHeightStaysBoundedOnSortedInput tikrina 1.4405 · log2(n+2) − 0.3277.

Pamatuok tikrą aukštį prie n = 10³, 10⁴, 10⁵, 10⁶ ir palygink su riba. Koks santykis tarp jų?

Tada atsakyk: kodėl testas tikrina ribą, o ne pamatuotą reikšmę, jei pamatuota visada mažesnė? Kada testas su pamatuota reikšme suklystų?

4. Skaitiklio riba, ketvirtą kartą

pamoka	ko skaitiklis nematė
4	atminties — pranešė nulį ten, kur augo krūva
6	savęs paties — persikirtimas pasislinko nuo n ≈ 6 iki n ≈ 3
11	atminties išdėstymo — tie patys 5000.5 palyginimo, 4.5 karto skirtingas laikas
12	rotacijų — 23 % mažiau palyginimų, 1.65 karto lėčiau

Surašyk visus darbus, kuriuos algo atlieka ir kurių metrics.Counter nematuoja. Bent keturi.

Tada pasiūlyk, kaip prietaisą būtų galima papildyti, kad rotacijos taptų matomos — ir paaiškink, kodėl to nedarėme, nors būtų buvę nesunku.

5. Lankas, savais žodžiais

Trys pastraipos, po vieną kiekvienai pamokai. Kiekvienoje:

• kokį klausimą struktūra atsako geriausiai;
• ko ji negali arba negarantuoja;
• ir vienas realus atvejis, kuriam ją rinktumeisi.

Tada ketvirta pastraipa: klausimas, kurį užduotum pirmiausia, jei rytoj tektų rinktis indeksą naujai programai. Ne struktūrą — klausimą.

---

Kursinio darbo pasirinkimai

Norintiems, ir nė vienas nėra šios pamokos reikalavimas:

• Delete su balansavimu — septintas žingsnis paaiškina, ką tai apima ir kiek kainuoja. Testas jau turi viską, ko reikia patikrinti.
• Prefiksų indeksas — dešimtos pamokos pasirinkimas, vis dar atviras.
• Raudonai-juodas medis — tos pačios garantijos, laisvesnis invariantas, mažiau rotacijų įterpimui. Palygink su savo AVL tais pačiais matavimais.