UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO
FAKULTETA ZA RAUNALNITVO IN INFORMATIKO Ra£unalni²tvo in matematika 2. stopnja
Delna Bari²a
GRAFINI PRIKAZ KAKOVOSTI ALGORITMOV
Magistrsko delo
Mentor: doc. dr. Tomaº Dobravec
Ljubljana, 2021
Zahvala
Iskreno se zahvaljujem mentorju doc. dr. Tomaºu Dobravec za pomo£ in vodenje pri izdelavi magistrske naloge.
Velika zahvala gre tudi moji druºini, Tomiju in prijateljem, ki so me ves £as
²olanja in pisanja magistrske naloge motivirali, bodrili in mi stali ob strani.
Kazalo
Program dela vii
1 Uvod 1
2 Gra£na predstavitev podatkov 3
2.1 Gra£ni prikaz podatkov s tabelo . . . 3
2.1.1 Primeri dobre prakse gra£nega prikaza podatkov s tabelo . . 4
2.1.2 Funkcionalnost ne stati£nosti . . . 5
2.2 Prikaz podatkov z grakonom . . . 6
2.2.1 Primeri dobre prakse prikaza podatkov z grakonom . . . 7
2.3 Prikaz podatkov za ljudi z omejitvami . . . 9
3 Gra£ni prikaz kakovosti algoritmov 13 3.1 Podatki v algoritmiki . . . 14
3.1.1 Parameter . . . 14
3.1.2 Indikator . . . 14
3.2 Gra£ni prikaz kakovosti algoritma s tabelo . . . 16
3.2.1 Tabelari£ni prikaz kakovosti enega algoritma . . . 17
3.2.2 Tabelari£ni prikaz kakovosti grupiran po algoritmih v stolpcih 18 3.2.3 Tabelari£ni prikaz kakovosti grupiran po indikatorjih v stolpcih 20 3.2.4 Tabelari£ni prikaz kakovosti grupiran po algoritmih v vrsticah 21 3.3 Gra£ni prikaz kakovosti algoritma z grakonom . . . 23
3.3.1 Prikaz kakovosti algoritma s £rtnim grakonom . . . 24
3.3.2 Prikaz kakovosti algoritma s pali£nim in stolp£nim grakonom 26 3.3.3 Prikaz kakovosti algoritma s ²katlastim grakonom . . . 30
3.3.4 Prikaz kakovosti algoritma s £rtnim in stolp£nim grakonom . 33 3.3.5 Prikaz kakovosti algoritma z mehur£nim grakonom . . . 35
3.3.6 Prikaz kakovosti algoritma s polarnim grakonom . . . 37
3.3.7 Prikaz kakovosti algoritma z grakonom vzporednih koordinat 40 3.3.8 Prikaza kakovosti algoritma s £asovnicami s krogi . . . 43
3.3.9 Prikaza kakovosti algoritma s toplotnim zemljevidom . . . 45
4 Implementacija v sistemu ALGator 51 4.1 Sistem ALGator . . . 51
4.2 ALGatorjeva stran za gra£ni prikaz kakovosti algoritmov . . . 53
4.3 Implementacija tabel . . . 56
4.3.1 Implementacija novih tabelari£nih prikazov . . . 58
4.4 Implementacija grakonov . . . 61
4.4.1 Implementacija £rtnega, pali£nega, plo²£inskega, tortnega in kolobarnega grakona . . . 65
4.4.2 Implementacija tridimenzionalnega stolp£nega grakona . . . 75
4.4.3 Implementacija ²katlastega grakona . . . 78
4.4.4 Implementacija polarnega grakona . . . 80
4.4.5 Implementacija toplotnega zemljevida . . . 83
4.4.6 Implementacija pali£nega grakona z isto osjo . . . 85
4.4.7 Implementacija vzporednih koordinat . . . 88
5 Zaklju£ek 93
Literatura 95
Program dela
Pri ocenjevanju kakovosti implementacij algoritmov imamo opravka z veliko koli£ino podatkov, ki predstavljajo vrednosti indikatorjev izvajanja izbranih algoritmov na vnaprej dolo£enih testnih primerih. Obdelava teh podatkov vklju£uje tudi razli£ne gra£ne in tabelari£ne prikaze, s pomo£jo katerih raziskovalec izvaja primerjave in ugotavlja prednosti in slabosti posameznega algoritma v primerjavi z ostalimi v analizo vklju£enimi algoritmi.
V magistrskem delu preglejte podro£je gra£nega prikaz podatkov v obliki gra- konov in tabel. Pri tem se posebej osredoto£ite na prikaze, ki so primerni za analizo kakovosti algoritmov. Opi²ite najpogosteje uporabljane prikaze in njihove zna£ilno- sti ter predstavite primere analize algoritmov, kjer lahko posamezen prikaz smiselno uporabimo. Izbrane prikaze implementirajte v programskem jeziku JavaScript in jih vklju£ite v sistem za avtomatsko analizo algoritmov ALGator. S pomo£jo realnih podatkov, pridobljenih s pomo£jo sistema ALGator pri izvajanju izbranih algorit- mov, izdelajte konkretne primere grafov in tabel ter opi²ite prednosti in slabosti teh prikazov v primerjavi z obstoje£imi.
Osnovna literatura
[30] C. C. McGeoch, A Guide to Experimental Algorithmics, Cambridge University Press, New York, 2012
[11] T. Dobravec, Chapter two - algatoran automatic algorithm evaluation sy- stem, Elsevier, Advances in Computers 116, 2020, str. 65131, doi: https:
//doi.org/10.1016/bs.adcom.2019.07.002
[35] S. K. Patra, Data visualization for hybrid application: the challenges in choo- sing an optimal library for line chart, Int. J. Emerg. Sci. Eng.(IJESE) 2(10) (2014) 1215
Podpis mentorja:
Gra£ni prikaz kakovosti algoritmov Povzetek
Za ve£ino ºivljenjskih teºav obstaja ve£ moºnih re²itev. Enako velja tudi v algo- ritmiki, saj za skoraj vsak problem obstaja ve£ algoritmi£nih re²itev. Na koncu izberemo tisto, ki ima najbolj²o kakovost. Slednjo obi£ajno ocenimo tako, da na- redimo primerjavo rezultatov izvajanja razli£nih algoritmov. Ti rezultati na£eloma vsebujejo ogromno koli£ino podatkov, zato jih je velikokrat najenostavneje primer- jati s pomo£jo gra£nih prikazov.
Na Fakulteti za ra£unalni²tvo in informatiko je bil izdelan sistem za avtomatsko evalvacijo algoritmov ALGator. Kot pove ºe samo ime, ta olaj²a in avtomatizira postopek ocenjevanja algoritmov. V njem lahko uporabnik enostavno in hitro pride do rezultatov izvajanja algoritmov. Za gra£no primerjavo teh podatkov je obstoje£i sistem omogo£al le prikaz nekaterih preprostih grakonov in tabel. Pojavile so se zahteve po novih prikazih, ki bi nudili podporo kompleksnej²i analizi podatkov in tem zahtevam smo sku²ali zadostiti s pri£ujo£o magistrsko nalogo.
Najprej smo preu£ili dva najpogosteje uporabljena gra£na prikaza, tabelo in grakon. Podali smo splo²en opis ter predstavili njune primere dobre prakse ter prilagoditve za osebe z omejitvami. Vsaka razli£ica tabele in grakona je primerna samo za dolo£eno vrsto podatkov. Zato smo v delu pregledali podatke v algoritmiki, raziskali vse primerne vrste tabel in grakonov ter prilagodili raziskane razli£ice za prikaz kakovosti algoritmov. Med njimi smo izbrali najbolj²e in jih implementirali v sistemu ALGator. Na koncu dela smo predstavili sistem ALGator in orodja, ki so uporabljena pri implementaciji prikazov ter opisali implementirano.
Math. Subj. Class. (2010): 68Q25, 68W40
Klju£ne besede: vizualizacija podatkov, vizualizacija podatkov v algoritmiki, gra-
£ni prikaz kakovosti algoritmov, sistem ALGator
Graphical representation of the quality of algorithms Abstract
There are usually several possible solutions for most life problems. The same is true for algorithmics, as there are several algorithmic solutions for almost every problem. In the end, we choose the one that has the best quality. The latter is usually estimated by comparing the results of the execution of dierent algorithms.
Usually, these results contain huge amounts of data, so it is often easiest to compare them with the help of graphical representations.
A system for automatic evaluation of algorithms named ALGator was developed at the Faculty of Computer and Information Science in Ljubljana. As the name suggests, it simplies and automates the algorithm evaluation process. With it, the user can easily and quickly get the results from the execution of algorithms. To graphically compare this data, the existing system only allowed the display of some simple graphs and tables. There was a demand for new displays that would support more complex data analysis, and we tried to meet these demands with this master's thesis.
We rst examined the two most commonly used graphical representations, the table and the graph. We gave a general description and presented their examples of good practice and their adaptations for people with limitations. Each version of the table and chart is only suitable for a specic type of data. Therefore, in the thesis we reviewed the data in algorithmics, researched all suitable types of tables and graphs, and adapted the researched versions for representations of the quality of algorithms.
We chose the best among them and implemented them in the ALGator system. At the end of the thesis, we presented the ALGator system and the tools used in the implementation of graphical representations and described the implementations.
Math. Subj. Class. (2010): 68Q25, 68W40
Keywords: Data visualization, Graphical representation of the quality of algori- thms, ALGator system
1 Uvod
Ljudje skozi ºivljenje naletimo na ²tevilne probleme. Dandanes je tehnologija tako napredovala, da jih s pomo£jo ra£unalnika lahko re²imo zelo hitro in u£inkovito.
Potreben pogoj za to je, da najprej programerji implementirajo algoritem, ki re²i dolo£en problem. Skoraj vsak problem v ºivljenju je moºno re²iti na ve£ razli£nih na£inov. Tako je tudi v ra£unalni²tvu, saj lahko obstaja ve£ razli£nih algoritmov, ki re²ijo dan problem. Algoritmi, ki re²ujejo isti problem se lahko med seboj zelo razlikujejo, saj imajo razli£ne kakovosti na razli£nih podro£jih, eni so bolj²i, drugi so slab²i.
Obstaja kar nekaj sistemov, ki omogo£ajo primerjavo algoritmov. V magistrski nalogi smo uporabili sistem za avtomatsko evalvacijo algoritmov ALGator. Primer- javo kakovosti algoritmov naredimo tako, da primerjamo rezultate izvajanja. To pomeni, da kakovost dolo£imo preko podatkov, ki jih dobimo pred, med in po izva- janju algoritmov. Tu pa se pojavi teºava, saj je lahko teh podatkov ogromno. Skozi
£as so ljudje iskali in raziskovali na£ine, na katere bi podatke predstavili na enosta- ven, u£inkovit in razumljiv na£in. Iz tega razloga so se do dana²njega dne razvile
²tevilne prestavitve podatkov. Od pojava ra£unalnikov se je ²tevilo informacij ²e pove£alo, zato je zacvetelo podro£je gra£ne predstavitve podatkov.
Obstaja veliko razli£nih gra£nih prikazov, v magistrski nalogi pa smo se osre- doto£ili na dva najbolj uporabljena, tabelo in grakon. Da bi bili prikazi £imbolj prijazni za uporabnika, je najprej potrebno raziskati primere dobre in slabe prakse prikazov ter ugotoviti, kako jih lahko prilagodimo za osebe z razli£nimi omejitvami, kot sta na primer daljnovidnost in barvna slepota. Nato pa je potrebno poiskati ²e vse moºne razli£ice, ki so primerne za prikaz kakovosti algoritmov in jih primerno prilagoditi. Obstaja ve£ spletnih strani, orodij in sistemov, ki omogo£ajo nalaganje in primerjavo algoritmov, za katere bo na²a raziskava zelo koristila. Mi se bomo osredoto£ili na sistem ALGator.
V sistemu ALGator so bili prvotno ºe implementirani osnovni gra£ni prikazi, cilj magistrske naloge je, da se sistem obogati ter doda nove, ki bodo uporabnikom dodatno olaj²ali delo. Da bi to bilo mogo£e, je najprej potrebno iti skozi vse opisane korake in nato ugotovitve implementirati v sistem ALGator.
V magistrski nalogi sta zato najprej v drugem poglavju raziskana dva najbolj uporabljena gra£na prikaza, tabela in grakon. V raziskavi so vklju£eni tudi primeri dobre in primeri slabe prakse ter prilagoditve za ljudi z omejitvami.
V tretjem poglavju so najprej opisani podatki, ki so prisotni v algoritmiki. Nato so raziskane vse moºne razli£ice grakonov in tabel, ki bi bile primerne za dane podatke. Vsaka razli£ica je sproti tudi prilagojena tako, da je primerna za prikaz kakovosti algoritmov.
V £etrtem poglavju je najprej opisan sistem ALGator in orodja, ki so bila upo- rabljena pri implementaciji gra£nih prikazov v sistemu ALGator. Med predstavlje- nimi prikazi iz drugega poglavja so nato izbrani prikazi, iz katerih je najbolj eno- stavno razbrati kakovost enega algoritma ali primerjavo kakovosti ve£ algoritmov na enem ali ve£ podro£jih. Ti so nato implementirani. Na koncu je implementirano tudi opisano.
2 Gra£na predstavitev podatkov
Skozi £as so ljudje iskali in raziskovali na£ine s katerimi bi podatke predstavili na enostaven, u£inkovit in razumljiv na£in. Iz tega razloga so se do dana²njega dne razvile ²tevilne prestavitve podatkov. Od pojavitve ra£unalnikov pa se je ²tevilo informacij ²e pove£alo, zato je zacvetelo podro£je gra£ne predstavitve podatkov.
Obstaja veliko razli£nih gra£nih prikazov, mi se bomo osredoto£ili predvsem na dve vrsti prikazov. To sta gra£ni prikaz podatkov s tabelo in gra£ni prikaz podatkov z grakonom. Prikaz podatkov s tabelo bomo podrobneje predstavili v poglavju 2.1, prikaz podatkov z grakonom pa bomo predstavili v poglavju 2.2. Med nami so tudi ljudje z razli£nimi po²kodbami vida, zato je potrebno gra£ne prikaze prilagoditi tako, da so ti tudi njim razumljivi. V poglavju 2.3 bomo opisali, kako moramo prilagoditi gra£ne predstavitve podatkov, da bodo primerne za ljudi z razli£nimi omejitvami, kot sta na primer daljnovidnost in barvna slepota.
2.1 Gra£ni prikaz podatkov s tabelo
Tabele so ene izmed najstarej²ih vrst gra£ne predstavitve podatkov. Najstarej²a ohranjena tabela je bila ustvarjena v drugem stoletju v Egiptu. Vsebovala je astro- nomske informacije in se je uporabljala za navigacijo [12].
Skozi £as so ugotovili, da so zelo uporabne zaradi £esar so se za£ele uveljavljati na ²tevilnih podro£jih. Iz tega razloga obstaja ve£ denicij tabel, ki so odvisne od podro£ja na katerem se uporabljajo. Ve£ina denicij pravi, da so tabele predvsem tekstovni prikazi podatkov v vrsticah in stolpcih [12].
Do sedaj so se razvile ²tevilne vrste gra£nih predstavitev podatkov. Posledi£no so ljudje za£eli raziskovati kdaj je in kdaj ni primerno uporabiti dolo£ene predsta- vitve ter katere so prednosti in katere so slabosti dolo£ene predstavitve. Za tabelo se je izkazalo, da ima naslednje prednosti:
• v njej so lahko zapisane to£ne vrednosti,
• je enostavna za izdelavo,
• je enostavna za razumevanje,
• predstavlja kompakten prikaz in
• je dober prikaz za nepovezane instance [44].
V primeru ra£unalni²kega gra£nega prikaza podatkov s tabelo ima ta prikaz ²e eno pomembno prednost oziroma funkcionalnost, ki jo ponuja. Poimenovali jo bomo ne stati£nost. Ta zelo pripomore k laºjemu razumevanju podatkov, ki jih ºelimo prikazati, zato jo bomo predstavili v posebnem poglavju 2.1.2. Izkazalo se je tudi, da ima tabela naslednje slabosti:
• ni primerna za velike mnoºice podatkov, saj imamo potem preveliko ²tevilo vrstic in/ali stolpcev,
• v£asih je tak²en prikaz nezanimiv in
• njen izgled ni najbolj vizualen [44].
Po na²tetih prednostih in slabostih lahko sklepamo, da je gra£ni prikaz podatkov s tabelo najbolj²a izbira v spodnjih primerih.
• Za podatke, ki jih je teºko predstaviti vizualno [4].
• Za podatke, ki jim ºelimo nameniti ve£ pozornosti. Torej v tistih primerih, ko bodo bralci ºeleli analizirati to£ne vrednosti in ne pribliºke [4].
• Ko ºelimo oceniti nabore podatkov z ve£ dimenzijami in vrednostmi ter ne ºelimo ustvariti zapletenih vizualizacij [4].
• Ko vemo, da bo ciljni uporabnik ºelel iz podatkov najti vzorce in poiskati vzroke zanj [4].
• Ko ºelimo analizirati podatke, kjer kot parameter uporabimo datum [4].
Ko se enkrat odlo£imo za dolo£en prikaz, ga je potrebno tudi primerno oblikovati.
Zato bomo v naslednjem poglavju 2.1.1 opisali primere dobre prakse oblikovanj informacij v tabeli.
2.1.1 Primeri dobre prakse gra£nega prikaza podatkov s tabelo
Pri gra£ni predstavitvi podatkov s tabelo si ºelimo, da bi kon£ni uporabnik £im laºje in £im hitreje razbral podatke. Da bi bilo to mogo£e, moramo upo²tevati primere dobre prakse oblikovanj podatkov v tabelah.
Pomembno je, da uporabljamo dovolj belega prostora in pravilno poravnavo teksta ter ²tevil. Priporo£ljivo je da (povzeto po [26]):
• Stolpce, ki vsebujejo tekst in ²tevila poravnamo desno.
• Stolpce, ki vsebujejo samo ²tevila poravnamo desno.
• Izklju£no tekstovna polja poravnamo levo.
S prevelikimi razmiki med vrsticami se zelo zmanj²a preglednost tabele. Zato je priporo£ljivo, da med posameznimi vrsticami pustimo ravno toliko praznega pro- stora, da ga opazimo [26].
tevila v tabelah naj bodo poravnana glede na decimalne vejice. Priporo£ljiva pa je tudi uporaba lo£il za tiso£ice [26].
Izogibati se moramo uporabi robnih £rt oziroma obrob. Te namre£ povzro£ajo opti£no iluzijo videnja sivih pik na prese£i²£ih £rnih £rt, kar pa odvra£a pozornost od prikazanih podatkov. Kot alternativo obrobam lahko uporabljamo alternirajo£e obarvano ozadje posameznih vrstic. Barve, ki jih uporabljamo morajo biti svetle in nevpadljive. e pa ºe moremo uporabljati obrobe za lo£evanje posameznih vrstic, naj bodo te £rte subtilne in £im tanj²e [26].
Pozorni moramo biti tudi na gostoto podatkov. Prevelika gostota povzro£a, da kon£ni uporabniki iz predstavitve teºko hitro razberejo pomembne informacije [26].
Za izbiro tipa pisave se priporo£ajo sans-serif tipi kot so Arial, Verdana in Hel- vetica. Ti so berljivi tudi pri manj²i velikosti pisave. Za hitrej²o berljivost je pripo- ro£ljiva tudi uporaba krepkega tiska za naslove vrstic in stolpcev [26].
2.1.2 Funkcionalnost ne stati£nosti
Velikokrat se zdi, da ne vemo kateri podatki v tabeli bodo uporabnikom bolj po- membni in kateri manj pomembni. V teh primerih je priporo£ljivo tabelo imple- mentirati tako, da ni stati£na. Dve najpomembnej²i funkcionalnosti pri ne stati£nih tabelah sta urejanje po stolpcih in iskanje po vrsticah. Tretja funkcionalnost, ki ve- likokrat pride prav pa je uporaba barv [32]. Za laºje razumevanje bomo pri razlagi vseh treh funkcionalnosti uporabili primer, ki je prikazan v tabeli 2.1. Ta prikazuje rezultate tekmovalcev iz logike. Vidimo, da tabela vsebuje tri stolpce:
• prvi stolpec: ime in priimek tekmovalca,
• drugi stolpec: ²tevilo doseºenih to£k na tekmovanju in
• tretji stolpec: razred, ki ga obiskuje tekmovalec.
Tabela 2.1: Primer za prikaz funkcionalnosti tabel Ime in priimek Doseºene to£ke Razred
Simon Pirc 123 3
Kaja Novak 78 2
Sabina Kralj 130 3
Matej Medved 100 3
Ana Cizelj 105 3
Nik Kova£i£ 80 2
Prva funkcionalnost je urejanje po stolpcih. Pri njej lahko uporabnik dolo£i ali bodo vrednosti v dolo£enem stolpcu razvr²£ene nara²£ajo£e ali padajo£e. Temu primerno se razvrstijo celotne vrstice v tabeli [32]. Podajmo ²e prakti£ni primer funkcionalnosti. Recimo, da ºeli uporabnik razvrstiti vrstice nara²£ajo£e glede na doseºene to£ke. Tabela 2.2 prikazuje rezultat urejanja stolpca doseºenih to£k nara-
²£ajo£e.
Tabela 2.2: Primer funkcionalnosti urejanja po stolpcih Ime in priimek Doseºene to£ke Razred
Sabina Kralj 130 3
Simon Pirc 123 3
Ana Cizelj 105 3
Matej Medved 100 3
Nik Kova£i£ 80 2
Kaja Novak 78 2
Druga funkcionalnost je iskanje po vrsticah. Pri njej lahko uporabnik i²£e po vrsticah. To pomeni, da lahko uporabnik izvede poizvedbo na tabeli in se mu izpi-
²ejo samo tiste vrstice, ki ustrezajo tej poizvedbi [32]. Recimo, da ºeli uporabnik imeti izpisane samo doseºene to£ke tistih tekmovalcev, ki obiskujejo tretji razred ("Rezred == 3"). Tabela 2.3 prikazuje rezultat tak²ne poizvedbe.
Tabela 2.3: Primer funkcionalnosti iskanja po vrsticah Ime in priimek Doseºene to£ke Razred
Sabina Kralj 130 3
Simon Pirc 123 3
Ana Cizelj 105 3
Matej Medved 100 3
Tretja funkcionalnost je uporaba barv. Ta usmeri uporabnikovo oko do zanimi- vih/pomembnej²ih informacij in jim pomaga z navigacijo po tabeli. Temu je tako zato, ker je barva mo£no orodje, ki pripomore k izstopanju pomembnej²ih informa- cij. Tako lahko na primer uporabimo razli£ne barve za razli£ne kategorije ali pa obarvamo najvi²je in najniºje vrednosti v vseh ali samo dolo£enih stolpcih. Pozorni moramo biti, da uporabimo razli£ne barve [32]. Podajmo ²e prakti£ni primer. Re- cimo, da si uporabnik ºeli hitro videti najmanj²e in najve£je ²tevilo doseºenih to£k.
Da bo ti dve informaciji lahko hitro videl, bomo najve£jo vrednost v tem stolpcu obarvali z zeleno in najmanj²o z rde£o. Primer je prikazan v tabeli 2.4.
Tabela 2.4: Primer funkcionalnosti uporabe barv Ime in priimek Doseºene to£ke Razred
Simon Pirc 123 3
Kaja Novak 78 2
Sabina Kralj 130 3
Matej Medved 100 3
Ana Cizelj 105 3
Nik Kova£i£ 80 2
2.2 Prikaz podatkov z grakonom
Prva vizualna oblika podatkov, ki je podobna dana²njim grakonom, je nastala veliko pozneje od prve tabele, in sicer v 17. stoletju. Takrat je francoski lozof in matematik izumil metodo za predstavitev koli£inskih podatkov. Ta prvotno ni bila namenjena predstavitvi podatkov, ampak za izvajanje vrste matematike, ki temelji
na sistemu koordinat. Komaj konec 18. stoletja in v za£etku 19. stoletja je ²kotski druºboslovec izumil in izbolj²al grafe, ki jih uporabljamo ²e danes. Med te grafe
²tejemo tudi tortne in stolp£ne diagrame. Po tem je minilo ve£ kot stoletje preden so postale tak²ne tehnike cenjene do te mere, da so bile akademsko priznane. V drugi polovici 19. stoletja pa je profesor statistike iz Princetona predstavil mo£
vizualizacije podatkov za raziskovanje in iskanje smisla v podatkih [12].
Pri ve£ini denicijah je grakon matemati£ni diagram, ki prikazuje razmerje med dvema ali ve£ mnoºicami ²tevil ali meritev [10]. Obstaja ve£ vrst grakonov, s katerimi lahko predstavimo informacije. Najpogosteje uporabljeni so £rtni, stolp£ni, tortni, pali£ni, raztreseni, plo²£inski, mehur£ni in cilindri£ni.
Do sedaj so se razvile ²tevilne vrste gra£nih predstavitev podatkov. Posledi£no so ljudje za£eli raziskovati kdaj je in kdaj ni primerno uporabiti dolo£ene predstavi- tve ter katere so prednosti in katere so slabosti dolo£ene predstavitve. Za grakone se je izkazalo, da imajo naslednje prednosti:
• ponujajo informacije v vizualno privla£ni obliki,
• ponujajo informacije v hitro razumljivi obliki,
• iz njih lahko razberemo "obliko"in vzorce podatkov,
• prikazujejo relacije med podatki in
• ponujajo enostavno vizualizacijo tudi, ko imamo veliko zbirko podatkov [4].
Izkazalo se je tudi, da imajo grakoni naslednje slabosti:
• iz njih ni moºno razbrati natan£nih vrednosti in
• ni najbolj²i prikaz za nepovezane instance [4].
Po na²tetih prednostih in slabostih lahko sklepamo, da uporabimo grakone namesto tabel takrat, ko:
• so zbirke podatkov velike in komplekse,
• razkrivamo odnose oziroma povezave med ²tevilnimi vrednostnimi podatki in
• je glavna sporo£ilnost v obliki in distribuciji podatkov [26].
Tako kot pri tabelah, moramo tudi pri grakonih za hitrej²o in enostavnej²o razumevanje podatkov upo²tevati primere dobre prakse oblikovanja. Zato bomo v naslednjem poglavju 2.2.1 opisali primere dobre prakse oblikovanj informacij v grakonih.
2.2.1 Primeri dobre prakse prikaza podatkov z grakonom
Oblikovanje grakona je precej zahtevnej²e od oblikovanja tabele. Razlog za to je ta, da moremo ob razumevanju predstavljenih podatkov tudi predvideti kako bo kon£ni uporabnik razumel in sprejel gra£ne elemente, ki so del grakona [26]. Za laºjo predstavo so na sliki 2.1 prikazani deli grakona.
Slika 2.1: Deli grakona (slika je povzeta iz [26, 25]) Lastnosti dobrih grakonov so (povzeto po [26]):
• Naslov grakona naj bo pri znanstvenih predstavitvah namenjen deniranju zbirke podatkov, ki je prestavljena v grakonu. Pri publicisti£nem sporo£anju pa naj povzame zaklju£ke, ki bi jih moral uporabnik zaklju£it glede na vsebino grakona.
• Naslovi osi naj bodo jedrnat in £im kraj²i.
• Skale osi in oznake podatkov predstavljajo velikosti oziroma vrednosti glavnih elementov na grakonu. Priporo£ljivo je, da se izogibamo ozna£evanju vsake to£ke na grakonu z oznakami podatkov. e je tak²no ozna£evanju nujno potrebno, je obi£ajno tovrstne podatke bolje prikazati v tabelari£ni obliki.
• Legende se v grakonih uporabljajo za analiziranje ve£ zbirk podatkov. Po- membno je, da se te nahajajo na mestu, kjer ne zmanj²ujejo prostora za gra-
£ne elemente, ki prikazujejo podatke ter, da se nahajajo znotraj grakona.
• Odsvetuje se uporaba mreºnih £rt. e so res nujno potrebne, naj bodo tanke in naj ne zasen£ijo prikaza pomembnih elementov.
• e do podatkov nismo pri²li z lastnimi meritvami je pomembno, da navedemo vir. S tem zagotovimo, da so podatki, ki jih bomo prikazali preverljivi in verodostojni.
• Vsem elementom, ki ne pripomorejo k razumevanju podatkov, ki jih ºelimo predstaviti, se moramo izogniti. Razna barvna ozadja, sen£enja in obrobe zmanj²ujejo berljivost.
• Ob vsem na²tetim pa je bistvenega pomena ºe na samem za£etku izbrati tip grakona, ki bo najbolje vizualno predstavil na²e informacije. Torej tako, da bo predstavljene informacije kon£ni uporabnik enostavno in hitro razumel.
Spoznali smo obe vrsti gra£nih predstavitev, ki jih bomo uporabljali v magistr- ski nalogi. V naslednjem poglavju 2.3 pa si bomo ogledali kako gra£no predstavitev oblikovati tako, da bo primerna tudi za tiste, ki so barvno slepi ali pa imajo teºave z daljnovidnostjo.
2.3 Prikaz podatkov za ljudi z omejitvami
Tone Pav£ek v Pesmi o zvezdah pravi: "Vsak £lovek je zase svet, £uden, svetal in lep kot zvezda na nebu ....". Z njim se moremo strinjati, saj ima vsak £lovek svoje prednosti, posebnosti in omejitve. Slednje so lahko prirojene ali pa jih £lovek pridobi pozneje v ºivljenju. Prav je, da smo ljudje solidarni med seboj in £e je le moºno prilagodimo svoja dela tako, da so primerna za £im ²ir²o mnoºico. Prikaz podatkov je predvsem vidni proces, zato bomo v magistrski nalogi premisli katere so pogoste vidne omejitve pri ljudeh in poiskali na£ine, da bo na² kon£ni produkt primeren za njih.
Veliko ljudi med nami je daljnovidnih. To pomeni, da ne vidijo predmetov v bliºini. Ta teºava se obi£ajno korigira s kontaktnimi le£ami, konveksnim steklom ali pa operativno. Pri gra£ni predstavitvi podatkov pa lahko pripomoremo tako, da v prikaz uvedemo pove£evalno steklo s katerim si lahko uporabnik z daljnovidnostjo pribliºa dele, ki jih slab²e vidi [40]. Primer tak²nega gra£nega prikaza je prikazan na sliki 2.2.
Slika 2.2: Primer gra£nega prikaza, ki omogo£a pove£evanje delov prikaza [13].
Naslednja skupina ljudi, za katere lahko primerno priredimo vizualizacijo so barvno slepi ljudje. Barvni slepoti pravimo tudi daltonizem. Na svetu je pribli- ºno 300 milijonov ljudi z barvno slepoto. To je zdravstveno stanje, pri katerem je oslabljena sposobnost razlikovanj nekaterih barv v barvnem spektru. Med temi ljudmi so nekateri, ki sploh ne vidijo barv, torej so omejeni s £rno-belimi barvami.
Drugi ne morejo razlikovati barv in odtenkov zelenega spektra (Deeranopija), mo- drega spektra (Tritanopija) ali rde£ega spektra (Protanopija). Tretji pa lahko vidijo barve, a ne morejo lo£iti ve£ine odtenkov med sabo [23].
Barvna slepota je malo bolj kompleksna kot daljnovidnost, zato si bomo zanjo vzeli malo ve£ £asa. Najprej bomo opisali kak²ne teºave imajo barvno slepi ter kako jih lahko odpravimo [23].
Da si bomo laºje predstavljali s £im se soo£ajo barvno slepi, si naprej oglejmo kako vidijo barve dolo£ene skupine barvno slepih ljudi in kak²ne teºave imajo zaradi tega. Na sliki 2.3 je prikazana ra£unalni²ka simulacija kako dolo£ene barve vidijo Protanopi, Deeranopi in Triranopi [23]. Opazimo lahko, da te skupine barvno slepih nekaterih barv ne morajo razlikovati. Posledi£no se tem skupinam pojavljajo spodaj napisane teºave.
• Ne vidijo nekaterih objektov. Na primer ne vidijo temno rde£ih in magentnih simbolov ter tankih £rt na £rnem ali temno modrem ozadju [23].
• Teºko razberejo poudarjene dele. Na primer temno rde£e £rke v £rnem bese- dilu, ki jih velikokrat uporabljamo za poudarek pomembnih pojmov. Tistim barvno slepim, ki ne razlikujejo barv in odtenkov rde£ega spektra se zdi temno rde£a podobna £rni [23].
• Zelo teºko povedo imena barv [23].
Slika 2.3: Slika prikazuje kako mnoºico 24 barv vidijo Protanopi, Deeranopi in Triranopi (slika je povzeta iz [23])
e ºelimo narediti vizualizacijo, ki bo prijaznej²a in razumljivej²a za barvno slepe, je priporo£ljivo upo²tevati spodnje napotke.
Prvo priporo£ilo je, da informacij, ²e posebej tistih pomembnih, ne podajamo samo z barvami. Bolje je, da razlike pokaºemo z barvo in obliko, ne pa samo z barvo.
Tako lahko ob barvi uporabimo tudi:
• polne in razli£no £rtaste/pik£aste £rte,
• kroge, trikotnike, pravokotnike ter
• abecedo in ²tevila [23].
Primer prikazuje slika 2.4, na kateri je na levi strani prikazan manj primeren, na desni pa bolj primeren prikaz za barvno slepe [24].
Slika 2.4: Prikaz slabega in dobrega prikaza za barvno slepe (slika je povzeta iz [24])
Drugo priporo£ilo je, da uporabimo £im manj²e ²tevilo barv. Bolje je uporabiti kombinacijo razli£nih simbolov z nekaj ºivimi barvami kot pa en simbol z razli£nimi barvami.
Tretje priporo£ilo je, da se izogibamo, da bi ozadje prevladalo nad besedilom in objekti. To pomeni, da se moramo izogibati barvnim kombinacijam, ki imajo enako svetlobo in se razlikujejo samo po barvnem tonu. Na primer rde£a pisava na zelenem ozadju ni berljiva za barvno slepe. Priporo£ljivo je uporabljati svetlo besedilo oziroma objekte na temnih ozadjih in obratno.
etrto priporo£ilo je, da se v gra£nem prikazu in njegovem opisu raje izogibamo razlage z imeni barv.
Ljudje z barvno slepoto teºko lo£ijo barve tankih £rt in majhnih simbolov, zato je peto poro£ilo, da za barvno besedilo uporabljamo krepke pisave, kot sta Arial ali Helvetica in ne tankih pisav kot sta Times in NewYork.
esto priporo£ilo je, da moramo biti zelo pazljivi pri uporabi rde£e barve. Za barvno slepe, ki ne razlikujejo barv in odtenkov rde£ega spektra, se zdi temno rde£a podobna £rni. e pa obvezno ºelimo uporabiti temno rde£o barvo, pa je bolje, da jo zamenjamo z vermilion ali svetlo rde£o.
Zadnje priporo£ilo pa je namenjeno za tiste primere, ko moramo oziroma ºelimo uporabljati barve. Takrat je najbolje uporabiti barvno paleto, ki je prikazana na sliki 2.5 in:
• je nedvoumna tako za tiste, ki so barvno slepi kot za tiste, ki niso,
• uporablja ºive barve, katere imena je enostavno prepoznati in
• je primerna za prikaz na zaslonu ter za tisk na tiskalniku [24].
Slika 2.5: Barve primerne za barvno slepe ljudi [13] (slika je povzeta iz [24]) Sedaj, ko smo podrobneje spoznali gra£ne predstavitve podatkov in prilagoditve na katere moramo biti pozorni, se bomo v naslednjem poglavju podrobneje osredo- to£ili na gra£ni prikaz podatkov na podro£ju kakovosti algoritmov. To pomeni, da bom za podatke, ki jih dobimo pred, med in po izvajanju algoritma poiskali gra-
£ne prikaze s pomo£jo katerih bo £im bolj enostavno razbrati kakovost algoritma na enem ali ve£ podro£jih.
3 Gra£ni prikaz kakovosti algoritmov
V prej²njem poglavju smo na splo²no opisali gra£ne prikaze podatkov. V tem po- glavju pa se bomo osredoto£ili na gra£ni prikaz podatkov na speci£nem podro£ju, in sicer na podro£ju kakovosti algoritmov.
Ljudje skozi ºivljenje naletimo na ²tevilne probleme. Dandanes je tehnologija tako napredovala, da jih s pomo£jo ra£unalnika lahko re²imo zelo hitro in u£inko- vito. Potreben pogoj za to je, da najprej programerji implementirajo algoritem, ki re²i dolo£en problem. Skoraj vsak problem v ºivljenju je moºno re²iti na ve£
razli£nih na£inov. Tako je tudi v ra£unalni²tvu, saj lahko obstaja ve£ razli£nih al- goritmov, ki re²ijo dan problem. olski primer ra£unalni²kega problema, ki ima ve£
moºnih implementacij re²itve, je urejanje ²tevil v tabeli. Zanj obstaja ve£ moºnih algoritmov, kot so na primer urejanje z izbiranjem, urejanje z mehur£ki, urejanje z zlivanjem in hitro urejanje.
Algoritmi, ki re²ujejo isti problem so med seboj lahko zelo razli£ni. Razlikujejo se lahko na primer v kolik²nem £asu bo algoritem vrnil odgovor in koliko prostora bo porabil [30]. Potemtakem imajo algoritmi razli£ne kakovosti na razli£nih podro£jih, eni so bolj²i drugi slab²i.
V magistrski nalogi bomo za podatke, ki jih dobimo pred, med in po izvajanju algoritma poiskali gra£ne prikaze, iz katerih bo £im bolj enostavno razbrati kakovost enega algoritma ali primerjati kakovost ve£ algoritmov na enem ali ve£ podro£jih.
Na ta na£in bomo uporabnikom v ²tevilnih primerih olaj²ali analize algoritmov.
Osredoto£ili se bomo na dva gra£na prikaza kakovosti algoritmov. To sta gra-
£ni prikaz kakovosti algoritmov s tabelo in gra£ni prikaz kakovosti algoritmov z grakonom. Oba gra£na prikaza smo podrobneje raziskali ºe v poglavju 2. Vse ugotovitve, ki smo jih pridobili, bomo upo²tevali pri sami implementaciji v sistemu ALGator. Prikaz kakovosti algoritmov s tabelo bomo podrobneje predstavili v po- glavju 3.2, prikaz kakovosti z grakonom pa bomo predstavili v poglavju 3.3. Vsak prikaz bomo sistemati£no pregledali v naslednjem vrstnem redu:
1. Splo²en opis prikaza.
2. Prilagoditev prikaza na²im potrebam.
3. Za katere kakovosti algoritma je primeren.
(a) Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
4. Kako se razlikuje od ostalih prikazov.
5. Prakti£en primer.
6. Moºne izbolj²ave.
Implementacija predstavljenih gra£nih prikazov in sam sistem ALGator pa bodo opisani v poglavju 4.
V drugem poglavju smo omenili, da je ºe na samem za£etku zelo pomembno izbrati pravilni gra£ni prikaz za podatke, ki jih imamo. Iz tega razloga moramo pred za£etkom iskanja primernega prikaza razumeti, s kak²nimi podatki bomo imeli opravka v algortimiki. Ve£ o tem bomo povedali v naslednjem poglavju 3.1.
3.1 Podatki v algoritmiki
Preden pri£nemo s pregledom podatkov v algoritmiki moramo ponoviti kaj je algo- ritem. Algoritem je postopek, ki prejme vhod in izra£una izhod. Lastnosti vhoda so parametri. Lastnosti izhoda pa so indikatorji. Torej se bomo pri prou£evanju kakovosti algoritmov ukvarjali s podatki, ki se imenujejo parametri in indikatorji.
Vsakega bomo podrobneje opisali v naslednjih dveh poglavjih.
3.1.1 Parameter
Algoritmi obi£ajno prejmejo enega ali ve£ vhodov, ti pa imajo svoje lastnosti, ki jim pravimo parametri. Da bo pravkar povedano bolj razumljivo, je spodaj podan konkreten primer.
Imamo problem urejanja ²tevil v tabeli. Algoritmi, ki re²ijo ta problem obi£ajno kot vhod prejmejo tabelo ²tevil. Ta ima dve pomembni lastnosti, ki mo£no vplivata na to kako se bo algoritem izvedel. Prvi parameter je velikost tabele. V ve£ini primerov ve£ja kot je tabela, dalj £asa se izvaja algoritem. Drugi parameter pa je razvrstitev ²tevil v tabeli. Ugotovili so, da na izvajanje algoritma ne vpliva le sama velikost tabele, ampak tudi razvrstitev ²tevil v njej. Zakaj je temu tako? e malo bolje premislimo zelo hitro ugotovimo, da razvrstitev ²tevil mo£no vpliva na ²tevilo zamenjav in posledi£no na izvajanje samega algoritma.
V primeru smo predstavili, da vrednosti parametrov vplivajo na izvajanje algo- ritma in s tem na indikatorje, ki jih bomo predstavili v naslednjem poglavju 3.1.2.
3.1.2 Indikator
Vsak algoritem glede na dani vhod izra£una izhod. Ta pa ima svoje lastnosti, ki jim pravimo indikatorji. Obi£ajno se ºe v naprej odlo£imo, katere zna£ilnosti izhoda nas bodo zanimale in jih merimo med samim izvajanjem algoritma. Torej je indikator neka zna£ilnost izhoda, ki nas zanima in jo zato merimo. Nato pa glede na izmerjeno vrednost ocenimo kak²ne kakovosti je algoritem na podro£ju te zna£ilnosti. Vsakega posameznika lahko zanimajo kakovosti algoritma na razli£nih podro£jih. Za bolj²o predstavo sta spodaj podana dva konkretna primera:
• e imamo na primer omejen £as, v katerem mora algoritem vrniti izhod, potem ocenjujemo kakovost glede na to, koliko £asa potrebuje algoritem, da vrne izhod. Torej za indikator izberemo £as.
• e imamo omejen prostor, katerega lahko porabi algoritem, potem ocenjujemo kakovost algoritma glede na to koliko prostora porabi, da vrne izhod. Torej za indikator izberemo prostor.
V£asih pa kakovost algoritma ne ocenjujemo samo glede na vrednost enega in- dikatorja, ampak glede na ve£ indikatorjev. V tem primeru nas zanima kako se algoritem obna²a na enem podro£ju, ki ga zavzema ve£ indikatorjev ali pa nas za- nima, kako se algoritem obna²a na ve£ razli£nih podro£jih.
e malo bolje premislimo, hitro ugotovimo, da obstaja zelo veliko ²tevilo in- dikatorjev. Dva najbolj pogosta indikatorja, ki ju merimo sta £as in prostor. Za
ra£unalnike, ki se napajajo preko baterije (prenosniki, mobiteli) in za zelo dolge izra£une (super ra£unalniki) sta tudi zanimiva indikatorja neposredne in posredne porabe energije. Manj pogosto uporabljeni indikatorji pa so velikost prenosa, zu- nanji prostor in odzivni £as [22]. V£asih pa programerju veliko pove tudi sama informacija kolikokrat se je ponovil dolo£en del programske kode ali kolikokrat se je uporabil ukaz zloºne kode. Pri algoritmih, ki ne vrnejo vedno najbolj²ega moºnega izhoda pa nas zanima tudi indikator kakovosti izhoda.
Sedaj, ko smo na hitro na²teli nekaj indikatorjev bomo, za laºje razumevanje, opisali vsakega posebej.
Indikator £asa nam pove koliko £asa potrebuje algoritem, da se izvede oz. vrne izhod. Pri tem indikatorju programerji obi£ajno izvajajo algoritme pri razli£nih testnih primerih in za kon£no analizo vzamejo povpre£je £asov. Zelo pomembno je, da so pri tem indikatorju vse meritve in algoritmi izvedeni pri istih pogojih, saj je £as izvajanja odvisen od izbire programskega jezika, prevajalnika in moºnosti prevajalnika [22].
Indikator prostora se ukvarja z merjenjem porabe pomnilni²kih virov (registrov, predpomnilnika, delovnega pomnilnika, virtualnega pomnilnika, sekundarnega po- mnilnika) med izvajanjem algoritma. Ta indikator lahko pogledamo s ²tirih vidikov (povzeto po [22]):
• Koli£ina pomnilnika, ki jo potrebuje programska koda algoritma (poraba po- moºnega prostora).
• Koli£ina pomnilnika potrebna za vhodne podatke.
• Koli£ina pomnilnika potrebna za izhodne podatke. Ta je pomembna, ker ne- kateri algoritmi, kot je urejanje pogosto preuredijo vhodne podatke in ne po- trebujejo dodatnega prostora za izhodne podatke.
• Koli£ina pomnilnika, ki je med izvajanjem algoritma potrebna kot delovni pro- stor. Tu so vklju£ene lokalne spremenljivke (kopica in sklad), ki ga potrebujejo rutine poklicane med izvajanjem algoritma. Sklad je ²e posebej pomemben za rekurzivne algoritme.
Indikator neposredne porabe energije nam pove koliko energije je bilo potrebno neposredno za upravljanje ra£unalnika [22].
Indikator posredne porabe energije nam pove koliko energije je potrebno za hla- jenje, razsvetljavo, . . . [22].
Indikator velikosti prenosa nam pove koliko podatkov je med izvajanjem algo- ritma potrebno prenesti. Velikost pasovne ²irine prenosa podatkov je lahko omeje- valni faktor, zato je informacija, koliko podatkov je med izvajanjem potrebno pre- nesti zelo pomembna. Najbolje bo, da podamo kar konkreten primer: e ºelimo na primer prikazati sliko, lahko to povzro£i prenos ve£ kot 100 MB podatkov. Ne smemo pa pozabiti, da lahko koli£ino podatkov za prenos zmanj²amo s stiskanjem [22].
Indikator zunanjega prostora nam pove, koliko prostora je potreboval algoritem na disku ali drugi zunanji pomnilni²ki napravi. Algoritem potrebuje zunanji prostor zaradi razli£nih razlogov. Eden izmed razlogov je na primer za dolgoro£no shrambo,
ki jo bomo potrebovali v prihodnosti ali pa za za£asno hrambo med izvajanjem algoritma [22].
Indikator odzivnega £asa nam pove, kako hitro se je algoritem odzval. Ta je zlasti pomemben za aplikacije, ki se dogajajo v realnem £asu in se morajo odzivi na kak²en zunanji dogodek zgoditi zelo hitro [22].
Indikator ponavljanj dela programske kode ali uporabe ukaza zloºne kode nam pove kolikokrat se je ponovil dolo£en del kode (na primer: if stavek, klic rekurzivne funkcije, . . . ) ali pa kolikokrat se uporabijo ukazi zloºne kode. Za razliko od prej na²tetih indikatorjev mora programer pri tem indikatorju sam vedeti, kaj mu bo
²tevilo ponavljan ali uporabe povedal o kakovosti algoritma. Najbolje, da si ogle- damo konkreten primer. Recimo, da primerjamo dva algoritma za urejanje ²tevil v tabeli. elimo izbrati tisti algoritem, ki naredi manj primerjav med ²tevili. Tako v programski kodi obeh algoritmov nastavimo ²tevec na delih kode, kjer se zgodi pri- merjava dveh ²tevil. Vidimo, da prvi v povpre£ju naredi manj primerjav kot drugi.
Torej lahko sklepamo, da je za na²e potrebe prvi bolj²e kakovosti [22].
Indikator kakovosti izhoda nam pove za koliko se na² izhod razlikuje od optimalne re²itve. Ko imamo opravka z algoritmi, ki ne vrnejo vedno optimalne re²itve, ºelimo vedeti kako dale£ od optimalne re²itve so izhodi algoritma in na ta na£in zelo hitro vidimo, kateri algoritem je bolj kakovosten na tem podro£ju [22].
Indikatorji se med sabo vsebinsko razlikujejo za vse pa velja, da morajo imeti naslednje lastnosti: so enostavni, natan£ni in merljivi [22].
V naslednjih poglavjih bomo predstavili gra£ne prikaze, ki smo jih na²li ali raz- vili med raziskavo in so najprimernej²i za na²e potrebe. Najbolj²e bomo v poglavju 4 tudi implementirali v sistem ALGator. Preden nadaljujemo je potrebno omeniti, da bodo v naslednjih podpoglavjih na slikah in tabelah prikazane skice idej, ki pa ne bodo nujno upo²tevale primere dobre prakse, ki smo jih raziskali v poglavjih 2.1.1 in 2.2.1. Primere dobre prakse pa bomo vsekakor upo²tevali pri sami implementaciji v sistemu ALGator.
3.2 Gra£ni prikaz kakovosti algoritma s tabelo
V tem poglavju si bomo ogledali primere prikazov kakovosti algoritmov s tabelo, ki smo jih na²li ali razvili med raziskavo in so najprimernej²i za na²e potrebe. Prikaze bomo z upo²tevanjem primerov dobre prakse iz poglavja 2.1 pozneje tudi implemen- tirali v sistemu ALGator.
Da bodo prikazi prijaznej²i za uporabnika, bomo pri vseh dodali tudi primerne funkcionalnosti ne stati£nih tabel ter jih prilagodili za ljudi z omejitvami. Ve£ o tem bomo povedali pri sami implementaciji.
Glede na podatke o algoritmih, ki jih ponuja sistem ALGator in so podrobneje opisani v poglavju 4.1 smo izbrali par tipov tabel, ki bodo opisane v nadaljevanju.
e ºelimo s tabelo primerjati meritve ve£ algoritmov, se ²tevilo podatkov zelo po- ve£a. Povedali smo, da v tabelah ni priporo£ljivo prikazovati preve£ podatkov, saj potem uporabnik teºko razbere tiste, ki so zanj pomembni. Iz tega razloga bomo v poglavju 3.2.1 posebej obravnavali tabelari£ni prikaz kakovosti enega algoritma in v poglavjih 3.2.2, 3.2.3 ter 3.2.4 posebej obravnavali tabelari£ne prikaze kakovosti ve£
algoritmov hkrati.
3.2.1 Tabelari£ni prikaz kakovosti enega algoritma Splo²en opis prikaza
Je najbolj enostaven in splo²en tabelari£ni prikaz, v katerem se nahajajo vsi podatki.
Prilagoditev prikaza na²im potrebam
Za na²e potrebe je to torej tabela, v kateri se nahajajo vsi parametri in indikatorji.
Za katere kakovosti algoritma je primeren
Tak²en prikaz je primeren za prikaz popolnoma vseh kakovosti.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Uporabnik mora sam glede na vrednosti v tabeli oceniti kak²ne kakovosti je algoritem.
Kako se razlikuje od ostalih prikazov
Prednost tak²nega prikaza je ta, da so v njej zapisane to£ne vrednosti za vse indi- katorje in parametre [44]. Te pa so nujno potrebni za dolo£ene analize. Ker obstaja velika verjetnost, da bodo uporabniki glede na podatke ºeleli delati razne nadaljnje analize, moramo tak²en prikaz vsekakor omogo£iti.
Slabost tak²nega prikaza pa je ta, da bodo v primeru, ko imamo veliko parame- trov in indikatorjev, tabele imele zelo veliko ²tevilo vrstic in stolpcev. To pa pomeni, da bodo uporabniki zelo teºko razbrali podatke, ki jih bodo potrebovali [44].
Prakti£en primer
Najbolje, da si ogledamo enostaven primer. V tabeli 3.1 je prikazana kakovost algo- ritma za urejanje tabel. Za parameter smo si izbrali velikost vhoda, za indikatorje pa povpre£ni £as izvajanja, maksimalni £as izvajanja in ²tevilo klicev funkcije f1.
Tabela 3.1: Tabelari£ni prikaz kakovosti enega algoritma Velikost vhoda T[s] maksT[s] |klicf1|
1 1 1 1
2 4 4 4
4 16 16 16
16 256 256 256
32 1024 1024 1024
64 4096 4096 4096
128 16384 16384 16384
Moºne izbolj²ave
Ker je, kot smo ºe omenili, nujno potrebno izpisati to£ne podatke v primeru, ko jih bo uporabnik potreboval, smo poiskali kako odpraviti slabost prevelike koli£ine podatkov. To storimo tako, da uporabniku omogo£imo moºnost izbiranja katere po- datke ºeli prikazati. Na ta na£in uporabniku prikaºemo to£ne vrednosti, a le za tiste podatke, ki jih bo uporabnik potreboval. Za laºji pregled pa bomo vse parametre postavili v skrajno leve stolpce, indikatorje pa desno od njih.
Kaj pa, £e ºelimo primerjati ve£ algoritmov? V tem primeru se zadeve zapletejo, saj ºelimo prikazati dosti ve£jo koli£ino podatkov. e imamo na primer tri algoritme, imamo pribliºno 3x ve£ podatkov kot pa £e bi prikazali podatke za en algoritem.
Ker je veliko podatkov, je tak²en prikaz za bralca lahko hitro nerazumljiv oziroma bo ta potreboval veliko £asa, da razbere pomembne podatke. Po dalj²i raziskavi smo pri²li do treh re²itev za tabelari£no primerjanje kakovosti ve£ algoritmov. V naslednjih poglavjih bomo predstavili vsako re²itev posebej.
3.2.2 Tabelari£ni prikaz kakovosti grupiran po algoritmih v stolpcih Splo²en opis prikaza
Prvo moºnost tabelari£nega prikaza, pri katerih se primerjajo razli£ni "objekti"po in- dikatorjih smo zasledili v ve£ £lankih [8],[15] in [1]. Primer je prikazan na sliki 3.1 [8].
Slika 3.1: Ideja tabelari£nega prikaza kakovosti ve£ algoritmov, ki je grupiran po algoritmih v stolpcih (slika je povzeta iz [8])
Prilagoditev prikaza na²im potrebam
Ta prikaz bomo bomo prilagodili na²im potrebam tako, da bomo iz prikaza na sliki 3.1 ohranili zdruºevanje algoritmov po stolpcih. Uporabniku pa bomo omogo£ili, da po lastni ºelji izbere poljubno ²tevilo indikatorjev, ki jih ºeli prikazati v stolpcih pod algoritmi. Ostali stolpci bodo namenjeni poljubnem ²tevilu parametrov, ki jih bo uporabnik prav tako lahko izbral sam. Tako bodo v celicah teh vrstic izpisane vrednosti, ki so enake za vse algoritme (na primer velikost vhoda). Glede na vre- dnosti parametrov, bodo v stolpcih z indikatorji (pod algoritmi) izpisane izmerjene vrednosti.
Za katere kakovosti algoritma je primeren
Prikaz je primeren za prikaz popolnoma vseh kakovosti.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Uporabnik mora sam glede na vrednosti v tabeli oceniti kak²ne kakovosti je algoritem.
Kako se razlikuje od ostalih prikazov
Prednost tak²nega prikaza je, da so v njej zapisane to£ne vrednosti za vse indikatorje in parametre za ve£ algoritmov. Te pa so nujno potrebne za dolo£ene analize. Ob tem pa je tak²en prikaz zelo enostaven in lahko berljiv. Slabost tega prikaza pa je, da bo uporabnik teºko razbral pomembne informacije, £e bo v njem preve£ podatkov.
Prakti£en primer
Za laºje razumevanje je v tabeli 3.2 prikazan enostaven primer.
Tabela 3.2: Tabelari£ni prikaz kakovosti ve£ algoritmov, ki je grupiran po algoritmih v stolpcih
Velikost vhoda Urejanje z mehur£ki Hitro urejanje T[s] maksT[s] T[s] maksT[s]
1 1 1 0 1
2 4 4 0,60 4
4 16 16 2,41 16
16 256 256 19,2 256
32 1024 1024 48,16 1024
64 4096 4096 115,60 4096
128 16384 16384 269,72 16384
Primerjamo dva algoritma za urejanje tabel: urejanje z mehur£ki in hitro ureja- nje. Za nadaljnjo analizo potrebujemo to£ne vrednosti povpre£nega in maksimalnega
£asa izvajanja algoritmov pri razli£nih velikostih vhoda. Torej smo za prikaz izbrali:
• parameter: velikost vhoda in
• indikatorja: povpre£ni in maksimalni £as izvajanja algoritma.
To pomeni, da bodo v stolpcu s parametrom prikazane vse moºne velikosti vhoda. V vsaki vrstici pod algoritmom pa bodo prikazani izmerjeni indikatorji glede na velikost vhoda. Seveda so lahko tak²ni prikazi ²e veliko bolj kompleksnej²i. Lahko izberemo ve£ parametrov. Na primer testno mnoºico, testni vhod in ²e velikost vhoda. Potem pa so prikazani indikatorji izmerjeni glede na vse tri vrednosti parametrov.
3.2.3 Tabelari£ni prikaz kakovosti grupiran po indikatorjih v stolpcih Splo²en opis prikaza
Druga moºnost tabelari£nega prikaza je zelo podobna prvemu, le da primerjamo vrednosti indikatorjev pri razli£nih "objektih". Idejo za tak²en tak²en na£in prikaza smo dobili v £lanku [5]. Slika tabele s pomo£jo katere smo dobili idejo za tak²en prikaz je prikazana na sliki 3.2.
Slika 3.2: Ideja tabelari£nega prikaza kakovosti ve£ algoritmov, ki je grupiran po indikatorjih v stolpcih (slika je povzeta iz [5])
Prilagoditev prikaza na²im potrebam
Prikaz bomo prilagodili na²im potrebam tako, da bomo stolpce zdruºili po indika- torjih. Torej bo pod vsakim indikatorjem toliko stolpcev, kolikor algoritmov bomo primerjali. Uporabniku bomo omogo£ili, da po lastni ºelji izbere poljubno ²tevilo indikatorjev. Ostali stolpci bodo namenjeni poljubnem ²tevilu parametrov, ki jih bo prav tako uporabnik lahko izbral po lastni izbiri.
Za katere kakovosti algoritma je primeren
Ta prikaz je primeren za prikaz popolnoma vseh kakovosti.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Uporabnik mora sam glede na vrednosti v tabeli oceniti kak²ne kakovosti je algoritem.
Kako se razlikuje od ostalih prikazov
Prikaz je zelo enostaven in lahko berljiv. Ob tem je bolj primeren od prvega prikaza za tiste, ki bodo delali analize primerjav algoritmov po posameznih indikatorjih.
Slabost tega prikaza pa je ta, da bo uporabnik teºko razbral pomembne informacije,
£e bo v njem preve£ podatkov.
Prakti£en primer
Za laºje razumevanje bomo podali enak primer kot v prej²njem poglavju 3.2.2. Pri- merjali bomo torej dva algoritma za urejanje tabel. Kot parameter smo izbrali velikost vhoda, kot indikatorja pa povpre£ni ter maksimalni £as izvajanja algoritma.
Skica kako bi zagledal tak²en prikaz se nahaja v tabeli 3.3.
Tabela 3.3: Tabelari£ni prikaz kakovosti ve£ algoritmov, ki je grupiran po indikatorjih v stolpcih
Velikost vhoda T[s] maksT[s]
Mehur£ki Hitro Mehur£ki Hitro
1 1 0 1 1
2 4 0,60 4 4
4 16 2,41 16 16
16 256 19,2 256 256
32 1024 48,16 1024 1024
64 4096 115,60 4096 4096
128 16384 269,72 16384 16384
Tako kot prvi prikaz, je lahko tudi ta ob izbiri ve£ parametrov veliko bolj kom- pleksen.
3.2.4 Tabelari£ni prikaz kakovosti grupiran po algoritmih v vrsticah Splo²en opis prikaza
Tretja moºnost tabelari£nega prikaza je bolj klasi£na in jo je videl ºe skoraj vsak programer. Pri tem prikazu se v prvem stolpcu nahajajo "objekti", ki jih primer- jamo; v ostalih stolpcih pa izbrane spremenljivke. Primer tak²nega prikaza lahko vidimo na sliki 3.3.
Prilagoditev prikaza na²im potrebam
e iz slike 3.3 je razvidno kako bomo prikaz prilagodili na²im potrebam. V prvem stolpcu se nahajajo vsi algoritmi, ki jih primerjamo. V ostalih pa poljubni indikatorji in parametri.
Za katere kakovosti algoritma je primeren
Prikaz je primeren za prikaz popolnoma vseh kakovosti.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Uporabnik mora sam glede na vrednosti v tabeli oceniti kak²ne kakovosti je algoritem.
Slika 3.3: Ideja tabelari£nega prikaza kakovosti ve£ algoritmov, ki je grupiran po algoritmih v vrsticah (slika je povzeta iz [28])
Kako se razlikuje od ostalih prikazov
Ta prikaz je primeren, ker je zelo pogosto uporabljen in se ljudje hitro znajdejo v njem. Po drugi strani pa v primerjavi s prvim in drugim prikazom:
• ima veliko ²tevilo vrstic in
• je iz njega teºko primerjati vrednosti indikatorjev razli£nih algoritmov pri do- lo£enem parametru.
Prakti£en primer
Za laºjo primerjavo prvega, drugega in tretjega prikaza je v tabeli 3.4 viden prakti£ni primer za ta prikaz, kjer smo uporabili enake podatke kot v prej²njih dveh poglavjih (primerjava dveh algoritmov za urejanje tabel: urejanje z mehur£ki in hitro ureja- nje). Kot parameter pa smo izbrali velikost vhoda, kot indikatorja pa povpre£ni ter maksimalni £as izvajanja algoritma.
Tabela 3.4: Tabelari£ni prikaz kakovosti ve£ algoritmov, ki je grupiran po algoritmih v vrsticah
Algoritmi Velikost vhoda T[s] maksT[s]
Urejanje z mehur£ki 1 1 1
2 4 4
4 16 16
16 256 256
32 1024 1024
64 4096 4096
128 16384 16384
Hitro urejanje 1 0 1
2 0,60 4
4 2,41 16
16 19,27 256
32 48,16 1024
64 115,60 4096
128 269,72 16384
Moºne izbolj²ave
Pri tem prikazu je za vsak algoritem namenjeno toliko vrstic, kolikor je razli£nih vednosti parametra. Zato je pri tak²nem prikazu pomembno omogo£iti tudi interval prikaza vrednosti parametra oziroma parametrov.
Sedaj, ko smo si ogledali tabelari£ne prikaze, si bomo v naslednjem poglavju 3.3 ogledali ²e moºne prikaze z grakoni, ki so primerni za na²e potrebe.
3.3 Gra£ni prikaz kakovosti algoritma z grakonom
V tem poglavju si bomo ogledali zanimive primere prikazov kakovosti algoritmov z grakoni, ki smo jih na²li ali razvili za na²e potrebe. V poglavju 4 pa bomo najbolj²e tudi implementirali v sistem ALGator. Vsi prikazi so primerni tako za prikaz kakovosti enega algoritma kot tudi za prikaz kakovosti ve£ algoritmov.
Pri grakonih se je zelo teºko izogniti barvam zlasti, £e primerjamo ve£ algorit- mov na enem grakonu. Ker ºelimo narediti na²e prikaze prijazne barvno slepim, se bomo pri implementaciji podrobneje posvetili tudi tej temi.
Ta vrsta prikazov pa ima to slabost, da je iz njih teºko razbrati to£ne vrednosti, ki pa so nujno potrebne za natan£ne analize. To slabost bomo v tistih primerih, kjer bo le moºno re²ili tako, da se bo ob dotiku speci£ne to£ke izpisala to£na vrednost.
Pravkar opisano slabost ne bomo omenjali v naslednjih podpoglavjih, ampak bomo pri sami implementaciji podali re²itev za vsak izbran prikaz.
Predstavili bomo devet prikazov. V naslednjem podpoglavju bomo za£eli z naj- enostavnej²im in najpogosteje uporabljenim na£inom prikaza kakovosti algoritmov.
3.3.1 Prikaz kakovosti algoritma s £rtnim grakonom
Najbolj pogosto uporabljen grakon v raziskavah in £lankih je £rtni grakon. Po- navadi se ljudje najlaºje znajdejo s stvarmi, ki jih ºe poznajo. Zato smo se odlo£ili, da mora biti tak²en prikaz obvezno implementiran tudi v sistemu ALGator.
Splo²en opis prikaza
Preden si ogledamo podrobnosti moramo pojasniti, kaj je £rtni grakon in kako zgleda. rtni grakon ali £rtni graf je vrsta grakona, ki prikaºe informacije kot niz podatkovnih to£k, ki so povezane z ravnimi segmenti oziroma £rtami [35]. Zelo enostaven primer tak²nega grakona je prikazan na sliki 3.4.
Slika 3.4: Enostaven primer £rtnega grakona (slika je povzeta iz [41])
Prilagoditev prikaza na²im potrebam
Na £rtnem grakonu lahko primerjamo dve spremenljivki. Ordinatni osi dodelimo eno spremenljivko, abscisni osi pa drugo. Prikaz bomo na²im potrebam prilagodili tako, da bomo omogo£ili naslednji logi£ni izbiri:
• grakon indikatorja v odvisnosti od parametra in
• grakon indikatorja v odvisnosti od indikatorja.
Na ta na£in lahko na lep in enostaven na£in prikaºemo kakovost algoritma glede na dve spremenljivki za veliko podatkov.
Za katere kakovosti algoritma je primeren Prikaz je primeren za vse kakovosti algoritma.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Ker lahko izbiramo razli£ne spremenljivke za abscisno in ordinatno os, moramo obravnavati dva primera:
• Grakon indikatorja v odvisnosti od parametra
e ºelimo, da ima problem £im manj²e vrednosti pri indikatorju, po- tem bliºje kot so vrednosti indikatorja abscisni osi, bolj²e kakovosti je algoritem.
e ºelimo, da ima problem £im ve£je vrednosti pri indikatorju, potem boj kot so oddaljene vrednosti indikatorja od abscisne osi, bolj²e kakovosti je algoritem.
• Graf indikatorja v odvisnosti od indikatorja
Pri tem grakonu je interpretacija kakovosti odvisna od narave problema.
Pri £rtnem grakonu lahko kot sestavljeni kazalnik kakovosti vzamemo tudi plo-
²£ino, ki jo povezani segmenti tvorijo z abscisno ali ordinatno osjo.
Kako se razlikuje od ostalih prikazov Prednosti tega prikaza sta:
• Je enostaven za implementacijo in razumevanje ter je vizualno privla£en.
• Na njem lahko prikaºemo kakovost algoritma za vse vrednosti, ki jih zavzema indikator/parameter.
Njegova slabost pa je ta, da je na njem moºno na enkrat prikazati le kakovost glede na dve spremenljivki.
Prakti£en primer
Za laºje razumevanje je najbolje podati konkreten primer grakona, ki prikazuje odvisnost £asa od velikosti vhoda. Recimo, da ºelimo primerjati dva algoritma za urejanje tabel: urejanje z mehur£ki in hitro urejanje. Slika 3.5 prikazuje £rtni grakon za ta primer.
Slika 3.5: Prakti£ni primer £rtnega grakona
3.3.2 Prikaz kakovosti algoritma s pali£nim in stolp£nim grakonom Poleg gra£nega prikaza podatkov s £rtnim grakonom je zelo pogosto uporabljen tudi prikaz podatkov s pali£nim in stolp£nim grakonom.
Splo²en opis prikaza
Stolp£ni ali pali£ni grakon je grakon, ki prikazuje podatke s pomo£jo pravokotnih stolpcev ali vrstic. Ti predstavljajo skupno koli£ino izmerjenih podatkov spremen- ljivke za to kategorijo [16]. Ena os grakona prikazuje dolo£ene kategorije, druga os pa izmerjeno vrednost pri tej kategoriji. Stolp£ni grakon ima kategorije na abscisni osi in izmerjene vrednosti na ordinatni os. Pali£ni pa ravno obratno. Temu primerno so orientirani tudi pravokotniki. Za laºjo predstavo je na sliki 3.6 prikazan stolp£ni grakon, na sliki 3.7 pa pali£ni grakon.
Slika 3.6: Primer stolp£nega grakona (slika je povzeta
iz [43])
Slika 3.7: Primer pali£nega grakona (slika je povzeta
iz [43])
Na tej vrsti grakona lahko hkrati primerjamo tudi ve£ spremenljivk. To lahko sto- rimo na dva na£ina. Prvi je tak, da pri vsaki kategoriji prikaºemo toliko stolpcev enega ob drugem, kolikor je spremenljivk. Primer je prikazan na sliki 3.8. Drugi na£in je podoben, le da so stolpci eden na drugem. Primer je prikazan na sliki 3.9.
Prilagoditev prikaza na²im potrebam
Prikaz lahko zelo enostavno prilagodimo na²im potrebam. Os s kategorijami bo na- menjena vrednostim parametra. Druga os pa bo namenjena vrednostim indikatorja.
Za katere kakovosti algoritma je primeren Prikaz je primeren za vse kakovosti algoritma.
Slika 3.8: Prva moºnost prikaza ve£ spremenljivk v stolp£nem
grakonu (slika je povzeta iz [46])
Slika 3.9: Druga moºnost prikaza ve£ spremenljivk v stolp£nem
grakonu (slika je povzeta iz [46])
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
O kakovosti lahko sklepamo iz vi²ine pravokotnikov. Niºji kot je pravokotnik pri dolo£enem parametru, manj²a je vrednost indikatorja. Torej, £e ºelimo, da ima v splo²nem algoritem £im manj²e vrednosti indikatorja, morajo biti vi²ine pravokotnikov £im manj²e. V primeru, ko pa primerjamo ve£ algoritmov, je tako bolj²e kakovosti tisti algoritem, ki ima v povpre£ju pravokotnike z manj²o vi²ino. e posplo²imo, lahko re£emo, da pri tem prikazu uporabimo plo²£ine pravokotnikov kot sestavljeni kazalnik kakovosti.
Kako se razlikuje od ostalih prikazov
Prikaz ima enake prednosti in slabosti kot £rtni grakon. Te so:
• Je enostaven za implementacijo in razumevanje ter vizualno privla£en.
• Na njem lahko prikaºemo kakovost algoritma za vse vrednosti, ki jih zavzema indikator/parameter.
Njegova slabost pa je ta, da je na njem moºno na enkrat prikazati le kakovost glede na dve spremenljivki.
Prakti£en primer
Za laºje razumevanje je najbolje podati enak konkreten primer kot pri £rtnem gra- konu. Primerjati ºelimo dva algoritma za urejanje tabel, in sicer urejanje z mehur£ki in hitro urejanje. Zanima nas primerjava algoritmov glede na povpre£ni £as pri pa- rametru velikost vhoda za vrednosti n = 1, 2, 4 in 8. Slika 3.10 prikazuje stolp£ni grakon za ta primer.
Slika 3.10: Prakti£en primer stolp£nega grakona Moºne izbolj²ave
Pri tej vrsti grakona smo na²li ²tiri moºne izbolj²ave. Pri prvi gre bolj za vizualno izbolj²avo. e ºelimo tak²en prikaz narediti vizualno privla£nej²i, lahko dodam ²e eno dimenzijo. Tako dobimo tridimenzionalni stolp£ni ali pali£ni grakon. Primer tak²nega grakona je prikazan na sliki 3.11. Na tretji osi se torej nahajajo imena algoritmov. Pri ocenjevanju kakovosti se od dvodimenzionalnega prikaza razlikuje le v tem, da ra£unamo prostornino kvadra in ne plo²£ino pravokotnika.
Slika 3.11: Primer tridimenzionalnega stolp£nega grakona
Druga izbolj²ava je malo bolj kompleksna. Gre za prikaz kakovosti z enim in- dikatorjem ve£. Do tak²nega prikaza pridemo tako, da v grakonu pravokotnike spremenimo v £rte. Nato pa z vi²ino £rte prikaºemo prvi indikator. S premerom kroga na vrhu £rte pa prikaºemo drug indikator. Idejo za prikaz smo dobili iz lizika grakona. Ta je dobil tak²no ime, ker njegovi elementi spominjajo na liziko. Primer grakona je prikazan na sliki 3.12.
Prikaz ima dve slabosti. Prva je ta, da v primeru, ko ºelimo na njem prikazati ka- kovost ve£ algoritmov, hitro postane prenatrpan in je iz njega teºko razbrati ºeleno.
Druga slabost pa je, da sredi²£e kroga na koncu £rte ozna£uje vrednost, a je le tega
s prostim o£esom teºko oceniti, zato je razbrana vrednost lahko nenatan£na [27].
Slika 3.12: Primer lizika grakona (slika je povzeta iz [27])
Pri tretji izbolj²avi osnovnemu prikazu kakovosti prav tako dodamo en indikator.
Ta izbolj²ava se vsebinsko od druge izbolj²ave razlikuje v tem, da lahko brez teºav prikaºemo kakovosti ve£ algoritmov. Pri tem prikazu gre za to, da vi²ina/dolºina pravokotnika v stolp£nem/pali£nem grakonu pove vrednost enega parametra. Deleº obarvanosti pravokotnika pa pove vrednost drugega indikatorja. e imata indika- torja razli£ni enoti, lahko uvedemo tudi dve skali. Zelo enostavna skica tak²nega prikaza je vidna na sliki 3.13.
Slika 3.13: Skica pali£nega grakona z dvema indikatorjema (slika je povzeta iz [45])
Pri £etrti izbolj²avi tako kot pri drugi in tretji dodamo prikazu kakovosti ²e en indikator. Tu prikaz dveh indikatorjev omogo£imo tako, da pri:
• stolp£nem grakonu: vrednosti enega indikatorja prikaºemo nad x osjo, vre- dnosti drugega pa pod x osjo in
• pali£nem grakonu: vrednosti enega indikatorja prikaºemo desno od y osi, vrednosti drugega pa levo od y osi.
Torej imamo dva grakona, ki imata skupno os za parameter. Za laºjo predstavo se primer tak²nega prikaza nahaja na sliki 3.14.
Slika 3.14: Dva pali£na grakona s skupno osjo (slika je povzeta iz [29]) Pri tej izbolj²avi moramo biti zelo previdni, saj se lahko zgodi, da bo uporabnik tak²en grakon zamenjal s splo²nim grakonom, kjer so levo od y osi negativne vrednosti, desno od y osi pozitivne vrednosti, nad x osjo pozitivne vrednosti in pod x osjo negativne vrednosti. Da se temu izognemo, moramo za vsak indikator dodati razvidne skale.
3.3.3 Prikaz kakovosti algoritma s ²katlastim grakonom
Sistem ALGator, v katerem bomo implementirali gra£ne prikaze, je namenjen ²iroki paleti uporabnikov. Odlo£ili smo se, da omogo£imo tudi ²katlasti grakon, ki je zelo priljubljen v statisti£nih analizah, saj prikazuje porazdelitev nabora podatkov.
Splo²en opis prikaza
V opisni statistiki je ²katlasti grakon metoda za gra£ni prikaz skupin ²tevil£nih podatkov z njihovimi kvartili. Kvartili (Q1, Q2 in Q3) delijo podatke na ²tiri enake dele. Pri tem morajo bit podatki razporejeni od najmanj²ega do najve£jega. Prvi kvartil Q1 je sredinska ²tevilka med najmanj²o ²tevilko v podatkih in mediano.
Drugi kvartil Q2 je enak mediani podatkov. Mediana razdeli podatke na dva enaka dela. V prvem delu je polovica podatkov, ki so manj²i od mediane. V drugem delu pa je polovica podatkov, ki so ve£ji od mediane. Tretji kvartil Q3 pa je sredinska
²tevilka med mediano in najve£jo ²tevilko v podatkih. katlasti grakoni imajo lahko tudi £rte, ki segajo iz zabojev. Tem £rtamo pravimo brki in predstavljajo variabilnost podatkov. rte segajo do najmanj²e in najve£je vrednosti v naboru podatkov. Za laºjo predstavo je na sliki 3.15 prikazana ena ²katla z brki in vsemi opisanimi deli, na sliki 3.16 pa konkreten primer ²katlastega grakona.
Slika 3.15: Primer ene komponente ²katlastega grakona (slika je povzeta iz [38])
Slika 3.16: Primer ²katlastega grakona (slika je povzeta iz [46]) Prilagoditev prikaza na²im potrebam
Prikaz lahko prilagodimo na²im potrebam na dva na£ina.
Pri prvem nari²emo ²katlasti grakon, ki prikazuje kakovost enega ali ve£ al- goritmov za en indikator pri vseh vrednostih enega parametra. Torej ra£unamo kvartile za izmerjene vrednosti indikatorja pri vsaki vrednosti parametra.
Pri drugem pa nari²emo ²katlasti grakon, ki prikazuje kakovost vsakega algo- ritma posebej pri enem indikatorju za to£no dolo£eno vrednost enega parametra.
Torej ra£unamo kvartile za izmerjene vrednosti indikatorja pri dolo£eni vrednosti parametra za vsak algoritem posebej.
Za katere kakovosti algoritma je primeren
Ta prikaz je primeren za prikaz vseh kakovosti, kjer imamo za vsako vrednost para- metra ve£ meritev indikatorja.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Pri tak²nem prikazu lahko hitro vidimo kak²na je povpre£na vrednost dolo£enega indikatorja in kak²na so odstopanja. Na ta na£in lahko hitro vidimo, kako se algoritem obna²a ter, £e imamo kak²na skrajna odstopanja.
Kako se razlikuje od ostalih prikazov
Pri tem prikazu imamo dve moºnosti prilagoditve za na²e potrebe. Prednosti obeh sta, da je prikaz vizualno privla£en in enostaven za implementacijo. Slabost obeh pa je, da prikazujeta le kakovost glede na dve spremenljivki.
Prikaza se med seboj dosti razlikujeta. Iz tega razloga bomo obravnavali pred- nosti in slabosti pri vsakemu posebej.
Prednost prikaza kakovosti enega algoritma za en indikator pri vseh vrednosti enega parametra je, da vidimo podrobnej²e obna²anje enega ali ve£ algoritmov za vse vrednosti parametra.
Prednost prikaza kakovosti ve£ algoritmov pri enem indikatorju za to£no dolo£eno vrednost parametra je, da vidimo podrobnej²e obna²anje ve£ algoritmov hkrati. Sla- bost pa ta, da vidimo kako se algoritmi obna²ajo pri samo eni vrednosti parametra in ni nujno, da bomo videli realno sliko obna²anja algoritma.
Prakti£en primer
Najbolje, da zopet uporabimo isti primer kot pri ºe opisanih prikatih. Primerjati ºelimo dva algoritma za urejanje tabel, in sicer urejanje z mehur£ki in hitro urejanje.
Zanima nas primerjava algoritmov glede na povpre£ni £as pri parametru velikost vhoda za vrednosti n = 100, 200, 400 in 800. Slika 3.17 prikazuje ²katlasti grakon za ta primer.
Slika 3.17: Prakti£en primer ²katlastega grakona
Vsi do sedaj opisani prikazi so enostavno berljivi in vizualno privla£ni, a je na njih moºno prikazati kakovost algoritma samo za en indikator. Zato smo raziskali tudi prikaze, ki omogo£ajo prikaz kakovosti algoritmov glede na dva indikatorja pri enem parametru in jih bomo predstavili v naslednjih poglavjih.
3.3.4 Prikaz kakovosti algoritma s £rtnim in stolp£nim grakonom
eleli smo, da bi imel uporabnik v sistemu ALGator celostni prikaz kakovosti algo- ritma/algoritmov tudi v primeru, ko bo ºelel oceniti kakovost algoritma glede na dva indikatorja pri enem parametru. Zato smo nadaljevali z raziskovanjem in ugotovili, da se raziskovalci v £lankih velikokrat posluºujejo gra£ne predstavitve z grakonom, ki je me²anica £rtnega grakona in stolp£nega grakona [3, 49]. Gra£ni prikaz iz
£lanka, preko katerega se je porodila ideja, je prikazan na sliki 3.18.
Slika 3.18: Ideja za gra£ni prikaz kakovosti s £rtnim in stolp£nim grakonom (slika je povzeta iz [3])
Splo²en opis prikaza
rtni grakon smo opisali v poglavju 3.3.1, stolp£ni pa v 3.3.2. Tudi v tem poglavju veljajo enaka pravila, samo da ta dva grakona zdruºimo in dobimo enega, ki ima obi£ajno dve skali - eno za £rtni grakon in drugo za stolp£ni grakon. Primer tak²nega prikaza je viden na sliki 3.18
Prilagoditev prikaza na²im potrebam
Sedaj, ko smo spoznali obe vrsti grakonov, ki jih nameravamo uporabiti, lahko pojasnimo, kako bomo prikaz prilagodili na²im potrebam. Uporabniku bomo omo- go£ili, da izbere dva poljubna indikatorja in en parameter, za katere ºeli dobiti prikaz kakovosti algoritma. S pomo£jo enega indikatorja in parametra bomo narisali £rtni grakon, kot smo ga ºe opisali v poglavju 3.3.1. Nato bomo ta grakon dopolnili
s stolp£nim grakonom v odvisnosti drugega indikatorja od parametra, kot smo ºe opisali v poglavju 3.3.2.
Za katere kakovosti algoritma je primeren
Grakon je primeren za prikaz kakovosti katerihkoli dveh indikatorjev.
Kaj lahko s pomo£jo tega prikaza ugotovimo o kakovosti algoritma?
Prva moºnost branja kakovosti je ta, da pogledamo vsak grakon posebej na na£in, ki smo ga opisali v poglavju o £rtnem in stolp£nem grakonu.
Druga moºnost branja kakovosti je ta, da uporabimo plo²£ino kot sestavljeni kazalnik kakovosti. Na primer, £e ºelimo, da bi imela oba indikatorja £im manj²o vrednost, potem je kakovost algoritma bolj²a, £e je vsota plo²£ine pod £rtnim grakonom in plo²£ina vsakega pravokotnika stolp£nega diagrama £im manj²a.
Vsekakor pa uporabnik lahko od£ita kakovost tudi po lastnih potrebah.
Kako se razlikuje od ostalih prikazov Gra£ni prikaz ima naslednje prednosti:
• Je enostaven za implementacijo in razumevanje ter vizualno privla£en.
• Na njem lahko prikaºemo kakovost algoritma glede na dva indikatorja in vse vrednosti parametra.
Njegova slabost pa je, da na njem ni moºno na enkrat prikazati kakovost za ve£ kot dva indikatorja.
Prakti£en primer
Najbolje, da tudi tu podamo konkreten primer, ki je podoben tistim v prej²njih poglavjih. Recimo, da ºelimo primerjati dva algoritma za urejanje tabel, in sicer al- goritem urejanja z mehur£ki in hitro urejanje. elimo videti primerjavo indikatorjev povpre£ni £as in povpre£na poraba prostora pri razli£nih velikostih vhoda. Torej bomo najprej narisali £rtni grakon odvisnosti povpre£nega £asa od velikosti vhoda in nato grakon dopolnili s £rtnim grakonom odvisnosti povpre£ne porabe prostora od velikosti vhoda. Skica primera tak²nega prikaza se nahaja na sliki 3.19
