Kai medis tampa sąrašu

Pirmame žingsnyje užsirašei atsakymą: ką -sorted padarys medžiui.

Ta pati biblioteka. Tie patys 10 000 pavadinimų. Keičiasi tik įterpimo tvarka:

$ algo gen -n 10000 -seed 7 -o s10k.jsonl
$ algo gen -n 10000 -seed 7 -sorted -o s10k-sorted.jsonl
$ algo shape -shuffled s10k.jsonl -sorted s10k-sorted.jsonl

insert order        n   height     log2 n    cmps/lookup  lookup time
shuffled        10000       30       13.3           16.7      2.488ms
-sorted         10000    10000       13.3         5000.5    532.978ms
linear (L1)     10000        -          -          5000.5    117.418ms

both trees hold the same keys and both answer correctly.

Aukštis 10 000

Ne 10 000 mazgų — 10 000 lygių. Tiek pat, kiek įrašų.

Kiekvienas naujas pavadinimas didesnis už visus ankstesnius, tad visada eina dešinėn, ir visada tampa lapu giliausioje vietoje. Nė vienas mazgas neįgyja kairiojo vaiko. Struktūra, kurią pastatei, yra:

Babažėrė Tiči
   └── Babosakė
          └── Baboti
                 └── Babočudu
                        └── ... dar 9 996 lygių

Tai vienkryptis sąrašas. Trečia pamoka, tik su nepanaudota left rodykle kiekviename mazge.

5000.5

Įsižiūrėk į du apatinius skaičius stulpelyje cmps/lookup.

-sorted        5000.5
linear (L1)    5000.5

Ne „panašiai". Tiksliai tas pats skaičius — (n+1)/2, tas pats, kurį pirma pamoka pamatavo tiesinei paieškai. Ir taip turi būti: eiti sąrašu nuo pradžios, kol randi raktą, yra tiesinė paieška, kad ir kaip pavadintum tipą.

Dvylika pamokų darbo, dvi rodyklės mazge, apėjimas didėjimo tvarka — ir grįžai lygiai į tą vietą, iš kurios pradėjai.

Ir dar blogiau, nei atrodo

Palygink laiką, ne palyginimus:

-sorted        532.978ms
linear (L1)    117.418ms

Tas pats palyginimų skaičius, bet 4.5 karto ilgiau.

Tiesinė paieška eina gretimu masyvu: procesorius užbėga į priekį, ištraukia kelis įrašus vienu kartu ir beveik nė karto nelaukia atminties. Išsigimęs medis eina rodyklėmis po 88 baitų mazgą, išbarstytą po visą krūvą, ir kiekvienas žingsnis yra atskiras kreipimasis, kurio adreso iš anksto nežinai.

Tai ta pati pastaba, kurią dešimtoje pamokoje transit padarė apie atminties išdėstymą — tik dabar ji tavo skaičiuose.

Išsigimęs medis nėra „toks pat blogas kaip tiesinė paieška". Jis blogesnis už tai, ką turėjai pirmoje pamokoje.

Ir tai trečias kartas, kai skaitiklis nemato visko

Įsižiūrėk, kas ką tik nutiko. Abi eilutės — 5000.5 palyginimo. Skaitiklis sako, kad darbo atlikta lygiai tiek pat. Laikrodis sako, kad 4.5 karto daugiau.

pamoka	ko skaitiklis nematė
4	atminties — pranešė nulį ten, kur augo krūva
6	savęs paties: su skaitikliu cikle persikirtimas pasislinko nuo n ≈ 6 iki n ≈ 3
11	atminties išdėstymo — tie patys 5000.5, du visai skirtingi laikai

Tai ne skaitiklio yda. Jis matuoja palyginimus, ir čia jie tikrai vienodi. Bet palyginimas rodyklėmis išbarstytoje krūvoje ir palyginimas gretimame masyve kainuoja nevienodai, o to skirtumo prietaisas nemato iš principo.

Kai du variantai duoda tą patį skaičių, o tu vis tiek jauti skirtumą — tai ženklas, kad matuoji ne ten. Imk laikrodį.

Trečias kartas, ir vėl kita pusė

-sorted jau trečią kartą keičia atsakymą, ir kaskart kita kryptimi:

pamoka	ką -sorted padarė
7	įterpimo rikiavimui — geriausią atvejį, O(n)
8	quicksort'ui — blogiausią atvejį, O(n²)
11	BST — blogiausią atvejį, O(n) vietoj O(log n)

Ta pati vėliavėlė, tie patys duomenys, trys skirtingi rezultatai. Ne duomenys yra „geri" ar „blogi" — jie tinka arba netinka konkrečiam algoritmui, ir vienintelis būdas sužinoti, kuris, yra pamatuoti.

Jei pirmame žingsnyje atspėjai, kad surikiuoti duomenys medžiui bus lengvesni — tai visiškai natūralus spėjimas. Surikiuoti duomenys skamba kaip tvarka, o medis laiko tvarką. Bet medis tvarką gamina, ne suvartoja; jam reikia, kad raktai ateitų netvarkingai.

Ir vis dėlto jis teisingas

Paskutinė matavimo eilutė sako: both trees hold the same keys and both answer correctly.

Išsigimęs medis randa viską, ką reikia rasti. Keys() vis tiek grąžina surikiuotą sąrašą. Min, Max ir rėžiai veikia. Nė vienas testas dėl teisingumo nekrenta.

Todėl tai ir pavojinga. Nėra klaidos pranešimo, nėra sugedusio atsakymo, nėra ko rasti klaidų žurnale. Yra tik programa, kuri veikia teisingai ir šimtą kartų lėčiau, negu manai — tol, kol pamatuoji gylį.

Būtent tam Height() ir yra atskiras metodas.