Search
Při práci s více vlákny lze na narazit na mnoho problémů. Jedním z nich je jak zajistit, aby si jednotlivá vlákna navzájem nepřepisovala a zároveň nečetla sdílená data. Toto by mohlo vést k nekonzistenci takových dat, což by vedlo k chybné funkci programu.
Jedním z možných řešení této situace je jednoduše neumožnit přepisování sdílených dat. V Javě se jedná o vytváření tzv. immutable objektů (tříd). U immutable objektu není možné po jeho vytvoření měnit jeho vnitřní stav. V Javě je typickým představitelem immutable objektu třídy String, v případě primitivních datových typů se jedná o použití klíčového slova final. Výhodou tohoto řešení je, že jakmile je objekt vytvořen, programátor nemusí hlídat jaká vlákna k němu přistupují (samozřejmě toto je výhoda i jednovláknových programech). Ví totiž, že se jeho stav měnit nebude a tedy nemůže dojít k nekonzistenci dat. Nevýhodou je vyšší paměťová a výpočetní náročnost. V případě potřeby změn dat je potřeba vytvořit nový objekt (copy-on-write). Viz třída String, kdy je například vytváření Stringu v iteraci neefektivní.
final
Za domácí úkol máte vytvořit immutable implementaci listu předepsaného v interface Pr2List (zkráceně list). Tento list je vlastně spojový seznam jak naznačuje i obrázek. Jedná se o druh listu běžně používaný například ve fukncionálních jazycích (Lisp, Scala …). Viz https://en.wikipedia.org/wiki/Cons. List typicky obsahuje odkaz na prvek který uchovává a na list, který obsahuje další prvky. Výjimkou je poslední prvek listu (nazývaný Nil), který reprezentuje zároveň prázný list. Zároveň také naimplementujte metody pro filtrování a mapování obsahu. Viz dále.
Jednotlivé metody listu si nyní projdeme, nezapomeňte si zároveň prostudovat javadoc:
append(T t)
cons(T t)
append
isEmpty()
size()
filter(Predicate<T> predicate)
map(Function<T, O> function)
head()
tail()
iterator()
view()
filter
map
Ukazuje se, že někdy při použití funkcí map a filter není třeba tyto hned aplikovat na všechny prvky listu, ale je výhodnější je vyhodnotit lazy. Představme si například situaci, kdy chceme z listu načíst první prvek, který splňuje daný predikát. Pak je zbytečné vyhodnotit vůči tomuto predikátu všechny prvky listu. V případě, že je list velký a víme, že někde blízko začátku se nachází vyhovující prvek, může se jednat o velkou časovou i paměťovou úsporu.
Funkce view() vrátí takovou instanci listu, která si při volání funkcí map a filter bude pamatovat zadané function a predicate a bude je vyhodnocovat teprve až to bude potřeba a to jen na minimálním množství prvků. Nezapomeňte i správně implementovat Iterator pro třídy reprezentující view. Pozor: jestltiže na view zavoláme tail(), vrátí se opět view reprezentující tail se stejnými vlastnostmi jako měl původní view.
function
predicate
Iterator
view
tail
Pro implementaci si stáhněte zdrojové kódy s příslušnými interface a factory třídou ListFactory. Řešení vytvořte do balíčku cz.cvut.k36.pr2.hw.hw06.impl. Odevzdávejte vámi vytvořené třídy potřebné k provozování listu, včetně implementované třídy ListFactory. Neodevzdávejte interface Pr2List, Predicate a Function.
ListFactory
cz.cvut.k36.pr2.hw.hw06.impl
Pr2List
Predicate
Function
nil()
Ukázkový kód práce s listem není záměrně k dispozici. Pro testování vašeho řešení si tento kód vytvořte.