Kvadratinė kreivė

Pirmoje pamokoje parašei algo gen -n 100000 ir sugeneravai šimtą tūkstančių įrašų per pusantros sekundės. Iki šiol tas skaičius nieko nekainavo.

Dabar kainuos.

$ algo gen -n 1000 -seed 42 -o s1k.jsonl
$ algo sort -in s1k.jsonl
n = 1000, order = shuffled

algorithm         comparisons            swaps         wall
bubble                 498680           243513      3.702ms
selection              499500              997      1.087ms
insertion              244506           243513        514µs

Tūkstantis įrašų — pusė milijono palyginimų. Nepastebimai.

$ algo sort -in s10k.jsonl
n = 10000, order = shuffled

algorithm         comparisons            swaps         wall
bubble               49993289         24883304     454.17ms
selection            49995000             9992    170.587ms
insertion            24893296         24883304     92.225ms

Dešimt kartų daugiau duomenų — šimtą kartų daugiau darbo. Beveik pusė sekundės.

$ algo sort -in s100k.jsonl
n = 100000, order = shuffled

algorithm         comparisons            swaps         wall
bubble             4999895385       2503732834 1m25.751674s
selection          4999950000            99986   41.607048s
insertion          2503832821       2503732834   26.916946s

Pusantros minutės. Penki milijardai palyginimų vienam rikiavimui.

Kreivė

n	burbuliukų palyginimai	santykis
1 000	498 680	—
10 000	49 993 289	×100,3
100 000	4 999 895 385	×100,0

Dešimteriopas n — šimteriopas darbas. Tai ir yra O(n²), ir palyginimų skaičius atkartoja tai tiksliai.

Laikrodis ir skaitiklis pagaliau sutampa — beveik

Šeštoje pamokoje jie nesutarė: skaitiklis sakė vieną dalyką, laikrodis kitą. Čia darbo tiek daug, kad laikrodis nebeturi ką slėpti.

Bet ne visai:

n	laikas	santykis
1 000	3,7 ms	—
10 000	454 ms	×123
100 000	85,8 s	×189

Palyginimų skaičius augo lygiai ×100. Laikas — ×123 ir ×189.

Laikas auga greičiau nei kvadratu. Prie 100 000 įrašų masyvas užima apie 7 MB ir nebetelpa į procesoriaus atmintinę, tad kiekvienas palyginimas ima brangti. Trečioje pamokoje matei tą patį reiškinį iš kitos pusės.

Skaitiklis vis dar tikslesnis. Jis tiesiog nebėra vienintelis, kuris mato problemą.

Kodėl išrinkimo rikiavimas — vidurinis

Palyginimų jis padaro daugiau už burbuliukų (4 999 950 000 prieš 4 999 895 385), o trunka dvigubai trumpiau.

Atsakymas — sukeitimų stulpelyje: 99 986 prieš 2 503 732 834. Dvidešimt penki tūkstančiai kartų mažiau judinamų duomenų.

Palyginimas yra pigus. Sukeitimas — trys priskyrimai ir struktūros kopijavimas. Kai jų 2,5 milijardo, jie ir nulemia laiką.

Dvi skirtingos operacijos, dvi skirtingos kainos. Todėl Sort funkcijos ima du skaitiklius, o ne vieną.