Teorija

Kaina, kurios skaitiklis nemato

Garantija nėra nemokama. Kad pamatytum kainą, matuok ten, kur BST jau veikė puikiai — maišytoje įvestyje.

$ algo rotate -in s10k.jsonl
n = 10000, inserted in the order given

                 build cmps   build time    rotations     height
  BST (11)           157025       3.33ms            -         30
  AVL (12)           120660      4.551ms         6922         16

  rotations per insert: 0.692
  worst |balance| anywhere in the AVL tree: 1

  lookups: BST 16.703 cmps, AVL 12.540 cmps

Skaitiklis sako, kad AVL pigesnis

BST  157 025 palyginimų
AVL  120 660 palyginimų

23 % mažiau. Ir tai tiesa: medis žemesnis, tad kiekvienas įterpimas nueina trumpesnį kelią, o kelio ilgis ir yra palyginimų skaičius.

Pagal vienintelį prietaisą, kurį naudojame nuo pirmos pamokos, balansavimas kainuoja mažiau nei nieko.

Laikrodis sako kitaip

Stulpelis build time toje išvestyje yra vienas matavimas ir jis triukšme — prie 10 000 įrašų abu variantai svyruoja 2–3 ms ribose ir keičiasi vietomis tarp paleidimų. Šeštos pamokos taisyklė galioja: kai skirtumas mažas, vienas matavimas nieko nereiškia.

Todėl matuojam kaip pridera:

$ go test -run XXX -bench 'Build|Lookup' -benchtime=20x -count=5

BenchmarkBuildBST-32       20    1859315 ns/op
BenchmarkBuildBST-32       20    1870065 ns/op
BenchmarkBuildBST-32       20    1800945 ns/op
BenchmarkBuildBST-32       20    1922465 ns/op
BenchmarkBuildBST-32       20    1940315 ns/op
BenchmarkBuildAVL-32       20    3202495 ns/op
BenchmarkBuildAVL-32       20    3352500 ns/op
BenchmarkBuildAVL-32       20    2894720 ns/op
BenchmarkBuildAVL-32       20    3288470 ns/op
BenchmarkBuildAVL-32       20    2817325 ns/op

Penki paleidimai kiekvienam, ir rėžiai nepersidengia: BST 1.80–1.94 ms, AVL 2.82–3.35 ms.

AVL pastatymas apie 1.65 karto lėtesnis — atlikdamas 23 % mažiau palyginimų.

Kur dingo skirtumas

Į stulpelį, kurio skaitiklis nemato:

rotations   6922

Rotacija yra keturios rodyklių priskyrimo operacijos ir du aukščių perskaičiavimai. Ji nėra raktų palyginimas, tad c.Hit() per ją neiškviečiamas — ir teisingai neiškviečiamas: skaitiklis matuoja palyginimus, ne visą darbą.

Ketvirta, šešta ir vienuolikta pamokos jau parodė, kur skaitikliui baigiasi matymas. Šis kartas ketvirtas ir aštriausias, nes du rodmenys rodo į PRIEŠINGAS puses:

Prietaisas parodė, kad AVL pigesnis. Laikrodis parodė, kad brangesnis. Abu teisūs — jie matuoja skirtingus dalykus.

Skaitiklis ir toliau yra teisingas įrankis algoritmo sudėtingumui — jis neprikausto tavęs prie mašinos ir nesikeičia tarp paleidimų. Bet konstanta jam nematoma, o balansavimo kaina visa yra konstantoje.

Antra pusė: paieška

BenchmarkLookupBST-32      20    1514950 ns/op   (1.45–1.56 ms)
BenchmarkLookupAVL-32      20    1246885 ns/op   (1.25–1.33 ms)

Paieška AVL medyje apie 1.16 karto greitesnė, nes medis žemesnis (16 prieš 30).

Sandoris, tikslus

	BST (11)	AVL (12)
įterpimas, maišyta įvestis	1.80–1.94 ms	2.82–3.35 ms (1.65× lėčiau)
paieška, maišyta įvestis	1.45–1.56 ms	1.25–1.33 ms (1.16× greičiau)
aukštis, maišyta įvestis	30	16
aukštis, `-sorted`	10 000	14
atmintis mazgui	88 B	96 B (`h` laukas)

Moki už kiekvieną įterpimą, kad išvengtum atvejo, kuris gali niekada neateiti.

Ir tai apsimoka, jei bent viena iš trijų tiesa:

negali garantuoti įterpimo tvarkos — o dažniausiai negali, nes ji ateina iš duomenų bazės, failo ar vartotojo;
skaitai dažniau nei rašai — tada 1.16 karto greitesnė paieška vienose svarstyklėse su 1.65 karto lėtesniu įterpimu, ir svarstyklės krypsta pagal santykį;
blogiausias atvejis yra nepriimtinas, o ne tik nemalonus.

Jei nė viena netiesa — jei duomenis pats sugeneruoji maišytus ir vieną kartą, o paskui tik skaitai — vienuoliktos pamokos medžio užtenka. Arba, kaip parodė ta pati pamoka, užtenka surikiuoto masyvo.