Na tomto m´ıstˇ e bude ofici´ aln´ı zad´ an´ı vaˇ s´ı pr´ ace • Toto zad´ an´ı je podepsan´e dˇekanem a vedouc´ım katedry, • mus´ıte si ho vyzvednout na studiijn´ım oddˇelen´ı Katedry poˇc´ıtaˇc˚ u na Karlovˇe n´amˇest´ı, • v jedn´e odevzdan´e pr´ aci bude origin´al tohoto zad´an´ı (origin´al z˚ ust´av´a po obhajobˇe na katedˇre), • ve druh´e bude na stejn´em m´ıstˇe neovˇeˇren´a kopie tohoto dokumentu (tato se v´am vr´ at´ı po obhajobˇe).
i
ii
ˇ e vysok´e uˇcen´ı technick´e v Praze Cesk´ Fakulta elektrotechnick´a Katedra poˇc´ıtaˇc˚ u
Bakal´aˇrsk´a pr´ace
Gener´ ator rozs´ ahl´ ych matic zadan´ ych parametr˚ u Jan Hlav´aˇcek
ˇ Vedouc´ı pr´ace: Ing. Ivan Simeˇ cek, Ph.D.
Studijn´ı program: Elektrotechnika a informatika, strukturovan´ y, Bakal´aˇrsk´ y Obor: V´ ypoˇcetn´ı technika 24. kvˇetna 2010
iv
v
Podˇ ekov´ an´ı Zde m˚ uˇzete napsat sv´e podˇekov´ an´ı, pokud chcete a m´ate komu dˇekovat.
vi
vii
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem pr´ aci vypracoval samostatnˇe a pouˇzil jsem pouze podklady uveden´e v pˇriloˇzen´em seznamu. Nem´am z´ avaˇzn´ y d˚ uvod proti uˇzit´ı tohoto ˇskoln´ıho d´ıla ve smyslu §60 Z´akona ˇc. 121/2000 Sb., o pr´ avu autorsk´em, o pr´ avech souvisej´ıc´ıch s pr´avem autorsk´ ym a o zmˇenˇe nˇekter´ ych z´akon˚ u (autorsk´ y z´ akon).
V Praze dne 15. 5. 2010
.............................................................
viii
Abstract Translation of Czech abstract into English.
Abstrakt Abstrakt pr´ ace by mˇel velmi struˇcnˇe vystihovat jej´ı podstatu. Tedy ˇc´ım se pr´ace zab´ yv´ aa co je jej´ım v´ ysledkem/pˇr´ınosem. Oˇcek´avaj´ı se cca 1 – 2 odstavce, maxim´alnˇe p˚ ul str´anky.
ix
x
Obsah ´ 1 Uvod 1.1 Rozbor . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Definice matice . . . . . . . . . . . . . . . . . . . . 1.3 Druhy matic . . . . . . . . . . . . . . . . . . . . . 1.3.1 Horn´ı troj´ uheln´ıkov´a matice . . . . . . . . . 1.3.2 Doln´ı troj´ uheln´ıkov´a matice . . . . . . . . . 1.3.3 Symetrick´ a matice . . . . . . . . . . . . . . 1.3.4 P´ asov´ a matice . . . . . . . . . . . . . . . . ˇ ıdk´ 1.3.5 R´ a matice . . . . . . . . . . . . . . . . . 1.4 Reprezentace matic v pamˇeti . . . . . . . . . . . . 1.4.1 Metody vhodn´e k vytv´aˇren´ı a modifikac´ım 1.4.2 Metody vhodn´e k maticov´ ym operac´ım . . 1.4.3 CRS - compressed row storage . . . . . . . 1.4.4 CCS - compressed column storage . . . . . 1.4.5 CDS - compressed diagonal storage . . . . . 1.4.6 BCRS - block compressed row storage . . . 1.4.7 Yale sparse matrix format . . . . . . . . . . 1.4.8 New Yale sprase matrix format . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
2 Popis probl´ emu, specifikace c´ıle 3 Anal´ yza a n´ avrh ˇ reˇ sen´ı 3.1 Anal´ yza prostˇred´ı . . . . . . . 3.2 Anal´ yza implementace . . . . 3.3 Anal´ yza generovan´ ych matic . 3.4 Rozdˇelen´ı na komponenty . . 3.5 Komponenta GUI . . . . . . . 3.6 Komponenta Controller . . . 3.7 Komponenta Saver . . . . . . 3.8 Komponenta Generator . . .
. . . . . . . .
1 1 2 3 3 3 3 3 3 4 4 4 5 7 8 9 9 10 11
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
13 13 14 16 17 18 18 18 19
4 Realizace 21 4.1 Implementace CRS form´atu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.1 Tˇr´ıda Tcrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.2 Tˇr´ıda Crs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
xi
xii
OBSAH
4.2 4.3 4.4 4.5
Implementace komponenty GUI . . . . Implementace komponenty Saver . . . Implementace komponenty Controller Implementace komponenty Generator 4.5.1 Tˇr´ıda Normal . . . . . . . . . . 4.5.2 Tˇr´ıda Band . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
22 22 23 24 24 24
5 Testov´ an´ı
25
6 Z´ avˇ er
27
Literatura
29
Seznam obr´ azk˚ u 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8
Z´ apis matice . . . . . . . . . Z´ apis matice . . . . . . . . . Horn´ı troj´ uheln´ıkov´ a matice . Compressed row storage . . . Compressed column storage . Compressed diagonal storage Yale sparse matrix format . . Yale sparse matrix format . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
2 2 3 6 7 8 9 10
3.1 3.2
Diagram aktivit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diagram komponent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 17
xiii
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
xiv
´ U ˚ SEZNAM OBRAZK
Seznam tabulek
xv
xvi
SEZNAM TABULEK
Kapitola 1
´ Uvod 1.1
Rozbor
ˇ ıdk´e matice se velmi hojnˇe objevuj´ı v r˚ R´ uzn´ ych vˇedeck´ ych ˇci stroj´ırensk´ ych oborech pˇri ˇreˇsen´ı parci´aln´ıch diferenci´ aln´ıch rovnic. Tento specifick´ y typ matice se tak´e vyskytuje v grafick´ ych algoritmech a aplikac´ıch. Z toho plyne, ˇze hlavn´ımi z´ ajemci o takov´ y gener´ator ˇr´ıdk´ ych matic jsou v´ yvojaˇri aplikac´ı ˇreˇs´ıc´ı probl´emy pr´ avˇe z tˇechto oblast´ı, kter´e ˇr´ıdk´e matice vyuˇz´ıvaj´ı ˇci aplikac´ı prov´adˇej´ıc´ıch r˚ uzn´e maticov´e operace nad ˇr´ıdk´ ymi maticemi.. Existuje nˇekolik gener´ ator˚ u ˇr´ıdk´ ych matic, avˇsak vˇetˇsina z nich dovoluje generovat matice pouze zcela n´ ahodn´e, nejsou multiplatformn´ı nebo nemaj´ı jednoduch´e intuitivn´ı ovl´ad´ an´ı (napˇr. MatLab). C´ılem pr´ ace tud´ıˇz je vytvoˇrit aplikaci generuj´ıc´ı ˇr´ıdk´e matice a to nejen zcela n´ahodn´e, ale hlavnˇe podle dan´ ych specifikac´ı a r˚ uzn´ ych typ˚ u. Samozˇrejmˇe s jednoduch´ ym ovl´ad´an´ım, platformnˇe nez´ avisl´ a a nejl´epe rozˇsiˇriteln´a o dalˇs´ı souˇc´asti, protoˇze krit´eri´ı pro tvorbu matic a samotn´ ych typ˚ u matice m˚ uˇze b´ yt velmi mnoho.
1
´ KAPITOLA 1. UVOD
2
1.2
Definice matice
Pojem matice v matematice oznaˇcuje sch´ema ˇci tabulku obsahuj´ıc´ı matematick´e objekty. Obecnˇe je obd´eln´ıkov´eho tvaru (m´ a m ˇra´dk˚ u, n sloupc˚ u) a vˇetˇsinou obsahuje ˇc´ısla. Takovou matici naz´ yv´ame typem m x n. K oznaˇcen´ı prvk˚ u matice se pouˇz´ıv´ a index˚ u urˇcuj´ıc´ı jejich ˇr´adek a sloupec. Prvek matice A na i-t´em ˇr´adku v j-t´em sloupci oznaˇcujeme Aij . Matice se velmi ˇcasto pouˇz´ıvaj´ı napˇr´ıklad pˇri ˇreˇsen´ı line´arn´ıch rovnic nebo pˇri operac´ıch s vektory (rotace, transformace mezi b´ azemi) a tak´e pro vyj´adˇren´ı oper´ator˚ u v kvantov´e mechanice. Informace ˇcerp´ any z [4]
A=
a11 a12 ... a1n a21 . . . ... ... ... ... ... a(m−1)n am1 . . . am(n−1) amn
Obr´ azek 1.1: Z´apis matice
A=
5 3 1 7 0 6 3 10 7 1 9 4
9 3 2 3
Obr´ azek 1.2: Z´apis matice
1.3. DRUHY MATIC
1.3
3
Druhy matic
Druh˚ u matice je nepˇrebern´e mnoˇzstv´ı. Pop´ıˇsi zde pouze ty druhy, kter´e jsou relevatn´ı k t´eto pr´aci.
1.3.1
Horn´ı troj´ uheln´ıkov´ a matice
Matice, jej´ıˇz nenulov´e prvky se nach´azej´ı pouze nad hlavn´ı diagon´alou.
a11 a12 . . . a1n .. 0 . ... a2n A= . .. a 0 0 (m−1)n 0 0 0 amn
Obr´ azek 1.3: Horn´ı troj´ uheln´ıkov´a matice
1.3.2
Doln´ı troj´ uheln´ıkov´ a matice
Matice, jej´ıˇz nenulov´e prvky se nach´azej´ı pouze pod hlavn´ı diagon´alou.
1.3.3
Symetrick´ a matice
Matice je symestrick´ a pokud, kdyˇz j´ı transponujeme vznikl´a matice je shodn´a s p˚ uvodn´ı. Transponov´ an´ım se rozum´ı pˇrepis ˇr´adk˚ u do sloupc˚ u.
1.3.4
P´ asov´ a matice
Je matice, kter´ a rozˇsiˇruje diagon´aln´ı matici a to t´ım zp˚ usobem, ˇze pod´el hlavn´ı diagon´ aly jsou vedeny dalˇs´ı diagon´ aly, kter´e jsou sloˇzen´e pouze z nenulov´ ych prvk˚ u.
1.3.5
ˇ ıdk´ R´ a matice
Mezi speci´ aln´ı druhy matic patˇr´ı tzv. ˇr´ıdk´e matice. Za ˇr´ıdkou povaˇzujeme matici pokud poˇcet nenulov´ ych prvk˚ u je vzhledem k poˇctu vˇsech prvk˚ u velmi mal´ y. Obecnˇe se ud´av´a hodnota 5-10%, ale za ˇr´ıdkou mohou b´ yt oznaˇceny matice i s vˇetˇs´ım poˇctem nenulov´ ych prvk˚ u d´ıky jejich uspoˇr´ ad´ an´ı. Tento typ matic je specifick´ y t´ım, ˇze je ˇcasto velmi efektivn´ı pouˇz´ıt speci´aln´ı metody pro jejich reprezentaci v pamˇeti.
´ KAPITOLA 1. UVOD
4
1.4
Reprezentace matic v pamˇ eti
D´ale bych r´ad rozebral problematiku ukl´ad´an´ı a reprezentaci matic v pamˇeti. V praxi se obecnˇe pouˇz´ıvaj´ı velmi rozs´ ahl´e ˇr´ıdk´e matice a z d˚ uvodu specifick´ ych vlastnost´ı tˇechto matic se pro jejich reprezentaci nepouˇz´ıv´ a standartn´ıch metod. Pˇri bˇeˇzn´em zp˚ usobu je potˇreba pro matici m x n uloˇzit m*n hodnot, vˇetˇsinou za pouˇz´ıt´ı bˇeˇzn´eho dvourozmˇern´eho pole. Pro ˇr´ıdk´e matice je v´ yhodn´e pouˇz´ıt jin´e datov´e struktury, kter´e mohou v´est k velk´ ym pamˇetov´ ym u ´spor´am. Form´aty pro ˇr´ıdk´e matice lze rozdˇelit do dvou skupin. Prvn´ı skupina umoˇzn ˇuje snaˇzˇs´ı tvorbu a modifikace matice, kdeˇzto druh´a skupina je v´ıce vhodn´a pro operace s maticemi.
1.4.1
Metody vhodn´ e k vytv´ aˇ ren´ı a modifikac´ım
• DOK - dictonary of keys Pouˇz´ıv´a syst´em slovn´ıkov´eho mapov´an´ı dvojic (ˇr´adek,sloupec) k hodnot´am. • LIL - list of lists Ukl´ad´a kaˇzd´ y ˇr´ adek jako seznam obsahuj´ıc´ı ˇc´ısla sloupc˚ u a odpov´ıdaj´ıc´ı hodnoty prvk˚ u. • COO - coordinate list Ukl´ad´a celou matici jako seznam prvk˚ u trojic (ˇr´adek, sloupec, hodnota).
1.4.2
Metody vhodn´ e k maticov´ ym operac´ım
• CRS - compressed row storage • CCS - compressed column storage • CDS - compressed diagonal storage V´ıce o tˇechto metod´ ach d´ ale. Metody prvn´ı skupiny se typicky pouˇz´ıvaj´ı pˇri vytv´aˇren´ı matic a pot´e se pˇrevedou do jednoho z form´ at˚ u druh´e skupiny.
ˇ 1.4. REPREZENTACE MATIC V PAMETI
1.4.3
5
CRS - compressed row storage
Spoleˇcnˇe s form´ atem CCS nejobecnˇejˇs´ı a nejjednoduˇsˇs´ı princip ukl´ad´an´ı ˇr´ıdk´ ych matic. Form´at neukl´ ad´ a ˇz´ adn´e nadbyteˇcn´e nulov´e prvky matic, pˇredem nedˇel´a ˇz´adn´ y rozbor struktury matice (napˇr. rozloˇzen´ı nenulov´ ych prvk˚ u). Nev´ yhodou je vˇsak neefektivn´ı, protoˇze potˇrebuj´ı nepˇr´ım´ y adresn´ı krok pro kaˇzdou skal´arn´ı operaci matice-vektor. Princip form´ atu spoˇc´ıv´ a v uloˇzen´ı do souvisl´eho pamˇetov´eho prostoru po sobˇe jdouc´ı nenulov´e prvky z jednoho ˇr´ adku. Matice je reprezentov´ana tˇremi poli - r, s, hod. Pole s obsahuje index sloupce, pole r obsahuje ukazatele na prvky z pole hod, kter´e jsou v dan´em ˇr´adku prvn´ımi nenulov´ ymi a pole hod samotn´e hodnoty prvk˚ u uloˇzen´e ˇr´adek po ˇr´adku (tzv. row-wise). Pole s obsahuje indexy sloupc˚ u prvk˚ u, kter´e jsou obsahem pole hod. Z toho tud´ıˇz plyne, ˇze pole s a hod maj´ı sten´ y poˇcet poloˇzek. Pole r naopak definujeme s d´elkou m + 1, jelikoˇz podle konvence jako posledn´ı prvek ukl´ad´ame nn + 1, kde nn je poˇcet nenulov´ ych prvk˚ u a m je poˇcet ˇr´ adk˚ u matice. Plat´ı-li hod(k) = a( i, j) , pak s(k) = j, kde i je ˇc´ıslo ˇr´adku, j je ˇc´ıslo sloupce matice a index k slouˇz´ı jako index do pole s. Pole r v sobˇe uchov´av´a indexy na prvky v poli hod, kter´e jsou prvn´ımi nenulov´ ymi prvky matice v ˇr´adku i. Matematicky toto lze vyj´ adˇrit n´asledovnˇe : Za pˇredpokladu hod(k) = a( i, j) , pak r(i) ≤ k ≤ r(i + 1). Velikost pole r je rovna m + 1 , kde m je poˇcet ˇr´ adk˚ u matice. Protoˇze nejniˇzˇs´ı index ˇr´adku a sloupce je 1, obsahuje r(0) v´ ychoz´ı hodnotu 1. To umoˇzn ˇuje snadn´e zjiˇstˇen´ı poˇctu prvk˚ u na prvn´ım ˇr´adku matice pouh´ ym odeˇcten´ım hodnot r(1) − r(0). ´ Uspora m´ısta, pˇri pouˇzit´ı form´atu CRS pro uloˇzen´ı matice, je znaˇcn´a. M´ısto uloˇzen´ı n2 prvk˚ u je potˇreba pouze s 2nn + m + 1 jednotek pro uloˇzen´ı, kde nn je poˇcet nenulov´ ych prvk˚ u.
´ KAPITOLA 1. UVOD
6
Obr´ azek 1.4: Compressed row storage
ˇ 1.4. REPREZENTACE MATIC V PAMETI
1.4.4
7
CCS - compressed column storage
Tento form´ at je t´emˇeˇr totoˇzn´ y s form´atem CRS. Je tak´e zn´am pod n´azvem Harwell-Boeing˚ uv. Jedin´ y rozd´ıl oproti CRS je, ˇze hodnoty nenulov´ ych prvk˚ u jsou do pole hod ukl´ad´any po sloupc´ıch, nikoli po ˇr´ adc´ıch. Matice A je tedy opˇet uloˇzena pomoc´ı tˇr´ı pol´ı – r, s, hod. Tentokr´ at ale r obsahuje indexy ˇr´adk˚ u, do kter´ ych patˇr´ı prvky z pole hod. Analogicky k CRS je pole r stejnˇe dlouh´e jako pol hod a pole s ud´av´a indexy na prvky z pole hod, kter´e jsou prvn´ı nenulov´e prvky matice v jednotliv´ ych sloupc´ıch.
Obr´ azek 1.5: Compressed column storage
´ KAPITOLA 1. UVOD
8
1.4.5
CDS - compressed diagonal storage
V pˇr´ıpadˇe ˇze matice A je tvoˇrena p´ asy nenulov´ ych prvk˚ u pod´el hlavn´ı diagon´aly a i samotn´a diagon´ala obsahuje nenulov´e prvky je v´ yhodn´e pouˇz´ıt form´at CDS. Principem je ukl´ad´an´ı vˇsech vedlejˇs´ıch diagon´ al obsahuj´ıc´ıch nenulov´e prvky spolu s hlavn´ı diagon´alou do souvisl´eho datov´eho prostoru. T´ımto zp˚ usobem se uˇsetˇr´ı m´ısto na urˇcen´ı polohy jednotliv´ ych prvk˚ u nebo menˇs´ıch blok˚ u. Pouze staˇc´ı urˇcit o jakou diagon´al˚ u se jedn´a pot´e uloˇzit jej´ı prvky souvisle za sebou. Matice, kter´e lze takto uloˇzit obsahuje nez´aporn´e konstanty p, q, naz´ yvan´e jako lev´a a prav´a polovina p´ asma, a souˇcasne a(i,j) 6= 0 pro i − p ≤ j ≤ i + p. Pro takovou matici staˇc´ı na jej´ı uloˇzen´ı alokovat pole o rozmˇerech (1 : n, −p : q).
Obr´ azek 1.6: Compressed diagonal storage
ˇ 1.4. REPREZENTACE MATIC V PAMETI
1.4.6
9
BCRS - block compressed row storage
Pokud ˇr´ıdk´ a matice A obsahuje ˇctvercov´e bloky nenulov´ ych prvk˚ u v urˇcit´em vzoru, lze upravit form´ aty CRS nebo CCS, tak aby toho l´epe vyuˇzily. Za pˇredpokladu ˇze nb je rozmˇer kaˇzd´eho bloku, npb je poˇcet vˇsech nenulov´ ych blok˚ u v A , potom celkov´e potˇrebn´e m´ısto k 2 uloˇzen´ı takov´e matice je rovno npb ∗ nb . Rozmˇer bloku A je pot´e definov´an jako nd = n/nb . Stejnˇe jako form´ aty CRS (CCS) pouˇz´ıv´a k uloˇzen´ı matice tˇri pole. Tˇr´ırozmˇern´e pole hod(1 : npb, 1 : nb, 1 : nb), do kter´eho se po ˇr´adc´ıch (row-wise) uklad´aj´ı bloky nenulov´ ych prvk˚ u, d´ale pole s(1 : npb) obsahuj´ıc´ı indexy sloupc˚ u prvk˚ u z matice A a pole ukazatel˚ u r, kter´e ´ urˇcuj´ı zaˇc´ atky ˇradk˚ u kaˇzd´eho bloku z pole hod. Uspora m´ısta a nepˇr´ım´eho adresov´an´ı m˚ uˇze b´ yt znaˇcn´ a pro matice s velk´ ym nb. Informace o vˇsech v´ yˇse zm´ınˇen´ ych form´atech ˇcerp´any ˇci pˇrevzaty z [1]
1.4.7
Yale sparse matrix format
Form´at totoˇzn´ y s CRS, pouze s pˇrejmenovan´ ymi poli na uloˇzen´ı matice. Pole A je totoˇzn´e s polem hod. Pole JA zase s polem index˚ u sloupc˚ u s a nakonec pole IA je shodn´e s r a ukl´ ad´ a tud´ıˇz indexy z pole hodnot A na prvn´ı nenulov´e prvky z p˚ uvodn´ı matice.
Obr´ azek 1.7: Yale sparse matrix format
´ KAPITOLA 1. UVOD
10
1.4.8
New Yale sprase matrix format
Tento form´at vych´ az´ı z form´ atu Yale sparse matrix, pouze vyuˇz´ıv´a toho, ˇze obecnˇe prvky na hlavn´ı diagon´ale jsou nenulov´e a b´ yv´ a k nim pˇristupov´an´ı ˇcastˇeji neˇz k ostatn´ım prvk˚ um. Kv˚ uli tomu se prvky z hlavn´ı diagon´ aly uloˇz´ı do oddˇelen´eho pole s velikost´ı m a nemus´ı se ukl´adat pozice sloupc˚ u tˇechto prvk˚ u. Prostor po tˇechto prvc´ıch v poli JA se napln´ı obsahem pole IA a takto vznikl´e pole se oznaˇcuje IJA. Toto pole m´a potom velikost nn + 1, kde nn je poˇcet nenulov´ ych prvk˚ u matice.
Obr´ azek 1.8: Yale sparse matrix format
Texty ˇcerp´ any a obr´ azek pˇrevzat z elektronick´eho zdroje [5]
Kapitola 2
Popis probl´ emu, specifikace c´ıle C´ılem pr´ ace tedy je vytvoˇrit aplikaci generuj´ıc´ı specifick´e rozs´ahl´e matice dle zadan´ ych kriteri´ı. Mezi kl´ıˇcov´e probl´emy v tomto pˇr´ıpadˇe tedy patˇr´ı n´ahodnost rozm´ıstˇen´ı prvk˚ u a samozˇrejmˇe, protoˇze jde o velikostnˇe velmi rozs´ahl´e matice, tak´e ˇcas za kter´ y aplikace matici vygeneruje a velikost pamˇeti, kterou pˇritom bude potˇrebovat, resp. ˇcasov´a a pamˇetov´ a sloˇzitost pouˇzit´ ych algoritm˚ u.
11
12
´ KAPITOLA 2. POPIS PROBLEMU, SPECIFIKACE C´ILE
Kapitola 3
Anal´ yza a n´ avrh ˇ reˇ sen´ı 3.1
Anal´ yza prostˇ red´ı
Nejdˇr´ıve je tˇreba vybrat v´ yvojov´e prostˇred´ı, potaˇzmo programovac´ı jazyk, ve kter´ ym bude aplikace implementov´ ana. Hlavn´ı kandid´ati na v´ ybˇer jsou jazyky C++ a Java, kaˇzd´ y s r˚ uzn´ ymi v´ yhodami i nev´ yhodami, kter´e by mohli ovlivnit zp˚ usob implementace i jej´ı v´ ysledek. Aˇckoli C++ by napˇr. zˇrejmˇe poskytovalo vˇetˇs´ı moˇznosti co se t´ yˇce kontroly nad pamˇet´ı, dospˇel jsem k rozhodnut´ı pouˇz´ıt programovac´ı jazyk Java. A to hned z nˇekolika d˚ uvod˚ u. Podle zad´ an´ı by aplikace mˇela b´ yt nez´avisl´a na platformˇe, coˇz je jasn´a dominanta pr´ avˇe jazyku Java, d´ ale rozˇsiˇritelnost o dalˇs´ı moduly je podle m´eho n´azoru o nˇeco snaˇzˇs´ı v Javˇe d´ıky jej´ımu ˇcistˇe objektov´emu zamˇeˇren´ı a v neposledn´ı ˇradˇe d˚ uvodem k v´ ybˇeru tohoto jazyka byly tak´e m´e o nˇeco vˇetˇs´ı znalosti neˇz z jazyka C++. Aplikace tedy bude soubor typu .jar a bude spustiteln´a v prostˇred´ı JRE (Java Runtime Enviroment). Nebude vyuˇz´ıvat ˇz´ adn´e dalˇs´ı syst´emov´e ˇci extern´ı knihovny. V´ıce o .jar souborech a JRE zde [2] , resp. [3]
13
´ ´ ˇ SEN ˇ ´I KAPITOLA 3. ANALYZA A NAVRH RE
14
3.2
Anal´ yza implementace
Jako prvn´ı pˇred samotnou implementac´ı je potˇreba rozhodnout o pouˇzit´em form´atu pro pr´aci a ukl´ad´an´ı matic. Z v´ ybˇeru uveden´eho v u ´vodn´ı kapitole jsem vybral jako dostaˇcuj´ıc´ı a z´aroveˇ n i relativnˇe jednoduch´ y form´ at CRS. To s sebou pˇr´ın´aˇs´ı poˇzadavek na datovou strukturu potˇrebnou k uloˇzen´ı vygenerovan´e matice. Ve form´atu CRS je pro reprezentaci matice pouˇzito 3 jednorozmˇern´ ych pol´ı. Pro jednoduchost a pˇrehlednost bude vytvoˇrena tˇr´ıda obsahuj´ıc´ı pr´ avˇe tyto 3 pole, pˇresnˇeji tedy 3 objekty typu kolekce. V t´eto kapitole nast´ın´ım pr˚ ubˇeh ˇcinnosti programu, rozeberu v´ ybˇer prostˇred´ı, tak´e bl´ıˇze analyzuji pˇresnˇe druhy matic, kter´e bude aplikace generovat a s t´ım spojen´e pojmy i dopady, d´ale se budu vˇenovat rozdˇelen´ı aplikace do komponent a pop´ıˇsu jejich obsah. Hlavn´ı ˇcinnost´ı programu tedy bude vygenerov´an´ı matice a jej´ı z´apis do souboru. K tomu budou zajist´e potˇreba nˇejak´ a vstupn´ı data pro urˇcen´ı parametr˚ u matice. Podle zad´an´ı by toto mˇelo b´ yt umoˇznˇeno zad´ an´ım jak pomoc´ı parametr˚ u na pˇr´ık´azov´e ˇr´adce, tak pomoc´ı GUI. Tyto vstupn´ı data se po kontrole jejich spr´avnosti pˇredaj´ı metodˇe ˇci metod´am na samotn´e vygenerov´an´ı matice. Nakonec se bude v´ ysledek generov´an´ı pˇred´avat metodˇe obstar´avaj´ıc´ı uloˇzen´ı do souboru. Toto je relativnˇe jednoduch´ y pr˚ ubˇeh a d´ıky tomu bude staˇcit i jednoduch´e uˇzivatelsk´e rozhran´ı. Pr˚ ubˇeh ˇcinnosti aplikace je zn´ azornˇen diagramem aktivit na obr´azku 3.1
´ 3.2. ANALYZA IMPLEMENTACE
Obr´azek 3.1: Diagram aktivit
15
16
3.3
´ ´ ˇ SEN ˇ ´I KAPITOLA 3. ANALYZA A NAVRH RE
Anal´ yza generovan´ ych matic
Bylo urˇceno, ˇze aplikace bude generovat dva hlavn´ı druhy matic. Obecn´e a p´asov´e, kter´e se d´ale m˚ uˇzou liˇsit nˇekolika podtypy. U obou typ˚ u to budou matice horn´ı a doln´ı troj´ uheln´ıkov´e, symetrick´e a obecn´e bez dalˇs´ıch specifikac´ı. Dva hlavn´ı typy se budou m´ırnˇe liˇsit potˇrebn´ ymi vstupn´ımi daty. Pro oba se samozˇrejmˇe bude zad´avat rozmˇer matice. U obecn´ ych to d´ ale bude celkov´ y poˇcet nenulov´ ych prvk˚ u, jak´ y podtyp se m´a generovat a tzv. ˇs´ıˇrka elementu. Tato hodnota bude urˇcovat kolik prvk˚ u bude tvoˇrit 1 element, coˇz je nˇekolik nenulov´ ych hodnot vedle sebe. Takˇze ve v´ ysledku se na ˇr´ad´ıch matice budou vyskytovat pouze skupiny nenulov´ ych prvk˚ u jejichˇz poˇcet bude urˇcen pr´avˇe zadanou ˇs´ıˇrkou elementu. U p´asov´ ych matic se nebude zad´ avat poˇcet prvk˚ u ani ˇs´ıˇrka elementu, ale pouze ˇs´ıˇrka p´asu pod a nad hlavn´ı diagon´ alou, ˇc´ımˇz se tedy tak´e urˇc´ı zda pˇr´ıpadnˇe p˚ ujde o horn´ı ˇci doln´ı troj´ uheln´ıkovou matici. Tak´e bude moˇznost generov´an´ı symetrick´e p´asov´e matice, samozˇrejmˇe za pˇredpokladu, ˇze ˇs´ıˇrka p´ asu pod i nad hlavn´ı diagon´alou bude shodn´a, coˇz vypl´ yv´a z definice symetrick´e matice. U obou druh˚ u bude takt´eˇz moˇzn´e nastavit vygenerov´an´ı regul´arn´ı matice. Avˇsak narozd´ıl od pˇresnˇe matematicky definovan´e regul´arn´ı matice bude rozd´ıl pouze v tom, ˇze vygenerovan´a regul´ arn´ı matice nebude obsahovat pr´azdn´e ˇr´adky. To hlavnˇe protoˇze dosaˇzen´ı ”prav´e”regul´arnosti velice rozs´ ahl´ ych matic by bylo v´ ypoˇcetnˇe n´aroˇcn´e.
ˇ ´I NA KOMPONENTY 3.4. ROZDELEN
3.4
17
Rozdˇ elen´ı na komponenty
Z poˇzadavk˚ u na aplikaci lze logicky celkem dobˇre usoudit, ˇze aplikaci bude vhodn´e rozdˇelit na komponenty obstar´ avaj´ıc´ı tyto jednotliv´e ˇcinnosti. Jedna komponenta pro uˇzivatelsk´e rozhran´ı, druh´ a pro samotn´e generov´an´ı matice, tˇret´ı na ukl´ad´an´ı vygenerovan´e matice. Toto rozvrˇzen´ı pˇr´ımo vyb´ız´ı k pouˇzit´ı softwarov´e architektury MVC (Model - View - Controller), kter´a rozdˇeluje datov´ y model, uˇzivatelsk´e rozhran´ı a ˇr´ıd´ıc´ı logiku do tˇr´ı komponent. D´ıky tomuto rozdˇelen´ı bude aplikace relativnˇe pˇrehledn´a a pomoc´ı dobr´eho rozvrˇzen´ı komponent by mˇelo b´ yt i snadn´e pˇr´ıpadn´e rozˇs´ıˇren´ı o dalˇs´ı moduly v budoucnu. Po spojen´ı vˇsech tˇechto zjiˇstˇen´ı tedy vych´az´ı rozdˇelen´ı do ˇctyˇr komponent. Komponenta GUI pro uˇzivatelsk´e rozhran´ı, komponenta Generator na generov´an´ı matice, komponenta Saver obstar´ avaj´ıc´ı uloˇzen´ı do souboru a komponenta Controller, kter´a bude zajiˇstovat komunikaci a ˇr´ızen´ı ostatn´ıch komponent.
Obr´ azek 3.2: Diagram komponent
´ ´ ˇ SEN ˇ ´I KAPITOLA 3. ANALYZA A NAVRH RE
18
3.5
Komponenta GUI
Hlavn´ım u ´kolem t´eto komponenty bude umoˇznˇen´ı komunikace s uˇzivatelem a pˇr´ıjm´an´ı vstupn´ıch dat pro specifikaci generovan´ ych matic. K vlastn´ımu vytvoˇren´ı bude pouˇzito standartn´ıch knihoven AWT a SWING. Samotn´e uˇzivatelsk´e rozhran´ı nebude nikterak sloˇzit´e. Postaˇc´ı nˇekolik vstupn´ıch pol´ı pro zad´ av´an´ı vstupn´ıch hodnot jak byly nast´ınˇeny v anal´ yze generovan´ ych matic. Pˇresnˇeji tedy ˇc´ıseln´ ych hodnot na urˇcen´ı rozmˇer˚ u matice, poˇctu nenulov´ ych prvk˚ u, velikosti elementu prvk˚ u a ˇs´ıˇrky p´asu u p´asov´ ych matic, nakonec bude tˇreba nˇekolik pˇrep´ınaˇc˚ u na nastaven´ı druhu matice, moˇznost v´ ybˇeru souboru pro uloˇzen´ı a samozˇrejmˇe nˇejak´e tlaˇc´ıtko, kter´e spust´ı samotn´e generov´an´ı matice. Komponenta by takt´eˇz mˇela umoˇzn ˇovat pˇrehledn´e zobrazov´ an´ı pˇr´ıpadn´ ych chybov´ ych hl´aˇsek a pr˚ ubˇehu generov´an´ı. V souladu se zad´ an´ım bude uˇzivatelsk´e rozhran´ı tak´e umoˇzn ˇovat zobrazen´ı ˇc´asti matice. Toto zobrazen´ı bude pouze informativn´ı a pro jednoduchost bude zobrazovat v´ ysek 10x10 z vygenerovan´e matice, kter´ ym p˚ ujde posouvat.
3.6
Komponenta Controller
Tato komponenta bude obstar´ avat celkovou komunikaci mezi vˇsemi ostatn´ımi komponentami. Nejdˇr´ıve naˇcte zadan´e vstupy z komponenty GUI, kter´e zkontroluje a pˇr´ıpadnˇe j´ı poˇsle zpˇet pˇr´ısluˇsn´e chybov´e hl´ aˇsky, kter´ a je zobraz´ı. V pˇr´ıpadˇe, ˇze vstupy budou v poˇr´adku, zavol´a metody komponenty Generator s pˇr´ısluˇsn´ ymi parametry na vygenerov´an´ı matice a pot´e Saver, kter´e pˇred´ a vygenerovanou matici pomoc´ı objektu tˇr´ıdy CRS.
3.7
Komponenta Saver
Komponenta s jednoduch´ ym u ´ˇcelem, a to zaps´an´ım vygenerovan´e matice do vybran´eho souboru. Bude obsahovat tˇr´ıdu, kter´ a jako parametr dostane objekt reprezentuj´ıc´ı matici v CRS form´atu a zap´ıˇse data do souboru, kter´ y se vybere pomoc´ı GUI. Jako v´ ystupn´ı form´at byl podle rady vybr´ an Matrix Market Coordinate Format, kter´ y reprezentuje matici jednoduchou trojic´ı hodnot ˇra ´dek sloupec hodnota. Tud´ıˇz bude nejsp´ıˇse obsahovat metody na jednoduch´ y pˇrevod z CRS form´ atu. Pˇr´ıpadn´e rozˇs´ıˇren´ı o dalˇs´ı form´aty lze opˇet jednoduˇsˇse prov´est pˇrid´an´ım tˇr´ıd do komponenty.
3.8. KOMPONENTA GENERATOR
3.8
19
Komponenta Generator
Nejd˚ uleˇzitˇejˇs´ı ˇc´ ast zajiˇstuj´ıc´ı hlavn´ı n´aplˇ n aplikace, generov´an´ı matic. Jelikoˇz pro r˚ uzn´e druhy matic bude vhodn´e, ˇci dokonce nezbytn´e, pouˇz´ıvat odliˇsn´e postupy pˇri generov´ an´ı, bude komponenta obsahovat r˚ uzn´e tˇr´ıdy a metody specifick´e pr´avˇe druhem matic, kter´e budou generovat. Pˇr´ıpadn´e rozˇsiˇrov´an´ı o moˇznosti generov´an´ı dalˇs´ıch typ˚ u matic bude tedy prob´ıhat pˇrid´ an´ım dalˇs´ıch tˇr´ıd do t´eto komponenty. Pro pˇrehlednost bude definov´an abstraktn´ı interface urˇcuj´ıc´ı nutn´e rozhran´ı pro komunikaci s ostatn´ımi komponentami. Coˇz vlastnˇe bude pouze metoda vracej´ıc´ı objekt zm´ınˇen´e tˇr´ıdy reprezentuj´ıc´ı form´at CRS, kter´ a bude obsahovat vygenerovanou matici. V r´ amci zad´ an´ı bude pr´ ace obsahovat dvˇe tˇr´ıdy. Prvn´ı urˇcen´a ke generov´an´ı p´asov´ ych matic a druh´ a obstar´ avaj´ıc´ı generov´an´ı obecn´ ych matic. Pˇri prvotn´ı anal´ yze byl pl´ an na vytvoˇren´ı d´ılˇc´ıch metod pro generov´an´ı specifick´ ych matic v r´ amci tˇr´ıd. Pˇresnˇeji vlastn´ı metodu pro troj´ uheln´ıkov´e matice, dalˇs´ı na symetrick´e a nakonec pro matice obecn´eho typu. Hned v prvn´ıch f´az´ıch implementace se ale uk´ azal tento n´ avrh jako t´emˇeˇr zbyteˇcn´ y, protoˇze rozd´ıl˚ u pˇri generov´an´ı rozd´ıln´ ych typ˚ u matic bylo daleko m´enˇe neˇz spoleˇcn´eho a vedlo by to na pˇr´ıliˇsn´e opakovan´ı nadbyteˇcn´eho k´odu. Tud´ıˇz vˇsechny druhy matic bude obstar´av´at pouze jedna metoda. Respektivˇe tedy jedna hlavn´ı metoda pouˇz´ıvaj´ıc´ı mal´e mnoˇzstv´ı dalˇs´ıch metod zpracov´avaj´ıc´ı menˇs´ı d´ılˇc´ı ˇcinnosti spojen´e s generov´ an´ım matice. Protoˇze z povahy probl´emu generov´an´ı rozs´ahl´ ych matic vypl´ yv´a relativnˇe vyˇsˇs´ı n´aroˇcnnost na v´ ypoˇcetn´ı v´ ykon, bylo tak´e od prvn´ı chv´ıle poˇc´ıt´ano s v´ıcevl´aknov´ ym zpracov´an´ım. Toto vˇsak bylo do pˇredbˇeˇzn´e anal´ yzy zahrnuto pouze faktem, ˇze bude vhodn´e implementovat metody generuj´ıc´ı matici tak, aby bylo moˇzn´e generovat r˚ uzn´e ˇc´asti matice nez´avisle na sobˇe. V´ıce o tom a celkov´ ych zmˇen´ach ke kter´ ym doˇslo po prvn´ıch f´az´ı implementace pop´ıˇsi pr´avˇe v kapitole vˇenovan´e realizaci.
20
´ ´ ˇ SEN ˇ ´I KAPITOLA 3. ANALYZA A NAVRH RE
Kapitola 4
Realizace 4.1
Implementace CRS form´ atu
Podle teoretick´eho u ´vodu je pro tento form´at potˇreba 3 pol´ı uchov´avaj´ıc´ı ˇc´ıseln´e hodnoty potˇrebn´e pro reprezentaci matice. Pro pˇrehlednost byl vytvoˇren java package formats obsahuj´ıc´ı potˇrebn´e tˇr´ıdy.
4.1.1
Tˇ r´ıda Tcrs
Tˇr´ıda reprezentuj´ıc´ı datov´ y typ jednoho prvku matice. Obsahuje dvˇe celoˇc´ıseln´e hodnoty col a val pˇredstavuj´ıc´ı sloupec a hodnotu prvku.
4.1.2
Tˇ r´ıda Crs
Obsahuje 2 dynamick´e kolekce typu ArrayList. Prvn´ı s n´azvem ValCol obsahuje prvky v´ yˇse zm´ınˇen´eho typu Tcrs, ˇc´ımˇz doˇslo ke spojen´ı pol´ı Col a Val do jednoho a druh´a kolekce RowP obsahuje celoˇc´ıseln´e hodnoty. D´ale tˇr´ıda obsahuje podp˚ urn´e metody pro z´ısk´an´ı a nastaven´ı tˇechto kolekc´ı (tzv. setry a getry) a tak´e metody na z´ısk´ an´ı poˇctu ˇr´adk˚ u ˇci z´ısk´an´ı prvku Tcrs z udan´eho ˇr´adku a sloupce.
21
22
4.2
KAPITOLA 4. REALIZACE
Implementace komponenty GUI
Tato komponenta je tvoˇrena jedinou tˇr´ıdou View. Rozvrˇzen´ı uˇzivatelsk´eho rozhran´ı je realizov´ano pomoc´ı z´ aloˇzek a tˇridy JTabbedPane, kde kaˇzd´a z´aloˇzka (objekt typu JPanel) je urˇcena pro ovl´ ad´ an´ı generov´ an´ı odliˇsn´ ych druh˚ u matice. Nav´ıc tak´e jeden panel pro zobrazen´ı v´ yseku matice. Panely urˇcen´e k obsluze generov´ an´ı matic jsou velmi podobn´e a obsahuj´ı jednotliv´e vstupn´ı pole pro parametry, jejich popisky, pˇrep´ınaˇce pro v´ ybˇer typu matice a rozhran´ı pro v´ ybˇer souboru na uloˇzen´ı. Panel pro zobrazen´ı ˇc´ asti matice obsahuje vstupn´ı pole pro urˇcen´ı poˇc´ateˇcn´ıch ˇr´adk˚ u a sloupc˚ u od kter´ ych se bude zobrazovat, d´ale je moˇzn´e pohyb v´ yseku z matice ovl´adat jednoduch´ ymi tlaˇc´ıtky urˇcen´ ymi pro pohyb do stran. Velikost zobrazovan´eho v´ yseku byla zvolena 10x10. To je realizov´ ano pomoc´ı 100 jednotliv´ ych pol´ı uspoˇr´adan´ ych do matice, kter´e jsou pro jednoduchost uloˇzen´ y v ArrayListu showArea. Samotn´e zobrazen´ı prvk˚ u je realizov´ano metodou show(ArrayList<String>x), kter´a jednoduˇsˇse pˇriˇrad´ı text z jednotliv´ ych prvk˚ u vstupn´ıho ArrayList˚ u ˇretˇezc˚ u odpov´ıdaj´ıc´ım zobrazovac´ım prvk˚ um z ArrayListu showArea. Kaˇzd´ y z panel˚ u pouˇz´ıv´ a GridBagLayout pro rozvrˇzen´ı prvk˚ u a je vytv´aˇren a inicializov´an samostatnou metodou. Vytvoˇren´ı hlavn´ıho okna, pˇrid´an´ı panel˚ u m´a na starosti metoda initLayout(), kter´ a je vol´ ana v konstruktoru pˇri vytv´aˇren´ı objektu GUI. Komponenta samozˇrejmˇe tak´e obsahuje dalˇs´ı podp˚ urn´e metody a logiku uˇzivatelsk´eho rozhran´ı pro komunikaci s ostatn´ımi komponentami. Tyto metody slouˇz´ı hlavnˇe k z´ısk´av´an´ı/nastaven´ı hodnot z/do vyplnˇen´ ych pol´ı, ale tak´e napˇr´ıklad k zobrazen´ı chybov´eho hl´aˇsen´ı. Ostatn´ı metody jsou pro ˇr´ızen´ı logiky rozhran´ı (Listenery tlaˇc´ıtek, kontrola ovl´adac´ıch prvk˚ u v zobrazovac´ım panelu.)
4.3
Implementace komponenty Saver
Komponenta urˇcen´ a k ukl´ ad´ an´ı matic do souboru jej´ıˇz tˇr´ıda SaveCrs obsahuje metodu save(File file, Crs crs), kter´ a obstar´ av´ a ukl´ad´an´ı z form´atu Crs. Vstupn´ımi parametry metody je objekt typu File a Crs. Metoda nejdˇr´ıve zap´ıˇse do souboru jednoduchou hlaviˇcku podle form´atu Matrix Market a pot´e jednoduch´ ym pˇrevodn´ım algoritmem zap´ıˇse jednotliv´e prvky matice podle Matrix Market form´atu, tj. kaˇzd´ y prvek reprezentov´an jedn´ım ˇr´ adkem obsahuj´ıc´ım hodnoty ˇra ´dek sloupec hodnota.
4.4. IMPLEMENTACE KOMPONENTY CONTROLLER
4.4
23
Implementace komponenty Controller
Obsahuje jedinou tˇr´ıdu, kter´ a ˇr´ıd´ı komunikaci mezi ostatn´ımi komponentami. Podle MVC standardu obsahuje metody realizuj´ıc´ı napojen´ı na stisk tlaˇc´ıtek v komponentˇe GUI, tzv. ActionListenery. Nejd˚ uleˇzitˇejˇs´ı z nich jsou metody NormalListener() a BandListener() napojen´e na tlaˇc´ıtka spuˇstˇen´ı generov´ an´ı pro norm´aln´ı resp. p´asov´e matice. Obˇe metody nejdˇr´ıvˇe zkontroluj´ı vstupn´ı hodnoty z´ıskan´e z komponenty GUI. Pokud jsou v poˇr´adku volaj´ı odpov´ıdaj´ıc´ı metody pro generov´an´ı z komponenty Generator s pˇr´ısluˇsn´ ymi parametry. V pˇr´ıpadˇe chyby ve vstupn´ıch datech pˇredaj´ı chybov´e hl´aˇsen´ı metodˇe showError(String x) odpovˇedn´e za jejich zobrazen´ı v GUI. Dalˇs´ı metodou v komponentˇe je getShowing(int rowStart, int colStart). Ta slouˇz´ı k vytvoˇren´ı obsahu ˇc´ asti matice, kter´ a se zobraz´ı. Pˇresnˇeji tedy metoda vrac´ı ArrayList obsahuj´ıc´ı 100 ˇretˇezc˚ u s odpov´ıdaj´ıc´ım obsahem matice. Vstupn´ı parametry metody slouˇz´ı k urˇcen´ı poˇc´ateˇcn´ıch souˇradnic od kter´ ych se bude v´ ysek 10x10 zobrazovat. Obsah matice je ˇcten z Crs objektu v pamˇeti, nikoliv z uloˇzen´eho souboru a to pˇrev´aˇznˇe z d˚ uvod˚ u efektivity, aby nebylo nutn´e neust´ ale naˇc´ıtat r˚ uzn´e ˇr´adky ze souboru. Jelikoˇz panel pro zobrazen´ı ˇca´sti matice je ovl´ad´an dvˇema zp˚ usoby obsahuje komponenta v´ıce ActionListener˚ u napojen´ ych na tlaˇc´ıtka v tomto panelu. Pˇri ovl´ ad´ an´ı pomoc´ı pˇr´ım´eho zad´an´ı vstupn´ıch hodnot a tlaˇc´ıtka Zobrazit je pouˇzit ShowListener(). V t´eto metodˇe se nejdˇr´ıve zkontroluj´ı zda poˇc´ateˇcn´ı souˇradnice nepˇrekraˇcuj´ı velikost matice, v pˇr´ıpadˇe ˇze ano jsou pˇr´ısluˇsn´a chybov´a hl´aˇsen´ı posl´any metodˇe na zobrazen´ı. Jinak je zavol´ ana v´ yˇse zm´ınˇen´ a metoda getShowing(int rowStart, int colStart) s parametry z´ıskan´ ymi z GUI a jej´ı v´ ysledek je pˇred´an metodˇe show(ArrayList<String>) z GUI komponenty, kter´ a ho zobraz´ı. Dalˇs´ı moˇznost´ı je ovl´ ad´ an´ı pomoc´ı 4 tlaˇc´ıtek funguj´ıc´ıch jako smˇerov´e ˇsipky. Tento zp˚ usob je jednoduˇsˇse realizov´ an pomoc´ı 4 ActionListener metod. Kaˇzd´a je napojena na jin´e tlaˇc´ıtko a pouze podle nˇej zvyˇsuje ˇci sniˇzuje indexy poˇc´ateˇcn´ıch souˇradnic zobrazovan´eho v´ yseku a vol´an´ı metody getShowing s tˇemito nov´ ymi parametry. Aby pˇri tomto zp˚ usobu ovl´ad´ an´ı nebylo moˇzn´e se dostat u ´plnˇe mimo matici jsou tlaˇc´ıtka ˇsipek r˚ uznˇe vyp´ın´ana a zap´ın´ana podle aktu´ aln´ıho um´ıstˇen´ı zobrazovan´e ˇc´asti a velikosti matice. Toto obstar´av´a metoda chechArrows().
24
KAPITOLA 4. REALIZACE
4.5
Implementace komponenty Generator
Jak jiˇz bylo uvedeno aplikace bude vytv´aˇret 2 druhy matic - p´asov´e a norm´aln´ı. Kaˇzd´ y z druh˚ u je v komponentˇe reprezentov´ an vlastn´ı tˇr´ıdou.
4.5.1
Tˇ r´ıda Normal
Toto byla prvn´ı tˇr´ıda, kter´ a byla implementov´ana a zˇrejmˇe i proto v n´ı doch´azelo k nejvˇetˇs´ım zmˇen´am. Hlavn´ım probl´emem bylo vytvoˇren´ı algoritmu, kter´ y by spr´avnˇe, rovnomˇernˇe a hlavnˇe co nejv´ıce n´ ahodnˇe rozm´ıstil nenulov´e prvky do matice. Nakonec je cel´ y proces generov´an´ı rozdˇelen do dvou metod a jedn´e vnitˇrn´ı tˇr´ıdy rozˇsiˇruj´ıc´ı Java tˇr´ıdu Thread pro potˇreby v´ıcevl´ aknov´eho zpracov´ an´ı. • metoda preGenerate(ArrayList¡Integer¿ out, int rows,int count, int eSize, int type) • metoda generate(int rows,int cols, int count, int eSize, int type) • tˇr´ıda Segment(ArrayList
4.5.2
Tˇ r´ıda Band
Kapitola 5
Testov´ an´ı • Zp˚ usob, pr˚ ubˇeh a v´ ysledky testov´an´ı. • Srovn´ an´ı s existuj´ıc´ımi ˇreˇsen´ımi, pokud jsou zn´amy.
25
26
´ ´I KAPITOLA 5. TESTOVAN
Kapitola 6
Z´ avˇ er • Zhodnocen´ı splnˇen´ı c´ıl˚ u DP/BP a vlastn´ıho pˇr´ınosu pr´ace (pˇri formulaci je tˇreba vz´ıt v potaz zad´ an´ı pr´ ace). • Diskuse dalˇs´ıho moˇzn´eho pokraˇcov´an´ı pr´ace.
27
28
´ ER ˇ KAPITOLA 6. ZAV
Literatura [1] J.Dongarra. Sparse matrix storage formats. http://www.cs.utk.edu/˜dongarra/etemplates/node372.html, stav z 15. 2. 2010. [2] Wikipedie — jar file. http://en.wikipedia.org/wiki/JAR_(file_format), stav z 15. 2. 2010. [3] Wikipedie — jre. http://en.wikipedia.org/wiki/JRE#Execution_environment, stav z 15. 2. 2010. [4] Wikipedie — matice. http://cs.wikipedia.org/wiki/Matice, stav z 15. 2. 2010. [5] Douglas wilhelm — the yale sparse-matrix data structure. www.ece.uwaterloo.ca/˜ece250/Lectures/Slides/11.02.Sparse.ppt, 15. 2. 2010.
29
stav
z
