Key Word In Context srovn´an´ı architektonick´ych styl˚u Anton´ın Danˇek
Jakub Stejskal
Fakulta elektrotechnick´a ˇ e vysok´e uˇcen´ı technick´e Cesk´ ˇ a Republika Praha, Cesk´
[email protected]
Fakulta elektrotechnick´a ˇ e vysok´e uˇcen´ı technick´e Cesk´ ˇ a Republika Praha, Cesk´
[email protected]
Abstract—V t´eto studii porovn´av´ame cˇ tyˇri obl´ıben´e architektonick´e styly (hlavn´ı program a podprogramy, Abstraktn´ı datov´e typy, Ud´alosti a Roury & Filtry) na pˇr´ıkladu jejich pouˇzit´ı pro implementaci Key Word in Context. Zjiˇst’ujeme, v cˇ em maj´ı jednotliv´e pˇr´ıstupy k n´avrhu software siln´e a v cˇ em naopak slab´e str´anky. Keywords—Kl´ıcˇ ov´a slova: KWIC, Sd´ılen´a pamˇet’, Abstraktn´ı datov´e typy, Ud´alosti, Roury & Filtry
´ VOD I. U V dob´ach pˇred rozˇs´ırˇen´ım fulltextov´eho vyhled´av´an´ı se KWIC indexy pouˇz´ıvaly pro snazˇs´ı orientaci a vyhled´av´an´ı v textu. Typick´ym pˇr´ıpadem vyuˇzit´ı jsou indexy dˇr´ıve pˇripojovan´e k Unixov´ych MAN str´ank´am. KWIC index vznik´a vytvoˇren´ım cyklick´ych permutac´ı jednotliv´ych u´ sek˚u (zpravidla ˇra´ dk˚u) textu a jejich n´asledn´e seˇrazen´ı dle abecedn´ıho poˇra´ dku. Pˇresto, zˇ e v praxi jiˇz nen´ı vyuˇz´ıv´an, koncept Kl´ıcˇ ov´ych slov v kontextu se stal klasick´ym pˇr´ıkladem pro srovn´av´an´ı softwarov´ych architektonick´ych vzor˚u. A. Moduly KWIC Aplikaci realizuj´ıc´ı KWIC je obecnˇe moˇzno rozliˇsit do pˇeti funkˇcn´ıch modul˚u: Input - vstupn´ı modul naˇc´ıt´a ze zdroje (napˇr. textov´eho souboru) vstupn´ı data, coˇz je uspoˇra´ dan´a mnoˇzina ˇra´ dk˚u, pˇrev´ad´ı je do formy potˇrebn´e pro zpracov´an´ı dalˇs´ımi moduly a dalˇs´ımu modulu tato data tak´e pˇred´av´a cˇ i je pˇr´ıpadnˇe ukl´ad´a do sd´ılen´eho u´ loˇziˇstˇe. Circular shifter - tento modul vytv´aˇr´ı vˇsechny moˇzn´e cyklick´e permutace ˇra´ dk˚u z´ıskan´ych ze vstupn´ıho modulu. To m˚uzˇ e v z´avislosti na implementaci vyˇzadovat fyzick´e vytvoˇren´ı jednotliv´ych permutovan´ych ˇra´ dk˚u, nebo tak´e pouh´e uloˇzen´ı index˚u slov na ˇra´ dc´ıch. Alphabetizer - z´ıskan´e permutace jsou pomoc´ı tohoto modulu seˇrazeny dle abecedn´ıho poˇra´ dku. Seˇrazenost umoˇznˇ uje rychejˇs´ı vyhled´av´an´ı nad tˇemito daty v n´asleduj´ıc´ım modulu. Search - vyhled´avac´ı modul nalezne v seˇrazen´em seznamu permutac´ı ˇra´ dky zaˇc´ınaj´ıc´ı na zadan´e slovo a tyto jednotliv´e v´yskyty pˇred´av´a spolu s okoln´ımi slovy a dalˇs´ımi informacemi, jako je napˇr. cˇ´ıslo ˇra´ dky, na kter´em se slovo nach´azelo. Output - tento modul vypisuje v´ysledn´a data na v´ystup at’ uˇz do konzole cˇ i souboru.
Jednotliv´e implementace zav´adˇej´ı i nˇekter´e dalˇs´ı moduly, kter´e slouˇz´ı k ˇr´ızen´ı aplikace, sd´ılen´ı dat a podobnˇe. R˚uzn´e architektury a jejich implementace se liˇs´ı v tom, jak jsou moduly reprezentov´any (napˇr. metodami cˇ i objekty), jak´ym zp˚usobem spolu moduly komunikuj´ı cˇ i jak si pˇred´avaj´ı a sd´ılej´ı data. Kaˇzd´y z tˇechto rys˚u s sebou pˇrin´asˇ´ı moˇzn´e v´yhody cˇ i nev´yhody. Pr´avˇe popisem a porovn´an´ım tˇechto charakteristik se zab´yv´ame v n´asleduj´ıc´ıch kapitol´ach. Implementace porovn´av´ame z pˇeti r˚uzn´ych hledisek: v´ypoˇcetn´ı v´ykon, modifikovatelnost algoritm˚u, modifikovatelnost reprezentace dat, rozˇsiˇritelnost a znovupouˇzitelnost k´odu. B. Spoleˇcn´y k´od Protoˇze implementace vstupn´ıch a v´ystupn´ıch metod se napˇr´ıcˇ architekturami prakticky neliˇs´ı, rozhodli jsme se zamezit duplikaci k´odu vytvoˇren´ım spoleˇcn´eho vstupnˇev´ystupn´ıho rozhran´ı IKwicIO. Moduly Input a Output jednotliv´ych implementac´ı jsou pak pouze obalov´ymi tˇr´ıdami (resp. metodami) vyuˇz´ıvaj´ıc´ımi tohoto rozhran´ı. Toto rozhran´ı m´a pro snadnˇejˇs´ı testov´an´ı implementac´ı dvˇe r˚uzn´e implementace: souborov´e FileIO a konzolov´e ConsoleIO. Dalˇs´ı sd´ılenou tˇr´ıdou je knihovna StringOperations, kter´a poskytuje cˇ asto pouˇz´ıvan´e operace s daty, jako je pˇrevod pole slov do textov´eho ˇretˇezce a zpˇet. II. H LAVN´I PROGRAM A PODPROGRAMY SE SD´I LENOU ˇ T´I PAM E A. Struˇcn´y popis bˇehu programu Tato architektura je z uveden´ych cˇ tyˇr zˇrejmˇe nejjednoduˇssˇ´ı. Kaˇzd´y modul je realizov´an jednou metodou spoleˇcn´e tˇr´ıdy. Datov´e u´ loˇziˇstˇe je reprezentov´ano tˇr´ıdn´ım atributem, konkr´etnˇe typu ArrayList<String[]>. Moduly maj´ı do tohoto u´ loˇziˇstˇe pˇr´ım´y pˇr´ıstup a sd´ıl´ı tak veˇsker´e informace o datech. D´ıky tomu nen´ı nutn´e vytv´aˇret redundantn´ı informace ani s uloˇzen´ymi daty jakkoli manipulovat - staˇc´ı je pouze doplˇnovat o informace novˇe z´ıskan´e. Metody jsou postupnˇe vol´any hlavn´ım programem, pr´ace kaˇzd´eho modulu je proto zapoˇcata aˇz ve chv´ıli, kdy pˇredchoz´ı modul zpracoval vˇsechna data. Program je vykon´an n´asledovnˇe: • Input modul naˇ c´ıt´a data a ukl´ad´a je po ˇra´ dc´ıch do datov´eho u´ loˇziˇstˇe jako pole slov typu String.
Figure 1. UML reprezentace objekt˚u KWIC implementovan´eho pomoc´ı Sd´ılen´e pamˇeti
•
• •
•
CircularShifter vytv´aˇr´ı vˇsechny moˇzn´e cyklick´e permutace reprezentovan´e cˇ´ıslem ˇra´ dku a poˇrad´ım prvn´ıho slova permutace. Tyto indexy jsou uloˇzeny v seznamu, kter´y je dalˇs´ım tˇr´ıdn´ım atributem. Alphabetizer pˇrev´ad´ı permutace do textov´ych ˇretˇezc˚u a ˇrad´ı jejich indexy dle abecedy. Search provede vyhled´an´ı slova nad permutacemi za pomoci seˇrazen´ych index˚u metodou bin´arn´ıho p˚ulen´ı. Nalezen´e ˇra´ dky, odeˇsle do modulu Output. Modul Output vypisuje z´ıskan´y v´ysledek.
B. Zhodnocen´ı implementace pomoc´ı sd´ılen´e pamˇeti V´ykon, a to jak cˇ asov´y, tak i pamˇet’ov´y, je silnou str´ankou t´eto architektury. D´ıky sd´ılen´e pamˇeti je zde minim´aln´ı reˇzie a nedoch´az´ı k redundantn´ımu v´ypoˇctu a ukl´ad´an´ı dat. Protoˇze se ˇrazen´ı, na rozd´ıl od jin´ych implementac´ı, vykon´av´a na vˇsech datech najednou, lze s v´yhodou vyuˇz´ıt efektivnˇejˇs´ıch ˇrad´ıc´ıch algoritm˚u. Moˇznost zmˇen v algoritmu je znaˇcnˇe omezena poˇzadavkem architektury na sekvenˇcn´ı zpracov´an´ı a nelimitovan´em pˇr´ıstupu k dat˚um ze vˇsech modul˚u. Napˇr´ıklad paraleln´ı cˇ i postupn´e vyhodnocov´an´ı zde t´emˇeˇr nepˇrich´az´ı v u´ vahu. Tak´e zmˇeny v datov´e cˇ a´ sti jsou pˇri pouˇzit´ı sd´ılen´e pamˇeti pˇrirozenˇe velice n´aroˇcn´e, protoˇze jak´akoli modifikace se pravdˇepodobnˇe prom´ıtne do vˇsech modul˚u. Rozˇsiˇrov´an´ı funkcionality v r´amci modulu je moˇzn´e prov´adˇet pomˇernˇe jednoduˇse, protoˇze jednotliv´e moduly se prakticky neovlivˇnuj´ı a nekomunikuj´ı navz´ajem. Pouze postupnˇe pracuj´ı nad stejn´ymi daty. Tato v´yhoda ovˇsem miz´ı v okamˇziku, kdy nem´ame moˇznost modifikovat zdrojov´y k´od programu. Moduly jsou nedˇelitelnˇe spjaty s programem a pokud nelze z nˇejak´eho d˚uvodu program dˇedit a modul pˇrekr´yt, je aplikace prakticky nemodifikovateln´a. Znovupouˇzitelnost komponent t´eto architektury je miziv´a, nebot’ moduly jsou pˇr´ımo v´az´any na datov´e u´ loˇziˇstˇe a hlavn´ı program. III. A BSTRAKTN´I DATOV E´ TYPY A. Struˇcn´y popis bˇehu programu Architektura ADT se liˇs´ı od pˇredchoz´ı t´ım, zˇ e datov´e u´ loˇziˇstˇe jiˇz nen´ı pˇr´ımo sd´ıleno mezi moduly. M´ısto toho kaˇzd´y modul poskytuje ostatn´ım rozhran´ı pro pˇr´ıstup ke sv´ym
Figure 2. UML reprezentace objekt˚u KWIC implementovan´eho pomoc´ı ADT
dat˚um. Toto opatˇren´ı z´asadn´ım zp˚usobem ovlivˇnuje vazby mezi komponentami. Moduly jsou stejnˇe jako u pˇredchoz´ı implementace vol´any sekvenˇcnˇe po zpracov´an´ı dat pˇredchoz´ımi moduly. Vykon´an´ı programu prob´ıh´a takto: ´ loˇziˇstˇe dat. • Input modul napln´ı u • CircularShifter vytv´ aˇr´ı indexy permutac´ı podobnˇe jako je tomu u sd´ılen´e pamˇeti s t´ım rozd´ılem, zˇ e k dat˚um je pˇristupov´ano pˇres rozhran´ı datov´eho u´ loˇziˇstˇe ´ dk˚um i jejich index˚um pˇres • Alphabetizer pˇristupuje k ˇra rozhran´ı CircularShifteru a abecednˇe je ˇrad´ı. • Search provede vyhled´ an´ı slova nad permutacemi za pomoci seˇrazen´ych index˚u metodou bin´arn´ıho p˚ulen´ı. Nalezen´e ˇra´ dky, odeˇsle do modulu Output. ˇe v´ysledky na v´ystup. • Output vyp´ıs B. Zhodnocen´ı implementace pomoc´ı ADT V´ykon architektury ADT se v z´asadˇe pˇr´ıliˇs neliˇs´ı od Sd´ılen´e pamˇeti, aˇckoliv ponˇekud pˇrib´yv´a reˇzie potˇrebn´e k z´ısk´an´ı dat. Zmˇeny v algoritmu jednotliv´ych modul˚u jsou snadno realizovateln´e d´ıky jejich zapouzdˇren´ı. Zapouzdˇren´ı datov´e reprezentace znaˇcnˇe ulehˇcuje i zmˇeny v datov´e cˇ a´ sti. Dokud je zachov´ano rozhran´ı dan´eho modulu, jeho datovou strukturu lze mˇenit bez vlivu na ostatn´ı komponenty. Tato architektura naopak nen´ı pˇr´ıliˇs vhodn´a k rozˇsiˇrov´an´ı. Pˇrid´an´ı nov´ych komponent by vedlo k niˇzsˇ´ımu v´ykonu a rozˇsiˇrov´an´ı tˇech st´avaj´ıc´ıch m˚uzˇ e ohrozit jejich jednoduchost, coˇz je zpravidla neˇza´ douc´ı. Vysok´a znovupouˇzitelnost komponent je d´ana t´ım, zˇ e pˇri jejich znovunasazen´ı mus´ıme respektovat pouze jejich rozhran´ı a rozhran´ı komponent, kter´e dan´y modul vyuˇz´ıv´a.
shiftedLinesWithIndexes seˇrazen´e vˇsechny permutace ˇra´ dk˚u ze vstupu, vˇcetnˇe jejich index˚u. N´aslednˇe je spuˇstˇen bˇeh modulu Search, kter´y se pokus´ı metodou bin´arn´ıho p˚ulen´ı nal´ezt hledan´e slovo a n´aslednˇe dohledat zadan´y poˇcet slov, kter´e hledan´e slovo pˇredch´azej´ı a n´asleduj´ı. Po dokonˇcen´ı pr´ace Search modul informuje (opˇet pomoc´ı n´avrhov´eho vzoru Observer) posledn´ı modul - Output, kter´y vˇsechny nalezen´e poloˇzky vyp´ısˇe. B. Zhodnocen´ı implementace pomoc´ı ud´alost´ı
Figure 3. ud´alost´ı
UML reprezentace objekt˚u KWIC implementovan´eho pomoc´ı
´ IV. U D ALOSTI Implementaci KWIC s pouˇzit´ım ud´alost´ı jsme realizovali n´avrhov´ym vzorem Observer. Jak je vidˇet na diagramu 3, vˇsechny moduly kromˇe modulu Input implementuj´ı rozhran´ı Observer, kter´e vyˇzaduje implementaci metody update(). Skrze tuto metodu mohou b´yt moduly informov´any o zmˇen´ach na objektech, kter´e pozoruj´ı. Pozorovan´ymi objekty jsou pˇredevˇs´ım instance tˇr´ıdy LineStorage, kter´e slouˇz´ı k ukl´ad´an´ı dat a program obsahuje celkem tˇri. Jedna instance pro p˚uvodn´ı data, druh´a pro permutace tˇechto dat s indexy a tˇret´ı pro v´ystupn´ı nalezen´e ˇra´ dky. A. Struˇcn´y popis bˇehu programu Pr´ace programu zaˇc´ın´a v modulu Input, kter´emu je pˇred´ana instance LineStorage a je zde plnˇena ˇra´ dky ze vstupu. LineStorage je navrˇzen tak, zˇ e po pˇrijet´ı kaˇzd´e ˇra´ dky informuje sv´e observery o zmˇenˇe. Toto ozn´amˇen´ı vyvol´a n´asleduj´ıc´ı s´erii ud´alost´ı: • Instance originalLines informuje CircularShifter o pˇrijet´ı nov´eho ˇra´ dku. • CircularShifter pˇreˇ cte posledn´ı ˇra´ dku z originalLines a vytvoˇr´ı ze slov tohoto ˇra´ dku vˇsechny moˇzn´e permutace ˇra´ dk˚u. Tyto permutace pˇrid´av´a do dalˇs´ı instance LineStorage - shiftedLinesWithIndexes. Aby bylo moˇzn´e z permutac´ı rekonstruovat origin´aln´ı text, pˇrid´av´a na konec index p˚uvodn´ıho ˇra´ dku a poˇrad´ı slova. • Instance shiftedLinesWithIndexes informuje Alphabetizer o pˇrijet´ı nov´eho ˇra´ dku. ´ dek ze seznamu nejprve odstran´ı a • Alphabetizer ˇra n´aslednˇe jej vloˇz´ı na spr´avn´e m´ısto, aby byla zachov´ana seˇrazenost vˇsech ˇra´ dek dle abecedy (jelikoˇz bˇeh programu zaˇc´ın´a s pr´azdn´ym seznamem, budou ˇra´ dky seˇrazen´e po jedin´em pr˚ubˇehu insertion sortu). Po pˇreˇcten´ı vˇsech ˇra´ dek ze vstupu a zpracov´an´ı ud´alost´ı vyvolan´ych t´ımto cˇ ten´ım m´ame v instanci
V´ykon tohoto rˇeˇsen´ı je pomˇernˇe n´ızk´y (viz. tabulka II). Rychlost sniˇzuje reˇzie pouˇzit´eho n´avrhov´eho vzoru, kter´a vznik´a pˇri informov´an´ı observer˚u, ale ani pouˇzit´y ˇrad´ıc´ı algoritmus nen´ı ide´aln´ı. Vhledem ke zpracov´an´ı po ˇra´ dc´ıch je ˇrazen´ı postupn´ym vkl´ad´an´ım optim´aln´ı, nejedn´a se vˇsak o optim´aln´ı ˇreˇsen´ı obecnˇe. Pokud bychom nejdˇr´ıve uloˇzili vˇsechny permutace vstupu a aˇz na z´avˇer je pouze jednou seˇradili napˇr. quick sortem, dos´ahli bychom v´yraznˇe lepˇs´ıch v´ysledk˚u. Pak bychom ale nedodrˇzovali dan´y architektonick´y styl. Zmˇeny v algoritmu lze prov´adˇet u tohoto stylu d´ıky rozdˇelen´ı do jednotliv´ych tˇr´ıd pomˇernˇe snadno. Hovoˇr´ıme vˇsak o lok´aln´ıch zmˇen´ach jednotliv´ych modul˚u, pokud bychom chtˇeli prov´est nˇejakou z´asadnˇejˇs´ı u´ pravu, jako napˇr. jiˇz zm´ınˇenou zmˇenu zp˚usobu ˇrazen´ı, museli bychom pomˇernˇe radik´alnˇe zas´ahnout do cel´eho syst´em, protoˇze jsme omezeni zpracov´an´ım po ˇra´ dc´ıch. Zmˇeny v datov´e cˇ a´ sti nelze prov´est bez z´asahu do vˇsech modul˚u. Pˇri pohledu na diagram 3 je snadno vidˇet, zˇ e jsou mezi jednotliv´ymi moduly datov´e cˇ a´ sti sd´ıleny, proto bychom museli na jejich zmˇenu reagovat vˇsude, kde jsou pouˇz´ıv´any. Rozˇsiˇritelnost je u ud´alostmi ˇr´ızen´e aplikace d´ıky takˇrka nulov´emu prov´az´an´ı mezi jednotliv´ymi komponentami velmi jednoduch´a. Pokud bychom chtˇeli do aplikace pˇridat nov´y modul - napˇr. logger - staˇcilo by n´am pˇridat souˇcasn´ym Observable objekt˚um nov´eho posluchaˇce a souˇcasn´e moduly by z˚ustaly zcela bez z´asahu. Tento architektonick´y styl u sv´ych komponent nab´ız´ı i urˇcitou znovupouˇzitelnost, moduly jsou vˇsak sv´az´any s rozhran´ım Observer a pokud jsou navrˇzeny spr´avnˇe dle stejnojmenn´eho n´avrhov´eho vzoru, stanou se velmi tˇezˇ ko pouˇziteln´ymi jin´ym zp˚usobem, neˇz prostˇrednictv´ım notifikac´ı od sledovan´ych objekt˚u. Pokud bychom tak chtˇeli napˇr. pouˇz´ıt Alphabetizer v jin´e cˇ a´ sti syst´emu k seˇrazen´ı ˇretˇezc˚u, museli bychom nejdˇr´ıve vytvoˇrit instanci LineStorage, t´eto instanci pˇridat mezi observery instanci Alphabetizeru, vytvoˇrit dalˇs´ı instanci LineStorage pro v´ystup a aˇz tehdy naˇc´ıst vstupn´ı data. V. ROURY & F ILTRY Jak je vidˇet na obr´azku 4, vˇsechny moduly tohoto ˇreˇsen´ı dˇed´ı od abstraktn´ıho pˇredka Filter, kter´y definuje konstruktory pro pˇripojen´ı potˇrebn´ych rour. Roury pouˇz´ıvaj´ı knihovn´ı PipedReader a PipedWriter.
Krit´erium / Architektura
Sd´ılen´a pamˇet’
ADT
Ud´alosti
Roury& Filtry
V´ykon
9
8
3
2
Zmˇeny v algoritmu
2
5
8
9
Zmˇeny v datov´e cˇ a´ sti
1
7
4
3
Rozˇsiˇritelnost
5
3
9
8
Znovupouˇzitelnost
1
5
6
8
Table I KWIC - HODNOCEN´I DLE KRIT E´ RI´I A ARCHITEKTUR
B. Zhodnocen´ı implementace pomoc´ı rour & filtr˚u
Figure 4. UML reprezentace objekt˚u KWIC implementovan´eho pomoc´ı rour & filtr˚u
A. Struˇcn´y popis bˇehu programu Tato verze programu je realizov´ana tak, zˇ e jednotliv´e filtry mohou d´ıky implementaci rozhran´ı Runnable bˇezˇ et v samostatn´ych vl´aknech. Nejdˇr´ıve jsou vytvoˇreny vˇsechny filtry i roury a n´aslednˇe spuˇstˇeny vl´akna, ve kter´ych filtry bˇezˇ´ı. Kaˇzd´y filtr cˇ ek´a, dokud nedostane na vstupu nov´y ˇra´ dek a v pravideln´ych intervalech pˇred´av´a ˇr´ızen´ı ostatn´ım filtr˚um, aby nedoˇslo k zaseknut´ı u jednoho filtru cˇ i zahlcen´ı pˇr´ısluˇsn´e roury (v dobˇe kdy uˇz data na vstupu jsou). Po spuˇstˇen´ı vˇsech filtr˚u prob´ıh´a n´asleduj´ıc´ı postup pr´ace: •
•
•
•
•
Input filtr cˇ te po ˇra´ dc´ıch data ze vstupu a pˇred´av´a je skrze dvˇe roury jak modulu CircularShifter, tak modulu Search. Po urˇcit´e dobˇe se vzd´a ˇr´ızen´ı (plat´ı pro vˇsechny filtry a nebude znovu zmiˇnov´ano). CircularShifter parsuje data ze vstupn´ı roury. Po obdrˇzen´ı cel´e ˇra´ dky vytvoˇr´ı vˇsechny moˇzn´e permutace tohoto ˇra´ dku a zap´ısˇe je do v´ystupn´ı roury. Aby bylo moˇzn´e z permutac´ı rekonstruovat origin´aln´ı text, pˇrid´av´a na konec index p˚uvodn´ıho ˇra´ dku a poˇrad´ı slova. Alphabetizer parsuje data ze vstupn´ı roury a po obdrˇzen´ı cel´e ˇra´ dky pomoc´ı insertion sortu zaˇrad´ı ˇra´ dek do lok´aln´ı cache tak, aby byly ˇra´ dky seˇrazen´e podle abecedy. Po pˇreˇcten´ı vˇsech ˇra´ dek ze vstupu a seˇrazen´ı jejich permutac´ı dojde k odesl´an´ı tˇechto ˇra´ dek modulu Search (origin´aln´ı ˇra´ dky m´a v t´eto dobˇe jiˇz naˇcten´e). Search provede vyhled´an´ı slova nad seˇrazen´ymi permutacemi a pomoc´ı index˚u na konci ˇra´ dek zrekonstruuje z origin´aln´ıch ˇra´ dek nalezen´e ˇra´ dky, kter´e odeˇsle do modulu Output. Filtr Output vyp´ısˇe v´ysledky na v´ystup.
V´ykon tohoto rˇeˇsen´ı, je o nˇeco horˇs´ı, neˇz v´ykon verze s ud´alostmi. Kromˇe stejn´eho probl´emu s pomal´ym ˇrad´ıc´ım algoritmem je zde velk´a reˇzie pˇri pˇred´av´an´ı dat mezi jednotliv´ymi filtry, kdy doch´az´ı k opˇetovn´emu k´odov´an´ı a zpˇetn´emu parsov´an´ı ˇra´ dk˚u. Zmˇeny v algoritmu lze prov´adˇet na u´ rovni jednotliv´ych filtr˚u bez jak´ehokoliv ovlivnˇen´ı filtr˚u okoln´ıch. Kromˇe toho (na rozd´ıl od ud´alostmi ˇr´ızen´e aplikace) je zde mnohem pˇr´ıstupnˇejˇs´ı moˇznost zruˇsit ˇra´ dkov´e zpracov´an´ı a napˇr. ˇradit ˇra´ dky rychlejˇs´ım algoritmem aˇz po pˇrijet´ı vˇsech permutac´ı vstupu. Toho by v pˇr´ıpadˇe tohoto architektonick´eho stylu bylo moˇzn´e doc´ılit bez z´asahu do jin´ych filtr˚u (aˇckoliv bychom t´ımto z´asahem pˇriˇsli o paraleln´ı zpracov´an´ı). Vzhledem k tomu, zˇ e definovan´y form´at dat, jak´e filtry pˇrij´ımaj´ı a odes´ılaj´ı je jedin´e rozhran´ı, kter´e u tohoto stylu mus´ıme vyˇzadovat, zmˇeny v datov´e cˇ a´ sti nelze prov´est bez z´asahu do pˇr´ısluˇsn´ych filtr˚u. Pokud bychom se napˇr. rozhodli oddˇelovat ˇra´ dky stˇredn´ıky m´ısto znaky nov´eho ˇra´ dku, museli bychom toto zmˇenit u vˇsech filtr˚u. D´ıky tomu, zˇ e je syst´em dekomponov´an mezi jednotliv´e filtry, kter´e definuj´ı pouze form´at dat, jak´y z nich vystupuje a jak´y poˇzaduj´ı, je moˇzn´e software pouˇz´ıvaj´ıc´ı tento architektonick´y styl snadno rozˇsiˇrovat. Takov´e rozˇs´ıˇren´ı pak spoˇc´ıv´a pouze ve vytvoˇren´ı nov´eho filtru a jeho pˇripojen´ı na pˇr´ısluˇsn´e roury. Zbytek syst´emu z˚ustane neovlivnˇen. Znovupouˇzitelnost je u rour & filtr˚u velmi dobr´a. D´ıky minim´aln´ım poˇzadavk˚um na rozhran´ı je moˇzn´e filtr pouˇz´ıt kdekoliv jinde, pouze je tˇreba mu zas´ılat data ve spr´avn´em form´atu. ´ Eˇ R VI. Z AV O zˇ a´ dn´em z pouˇzit´ych styl˚u nem˚uzˇ eme prohl´asit, zˇ e by byl pro KWIC cˇ i jin´y projekt ide´aln´ı, dokud nezn´ame kompletn´ı zad´an´ı a i tehdy budeme pravdˇepodobnˇe muset pˇristoupit na kompromis mezi nˇekter´ymi poˇzadovan´ymi vlastnostmi. A. V´ykon a pamˇet’ov´a n´aroˇcnost Jak je vidˇet v tabulce II a grafu 5, nejv´ykonˇejˇs´ım ˇreˇsen´ım je styl Sd´ılen´a pamˇet’. Na druh´em m´ıstˇe je Abstraktn´ı datov´y typ, kter´y je oproti prvn´ımu m´ıstu asi 3* pomalejˇs´ı, ale v obou pˇr´ıpadech doch´az´ı se zvˇetˇsov´an´ım vstupn´ıch dat pouze k line´arn´ımu r˚ustu cˇ asu (na vˇetˇs´ım vzorku dat bychom
architektonick´y styl / cˇ as
1000 rˇ a´ dek
3000 rˇ a´ dek
9000 rˇ a´ dek
architektonick´y styl / datov´y objem
1000 rˇ a´ dek
3000 rˇ a´ dek
9000 rˇ a´ dek
Sd´ılen´a pamˇet’
361ms
1.306ms
3.324ms
Sd´ılen´a pamˇet’
2.963kB
2.493kB
5.704kB
Abstraktn´ı datov´e typy
1.143ms
3.395ms
10.800ms
Abstraktn´ı datov´e typy
4.288kB
5.924kB
9.548kB
Ud´alosti
1.574ms
14.450ms
157.358ms
Ud´alosti
1.903kB
5.492kB
19.543kB
Roury & Filtry
6.463ms
20.666ms
192.731ms
Roury & Filtry
3.404kB
10.305kB
31.575kB
Table II ´ Cˇ NOST JEDNOTLIV YCH ´ ˇ E Sˇ EN´I KWIC - Cˇ ASOV A´ N ARO R
Figure 5.
KWIC - cˇ asov´a n´aroˇcnost jednotliv´ych ˇreˇsen´ı - graf
Table III ´ Cˇ NOST JEDNOTLIV YCH ´ ˇ E Sˇ EN´I KWIC - PAM Eˇ T’ OV A´ N ARO R
Figure 6.
KWIC - pamˇet’ov´a n´aroˇcnost jednotliv´ych ˇreˇsen´ı - graf
pravdˇepodobnˇe zjistili, zˇ e jde o r˚ust n*long(n)). U ud´alost´ı a filtr˚u cˇ asov´e n´aroky rostou kvadratickou rychlost´ı, coˇz je zp˚usoben´e pouˇzit´ym typem ˇrad´ıc´ıho algoritmu. To sam´e plat´ı i pro pamˇet’ov´e n´aroky (viz. tabulka III a graf 6), aˇckoliv u menˇs´ıch vstup˚u doch´az´ı k urˇcit´ych v´ykyv˚um, kter´e jsou pravdˇepodobnˇe zp˚usobeny optimalizac´ı alokace pamˇeti v JVM1 .
Pokud bude n´asˇ software v budoucnu hojnˇe rozˇsiˇrov´an, mˇeli bychom zvolit Ud´alosti nebo Roury & Filtry. Oba tyto styly umoˇznˇ uj´ı pˇrid´an´ı nov´eho modulu bez nutnosti z´asahu do ostatn´ıch, p˚uvodn´ıch modul˚u. Naopak velmi nevhodn´ym stylem v tomto ohledu je Abstraktn´ı datov´y typ, kde jsou moduly silnˇe prov´azan´e.
B. Zmˇenitelnost algoritmu
E. Znovupouˇzitelnost
Pokud bychom navrhovali software, u kter´eho se d´a pˇredem oˇcek´avat, zˇ e bude potˇreba mˇenit zp˚usob jak´ym pracuje, nejlepˇs´ım ˇreˇsen´ım bude styl Roury & Filtry a srovnatelnˇe dobr´e ˇreˇsen´ı budou tak´e Ud´alosti. Vyloˇzenˇe nevhodn´ym stylem je z d˚uvodu minim´aln´ıho zapouzdˇren´ı a nutnost´ı zasahovat pˇri zmˇen´ach do cel´eho programu Sd´ılen´a pamˇet’.
Nejsnadnˇeji znovupouˇziteln´e jsou komponenty stylu Roury & Filtry, kde je pouze nutn´e dodrˇzovat form´at dat, jak´e filtry poˇzaduj´ı, zˇ a´ dn´e dalˇs´ı omezen´ı zde nejsou. Naopak nejh˚uˇre znovupouˇziteln´e jsou ze zˇrejm´ych d˚uvod˚u moduly stylu Sd´ılen´a pamˇet’.
D. Rozˇsiˇrovatelnost
R EFERENCES C. Zmˇenitelnost datov´e cˇ a´ sti Ke zmˇen´am form´atu dat s jak´ym aplikace pracuje je benevolentn´ı pouze styl Abstraktn´ı datov´e typy a to d´ıky jejich dobr´emu zapouzdˇren´ı. Velmi nevhodn´ym je pak styl Roury & Filtry, kde definice form´atu dat souˇcasnˇe definuje i rozhran´ı filtr˚u a jeho zmˇena by zp˚usobila nutnost prov´est zmˇeny po cel´e aplikaci. 1 Java
Virtual Machine
ˇ y, 08.05.2011, [1] Architektura softwarov´ych syst´em˚u, Ing. Tom´asˇ Cern´ http://icpc.felk.cvut.cz/web/slides/y36ass/Arch/1 styly.pdf [2] An Introduction to Software Architecture, David Garlan, Mary Shaw, 08.05.2011, http://www.cs.cmu.edu/afs/cs/project/vit/ftp/pdf/intro softarch.pdf
