Apkrovos koeficientas yra atsakymas

10 000 įrašų, indeksas su plėtimusi:

$ algo index -in s10k.jsonl
n = 10000, resize = true

  buckets          16384
  stored           10000
  resizes          10
  load factor      0.610
  empty buckets    8925
  mean chain       1.341
  LONGEST chain    5
  build time       1.5ms

  10000 lookups: 13095 comparisons (1.310 per lookup), 0s
  same by linear scan: 50005000 comparisons (5000.5 per lookup), 85ms

1.310 palyginimo vienam ieškojimui. Tiesinė paieška tiems patiems 10 000 klausimų sunaudojo 5000.5. Skirtumas — 3818 kartų, o laikas 85 ms prieš tiek, kad laikrodis jo neužfiksavo.

Blogiausias atvejis — ilgiausia grandinėlė — yra 5. Ne 5000. Būtent tai reiškia „vidutiniškai O(1)": ne kad kiekvienas ieškojimas kainuoja lygiai vieną žingsnį, o kad grandinėlės lieka trumpos ir nepriklauso nuo n.

Kur dingo O(1), kai neplečiama

$ algo index -in s10k.jsonl -nogrow -buckets 16
n = 10000, resize = false

  buckets          16
  stored           10000
  resizes          0
  load factor      625.000
  empty buckets    0
  mean chain       625.000
  LONGEST chain    680
  build time       20.527ms

  10000 lookups: 3134392 comparisons (313.439 per lookup), 17.117ms

Tie patys duomenys, ta pati maišos funkcija, tas pats kodas — 239 kartus daugiau palyginimų. Nes 10 000 įrašų suverstų į 16 kibirų yra tiesiog 16 tiesinių paieškų, sudėtų greta.

Plėtimasis nėra optimizacija. Be jo maišos lentelė nėra maišos lentelė.

Tavo spėjimas

Pirmame žingsnyje užsirašei skaičių: kiek palyginimų su 10 000 įrašų ir 128 kibirais?

$ for b in 128 512 2048 8192 16384; do algo index -in s10k.jsonl -nogrow -buckets $b; done

   buckets      load      mean   longest    cmps/lookup
       128    78.125    78.125       105         40.161
       512    19.531    19.531        34         10.830
      2048     4.883     4.929        15          3.465
      8192     1.221     1.740         7          1.620
     16384     0.610     1.341         5          1.310

40.161 — maždaug pusė apkrovos koeficiento (78.125 / 2 ≈ 39), plius truputis.

Ir taip visoje lentelėje: 19.531 → 10.8, 4.883 → 3.5, 1.221 → 1.6. Sėkmingas ieškojimas vidutiniškai sustoja grandinėlės viduryje, todėl kaina yra apkrova / 2 + 1. Tai ne empirinė taisyklė — tai tiesiog vidurkis, kai raktas yra kažkurioje grandinėlės vietoje ir visos vietos vienodai tikėtinos.

Todėl riba yra 1.0, o ne 10 ar 100: plėtimasis laiko dalmenį mažesnį už du.

Ir atkreipk dėmesį į stulpelį longest. Prie 128 kibirų ilgiausia grandinėlė — 105, nors vidurkis 78. Vidurkis nėra pažadas kiekvienam paieškos veiksmui; kai kuriems raktams visada bus blogiau.