Skip to content

2 oji užduotis

Jump to bottom
objprog edited this page Mar 28, 2019 · 23 revisions

Duomenų apdorojimas

Turinys

Užduoties formuluotė

  • Parašykite programą, kuri nuskaito šiuos studentų duomenis:
    • vardą ir pavardę
    • n atliktų namų darbų (nd) rezultatus (10-balėje sistemoje), o taip pat egzamino (egz) rezultatą.
  • Tuomet iš šių duomenų, suskaičiuoja galutinį balą (galutinis):
galutinis = 0.4 * vidurkis + 0.6 * egzaminas

Reikalavimai skirtingoms programos versijoms

Reikalavimai versijai (v0.1) (Terminas: 2019-02-17 🕒)

  • Pagal aprašytus užduoties reikalavimus realizuokite programą, kuri nuskaito vartotojų įvedamus reikiamus duomenis:

    • studento vardą ir pavardę;
    • namų darbų ir egzamino rezultatą;

    Baigus duomenų įvedimą, suskaičiuoja galutį balą ir juos pateikia į ekraną tokiu ar panašiu pavidalu (kur galutinis apskaičiuotas balas pateikiamas dviejų skaičių po kablelio tikslumu):

    Pavardė     Vardas       Galutinis (Vid.)
--------------------------------------------------
Arvydas     Sabonis      x.xx
Rimas       Kurtinaitis  y.yy
...

  • Papildykite programą, kad vietoj vidurkio galutinio balo skaičiavimui būtų galima naudoti ir medianą. Tuomet išvedimas (output’as) turėtų atrodyti panašiai į šį, kur tik vienas pasirinktas Galutinis (Vid.) arba Galutinis (Med.) yra išvedamas:

    Pavardė     Vardas       Galutinis (Vid.) / Galutinis (Med.)
-----------------------------------------------------------
Arvydas     Sabonis      x.xx               x.xx
Rimas       Kurtinaitis  y.yy               y.yy
...

  • Papildykite programą taip, kad ji veiktų ir tokiu atveju, kai namų darbų skaičius (n) yra nežinomas iš anksto, t.y. tik įvedimo metu vartotojas nuspręndžia kuomet jis jau įvedė visų namų darbų rezultatus. Šią dalį realizuoti reiktų dviem būdais, kur namų darbų rezultatus saugant į:

    • C masyvą.
    • std::vector tipo konteinerį.

    Atliekant šią užduotį galite sukurti du atskirus (*.cpp) failus (arba du projektus), tačiau nuo versijos v0.2 (žr. žemiau) naudosime tik realizaciją su vector'iais.

  • Papildykite programą taip, kad būtų galimybė, jog mokinio gautieji balai už namų darbus bei egzaminą būtų generuojami atsitiktinai.

Reikalavimai versijai (v0.2) (Terminas: 2019-02-24 🕒)

  • Papildykite programos versiją (v0.1) taip, kad būtų galima duomenis ne tik įvesti bet ir nuskaityti iš failo. Todėl sukurkite ir užpildykite failą kursiokai.txt, kurio (pleriminari) struktūra:

    Pavardė     Vardas      ND1  ND2   ND3  ND4  ND5  Egzaminas
Vardas1     Pavardė1    8    9     10   6    10   9
Vardas2     Pavardė2    7    10    8    5    4    6
...

  • Papildykite programą taip, kad nuskaičiuos duomenis iš failo, išvedimas pleriminariai atrodytų taip:

    Pavardė     Vardas       Galutinis (Vid.) Galutinis (Med.)
----------------------------------------------------------
Arvydas     Sabonis      x.xx             x.xx
Rimas       Kurtinaitis  y.yy             y.yy
...

    Reikalavimai output’ui: studentai turi būti surūšiuoti pagal vardus (ar pavardes) ir visi stulpeliai būtų gražiai "išlygiuoti".

