Kurssiaiheen 10 tehtävät¶
Seuraavien harjoitusten tehtävänä on muokata toimitettua koodia ja optimoida annetut funktiot siten että ne olisivat tehokkaampia. Koodisi tullaan ajamaan ja sen antamia tuloksia tullaan vertaamaan kurssin henkilökunnan tekemään referenssitoteutukseen.
Vertailu tehdään laskemalla koodisi suorittamien operaatioiden lukumäärä ja vertaamalla tätä referenssitoteutuksen suorittamaan operaatioiden lukumäärään. Huomaa, että tämä sisältää myös operaatiot, jotka on suoritettu millä tahansa valitsemallasi STL algoritmilla.
Tehtävän arvostelu tapahtuu seuraavasti:
- jos koodisi tehokkuus on 15% sisällä referenssitoteutuksesta, saat täydet 10/10 pistettä
- jos koodisi tehokkuus on vähintään 10% parempi kuin alkuperäinen templaattikoodi, mutta silti yli 15% hitaampi kuin referenssitoteutus, saat 6/10 pistettä.
- jos koodisi on hitaampi kuin alkuperäinen templaattikoodi tai 10% sisällä sen tehokkuudesta, saat 0/10 pistettä.
- lisäksi Valgrind-testaus mahdollisten muistivuotojen varalta
Attention
Saat käyttää kaikkia STL algoritmeja ja myös muita menetelmiä. Kuitenkin funktion tulee olla Plussan arvostelijan kutsuttavissa. Tämä tarkoittaa sitä, että et saa muuttaa funktion palautustyyppiä tai argumenttien lukumäärää tai tyyppiä yhtä poikkeusta lukuun ottamatta argumenttien const viittausten tekeminen. Saat myös luoda apufunktioita.
std::sort algoritmin käyttö ei ole sallittua viimeisessä tehtävässä, jossa tulee optimoida lajittelualgoritmi.
HUOMAA: Koodisi testataan vektoreilla, jotka sisältävät jopa 1 000 000 (miljoona) elementtiä. Varmista, että testaat funktioita suurilla vektoreilla.
Funktiot löytyvät päivitetystä reposta hakemistosta wk05_graphs/improving_functions .
Voit käyttää cplusplus.com: algoritmisivuja tai vastaavia apunasi.
ascendingVector (suom.) kasvavaVektori¶
Palauttaa vektorin jossa on kasvavassa järjestyksessä kokonaisluvut 0 - (n-1).
Paranna funktion tehokkuutta, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk05_graphs/improving_functions/improve1.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
minValue (suom.) pieninArvo¶
Palauttaa pienimmän arvon parametrina välitetystä vektorista tai 0 (nolla), jos vektori on tyhjä.
Paranna funktion tehokkuutta, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk05_graphs/improving_functions/improve2.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
cumulativeSums (suom.) kumulatiivisetSummat¶
Laskee vektorin arvot kumulatiivisesti ja tallentaa vektorin kumulatiivisen summan map-tietorakenteeseen. Mapin avaimet ovat vektorin uniikkeja alkioita, ja niiden arvot ovat viimeiset kumulatiiviset summat niistä hetkistä, kun kyseinen avain viimeksi kohdattiin
Esimerkiksi:
- vektori
[4, 5, 4, 6] - funktio palauttaa seuraavan map-tietorakenteen:
{{4, 13}, {5, 9}, {6, 19}}
- Aloita vektorin alusta ja sijoita arvo 4 avaimen 4 kohtaan
- Kumulatiivinen summa (4 + 5) ja tallenna se avaimeen 5
- Kumulatiivinen summa (4 + 5 + 4) ja tallenna se avaimeen 4
- Kumulatiivinen summa (4 + 5 + 4 + 6) and tallenna se avaimeen 6
Paranna funktion tehokkuutta, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk05_graphs/improving_functions/improve3.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.
randomizedThreePartQuicksort (suom.) randomisoituKolmiOsainenPikalajittelu¶
Lajittele annettu vektori käyttämällä 3-osaista satunnaistettua pikalajittelualgoritmia. Satunnaistamista käytetään pahimman tapauksen välttämiseksi (missä pivot-arvo on huonosti valittu).
HUOMIO!! std::sort käyttö on kielletty tässä tehtävässä!
Paranna funktion tehokkuutta, työnnä muutokset git-repoon ja lähetä se arvosteltavaksi.
Vastauksesi tulee olla tiedostossa wk05_graphs/improving_functions/improve4.cc
A+ esittää tässä kohdassa tehtävän palautuslomakkeen.