Järjestämme Helsingin yliopistossa tänä keväänä Algoritmit ongelmanratkaisussa -kurssin. Kurssi muodostuu viikoittaisista ohjelmointitehtävistä, jotka palautetaan automaattisesti tarkastettavaksi CSES-järjestelmään.
Kurssijärjestelmä on kaikille avoin seuraavassa osoitteessa:
Tervetuloa mukaan oppimaan algoritmien suunnittelua ja ongelmanratkaisua!
Hyviä tehtäviä. Saattaa kuitenkin olla, että Pythonille tuo 4 sekunnin aikaraja on hieman liian tiukka joidenkin tehtävien kohdalla. Pypy-tulkilla suoritusnopeus voisi riittää kaikkiin tehtäviin, mutta sitä ei näytä olevan tarjolla.
Raakaan laskentaan C++ ja Java ovat tietysti Pythonia luontevampia toteutuskieliä, mutta on silti harmi, jos tehokkaallakaan algoritmilla ei pääse aikarajan alle kaikilla tuetuilla kielillä.
Sekä Java että Python ovat huonommassa asemassa C++:aan verrattuna. Tähän mennessä kuitenkin Python-ratkaisut ovat menestyneet hyvin tehtävissä. Tarvittaessa tarkastamme aikarajoja, ja on mahdollista valita kielikohtaisia kertoimia.
CSES:ään on tulossa myöhemmin vielä lisää kieliä, emmekä voi taata tehtävien ratkeavuutta kaikilla kielillä. Tällä hetkellä testaamme jokaisen tehtävän itse C++:lla ja Javalla ennen tehtävän julkaisua.
Viikon 3 Lämpötila-tehtävässä Python-toteutukseni oli liian hidas. Täsmälleen sama algoritmi C++:lla toteutettuna meni kirkkaasti läpi.
Lämpötila-tehtävän testi #6 omassa ympäristössäni:
Python3: 4,2 s
C++: 0,15 s (CSES C++: 0,78 s)
Varmistin lisäksi, että ongelmana on nimenomaan laskenta-aika, ei input/output. Viilaamalla Python-suoritusaika varmasti parantuisi jonkin verran, mutta lyhyen optimointiyrityksen jälkeen vaihdoin suosiolla kieltä.
Tämä palautteeni suorituskykyeroista on lähinnä informatiivista, ei moitteeksi tarkoitettua. Oman kokemukseni mukaan raa'assa laskennassa Pythonin suorituskyky on C++:aan verrattuna yleisestikin noin 20-30 kertaa huonompi. Pypy kaventaa eroa valtavasti, mutta odotetusti C++ on vielä nopeampi.
Kiitos tiedosta, ja olin selvästi liian optimistinen Pythonin nopeuden suhteen. En toki tulkinnut viestiäsi moitteena, vaan se on meille arvokasta palautetta.
Tuossa tapauksessa Python-koodi vaatisi siis ehkä 30 sekunnin aikarajan, mikä ei ole mielekästä. Pypy voisi tosiaan olla harkitsemisen arvoinen vaihtoehto.
"Uolevi on tutkinut autonsa polttoaineen kulutusta ja havainnut, että jos tankissa on x litraa polttoainetta, niin autolla pystyy ajamaan e^x+sqrt(x) kilometriä."
Ei vaikuta kovinkaan realistiselta. Luulisi pikemminkin, että kilometriä kohti ajo on edullisinta mahdollisimman kevyellä kuormalla eli pienellä polttoaineella.
Pythonin hitaus nousi taas esteeksi, tällä kertaa Siltapulma-tehtävässä (viikko 8, tehtävä 1). Python-koodi läpäisi 38/40 testiä, mutta kahdessa aikaraja tuli vastaan.
C++-toteutuksena sama algoritmi toimi raskaimmassakin testissä alle sekunnissa. Python-toteutuksena suoritusaika oli noin 40-kertainen C++:aan verrattuna. Tässä tapauksessa PyPystäkään ei ollut merkittävää apua. Tosin kokeilin PyPystä vain vanhahkoa versiota.
Lisään tähän vielä vinkin verkkojen hahmottamiseen. DOT-kuvauskielellä esimerkiksi mainitun Siltapulman 3. testin verkon saa png-kuvaksi linuxilla näin:
Tiedoston siltapulma_test3.gv sisältö:
graph graphname {
5 -- 4 [label="1"];
1 -- 3 [label="2"];
1 -- 2 [label="3"];
4 -- 6 [label="4"];
4 -- 6 [label="5"];
4 -- 5 [label="6"];
3 -- 6 [label="7"];
6 -- 2 [label="8"];
}ja kuvaksi tuon saa komennolla:
dot -o siltapulma_test3.png -Tpng siltapulma_test3.gv
Onko viikon 10 Ohjelmointikieli-tehtävässä poikkeuksellinen 6 sekunnin aikaraja (normaalisti 4 s) Pythonin takia? Ainakin C++:lla ratkaisu löytyi kaikkiin testeihin 0,14 sekunnissa.
Hetken mietin oliko ratkaisuni jotenkin erityisen nokkela, mutta siitä tuskin on kyse. Jos Pythonin suoritusaikakerroin C++:aan verrattuna olisi noin 40 tässäkin tehtävässä, tuo 6 s osuisi hyvin algoritmini Python-versiolle.
Sen sijaan tämän viikon Palikkapino oli kuin luotu Pythonilla ratkaistavaksi: Lyhyehkön ja selkeän koodin maksimisuoritusaika oli 0,55 s.
Yleensä ottaen valitsemme aika- ja syöterajat niin, että Java-malliratkaisu läpäisee kaikki testit käyttäen enintään puolet ajasta. Tarkoituksena on, että haluttua aikavaativuutta edustava suunnilleen järkevästi koodattu Java-ratkaisu suoriutuisi tehtävästä.
Joissakin tehtävissä C++:n käyttäjällä on selkeä etu, koska tietyt asiat C++:ssa ovat paljon nopeampia kuin Javassa. Myös Javassa toteutuksen yksityiskohdat vaikuttavat paljon suoritusaikaan. Esimerkiksi jos tehtävässä on verkko, solmujen käsittely yksittäisinä lukuina on huomattavasti nopeampaa kuin olioina, vaikka aikavaativuudet ovat samat.
Välillä myös joku keksii teoreettisesti paremman algoritmin kuin omamme, mikä on aina meille opettavaista.
Aihe on jo aika vanha, joten et voi enää vastata siihen.