Sorting Race — liec likmi uz ātrāko algoritmu
Divi kārtošanas algoritmi sacenšas vienā un tajā pašā masīvā. Liec likmi uz uzvarētāju: labākā sarežģītība zaudē biežāk, nekā šķiet.
Sešas sacensības. Viens masīvs, divi algoritmi — izvēlies to, kurš, tavuprāt, finišēs pirmais.
Kā spēlēt
- Divas kārtošanas, viens masīvs. Liec uz to, kura finišēs pirmā, un skaties.
- Uzvar tā, kas patērē mazāk darbību — salīdzinājumu plus pārvietojumu —, nevis tā, kurai labāka mācību grāmatas sarežģītība.
- Lasi izmēru un formu. Zem apmēram divdesmit stabiņiem uzvar vienkāršās; gandrīz sakārtotā masīvā iespraušana pārspēj visas.
- Pareiza likme dod 50, nepareiza atņem 50. Sešas sacensības, un tu sāc ar 100.
Kā tas darbojas
Divi kārtošanas algoritmi sacenšas identiskā masīvā, kas uzzīmēts kā stabiņi, un tu liec likmi uz to, kurš finišēs pirmais. Katra kārta saliek O(n log n) kārtošanu pret O(n²) kārtošanu, tāpēc acīmredzams favorīts ir vienmēr — un acīmredzamais favorīts kļūdās apmēram pusē gadījumu. Patiesībā izšķir masīva izmērs un tā forma: iespraušanas kārtošana pabeidz gandrīz sakārtotu masīvu ar divdesmito daļu darbību, kas vajadzīgas naivai ātrajai kārtošanai, un zem apmēram divdesmit elementiem konstantes sver vairāk nekā asimptotika — tieši tāpēc īstās kārtošanas bibliotēkas pie tik maziem izmēriem pārslēdzas uz iespraušanu. Uzvarētāju nosaka darbību skaits, nevis hronometrs, tāpēc rezultāts ir vienāds jebkurā mašīnā. Viss darbojas tavā ierīcē, nekas nekur netiek sūtīts, un reģistrēties nav kur.
Darbības nozīmē salīdzinājumus plus datu pārvietojumus, kur apmaiņa skaitās viena, skaitītas mācību grāmatas implementācijās. Īstās bibliotēku kārtošanas ir hibrīdi un uzvarētu gandrīz katrā sacensībā — tieši par to arī ir runa.
Biežāk uzdotie jautājumi
Vai labākais algoritms vienmēr nav ātrāks?
Šajos izmēros nē. O apzīmējums apraksta, kā izmaksas aug, nevis cik tās ir, un pilnībā noslēpj konstanti. Mērīts 400 spēlēs: likme uz labāku teorētisko sarežģītību trāpa 3,19 no 6 pret 3,00, liekot vienmēr uz vienu pusi. Divi noteikumi — gandrīz sakārtots masīvs un mazs masīvs abi ir par labu vienkāršajai kārtošanai — trāpa aptuveni 4,8 no 6.
Kā tiek noteikts uzvarētājs?
Skaitot salīdzinājumus un pārvietojumus, kas aprēķināti pirms jebkā zīmēšanas. Animācija atskaņo šo skaitu vienādā tempā abās pusēs, tāpēc puse, kurai vajag mazāk darbību, ekrānā finišē pirmā tā paša iemesla dēļ, kāpēc tā uzvar. Vizualizators, kas darbinātu divus reāllaika ciklus, uz ātras mašīnas dotu citu atbildi nekā uz lēnas.
Kāpēc ātrā kārtošana dažreiz ir tik slikta?
Tā ņem pēdējo elementu par balstu — naivo variantu. Jau vai gandrīz sakārtotā masīvā tā ir sliktākā iespējamā izvēle: sadalījumi deģenerējas, un tā veic kvadrātisku darbu tieši ar tiem datiem, ar kuriem iespraušanas kārtošana tiek galā visātrāk. Īstās implementācijas ņem trīs mediānu vai nejaušu balstu tieši tāpēc.
Ko nozīmē masīva formas?
Nejaušs ir sajaukts. Gandrīz sakārtots ir kārtībā, izņemot dažas blakusesošu elementu apmaiņas. Apgriezts ir tieši otrādi. Maz vērtību ir tikai četras dažādas vērtības, un tur naivās ātrās kārtošanas sadalījums izjūk. Zāģis atkārto vienu un to pašu kāpumu vairākas reizes.