Ta pati klaida tikroje sistemoje

Praeitas žingsnis parodė, ką nestabilus rikiavimas padaro aštuoniems įrašams. Štai ką jis padarė veikiančiai sistemai.

Kaip transit stato tvarkaraščio grafą

Kiekvienoje stotelėje transit surikiuoja visus išvykimo įvykius pagal laiką ir sujungia juos į grandinę: stovi stotelėje, laikas eina, pereini nuo vieno išvykimo prie kito.

Esminė detalė: mazgas pasiekia tik savo grandinės SEKĖJUS. Iš įvykio gali patekti į vėlesnius, bet ne į ankstesnius — laikas eina viena kryptimi.

Grandinė rikiuojama su sort.Slice. O sort.Slice nestabilus.

Kas nutiko

Vilniaus tvarkaraštis surašytas minutės tikslumu, tad vienodi išvykimo laikai yra dažni — keli autobusai išvyksta tą pačią sekundę.

transit tą patį maršrutą skaičiuoja dviem grafais: pilnos dienos ir siauresniu laiko langu. Abu naudoja tą patį rikiavimą tiems patiems duomenims.

Nestabilus rikiavimas vienodo laiko įvykius sudėliojo skirtinga tvarka dviem grafuose. O kadangi mazgas pasiekia tik sekėjus, tai reiškė, kad du grafai nesutarė, kuriuos autobusus keleivis apskritai gali sugauti.

transit kode tai užrašyta taip:

„Ties on departure MUST break deterministically. With an unstable sort, a stop whose events share a departure time gets a different chain order in the windowed and full-day graphs, and since a node only reaches its chain SUCCESSORS, the two graphs then disagree about which vehicles are catchable. That produced real mismatches until this tiebreak was added."

Pataisymas

sort.Slice(chain, func(a, b int) bool {
    ea, eb := t.Events[chain[a]], t.Events[chain[b]]
    if ea.Departure != eb.Departure {
        return ea.Departure < eb.Departure
    }
    return chain[a] < chain[b]   // ← lygiuosius sprendžia indeksas
})

Antroji eilutė — visas taisymas. Kai išvykimo laikai lygūs, tvarką nusprendžia pradinis indeksas. Rikiavimas lieka nestabilus, bet palyginimas tampa pilnas: nebelieka dviejų elementų, kurių tarpusavio tvarka nenusakyta.

Nestabilų rikiavimą gali padaryti determinuotą, pridėdamas raktą, kuris niekada nesutampa. Suliejimo rikiavimui to nereikia — jam determinuotumą duoda tas vienas <=.

Ką iš to pasiimti

Tai ne greičio klaida ir ne sugriuvimas. Programa veikė, grąžindavo maršrutus ir niekada nepranešdavo apie problemą. Tiesiog du to paties skaičiavimo variantai nesutapdavo, ir tai buvo vienintelis ženklas, kad kažkas ne taip.

Būtent tokios klaidos yra brangiausios: tylios, nereguliarios ir priklausančios nuo duomenų, kurių paprastai nepasitaiko — kol tavo miestas nepradeda leisti dviejų autobusų tą pačią sekundę.