Teorija

transit: Dijkstros eilė

Krūva egzistuoja dėl vieno klausimo: kuris nelankytas mazgas artimiausias?

Dijkstros algoritmas jo klausia kiekviename žingsnyje. transit — Vilniaus viešojo transporto maršrutų serveris — vykdo Dijkstrą kiekvienai užklausai, tad jam tai ne akademinis klausimas.

Keturioliktoje ir penkioliktoje pamokose rašysi tą algoritmą. Šis žingsnis parodo, kiek kainuoja eilė, į kurią jį pastatysi.

Ar krūva iš viso reikalinga

Paprasčiausias būdas rasti artimiausią — peržiūrėti visus ir pasiimti mažiausią. O(n) vietoj O(log n), bet be jokios struktūros.

Mūsų matavimas (docs/reference/transit-benchmarks.md, ta pati užklausa):

Dijkstros eilė	mūsų laikas	prieš ranka rašytą krūvą
tiesinė minimumo paieška	876.6 ms	16.4 karto lėčiau
ranka rašyta dvejetainė krūva	53.4 ms	1.0 (atskaitos taškas)
`container/heap`	73.1 ms	1.37 karto lėčiau

Pirma eilutė yra atsakymas, kodėl ši pamoka egzistuoja. Beveik sekundė prieš penkiasdešimt milisekundžių — vartotojui tai skirtumas tarp „veikia" ir „pakibo".

Ir antra eilutė — tas pats, ką ką tik pamatavai

container/heap pralaimi ir ten. Keturi nepriklausomi matavimai:

iš kur	santykis
`transit` README	1.7 karto
mūsų `transit` matavimas, CLI	1.37 karto
mūsų `transit` matavimas, `BenchmarkRouter`	1.67 karto
tavo `algo pq`, šeštas žingsnis	1.66 karto

Skirtinga programa, skirtingi duomenys, skirtingas elemento tipas — ir tas pats atsakymas. Šeštame žingsnyje matei kodėl, ir būtent todėl jis atkartojasi: pakavimas ir iškvietimai per lentelę nepriklauso nei nuo užduoties, nei nuo mašinos.

Palygink su šeštos pamokos medžio ginču, kuris tarp mašinų apsivertė. Ten skirtumas buvo dešimtoji milisekundės dalis ir jį nunešė procesoriaus pokytis. Čia priežastis yra 20 000 paskirstymų, o jie niekur nedingsta.

Pamatuok tada, kai skirtumo priežasties nežinai. Kai žinai — pakartojamumas darosi nuspėjamas.

Spąstai

Absoliutūs skaičiai čia mūsų, ne iš transit README. Tos pačios užklausos mūsų mašinoje trunka 1.5–1.9 karto ilgiau, nors mikromatavimai buvo greitesni.

Cituok santykius, ne milisekundes. Santykiai atsikartoja; laikai — ne.

Ir dar viena eilutė, kurios šioje pamokoje nepaaiškinsime

Toje pačioje lentelėje yra ketvirtas variantas:

| Connection Scan | 0.70 ms | 76 kartus greičiau už geriausią Dijkstrą |

Be jokios eilės. Be krūvos.

Kaip galima aplenkti gerai realizuotą Dijkstrą 76 kartus, atsisakius struktūros, kurią ką tik pastatei? Atsakymas yra penkioliktoje pamokoje ir jis nėra „krūva buvo bloga". Kol kas tiek: greičiausias būdas atsakyti į klausimą kartais yra klausti kito klausimo.