Labori materjal

• Slaidid: Puud

Laboriülesanded

Selle labori baasülesande käigus pead looma kaks programmi sama ülesande lahendamiseks ning võrdlema mõlema lähenemise kiirust. Lisaülesande raames tuleb luua kolmas programm ning võrrelda selle jõudlust kahe eelneva.

Laboriülesanne [W13-1]: lineaarotsing võrdlus kahendotsingpuuga

Labori baasülesande raames on sul tarvis luua kaks programmi. Mõlemad täidavad täpselt sama ülesannet, leides mitu korda iga nimi kordub ette antud andmefailis. Esimese programmi raames pead kasutame lineaarset otsingut koos dünaamilise massiiviga leitavate kirjete hoidmiseks. Teises programmis täidab sama rolli meile kahendotsingpuu.

• Lae alla näidisrakendused, mille põhjal laboritööd teha: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/13_trees_samples.zip
• Lae alla laboriülesande andmefail: https://blue.pri.ee/ttu/files/iax0584/andmefailid/13_trees_random_people_city_data.zip

Läbi labor jälgides samm-sammulist juhendit.

Üldised nõuded

• Leia kõik failis olevad nimekombinatsioonid (ees + perenimi).
• Loenda, mitu korda iga nimekombinatsioon esines.
• Väljasta leitud tulemused väljundfaili
  • Kasuta järgnevat väljundi struktuuri:
    <eesnimi> <perenimi> <korduste arv>
• Loo kaks lahendust samale ülesandele
  • Esimeses lahenduses kasuta dünaamilist massiivi, mida laiendad jooksvalt realloc()  funktsiooniga.
  • Teises lahenduses kasuta binaarotsingpuud.
• Arvuta programmi siseselt, kui kaua kulus erinevatel etappidel aega
  • Kasuta etteantud struktuuri ja aja kuvamise funktsiooni, mis on esitatud samm-sammulises juhendis
  • Tuleb mõõda, kui kaua aega kulus andmete lugemiseks, andmete väljastamiseks, andmete vabastamiseks ning kogu ajakulu
• Kuva ekraanil, mitu erinevat nimekombinatsiooni programm leidis, veendu numbri õigsuses.
• Optimeeri oma programmi võimalikult palju
  • Väldi nimekombinatsioonide ekraanile kuvamist – see on aeglane!
  • Puu loomisel kasuta globaalmuutujat elementide arvu jälgimiseks
  • Kahendpuu väljastamisel kasuta väljundfaili avamiseks globaalset failiviita, fail ava ja sulge ühekordselt
  • Hoia nimi struktuuris staatilisena – nt char combinedName[64]
• Labori kaitsmiseks mõtle, kuidas vastaksid küsimustele, mis on esitatud peatükis Programmi tööaja võrdlemine

Programm 1: Lineaarotsing

Alustamiseks tutvu esmalt näidisprogrammiga. Selleks ava    example_linear.c  ja   example_linear.h  failid ning tutvu nende ülesehitusega, ehita ja käivita see rakendus. See saab olema su aluskood.

Märka, et programm kasutab käsurea argumente – st käivita seda järgnevalt:  ./program_name input_file_name

Tutvus tehtud, alustame koodi muutmist enda ülesandele sobivaks.

1. Muuda lugemisfunktsioon sobilikuks ülesande andmefailile
   • Praegune versioon faili lugemisest eeldab ühte nime (ühesõnaline). Tunnitöö andmefailis on neli välja rea kohta – eID, first name, last name and city.
   • Muuda fscanf()  funktsiooni sedasi, et see saaks hakkama täiendavate väljadega. eID ja linna salvestada pole vaja, ülesanne neid ei vaja.
   • Kleebi nimi kokku kujul  "Eesnimi Perenimi" . Kasuta kleebitud kuju nii otsingufunktsioonis veendumaks, kas tegu on uue nimega või mitte, ning uue nime puhul lisa see oma andmestruktuuri.
     Vihje: snprintf() on kõige lihtsam viis nime kokku kleepida.
     Vihje: välja ignoreerimiseks saad kasutada formaati %*s
