Timsort je vseboval hrošča

Algoritem Timsort je eden izmed najpogosteje uporabljanih algoritmov za urejanje zaporedja števil. Prva implementacija je bila uporabljena v programskem jeziku Python, kasneje pa je postal tudi privzeti algoritem za urejanje v Javi. Uporablja se v Androidovem SDKju, Sunovem JDKju, OpenJDKju in morda še kje. Zasnoval ga je Tim Peters leta 2002, kot zvito mešanico urejanja z vstavljanjem in urejanja z zlivanjem, in je vse do nedavnega vseboval majcenega hrošča. Napaka ni kritična, ker se ne more zgoditi pri trenutno realnih velikostih tabel. Torej ni panike.

Hrošča so odkrili pri formalni analizi algoritma, ki je nikakor niso uspeli izvesti. Na koncu se je izkazalo, da gre za napako v algoritmu. Težava je pri preverjanju invariante za dolžino čet. Napako je moč preprosto odpraviti, v Pythonu je bila že naslednji dan odpravljena.

Sam podrobnosti še nisem uspel preštudirati. Vse pa je lepo opisano tukaj. Poanta vsega skupaj pa je, da je formalna analiza pravilnosti implementacij algoritmov pomembna. Ni dovolj le na papir preveriti pravilnosti. Bolje danes odkriti in odpraviti hrošča, ki bi morda šele čez 10 ali več let povzročil prvo sesutje programa.

Dodaj odgovor

Vaš e-naslov ne bo objavljen. * označuje zahtevana polja

Help

WordPress theme: Kippis 1.15