Prg1 orientoivat tehtävät¶

Harjoitusten tarkoituksena on varmistaa, että opiskelija ymmärtää olennaisimmat asiat prg1-ohjeistuksesta ja perehtyy dokumentaatioon riittävän ajoissa, mikä helpottaa työn loppuunsaattamisessa. Toinen tavoite on perehdyttää opiskelija myös työn lokaaliin testaukseen, mikä paitsi nopeuttaa testaamista vähentää myös Plussan kuormitusta.

Kaikki kysymykset liittyvät prg1-dokumentaatioon.

Kysymys 1

Paikalla on

yksilöllinen kokonaislukutunniste (id)

yksilöllinen merkkijonotunniste (id)

korkeus

sijaintikoordinaatit (x, y)

nimi

yksilöllinen emoji

tyyppi

Kysymys 2

Paikka …

sijaitsee uniikissa lokaatiossa, jossa ei voi olla muita paikkoja

sillä on koordinaatit, joita käytetään lajittelua varten Manhattan-etäisyyden perusteella

sillä on koordinaatit, joita käytetään lajittelua varten Euklidisen-etäisyyden perusteella

sillä voi olla desimaaleja sisältävä koordinaatti (NO_COORD-vakiota ei kuitenkaan lasketa)

voidaan lisätä suoraan ainoastaan yhdelle alueelle

Kysymys 3

Alueella on

yksilöllinen kokonaislukutunniste (id)

yksilöllinen merkkijonotunniste (id)

lista koordinaatteja (x, y)

nimi

perustamisvuosi

korkeus

paikkoja (sillä hetkellä, kun korkeuskäyrä lisätään tietorakenteeseen)

Kysymys 4

Alueella ..

voi olla monia alialueita (lapsi)

voi olla vain yksi alialue (lapsi)

voi olla monia vanhempia (parent)

voi olla monia esi-isiä (ancestor)

lähimmän yhteisen esi-isän löytäminen on monikäsitteistä

Kysymys 5

Kuinka monta alialuetta yksittäisellä alueella voi olla?

vähintään 0, enintään 9.

vähintään 0, ei enimmäismäärää.

vähintään 1, enintään 9.

vähintään 1, ei enimmäismäärää.

Kysymys 6

Mitkä ovat hyviä valintoja paikan tietojen tallentamiseen?

struct

class

vector

function

järjestämätön kartta

Kysymys 7

Miten voit muuttaa työhakemistoa Qt Creatorissa?

Paina käynnistyspainiketta ja toivo parasta

Siirry projektiasetuksiin ja aseta työhakemisto suorituskonfiguraation alle

Et voi muuttaa työhakemistoa Qt Creatorista

PRG1-testausohjeet¶

Kaikki kysymykset koskevat prg1-testausohjeita. Perftest-tulosteet tässä harjoituksessa eivät ole todellisia lukuja, eikä niitä tule käyttää vertailuun oman toteutuksen kanssa.

Kysymys 1

Toiminnallisuuden testaaminen voidaan suorittaa

test-käskyllä

antamalla testattava funktio nimenä parametrina, kuten all_places

testread-käskyllä

käyttämällä parametreina -in.txt- ja -out.txt-tiedostoja

perftest-käskyllä

antamalla komennon nimi, aikaraja, toistojen määrä ja N-arvot parametreina

Kysymys 2

Suorituskykytesti voidaan suorittaa

test-käskyllä

antamalla vain testattavan funktion nimi parametrina, kuten all_places

testread-käskyllä

käyttämällä parametreina -in.txt- ja -out.txt-tiedostoja

perftest-käskyllä

antamalla komennon parametreina nimi, aikaraja, toistojen määrä ja N-arvot

Kysymys 3

Toiminnallisuustestit näyttävät eroja, mitä tehdä seuraavaksi?

ei mitään, toiminnallisuustesti voi näyttää eroja suoritusaikavaihtelun vuoksi

selvittää, miksi eroja ilmenee, ja korjata koodi tiedostoissa datastructures.cc ja datastructures.hh

Kysymys 4

Mitä on tärkeää huomioida suorittaessa perftestejä?

perftestin tuloste ei anna koodin asymptotista suorituskykyä

perftest antaa erilaisia aika- ja komentolaskurimääriä eri laitteistoissa ja käyttöjärjestelmissä

on tärkeää tarkistaa, onko toiminnallisuus oikein ennen optimointia

Kysymys 5

Mitä sanotaan komentolaskureiden käytöstä suorituskyvyn mittarina?

komentolaskureilla mittaavat suorituskykyä tarkemmin kuin stopwatch-tyyppinen aikaan pohjautuva mittaus

