Klausimas, likęs nuo trečios ir šeštos

Ši pamoka atsako į klausimą, kurį trečioji uždavė, o šeštoji atsisakė atsakyti.

Trečioje pamokoje pastatei savo dvikryptį sąrašą ir palyginai su container/list:

                             walk/shift pointer writes
slice (shift)                        44              0
Playlist (ours)                      50              4
container/list                       50       (hidden)

Lygiosios. Iki vieno šuolio.

Šeštoje pamokoje palyginai savo dvejetainę paiešką su sort.Search:

                        comparisons        ns/op
hand-rolled LowerBound            7           18
sort.Search                       7           15

Standartinė biblioteka laimėjo. Ir tos pamokos pabaigoje buvo parašyta:

Ar tai reiškia, kad standartinė biblioteka visada bent jau ne blogesnė? Skamba pagrįstai. Bet 13 pamokoje pastatysi krūvą ranka ir palyginsi su container/heap — ir atsakymas bus priešingas, aiškiai ir pamatuojamai.

Čia ta pamoka.

Spėk prieš skaitydamas toliau

Pastatysi dvejetainę krūvą — priešdėlį, kurio prireiks keturioliktai ir penkioliktai pamokoms — ir palyginsi su container/heap. Tas pats algoritmas, tas pats palyginimų skaičius.

Kiek kartų skirsis laikas, ir kuria puse?

Užsirašyk. Šeštame žingsnyje pamatuosi, o septintame pamatysi, kodėl trys atsakymai skirtingi ir kodėl visi trys teisingi.

Ir kodėl būtent krūva

Ne dėl standartinės bibliotekos ginčo — tai priedas. Krūva reikalinga dėl dviejų dalykų.

Pirma: geriausi dešimt. Nori parodyti dešimt geriausiai įvertintų knygų iš 100 000. Akivaizdus būdas — surikiuoti ir paimti pirmus dešimt. Penktame žingsnyje pamatuosi, kiek tas „akivaizdus" kainuoja.

Antra: tai Dijkstros algoritmo eilė. Keturioliktoje ir penkioliktoje pamokose ieškosi kelių grafe, ir kiekviename žingsnyje reikės klausti „kuris nelankytas mazgas artimiausias?". Būtent tam krūva ir egzistuoja. transit — Vilniaus maršrutų serveris — sukasi apie šitą vieną klausimą, ir aštuntame žingsnyje pamatysi, ką jam kainuoja atsakyti jį blogai.