Nulis palyginimų

$ algo count -in s100k.jsonl
n = 100000, key = Rating (0..100, so k = 101)

algorithm                       comparisons            moves         wall
counting                                  0           100000      3.017ms
sort.SliceStable                    1432948         (hidden)     93.609ms
insertion (lesson 7)             2503832821       2503732834   26.316217s

Palygink su spėjimu iš pirmo žingsnio.

Nulis. Ne „mažiau" — nė vieno. Šimtas tūkstančių įrašų surikiuoti neatlikus nė vieno palyginimo tarp dviejų įrašų.

Ir judesių lygiai 100 000 — po vieną kiekvienam įrašui. Kiekvienas elementas padedamas vieną kartą ir daugiau nejudinamas. Palygink su septintos pamokos 2 503 732 834.

Laikas: 3 ms prieš 93,6 ms standartinei bibliotekai (31 kartas) ir prieš 26,3 s įterpimo rikiavimui (8 700 kartų).

Kur dingo darbas

Niekur — jis pakeitė formą. Vietoj to, kad klaustum „ar A prieš B?" n log n kartų, vieną kartą pereini duomenis ir suskaičiuoji. Raktas pats nurodo vietą.

Tai įmanoma tik todėl, kad raktas yra mažas sveikasis skaičius su žinomomis ribomis. Būtent dėl to Rating turi rėžius nuo pirmos pamokos.

Kaina, kurios lentelėje nesimato

count masyvas turi k vietų — čia 101.

Tai atmintis, kurios palyginimų rikiavimai nereikalauja, ir ji priklauso ne nuo duomenų kiekio, o nuo reikšmių aibės dydžio. Šimtui įrašų — 101 vieta. Šimtui milijonų įrašų — vis dar 101.

Šia kryptimi mainai puikūs. Kita kryptimi jie žlunga, ir tai kitas žingsnis.