Algoritmitekniikka, Harjoitus 2, 3.2.2000

1. Lue harjoitustyöartikkelisi. Mitkä ovat sen kokeellisen tutkimuksen pääräärät? kysymykset, joihin etsitään vastausta? hypoteesit, joita testataan? Vaikuttaako siltä, että päämäärät on määritelty selkeästi ja etukäteen?

2. Selvitä mitä eri keinoja käyttämässäsi koneessa on mitata ohjelman tai sen osien suorittamiseen kuluvaa aikaa? Mitä aikaa ne mittaavat (user/system/real)? Mikä on menetelmien resoluutio eli kuinka lyhyitä aikoja niillä voi mitata tarkasti ja luotettavasti? Mitä hyviä tai huonoja puolia eri menetelmiin liittyy?

3. Prioriteettijonon (Tehtävä 1.3) keko-toteutuksessa operaatio extract-min poistaa keon huipun. Huipun paikalle tuodaan keon pohjimmaisin alkio, joka sitten pudotetaan askel kerrallaan alaspäin, kunnes se on lapsiaan pienempi. Jokaisella askeleella tehdään kaksi alkioiden välistä vertailua: lapsien vertailu toisiinsa pienemmän lapsen löytämiseksi ja pienemmän lapsen vertailu vanhempaan lopetuskohdan havaitsemiseksi.

   Vaihtoehtoinen toteutus on Floydin "pomppu"-heuristiikka, jossa alkio pudotetaan ensin huipulta pohjalle asti, josta se sen jälkeen "pomppaa" takaisin ylöspäin omalle paikalleen. Pudotuksen aikana tarvitaan nyt vain yksi vertailu. Pomppu taas jää keskimäärin hyvin matalaksi.

   Vertaa näiden kahden variaation tehokkuutta toisiinsa kokeellisesti. Kiinnitä huomiota toteutuksen tehokkuuteen ja tasapuolisuuteen. Kokeile myös suurilla keoilla. Sopiva testi on esimerkiksi kekolajittelu.

   Voit käyttää toteutuksen pohjana omaa toteutustasi tehtävästä 1.3 tai esimerkiksi seuraavaa toteutusta (joka sisältää myös kekolajittelun):

   http://www.programmingpearls.com/priqueue.cpp
   

   [Laitoksen Linuxeissa muuta "iostream" "iostream.h":ksi.]

4. Toteuta tehtävän 3 algoritmeista myös versiot, joissa lasketaan eri operaatioiden lukumääriä. Ovatko tulokset samanlaisia? Saatko laskureiden avulla selville jotain informaatiota, joka ajastamalla ei selviä?

5. Vertaile ajastamista ja laskureiden käyttöä toisiinsa. Kumpi menetelmä vaatii enemmän aikaa? Mitä muita etuja ja haittoja niissä on? Kumpaa suosittelisit käytettäväksi, jos joku haluaisi käyttää vain toista tehtävien 3 ja 4 algoritmien vertailuun? Miksi?