sort.Search — ir klausimas 13 pamokai

Parašei dvejetainę paiešką ranka. Standartinėje bibliotekoje ji jau yra:

sort.Search(len(items), func(i int) bool { return items[i].Title >= target })

Viena eilutė vietoj dešimties, ir visi kraštiniai atvejai jau apgalvoti.

Bet ji ima funkciją. Kiekvienas palyginimas — iškvietimas per func reikšmę. Skamba brangiau.

$ algo std -n 127
                        comparisons        ns/op
hand-rolled LowerBound            7           18
sort.Search                       7           15

$ algo std -n 2254
hand-rolled LowerBound           12           38
sort.Search                      12           37

$ algo std -n 100000
hand-rolled LowerBound           16           53
sort.Search                      16           55

Palyginimų skaičius identiškas — tas pats algoritmas. O laikas: sort.Search greitesnė trimis atvejais iš keturių, ir niekur reikšmingai nepralaimi.

Funkcija nekainavo nieko.

Priežastis — kompiliatorius. Uždaris (closure) čia žinomas kompiliavimo metu, tad Go jį įterpia (inline) tiesiai į ciklą. Po optimizacijos jokio iškvietimo nelieka: lieka toks pat ciklas, kokį parašei ranka, tik parašytas ne tavo.

transit tą patį pamatavo dar aiškiau: 7,9 ns ranka rašytai prieš 4,9 ns sort.Search. Mūsų skirtumas mažesnis, bet kryptis ta pati.

Tai kam rašyti ranka?

Kad suprastum invariantą. Ketvirtas žingsnis parodė dešimt vietų, kur ranka rašyta paieška lūžta — tų vietų nesuprasi, kol jų nepataisysi pats.

Bet darbiniame kode naudok sort.Search. Ji greitesnė, trumpesnė ir jau išbandyta.

Klausimas, kurio dar neatsakysim

Trečioje pamokoje pastatei savo dvipusį sąrašą ir palyginai su container/list. Skaičiai sutapo iki vieno šuolio.

Čia standartinė biblioteka laimėjo.

Ar tai reiškia, kad standartinė biblioteka visada bent tokia pat gera?

Skamba pagrįstai. Bet 13 pamokoje pastatysi krūvą ranka ir palyginsi su container/heap — ir atsakymas bus priešingas, aiškiai ir pamatuotai.

Neskubėk daryti išvados. Taisyklė, suderinanti abu atvejus, egzistuoja, bet ji kalba ne apie standartinę biblioteką, o apie tai, ką kompiliatorius sugeba pamatyti. Šioje pamokoje jis matė viską. Kitą kartą — ne.