Sorting Race — statyk už greitesnį algoritmą
Du rikiavimo algoritmai lenktyniauja tame pačiame masyve. Statyk už nugalėtoją: geresnis sudėtingumas pralaimi dažniau, nei atrodo.
Šešios lenktynės. Tas pats masyvas, du algoritmai — pasirink tą, kuris, tavo manymu, finišuos pirmas.
Kaip žaisti
- Du rikiavimai, vienas masyvas. Statyk už tą, kuris finišuos pirmas, ir žiūrėk.
- Laimi tas, kuris sunaudoja mažiau operacijų — palyginimų plius perkėlimų — o ne tas, kurio vadovėlinis sudėtingumas geresnis.
- Skaityk dydį ir formą. Žemiau maždaug dvidešimties stulpelių laimi paprastieji; beveik surikiuotame masyve įterpimas įveikia viską.
- Teisingas statymas moka 50, klaidingas kainuoja 50. Šešios lenktynės, pradedi nuo 100.
Kaip tai veikia
Du rikiavimo algoritmai lenktyniauja identiškame masyve, nupieštame stulpeliais, o tu statai už tą, kuris finišuos pirmas. Kiekvienas ratas sustato O(n log n) rikiavimą prieš O(n²) rikiavimą, tad akivaizdus favoritas yra visada — ir akivaizdus favoritas klysta maždaug pusėje atvejų. Iš tikrųjų sprendžia masyvo dydis ir jo forma: rikiavimas įterpimu užbaigia beveik surikiuotą masyvą per dvidešimtadalį operacijų, kurių reikia naiviam greitajam rikiavimui, o žemiau maždaug dvidešimties elementų konstantos sveria daugiau nei asimptotika — būtent todėl tikros rikiavimo bibliotekos prie tokių dydžių persijungia į įterpimą. Nugalėtoją lemia operacijų skaičius, o ne chronometras, tad rezultatas toks pat bet kurioje mašinoje. Viskas veikia tavo įrenginyje, niekas niekur nesiunčiama, ir registruotis nereikia.
Operacijos reiškia palyginimus plius duomenų perkėlimus, kur sukeitimas skaičiuojamas kaip vienas, suskaičiuotus vadovėlinėse realizacijose. Tikri bibliotekiniai rikiavimai yra hibridiniai ir laimėtų beveik kiekvienas lenktynes — apie tai ir kalbama.
Dažnai užduodami klausimai
Argi geresnis algoritmas ne visada greitesnis?
Tokiais dydžiais – ne. O žymėjimas aprašo, kaip auga kaina, o ne kokia ji, ir visiškai paslepia konstantą. Išmatuota per 400 partijų: statymas už geresnį teorinį sudėtingumą pataiko 3,19 iš 6, palyginti su 3,00 statant vis į tą pačią pusę. Dvi taisyklės — beveik surikiuotas masyvas ir mažas masyvas abi palaiko paprastą rikiavimą — pataiko apie 4,8 iš 6.
Kaip nustatomas nugalėtojas?
Skaičiuojant palyginimus ir perkėlimus, apskaičiuotus prieš bet ką nupiešiant. Animacija atkuria tą skaičių vienodu tempu abiejose pusėse, tad pusė, kuriai reikia mažiau operacijų, ekrane finišuoja pirma dėl tos pačios priežasties, dėl kurios laimi. Vizualizatorius, sukantis du realaus laiko ciklus, greitoje mašinoje duotų kitą atsakymą nei lėtoje.
Kodėl greitasis rikiavimas kartais toks prastas?
Jis ima paskutinį elementą kaip atramą – naivųjį variantą. Jau arba beveik surikiuotame masyve tai blogiausias įmanomas pasirinkimas: skaidiniai išsigimsta ir jis atlieka kvadratinį darbą būtent su tais duomenimis, kuriuos rikiavimas įterpimu sutvarko greičiausiai. Tikros realizacijos ima trijų medianą arba atsitiktinę atramą būtent dėl to.
Ką reiškia masyvo formos?
Atsitiktinis yra sumaišytas. Beveik surikiuotas yra tvarkingas, išskyrus kelis gretimų elementų sukeitimus. Apverstas yra tiksliai atvirkščiai. Mažai reikšmių turi tik keturias skirtingas reikšmes, ir ten naivaus greitojo rikiavimo skaidinys subyra. Pjūklas kelis kartus kartoja tą patį kilimą.