2. Loenda mitu korda nimi esinenud on. Loendamine toimub faili lugemise käigus.
   • Lisa oma struktuuri kirjeldusse loendur – kasuta kas  int või  unsigned andmetüüpi.
   • Enne kui hakkad oma loendamist kodeerima, vaata kuidas on näitekoodis lahendatud korduvate (juba massiivis eksisteerivate) nimede tuvastamine.
     Vihje: Vaata funktsiooni GetNameIndex()  tagastust. Kasuta oma koodis tagastatavat väärtust vajaliku funktsionaalsuse lisamiseks. Funktsiooni GetNameIndex()  ära muuda!
   • Lisa oma struktuuris paiknevale loendurile algväärtustamine. Seda pead tegema  ReadData()  funktsioonis. Mõtle läbi, millal on kõige sobilikum hetk välja algväärtustamiseks.
   • Lisaks algväärtustamisele peab ReadData()  funktsioonis lahendama loenduri väärtuse suurendamise, kui nimi on varasemalt juba esinenud. Selleks meenuta, mida tagastas GetNameIndex() funktsioon, kui nimi oli massiivis juba olemas.
3. Muuda oma väljastuse funktsiooni
   1. • Asenda ekraanile trükkimine väljundfaili kirjutamisega
      • Väljastus peab koosnema täisnimest ja korduste arvust
4. Kuva ekraanil, mitu erinevat nimekombinatsiooni kokku esines
5. Lisa andmete vabastamine
6. Lisa aja mõõtmine
   • Aega on vaja mõõta neljas punktis. Selleks on mõistlik luua uus struktuur
     
     struct TimePoints { clock_t start; /* Right before staring to read */ clock_t read; /* After the reading function finishes, before printing */ clock_t print; /* After printing to file is finished */ clock_t free; /* Data structure is freed */ };

     1 2 3 4 5 6 7

     struct TimePoints {     clock_t start; /* Right before staring to read */     clock_t read;  /* After the reading function finishes, before printing */     clock_t print; /* After printing to file is finished */     clock_t free;  /* Data structure is freed */ };

   • Paiguta oma main()  funktsiooni õigetesse kohtadesse ajavõtupunktid
   • Aegade arvutamiseks pakume välja järgneva funktsiooni
     
     void PrintTime(struct TimePoints t) { printf("Reading: %9.6lf s\n", (double)(t.read - t.start) / CLOCKS_PER_SEC); printf("Printing: %9.6lf s\n", (double)(t.print - t.read) / CLOCKS_PER_SEC); printf("Freeing: %9.6lf s\n", (double)(t.free - t.print) / CLOCKS_PER_SEC); printf("Total: %9.6lf s\n", (double)(t.free - t.start) / CLOCKS_PER_SEC); }

     1 2 3 4 5 6 7

     void PrintTime(struct TimePoints t) {     printf("Reading:  %9.6lf s\n", (double)(t.read - t.start) / CLOCKS_PER_SEC);     printf("Printing: %9.6lf s\n", (double)(t.print - t.read) / CLOCKS_PER_SEC);     printf("Freeing:  %9.6lf s\n", (double)(t.free - t.print) / CLOCKS_PER_SEC);     printf("Total:    %9.6lf s\n", (double)(t.free - t.start) / CLOCKS_PER_SEC); }

7. Testi esmalt oma koodi ilma valgrindita. Veendu leitud nimede arvus ja väljundfaili tulemustes. Mäluvigade korral on soovitav esimene test teha kasutades LibASANi (address sanitizer), valgrind on aeglane.
8. Kui funktsionaalselt lahendus töötab, testi oma koodi ka valgrindiga. Valgrindiga jooksutades peab käsureaargument olema pärast programmi nime. Valgrindiga võtab rakenduse testimine üle minuti!
   valgrind ./example_linear random_people_city_data.txt

Lineaarse algoritmi testimine

Programmi väljundis on oluline jälgida leitud erinevate kombinatsioonide arvu ning programmi erinevateks osadeks kulunud aegu. Erinevate aegade suhtes tuleks kriitiliselt hinnata nende realistlikkust.

Loendamise korrektsuses veendumiseks vaata andmefaili algust. Järgnevalt on esitatud andmefaili esimeste ridade näide.

