Lankas užsidaro

Vienuoliktos pamokos pirmoji pratybų užduotis parodė spąstus: išsaugai medį per Keys(), įkeldamas įterpi raktą po rakto — ir gauni sąrašą, nes Keys() grąžina surikiuotą sąrašą.

Klausimas savaime aiškus: ar dabar tai saugu?

$ algo reload -in s10k.jsonl
original:              BST height    30, AVL height    16
reloaded from Keys():  BST height 10000, AVL height    14

AVL rotations during that reload: 9986 (0.999 per insert)

Taip. Ir ne šiaip saugu — po įkėlimo medis geresnis nei buvo. 16 → 14.

Priežastis jau žinoma iš pirmo žingsnio: surikiuota įvestis AVL medžiui yra geriausias atvejis. Naivus išsaugojimas paduoda būtent ją.

Ta pati eilutė BST'ui duoda 10 000.

Vienuoliktoje pamokoje išsaugojimo formatas buvo teisingumo klausimas. Dvyliktoje jis vėl tapo tik formatu.

Štai kas iš tikrųjų perkama garantija. Ne greitis — atkritusi ištisa klaidų klasė, apie kurią nebereikia galvoti. Nebereikia klausti, kokia tvarka ateina raktai, nes atsakymas nustojo turėti reikšmės.

Trys struktūros, vienas klausimas

Nuo dešimtos pamokos statei tris indeksus tai pačiai bibliotekai. Visi trys pamatuoti tais pačiais 10 000 įrašų:

	maiša (10)	BST (11)	AVL (12)
tikslaus rakto paieška	1.310 palyginimo	16.703	12.540
ta pati, -sorted įvestis	1.310	5000.5	12.363
surikiuotas sąrašas	neįmanoma be pilno rikiavimo	apėjimas	apėjimas
rėžis, Min, Max, kaimynai	nėra tokios sąvokos	yra	yra
pastatymas (maišyta)	greičiausias	1.80–1.94 ms	2.82–3.35 ms
ką žada	vidutiniškai O(1)	vidutiniškai O(log n)	blogiausiu atveju O(log n)

Ir tai nėra kopėčios

Lengva perskaityti šią lentelę kaip „12 geriausia". Neteisinga.

Dešimta pamoka laimi. Jei tavo programai reikia tik „ar yra toks raktas" — sesijų saugykla, žodžių dažniai, „ar užimtas vartotojo vardas" — maišos lentelė yra 9.6 karto pigesnė už AVL ir nė vienos kitos operacijos tau nereikia. Statyti ten medį būtų klaida, o ne atsargumas.

Kiekviena struktūra kažką pardavė:

pamoka	ką nusipirko	kuo sumokėjo
10	O(1) tikslaus rakto paieškai	visa tvarka — jokių rėžių, kaimynų, rikiavimo
11	tvarką ir visas jos operacijas	garantiją — įterpimo tvarka lemia viską
12	garantiją atgal	konstantą — 1.65 karto lėtesnis įterpimas

Trys eilutės, trys mainai. Nė vienos struktūros nėra „geresnės" — jos atsako į skirtingus klausimus, o dešimtoje pamokoje užduotas klausimas nuo to nepasikeitė.

Ko iš tikrųjų išmokai

Ne trijų duomenų struktūrų. Kaip pasirenkama.

Kiekvienoje iš trijų pamokų kelias buvo tas pats:

1. užduok konkretų klausimą apie duomenis;
2. pamatuok, ką kiekviena struktūra už jį ima — palyginimais, ne nuojauta;
3. įvardyk, ko ji negali, o ne tik ką daro lėtai;
4. paklausk, ar tavo blogiausias atvejis yra tik nemalonus, ar nepriimtinas.

Ketvirtasis punktas ir yra šios pamokos indėlis. Vienuoliktos pamokos medis maišytoje įvestyje veikė puikiai — kol viena diena kažkas neimportavo duomenų ORDER BY title.

Skirtumas tarp „paprastai" ir „visada" kainuoja 1.65 karto. Ar verta — jau ne algoritmų, o tavo programos klausimas.