komentolaskureilla on taipumus kaataa ohjelma

komentolaskureiden käyttö on mahdotonta, jos ei omista Linux-tietokonetta

Seuraavat kysymykset koskevat seuraavaa perftest-tulostetta

> perftest 10*all_places 10 100;1000;10000;100000
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
all_places

     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,    0.5000000 ,  1.000000000 ,    1.5000000
  1000 ,     1.000000 ,   2.00000000 ,     3.000000
 10000 ,      5.00000 ,    4.0000000 ,      9.00000
100000 , ADD Timeout!
>

Kysymys 6

Mitä funktiota perftestataan?

all_places

get_places_alphabetically

all_areas

Kysymys 7

Aikaraja ylittyi/perftesti epäonnistui. Jos kyllä, miksi?

perftesti päättyi eikä ylittynyt aikarajaa tai epäonnistunut

lisäys ylitti aikarajan, olisi hyvä parantaa add_place ja/tai add_area suorituskykyä

testattava funktio ylitti aikarajan

ohjelma kaatui

Seuraavat kysymykset koskevat seuraavaa perftest-tulostetta

> perftest 10*all_places 20 100;1000;10000;100000
Timeout for each N is 20 sec (for ADD and test functions).
For each N perform command(s):
all_places

     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,  0.500000000 ,     3.000000 ,     3.500000
  1000 ,   1.00000000 ,      6.00000 ,      7.00000
 10000 ,    5.0000000 ,      12.0000 ,       17.000
100000 ,    8.0000000 , Timeout!
>

Kysymys 8

Mikä on aikaraja (sekunneissa) kullekin N:lle?

Kysymys 9

Kuinka monta kertaa testattava komento suoritetaan kullekin N:lle?

Kysymys 10

Miksi komento tulosti Timeout!?

(paikkojen ja/tai alueiden) lisääminen vei liian kauan

10 kertaa all_places suorittaminen kesti liian kauan

ohjelma kaatui

Seuraavat kysymykset koskevat seuraavaa perftest-tulostetta

> perftest 10*get_place_name 10 5;10;50;100
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
get_place_name

      N ,    add (sec) ,   cmds (sec) ,  total (sec)
      5 ,   2.9655e-05 , terminate called after throwing an instance of 'std::out_of_range'
  what():  unordered_map::at
Aborted (core dumped)

Kysymys 11

Mitä tapahtui perftestissä?

ohjelma kaatui get_place_name-suorituksen aikana, todennäköisesti koodi ei tarkista unordered_map-avaimen kelvollisuutta

perftest onnistui, ohjelma toimii kuten pitäisi

(paikkojen ja/tai alueiden) lisääminen vei liian kauan

10 kertaa all_places suorittaminen kesti liian kauan

Seuraavat kysymykset koskevat seuraavaa perftest-tulostetta

> perftest 10*all_places 10 100;1000;10000;100000
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
all_places

     N ,    add (sec) ,  add (count) ,   cmds (sec) , cmds (count) ,  total (sec) , total (count)
   100 ,  0,000112247 ,       280203 ,   3,5244e-05 ,        43740 ,  0,000147491 ,       323943
  1000 ,  0,000116914 ,       569395 ,   3,8864e-05 ,        74040 ,  0,000155778 ,       643435
 10000 ,   0,00051654 ,      2740514 ,   8,6724e-05 ,       317460 ,  0,000603264 ,      3057974
100000 ,  0,000976794 ,      5443984 ,  0,000131009 ,       619420 ,    0,0011078 ,      6063404
>

Kysymys 12

Mikä on käskylukulaskurin arvo, eli ajettujen komentojen määrä, kun ajetaan 10 kertaa all_places ja paikkojen lukumäärä (N) on 10000?

Kysymys 13

Kuinka kauan edellisen kysymyksen tapauksen suorittamiseen kaikkiaan kului, kun aikaan lasketaan komentojen suorittamiseen käytetyn ajan lisäksi testiaineiston lisäämiseen käytetty aika? (sekunteina, samassa formaatissa kuin tulosteessa)

Kysymys 14

Kuinka monta komentoa ajettiin lisäysvaiheessa, kun lisättiin 1000 paikkaa (N) ja alueita?

Kysymys 15

Kuinka monta komentoa ajettiin yhteensä lisäysvaiheessa JA suoritettaessa all_places 10 kertaa kun N=100000?

Kysymys 16

Mitä voidaan sanoa perftest-tulosteesta:

all_places on varmasti asymptootisesti vakioaikainen

all_places in ajaminen 10 kertaa on hitaampaa suuremmalla paikkojen lukumäärällä (N)

lisäys on asymptoottisesti \(\Theta(n)\) (lineaarinen)