Kui programm on funktsionaalne, ajad realistlikud ja väljundid korrektsed, testi üle ka valgrindiga veendumaks mäluvigade puudumist.  See võib võtta minutike-kaks!

Programm 2: Kahendotsingpuu

Alustuseks ava näiteprogramm  example_bin_search_tree.c ning tutvu selle ülesehitusega. Käivita programm, tutvu selle väljundiga.  See saab olema su aluskood.

Märka, et programm kasutab käsurea argumente – st käivita seda järgnevalt:  ./program_name input_file_name

Tutvus tehtud, alustame koodi muutmist enda ülesandele sobivaks. Eesmärk on saavutada täpselt sama funktsionaalsus nagu esimese programmiga.

1. Uuenda struktuuri kirjeldust. Sul on vaja hoida seal nii sõne kui loendurit, täpselt nagu lineaarse otsingu puhul.
2. Uuenda oma lugemisfunktsioon samal põhimõttel nagu lineaarse otsinguga
   • Muuda fscanf()  funktsiooni toetamaks failis olevat nelja parameetrit.
   • Kleebi ees- ja perenimi kokku.
3. Uuenda lisamise funktsiooni InsertNode()
   • Muuda andmetüüpi – näidiskoodis lisatakse puusse täisarv, meie lahenduses tuleb lisada nimi
   • Muuda võrdlemise operatsiooni sõnedele sobilikuks. Pane tähele, et erinevalt näitekoodist peame meie tuvastama ka olukorra, kui puus nimi juba eksisteerib. Sellisel juhul peame loendurit uuendama.
4. Uuenda uue tipu loomise funktsiooni CreateNode()
   • Muuda parameetrit, et sinna saaks edastada sõne (inimese täisnime)
   • Lisa struktuuris oleva loenduri (nime korduste arv) algväärtustamine
5. Uuenda puu väljastamise funktsiooni PrintTree()
   • Vii sisse uuendused lähtuvalt muudetud andmestruktuurist
   • NB! Kuna meie eesmärgiks on kiire programm, siis tuleks failiviit luua globaalse muutujana. Fail ava enne väljastuse funktsiooni väljakutset ning sulge pärast funktsiooni töö lõppu.
   • Muuda puu läbikäiku. Näitekoodis on puu läbikäiguks valitud eesjärjestus. Leia selline läbikäigu meetod, mille puhul oleks vastus sorteeritud tähestikulises järjekorras. Läbikäigu muutmiseks pead vahetama rekursiivsete kutsete ja praeguse liikme väljastamise järjekorda.
6. Realiseeri vabastamise funktsioon
   • Nii nagu kõik puu funktsioonid, peab ka vabastamine olema rekursiivne. Võta inspiratsiooni puu väljastamise funktsioonist. NB! Oluline on valida õige puu läbikäigu meetod (ees-, lõpp- või keskjärjestus). Valesti valitud järjestuse  puhul ei ole võimalik puud vabastada.
7. Lisa aja mõõtmine samamoodi nagu tegime seda lineaarse programmi korral – kõik käsud, andmestruktuur ja väljastus on täpselt samasugused.
8. Testi oma koodi nii valgrindiga kui ilma. Valgrindiga jooksutades peab käsureaargument olema pärast programmi nime, nt valgrind ./programm andmefail

Kahendotsingpuu testimine

Testimise jaoks oleme alamosadeks kulunud aja jätnud esitamata, et jätta nende tulemuste hindamine ja võrdlemine lineaarse algoritmiga sinu ülesandeks. See on ka osa ülesande kaitsmisest. Olenemata algoritmist peab leitud nimekombinatsioonide arv olema sama, st 27454.

Küll aga pakume väljavõtet kahendotsingpuu poolt loodavast andmefailist. Võrdle enda andmefaili algust järgneva tulemusega.

Programmide tööaja võrdlemine

Nüüd võrdle mõlema programmi ajakulu.

• Kumb on kiirem, kumb on aeglasem?
• Kas mõned rakenduse alamosad on puu ja lineaarse struktuuri võrdluses ajaliselt märkimisväärselt erinevad?
• Kas üks või teine lahendus on läbivalt teisest aeglasem?
• Ära unusta iga küsimuse juures ka oma mõttekäike laiendamast!

