Kai eilės nebereikia visai

Keturioliktos pamokos pabaigoje liko eilutė be paaiškinimo:

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

Be prioritetinės eilės. Be krūvos. Be euristikos.

Pilna lentelė, mūsų matavimas:

	mūsų laikas	prieš ranka rašytą krūvą
Dijkstra, tiesinė peržiūra	876.6 ms	16.4× lėčiau
Dijkstra, ranka rašyta krūva	53.4 ms	1.0
Dijkstra, container/heap	73.1 ms	1.37× lėčiau
A*, euristika	77.2 ms	1.45× lėčiau
Connection Scan	0.70 ms	76× greičiau

Prieš naiviąją versiją — 1252 kartus.

Kaip

Dijkstra klausia „kuris mazgas pigiausias?", ir tam reikia eilės.

CSA neklausia to visai. Ji laiko jungčių sąrašą, surikiuotą pagal išvykimo laiką, ir pereina jį vieną kartą, nuo pradžios iki galo:

CSA(from, departAt, to):
    arrival[*] ← ∞;  arrival[from] ← departAt
    kiekvienai jungčiai c sąraše (didėjančio išvykimo tvarka):
        jei c.dep < arrival[c.from]: praleisk     // nespėji įsėsti
        jei c.arr < arrival[c.to]:
            arrival[c.to] ← c.arr
    grąžink arrival[to]

Jokios eilės. Jokių pakartotinių aplankymų. Vienas praėjimas per masyvą.

Tai veikia todėl, kad jungtys jau surikiuotos pagal laiką: kai jas skaitai iš eilės, kiekvienos jungties metu jau žinai viską, kas galėjo įvykti anksčiau. Laiko tvarką turi masyvas, todėl eilei nebelieka darbo.

Prisimeni trylikos pamokos vidinę mintį — imk tiek tvarkos, kiek klausimui reikia? Čia ji nueina iki galo: reikiama tvarka jau įrašyta į duomenis, ir struktūros nebereikia jokios.

Aštuntos pamokos klausimas, atsakytas

Aštuntos pamokos namų darbe buvo užduotis, kurios niekas nebuvo atsakęs:

transit niekada nepamatavo to rikiavimo. Įvertink: 196 412 elementų, O(n log n). Po kelių užklausų rikiavimas atsiperka? Ir ar 76 kartai vis dar teisingas skaičius, jei skaičiuoji paruošimą?

Pamatuota:

sorting 196412 connections by (departure, trip): 3694130 comparisons, 32.785ms (best of 5)
one query saves 52.7 ms; the sort costs 32.8 ms => it pays for itself after 0.62 queries

Atsiperka po 0.62 užklausos — tai yra anksčiau, nei pirmoji spėja pasibaigti.

Ir kadangi rikiuojama vieną kartą paleidžiant serverį, o užklausų būna tūkstančiai, 76 kartai lieka teisingas skaičius. Klausimas buvo geras; atsakymas pasirodė nedviprasmiškas.

Aštunta pamoka rikiavimą pristatė kaip algoritmą. Čia jis yra paruošimas — vienkartinė investicija, kuri leidžia paskui nebeturėti struktūros.

Sąžininga sąlyga

CSA nėra greitesnė Dijkstra. Ji atsako į siauresnį klausimą.

Dijkstra   arrive 10:27, 147 min,  6 persėdimai
CSA        arrive 10:27,           11 persėdimų

Tas pats atvykimo laikas. Vienuolika persėdimų vietoj šešių.

CSA optimizuoja tik anksčiausią atvykimą. Apibendrintos kainos — laukimo svorio 2.0 ir 5 minučių persėdimo bausmės — ji nemato, todėl ir maršruto pagal jas nerenka.

Ar tai priimtina, priklauso nuo to, kam programa skirta. Keleiviui, kuriam svarbu atvykti kuo anksčiau — taip. Keleiviui su lagaminu — ne.

Greitis gautas ne todėl, kad algoritmas gudresnis. Jis gautas todėl, kad klausimas paprastesnis. Sumažink klausimą — ir dingsta struktūra, kurios jam reikėjo.

Būtent todėl transit laiko visus penkis algoritmus, o ne vien greičiausią. Jie atsako į skirtingus klausimus, ir tik viena eilutė lentelėje pasako, kurie atsakymai apskritai palyginami.

Visos trys pakopos

	ką pakeitė	ką laimėjo
tiesinė peržiūra → krūva	struktūrą	~16–19×
krūva → A*	žinias apie uždavinį	−1.45× (pralaimėjo)
Dijkstra → CSA	klausimą ir duomenų tvarką	~76×

Vidurinė eilutė yra ne mažiau svarbi už kitas dvi. Ji parodo, kad pakopos nėra kopėčios: kiekviena keičia kažką kita, ir nė viena negarantuoja laimėjimo.