Ta pati komanda, dvi naujos eilutės
Vienuolikta pamoka baigėsi šia lentele:
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
Aukštis 10 000. Palyginimų 5000.5 — tiksliai tiek, kiek pirmos pamokos tiesinė paieška.
Ta pati komanda. Tie patys du failai. Tik dabar apačioje yra dar dvi eilutės:
$ algo balance -shuffled s10k.jsonl -sorted s10k-sorted.jsonl
structure insert n height log2 n cmps/lookup lookup time
BST (11) shuffled 10000 30 13.3 16.7 1.667ms
BST (11) -sorted 10000 10000 13.3 5000.5 354.556ms
AVL (12) shuffled 10000 16 13.3 12.5 1ms
AVL (12) -sorted 10000 14 13.3 12.4 998µs
Perskaityk paskutinę eilutę dar kartą
Aukštis 14. log2(10000) yra 13.3.
Įvestis, kuri vienuoliktoje pamokoje pavertė medį 10 000 lygių sąrašu, dabar duoda medį, vieno lygio nutolusį nuo tobulo.
Ir kai kas netikėto
Palygink dvi AVL eilutes tarpusavyje:
AVL shuffled height 16 12.5 palyginimo
AVL -sorted height 14 12.4 palyginimo
Surikiuota įvestis AVL medžiui yra GERESNĖ nei maišyta.
Tai ne atsitiktinumas. Maišyta tvarka duoda kreivą medį, kurį rotacijos ištaiso iki „pakankamai gerai"; griežtai didėjanti tvarka po kiekvieno įterpimo verčia medį persitvarkyti į beveik tobulai pilną.
Vienuoliktos pamokos blogiausias atvejis yra dvyliktos geriausias.
Ir dar viena eilutė, kurios nesitikėjai
BST shuffled height 30 16.7 palyginimo
AVL shuffled height 16 12.5 palyginimo
Maišytoje įvestyje BST veikė puikiai — vienuoliktoje pamokoje jo dėl to ir nesigailėjome. Ir vis dėlto AVL ten laimi 25 %.
Taigi balansavimas nėra tik draudimas nuo blogo atvejo. Jis pagerina ir vidutinį. Bet už tai mokama, ir šeštame žingsnyje pamatuosi, kur ta kaina slepiasi — vietoje, kurios tavo skaitiklis nemato.
Spėk prieš skaitydamas toliau
Aukštis 14 prie 10 000 įrašų. Kiek bus prie milijono, jei įvestis vis dar griežtai didėjanti?
Užsirašyk skaičių. Penktame žingsnyje jis yra lentelėje.