Mõtle, kuidas võiksid järgnevad muudatused mõjutada programmide tööaega!

• Kahendotsingpuu lahendus sisaldab veel ühte täiendavat funktsionaalsust, mida lineaarne otsing ei sisalda. Mis funktsionaalsusega on tegu ning kuidas see mõjutaks lineaarset otsingut täiendavalt?
• Kuidas muutuks lineaarse programmi tööaeg, kui muudaksid realloc()  mälu laiendamise strateegia (n + 1) pealt (n * 2) peale.
• Kuidas oleksid mõlemad programmid mõjutatud, kui erinevate nimekombinatsioonide arv suureneks märkimisväärselt? Katsu end väljendada Big O notatsiooni kasutades (https://www.bigocheatsheet.com)
• Kuidas oleksid mõlemad programmid mõjutatud, kui korduste arvud suureneksid märkimisväärselt, kuid erinevate kirjete arv jääks samaks?
• Kuidas mõjutaks puu tasakaalustamine lahendust?
  • Kas ja mil määral võiks see mõjutada rakenduse töökiirust?
  • Mis on kõige halvem võimalik olukord tasakaalustamata kahendotsingpuu jaoks?
• Kui lahendasid ka lisaülesande, kaasa samasse võrdlusse ka trie andmestruktuur. Kas sellel on ka mõni märkimisväärne eelis tavalise kahendotsingpuu ees?

Lisaülesanne [W13-2]: Trie puu

Loo kolmas programm ning võrdle selle efektiivsust eelneva kahe programmiga. Kasuta kolmandas rakenduses trie andmestruktuuri.

Kõik teised nõuded jäävad samaks.

Soovituslik andmestruktuur

Kasutame muudetud versiooni slaididel olnud näidisest. Asendame struktuuris oleva tõeväärtuse ( isLeaf ), mis näitas sõne lõppu, hoopis täisarvulise väärtusega. Kui väärtus on 0, siis selles asukohas nime lõppu ei ole. Kui väärtus on nullist suurem, siis on tegu lehega, mis tähistab nime. Number ütleb, mitu korda nimi failis eksisteeris.

Vihje 1: Lisaks tähestikule arvesta ka tühiku ja miinuse sümboliga. Mõlemad neist on olemas andmefailis. Täiendavaid erisümboleid failis ei ole.

Vihje 2: Andmestruktuuri väljade algväärtustamine CreateNode()  funktsioonis on äärmiselt tähtis. Algväärtusta nii loendur kui kogu viitade massiiv.

Pärast seda tundi peaksid

• Oskama mõõta rakenduse tööaega programmisiseselt ja süsteemse tööriistaga
• Teadma, kuidas seostuvad omavahel kerneli aeg, kasutaja aeg ning reaalne aeg
• Teadma, mis võib juhtuda, kui kõik süsteemis töötavad protsessid ei mahu enam arvuti põhimällu ära
• Teadma erinevaid kompilaatori optimeerimise tasemeid ning lihtsamal tasemel, mis eeliseid ja probleeme optimeerimine võib tuua
• Teadma puudega seotud mõisteid nagu tipp, juur, leht, kõrgus jne
• Teadma puu liike ja nendega seotud omadusi (kahendpuu, kahendotsingpuu ning tasakaalustatud kahendpuu)
• Teadma erinevaid puu läbikäigu viise (eesjärjestus, keskjärjestus, lõppjärjestus) ning nende kasutusjuhte – st milleks iga läbikäigumeetod sobilik on
• Oskama kahendpuu kasutamiseks luua rekursiivseid funktsioone andmete lisamiseks, otsimiseks ja kustutamiseks
• Teadma Trie puu omadusi, kasutusvaldkonda ja struktuuri

Täiendav materjal

• Binary search tree
  https://www.geeksforgeeks.org/binary-search-tree-data-structure/
• Binary search tree visualization
  https://www.cs.usfca.edu/~galles/visualization/BST.html
• Trashing
  https://en.wikipedia.org/wiki/Thrashing_(computer_science)
• Algoritmid ja andmestruktuurid (Tartu Ülikool)
  https://dspace.ut.ee/bitstream/handle/10062/16872/9985567676.pdf