Reikalavimai versijai (v0.3) (Terminas: 2019-02-24 🕒)

  • Atlikite versijos (v0.2) kodo reorganizavimą (refactoring'ą):

    • Kur tikslinga, programoje naudokite (jeigu dar nenaudojote) struct'ūras;
    • Funkcijas, naujus duomenų tipus (struct’ūras) perkelkite į antraštinius (angl. header (*.h)) failus, t.y. tokiu būdu turėtumete sukurtame projekte turėti kelis *.cpp failus, kaip ir kelis *.h failus.

  • Kur tikslinga, bent minimaliai panaudokite išimčių valdymą (angl. Exception Handling)

    try {  // išimtys yra apdorojamos žemiau
       // kodas, kuris atlieka tam tikras užduotis
    } catch (std::exception& e) {
      // kodas, kuris apdoroja išimtis
}

    Kam viso to reikia? O pvz. kas atsitiks, jeigu failas, kurį bandote atidaryti neegzistuoja; arba bandote gauti masyvo elementą, kuris neegzistuoja?

Reikalavimai versijai (v0.4) (Terminas: 2019-03-04 🕒)

  • Patobulinkite (jeigu reikia pagal v0.1 paskutinę užduotį turimą realizaciją) ir sugeneruokite penkis atsitiktinius studentų sąrašų failus, sudarytus iš: 10, 100, 1000, 10000, 100000 įrašų. Vardus ir Pavardes galite generuoti "šabloninius", kaip pvz. Vardas1 Pavarde1, Vardas2 Pavarde2 ir t.t.
  • Sūrušiuokite (padalinkite) studentus į dvi kategorijas:
    • Studentai, kurių galutinis balas < 5.0 galėtume vadinti “vargšiukai”, “nuskriaustukai” ir pan.
    • Studentai, kurių galutinis balas >= 5.0 galėtume vadinti "kietiakiai", "galvočiai" ir pan.
  • Surūšiuotus studentus išveskite į du naujus failus.
  • Atlikite programos veikimo greičio (spartos) analizę: t.y. išmatuokite programos spartą išskiriant kiek laiko užtruko kiekvienas iš žemiau išvardintų žingsnių:
    • failų kūrimą;
    • duomenų nuskaitymą iš failų;
    • studentų rūšiąvimą į dvi grupes/kategorijas;
    • surūšiuotų studentų išvedimą į du naujus failus.

Programos testavimą pakartokite ir aprašykite naudojant sugeneruotus penkis skirtingo įrašų dydžio duomenų failus.

Reikalavimai versijai (v0.5) (Terminas: 2019-03-12 🕒)

  • Konteinerių testavimas: Išmatuokite patobulintos v0.4 realizacijos veikimo spartą priklausomai nuo naudojamo vieno iš trijų konteinerių:

    T.y., jeigu Jūs turite susikurę struktūrą Studentai (ar kaip jūs ją pavadinote) ir iki v0.4 naudojote std::vector<Studentai>, tai turite ištirti: ar pasikeistų ir kaip pasikeistų programos sparta, jei vietoje std::vector<Studentai> naudotumėte std::list<Studentai> ir std::deque<Studentai>.

Labai svarbu, kadangi tiek failų kūrimas, tiek ir surūšiuotų rezultatų išvedimas į failus nepriklauso nuo naudojamo konteinerio, todėl šioje užduotyje reiktų matuoti tik šiuos programoje atliekamus žingsnius:

  • duomenų nuskaitymą iš failų;
  • studentų rūšiąvimą į dvi grupes/kategorijas;

Reikalavimai versijai (v1.0) (Terminas: 2019-03-24 🕒)

  • Optimizuokite studentų rūšiavimo (dalijimo) į dvi kategorijas ("vargšiukų" ir "kietiakų") realizaciją: t.y. visiems trims konteinerių tipams (vector, list ir deque) išmatuokite programos veikimo spartą priklausomai nuo studentų dalijimo į dvi kategorijas strategijos:

    • 1 strategija: Bendro studentai konteinerio (vector, list ir deque tipų) skaidymas (rūšiavimas) į du naujus to paties tipo konteinerius: "vargšiukų" ir "kietiakų". Tokiu būdu tas pats studentas yra dvejuose konteineriuose: bendrame studentai ir viename iš suskaidytų (vargšiukai arba kietiakai). Nesunku pastebėti, kad tokia strategija yra neefektyvi užimamos atminties atžvilgiu (įsitikinkite tuo!), tačiau šiame žingsnyje svarbiausia yra patyrinėti, kaip programos veikimo sparta priklauso nuo konteinerio tipo?
    • 2 strategija: Bendro studentų konteinerio (vector, list ir deque) skaidymas (rūšiavimas) panaudojant tik vieną naują konteinerį: "vargšiukai". Tokiu būdu, jei studentas yra vargšiukas, jį turime įkelti į naująjį "vargšiukų" konteinerį ir ištrinti iš bendro studentai konteinerio. Po šio žingsnio studentai konteineryje liks vien tik kietiakai. Atminties atveju tai efektyviau, tačiau dažni trynimai gali būti "skausmingi", ypač tam tikro tipo konteineriams.

    P.s. Jeigu Jūsų šiuo metu realizuota strategija nesutampa nė su viena iš šių dviejų aukščiau aprašytų strategijų, turėsite palyginti tris strategijas: Jūsų ir abi aukščiau aprašytas strategijas.

  • Programos efektyvumas stipriai gali priklausyti ne tik nuo naudojamo konteinerio tipo, tačiau ir nuo naudojamų algoritmų. Susipažinkite su žemiau pateiktais algoritmais:

    ir pabandykite iš jų atsirinkti ir pritaikyti tinkamus algoritmus studentų dalijimo procedūrai paspartinti (optimizuoti) ant vieno fiksuoto konteinerio - vektoriaus. Palyginkite programos veikimo spartą po šių pakeitimų.

  • Galutinėje versijoje v1.0 turi būti pateikta:

    • Tvarkinga github repozicija, kurioje būtų tik Jūsų kurti (source) failai, t.y. jokių naudojamo IDE "šiukšlių".
    • README.md faile aprašyti visi releasai, bei pakomentuoti gauti rezultatai.
    • Parengta naudojimosi instrukcija, t.y. pagrindiniai žingsniai aprašyti tame pačiame README.md faile.
    • Parengta įdiegimo instrukcija, t.y. paruoštas make Makefile (Unix OS atveju) arba cmake CMakeLists.txt (bet kokios OS atveju).

Vertinimo kriterijai

  • Iki versijos (v0.5) svarbiausia, kad Jūsų programos atliktų tai, kas yra prašoma užduotyse. Jeigu yra prašomą kažką panaudoti, pvz. antraštės (header) failus, iššimtis (exceptions) ir pan. - vadinasi juos ir turite panaudoti Jūsų realizacijose. Tačiau tikrai nebus baudžiama už tai, jeigu Jūsų realizacijos nebus labai efektyvios ar "modernios" - tą mes mokysimės ir tobulėsime viso kurso (kaip ir tolesnio gyvenimo) metu - svarbu daryti sąvarankiškai, tačiau diskutuoti su kolegomis ir dėstytojais drąsiai!

  • Tuomet natūralus klausimas - o už ką gi bus baudžiama, jeigu yra svarbu tik kad veiktų? Ogi bus baudžiama už tai, jeigu veiks "bug'ovai" 😄 Pvz.:

    • Kas nutiktų, jeigu ten kur reikia "rankomis" suvesti duomenis aš vietoj balo įvedu kažkokį kitą simbolį, pvz. "s" raidę? Ar Jūsų programa "neužlūžtų"? Juk natūralu, kad taip neturėtų įvykti, o programa tiesiog turėtų informuotų apie situaciją ir pagal ją priimtų atitinkamą sprendimą.
    • Kas nutiktų, jeigu neįvesčiau nė vieno namų darbų? Ar nesigautų dalyba iš nulio?
    • Kas nutiktų, jeigu studentų duomenų failas neegzistuoja? Arba jame toje vietoje kur turi būti namų darbų/egzamino balai, būtų ne skaičius, o koks nors kitas simbolis, pvz. "s" raidė?

  • Bus vertinamas pačio darbo ir rezultatų apipavidalinimas, t.y.:

    • Kiekvienai versijai turi būti padarytas atskiras relyzas, o įvairūs efektyvumo tyrimai būtų išsamiai aprašyti ir pakomentuoti Jūsų repozicijos README.md faile.

  • Galiausiai, bus atsižvelgiama į suplanuotų darbų atlikimo grafiko, t.y. bus baudžiama: už nustatytų terminų nesilaikymą.

Papildoma užduotis

Ši užduotis skirta norint pasikelti balą, gautą atsiskaičius/apgynus atliktą Jūsų užduotį - "Duomenų apdorojimas".

  • Modifikuokite Jūsų programos versijoje v0.4 susikurtą studentų skirstymo į dvi kategorijas (kietus ir minkštus) funkciją - raskMinkstus() (jei tokios funkcijos neturėjote, susikurkite, inkorporuokitą ją į Jūsų turimą programą ir tuomet atlikite žemiau nurodytas užduotis):
// minkštus studentus nukopijuoja į naują vektorių ir ištrina iš seno
vector<Studentas> raskMinkstus(vector<Studentas>& studentai) {
    vector<Studentas> minksti;
    vector<Studentas>::size_type i = 0;  
    // invariantas: vektoriaus `studentai` elementai [0, i) yra "kieti"
    while (i != studentai.size()) { 
      if (gavoSkola(studentai[i])) {  
        minksti.push_back(studentai[i]);
        studentai.erase(studentai.begin() + i);  // ištrinti i-ąjį stud.
      } else
        ++i;  // pereiti prie kito studento
    }
    return minksti;  // grąžina studentus gavusius skolą
}

taip, kad vietoj to, kad kiekvieną "minkštą" studentą ištrinti iš vektoriaus (ar kito tipo konteinerio) studentai:

studentai.erase(studentai.begin() + i);  // ištrinti i-ąjį stud.

kiekvieną "kietą" studentą nukopijuokite/įterpkite į konteinerio studentai pradžią. Baigus ciklą (t.y. kai peržvelgsite visus studentus), panaudokite resize() funkciją ir iš šio studentai konteinerio pašalinkite perteklinius elementus (stundetus).

  • Panaudojus resize() dažnai (tame tarpe ir šiuo atveju) yra tikslinga panaudoti dar vieną funkciją. Kokią? Panaudokite ją!
  • Palyginkite (pvz. dirbant su 10000 ir 100000 studentų), kaip šios naujosios funkcijos (pavadinkime iterpkKietus()) našumas pagerėjo/pablogėjo lyginant su raskMinkstus()? Išmatuokite laiką tik šių funkcijų - visą kitą programos veiklą - ignoruokite.
  • Palyginkite ar našumas kinta, vietoj std::vector konteinerio naudojant std::deque? Neužmirškite, kad std::deque tipo konteineriams galima ne tik push_back'inti bet ir push_front'inti.

Kurso turinys yra aktyviai pildomas ir tobulinamas, todėl iš anksto atsiprašau už esančias klaidas ir netikslumus. Dar daugiau, būsiu labai dėkingas už visas pastabas ir komentarus, kaip šį kursą padaryti įdomesnį ir naudingesnį.

Praktinės užduotys

Teorinė ir praktinė medžiaga

Git pradžiamokslis

Clone this wiki locally