transit: du grafai, nes du klausimai

transit turi du grafus. Ne dėl to, kad vienas geresnis — dėl to, kad klausimai du.

Pirmasis: stotelių grafas

Viršūnė — stotelė. Briauna A→B yra, jei koks nors reisas važiuoja iš A į B be tarpinių stotelių.

stotelių grafas   1 531 viršūnė, 2 190 briaunų
BFS vienai užklausai   5.8 – 8.3 µs

Vidutinis laipsnis — 2190 / 1531 = 1.43. Tavo bibliotekos tinklo — 1.49. Beveik tas pats skaičius, ir ne atsitiktinai: abu tinklai yra ilgos grandinės su retomis sankryžomis.

Pačios transit kodo pastabos sako, kad mediana yra 1. Tai jų teiginys, ne mūsų matavimas — laikykim jį taip pat, kaip antra pamoka laikė griežinių antraščių skaičiavimą.

Ir tos mažumos pasekmė pasakyta ten pat: todėl BFS čia kainuoja mikrosekundes, ir todėl šis grafas niekada negalėtų atlaikyti prioritetinės eilės palyginimo. Penkiolikta pamoka to palyginimo reikalaus, ir jai reikės kito grafo.

Kodėl laiko šitame grafe NĖRA

Tai svarbiausia šio žingsnio mintis, ir ji ne apie greitį.

transit kodas sako tiesiai:

Laikas sąmoningai praleistas: klausimas yra perėjimų skaičius, tad ir modelis yra perėjimų grafas, o BFS jam yra tiksliai tinkamas.

„Per kiek mažiausiai stotelių nuvažiuosiu iš A į B?" — tai perėjimų skaičiavimas. Kiek minučių trunka kiekviena atkarpa, atsakymui nesvarbu. Jei laikas būtų modelyje, jis būtų duomenys, kurių klausimas neužduoda — o BFS jais vis tiek nesinaudotų.

Modelis atitinka klausimą. Ne atvirkščiai.

Antrasis: laiko išplėstinis grafas

Dabar užduok kitą klausimą: „kada anksčiausiai atvyksiu?"

Į jį perėjimų grafas atsakyti negali — ne lėtai, o iš principo. Jame nėra laiko. Dviejų stotelių atstumas ten yra „viena briauna", ir tiek.

Todėl transit turi antrą grafą, kuriame viršūnė yra ne stotelė, o įvykis: konkretus autobusas konkrečioje stotelėje konkrečiu laiku.

laiko išplėstinis grafas   206 875 viršūnių, 422 661 briauna

Tas pats miestas. 135 kartus daugiau viršūnių, nes vietoj 1 531 stotelės yra kiekvienas dienos išvykimas atskirai.

Ir reprezentacija pasikeitė kartu

Septintame žingsnyje pamatavai, kad matricos ir sąrašo skirtumas auga su V. transit tą patį rodo kita ašimi — jo du grafai laikomi skirtingai:

	viršūnių	kaip laikoma
stotelių grafas	1 531	adj [][]int32 — griežinių griežinys
laiko išplėstinis	206 875	offsets []int32 + edges []Edge — vienas plokščias masyvas

Antrasis yra būtent tai, ką antra pamoka apskaičiavo: prie 206 875 viršūnių atskiros antraštės kainuotų ~5 MB vien rodyklėms, tad transit jų neturi.

Ta pati programa, du grafai, dvi reprezentacijos, ir pasirinkimą lemia dydis.

Kodėl BFS ten netinka

Paleisk BFS laiko išplėstiniame grafe — jis veiks. Ir atsakys į klausimą „per kiek mažiausiai įvykių".

Niekas to neklausė.

Mažiausiai įvykių nėra nei anksčiausias atvykimas, nei mažiausiai persėdimų, nei trumpiausias laikas. Tai teisingas atsakymas į klausimą, kurio nėra.

BFS atsako „per kiek perėjimų", nes kiekvienas perėjimas kainuoja tiek pat. Laiko išplėstiniame grafe jie kainuoja skirtingai — ir BFS tai ignoruoja.

Štai kur baigiasi ši pamoka ir prasideda kita. Kai briaunos nustoja būti vienodos, reikia paieškos, kuri skaičiuoja kainą, o ne perėjimus — ir eilės, kuri kaskart atiduoda pigiausią.

Tokią eilę pastatei tryliktoje pamokoje.