laborid,pr2_et

PR2ET13: Puud

Labori materjal

Laboriülesanded

Selle labori baasülesande käigus pead looma kaks programmi ning võrdlema nende jõudlust. Edasijõudnute ülesande raames tuleb luua kolmas programm ning võrrelda selle jõudlust eelneva kahega.

Laboriülesanne: lineaarotsing vs kahendotsingpuu

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 unikaalsete kirjete hoidmiseks. Teises programmis täidab sama rolli meile kahendotsingpuu.

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

Nõuded
  • Leia kõik failis olevad nimekombinatsioonid (ees + perenimi).
  • Loenda mitu korda iga nimekombinatsioon esines.
  • Väljasta tulemused väljundfaili
    • NB! Kuna ülesande eesmärk on saavutada paremat jõudlust, võid puu lahenduse juures kasutada globaalset failiviita. Ära ava korduvalt oma 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 kui kaua kulus sinu programmil andmete töötlemiseks aega
    • Pead arvestama vähemalt faili lugemise ja andmestruktuuri loomise ajakuluga
    • Võid arvesse võtta ka faili kirjutamise ja vabastamise
    • Tulemused peavad olema võrreldavad! St kui üks programmidest arvestas aja sisse vabastamise, siis peab ka teine seda tegema.
  • Kuva rakenduses mitu unikaalset kombinatsiooni rakendus leidis
    • NB! Kuna rakendus peab olema
  • Print the number of unique combinations your program found
    • NB! Kuna ülesande eesmärk on saavutada paremat jõudlust, võid puu lahenduse juures kasutada globaalset loendurit.
  • Juhindu ülesande lahendamisel ajakulu optimeerimisele. Jäta struktuuri liikmeks olevad sõned staatiliseks – nt char combinedName[64]
Programm 1:Lineaarotsing

Alustuseks ava näiteprogramm  example_linear.c  ning tutvu selle ülesehituse ja sisuga. Proovi seda käivitada ja vaata väljundit.  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 ülesandele
    • Praegune versioon faili lugemisest eeldab ühte nime (ühesõnaline). Tunnitöö andmefailis on 4 välja rea kohta – eID, first name, last name and city.
    • Muuda fscanf()  funktsiooni, et see saaks hakkama täiendavate väljadega. eID ja linna salvestada vaja pole, ülesanne neid ei vaja.
    • Kleebi nimi kokku kujule  "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: sprintf() on kõige lihtsam viis nime kokku kleepida.
  2. Loenda mitu korda nimi esinenud on
    1. Lisa oma struktuuri kirjeldusse loendur – kasuta kas  int või  unsigned andmetüüpi.
    2. Enne kui hakkad oma loendamise osa kirjutama, vaata kuidas näitekoodis olev unikaalsuse kontroll ja laiendamine on ehitatud.
      Vihje: Vaata mida tagastab  CheckNameUnique()  funktsioon. Funktsiooni tagastus on võimekam kui selle praegune kasutusjuht näitekoodis.
    3. Lisa oma loendurile algväärtustamine olukorras kus said teada, et nägid nime esmakordselt (nimi ei ole massiivis).
    4. Lisa oma loenduri väärtuse uuendamine (suurendamine) olukorras, kui nimi oli korduv (juba lisatud andmebaasi).
  3. Muuda oma väljastuse funktsiooni
    1. Muuda väljastust sedasi, et tulemus kirjutataks faili
    2. Väljasta nii nimi kui korduste arv
  4. Väljasta mitu unikaalset nime kokku failist leiti
  5. Lisa andmete vabastamine
  6. Lisa aja mõõtmine
    1. Lisa 2 clock  tüüpi muutujat
    2. Pane paika 2 ajavõtupunkti – koht kust alustad aja mõõtmist (enne faili lugemist) ja koht kus lõpetad (nt enne väljastuse alustamist või pärast  mälu vabastamist)
    3. Arvuta palju aega kulus. Väljasta ajakulu.
  7. Jooksuta koodi läbi valgrindi ja veendu selle korrektsuses. Nt. valgrind ./example_linear random_people_city_data.txt
Programm 2: Kahendotsingpuu

Alustuseks ava näiteprogramm  example_bin_search_tree c  ning tutvu selle ülesehituse ja sisuga. Proovi seda käivitada ja vaata väljundit.  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. Uuenda struktuuri kirjeldust. Sul on vaja hoida seal nii sõne kui loendurit, täpselt nagu lineaarse otsingu puhul.
  2. Muuda lugemisfunktsiooni sarnaselt nagu tegid lineaarse otsinguga.
    1. Muuda fscanf() funktsiooni toetamaks failis olevat nelja parameetrit.
    2. Kleebi ees- ja perenimi kokku.
  3. Uuenda lisamise funktsiooni InsertNode()
    1. Muuda selle parameetrit, et see toetaks lisamisel sõnet (meie puhul siis nimi)
    2. Muuda võrdlemise operatsiooni. Pane tähele, et erinevalt näitekoodist peame me tuvastama ka olukorda, kui puus täpselt sama sõne juba eksisteerib. Sellisel juhul peame loendurit uuendama.
  4. Uuenda uue tipu loomise funktsiooni CreateNode()
    1. Muuda parameetrit, et sinna saaks edastada nime
    2. Lisa loenduri 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 võid  sel korral failiviida luua globaalse muutujana. Muidugi kohustust pole, võid vabalt ka selle parameetrina edastada.
    • Muuda puu läbikäiku. Näites 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, järe või keskjärjestus). Vale meetodi puhul ei ole võimalik puud vabastada.
  7. Lisa aja mõõtmine
  8. Jooksuta koodi läbi valgrindi ja veendu selle korrektsuses. Nt. valgrind ./example_bin_search_tree random_people_city_data.txt
Programmi tööaja võrdlemine

Nüüd võrdle mõlema programmi ajakulu. Kumb on aeglasem, miks?

Mõtle ka kuidas võiks ajakulu muutuda kui

  • Muudaksid realloc()  mälu laiendamise strateegia (n + 1) pealt  (n * 2) peale lineaarotsingul.
  • Unikaalsete nimede arv suureneks märkimisväärselt. Kuidas kumbki rakendus sellele reageeriks – ürita väljendada end Big O  notatsiooni kasutades (https://www.bigocheatsheet.com)
  • Failis oleks märkimisväärselt rohkem nimesid, kuid unikaalsete nimede arv jääks samaks (tõuseks korduste arv)
  • Kui lahendasid ka edasijõudnute ülesande, siis kaasa samasse võrdlusse ka trie andmestruktuur. Kas sellel on ka mõni märkimisväärne eelis tavalise kahendotsingpuu ees?
Testimine

Järgnevad näited sisaldavad väljundit kõigi kolme versiooni tulemustefaili algusest. Võrdle enda loenduse tulemusi allolevatega.

Kokku peab olema  11440 unikaalset nimekombinatsiooni.

NB! Näidetes on ainult rakenduste arvutustulemused, et saaksid neid enda omadega võrrelda. Tegu ei ole programmi väljundiga – programm peab väljastama palju unikaalseid nimekombinatsioone esines ning kui kaua rakenduse töö kestis.

Lineaarne otsing
Kahendotsingpuu ja Trie

Edasijõudnute ülesanne: 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

Täiendav materjal