Ką už tvarką sumoki

Ta pati biblioteka, tie patys 10 000 klausimų, trys struktūros:

$ algo tree -in s10k.jsonl
n = 10000 distinct titles

  tree height      30   (log2 n = 13.3)
  in order?        true

                      cmps/lookup     build cmps  lookup time
  tree                     16.703         157025      3.108ms
  hash (lesson 10)          1.310           7198      1.001ms
  linear (lesson 1)         5000.5              0        125ms

  build time: tree 4ms, hash 2.501ms

  keys in sorted order: tree yes (walk), hash no (must sort all 10000)

Medis pralaimi maišos lentelei 12.8 karto vieninteliam klausimui „ar yra toks pavadinimas". Pastatymas kainuoja 157 025 palyginimų prieš 7 198 — dvidešimt du kartus daugiau.

Tai reikia pasakyti tiesiai, o ne apeiti. Jei tavo programai reikia tik tikslaus rakto paieškos, maišos lentelė yra teisingas pasirinkimas ir medis būtų klaida.

Kur dingsta tie 16.7

Aukštis 30, o log2(10000) yra 13.3. Medis daugiau nei dvigubai gilesnis už idealų.

Taip ir turi būti. Nė vienas mazgas nesirūpina pusiausvyra — medis įgauna tokią formą, kokią jam duoda įterpimo tvarka, o atsitiktinė tvarka duoda kreivoką, bet ne katastrofišką. Pamatuota:

$ for n in 100 1000 10000 100000; do algo gen -n $n -seed 7; algo tree; done

        n   height   log2 n    cmps/lookup
      100       13      6.6          7.710
     1000       22     10.0         12.273
    10000       30     13.3         16.703
   100000       41     16.6         21.367

Šimteriopai padidinus n nuo 1 000 iki 100 000, kaina paaugo nuo 12.3 iki 21.4 — mažiau nei dvigubai. Tai ir yra logaritmas: augimas yra, bet jis nyksta.

Padalyk stulpelius vienas iš kito ir pamatysi pastovią daugybą:

n	aukštis ÷ log2 n	palyginimai ÷ log2 n
100	1.97	1.17
1 000	2.20	1.23
10 000	2.26	1.26
100 000	2.47	1.29

Ne 1.0, bet ir ne augantis dydis. Medis yra maždaug dvigubai gilesnis už idealų ir tokiu lieka — būtent tai reiškia „O(log n) su blogesne konstanta".

Maišos lentelės stulpelis toje pačioje lentelėje būtų buvęs 1.31 visur, be jokio log n.

Atmintis: pamatuok, o ne spėk

Medžio mazgas turi dvi rodykles ten, kur grandinėlės įrašas turėjo vieną:

Item         56 baitų
entry (10)   80 baitų  (raktas + įrašas + 1 rodyklė)
node  (11)   88 baitų  (raktas + įrašas + 2 rodyklės)

Aštuoni baitai mazgui — atrodo, medis brangesnis. Bet suskaičiuok visą struktūrą prie n = 10 000:

maišos: 10 000 × 80 B  +  16 384 kibirų × 8 B  =  931 072 B
medis:  10 000 × 88 B                          =  880 000 B

Bendrai medis sunaudoja mažiau. Nes maišos lentelė moka ne tik už įrašus — ji moka ir už kibirų masyvą, o tas masyvas ir yra tai, kas jai perka trumpas grandinėles. Prie apkrovos 0.61 tuščių kibirų yra 8 925, ir jie visi užima vietą.

Vienam mazgui medis brangesnis; visai struktūrai — ne. Skirtumas priklauso nuo apkrovos koeficiento, kurį pasirinkai dešimtoje pamokoje.

Sandoris, dviem eilutėmis

Maišos lentelė: 1.3 palyginimo vienam klausimui, ir vienas klausimas. Medis: 16.7 palyginimo, ir šeši klausimai.

Antrasis stulpelis nėra „taip pat, tik lėčiau". Jis yra kitas produktas.