Głównym językiem tego posta będzie Java8 której pisanie zużywa klawiaturę jak mało który język.. Ale będzie też o tzw. "sztuce upadania". Był o tym jakiś czas temu artykuł w magazynie Coaching - numer listopad-grudzień 2015. Konkretnie artykuł nazywa się "Dlaczego warto ćwiczyć upadanie" i w formie wywiadu opowiada o toksycznej zdaniem autorów (i nie tylko) obecnej kulturze, gdzie każdy się musi porównywać z człowiekiem obok, zawsze ale to zawsze musi się wszystko udawać a jak się nie udaje to jest tragedyja nad tragedyje.
No i przez to ludzie się boją eksperymentować i tkwią w czymś popularnie zwanym "strefa komfortu". Później w artykule jest porównanie do sztuk walki gdzie ćwiczy się pady i oswaja z sytuacją "gleby", że ta już nie jest straszna itd itp. I właśnie w tym duchu będzie ten post gdzie nie wszystko będzie działało. A w zasadzie cały czas nie będzie działało i dopiero cos pod koniec zadziała.
Ale od poczatku...
Gdzie jest mój Fold????
W Scali i nie tylko mamy na kolekcjach kilka metod, które potrafią zamienić kolekcję w "jedną rzecz". Ta "jedna rzecz" to może być intem jak np. sumujemy cyfry w liście lub nawet i inna kolekcja jeśli chcemy elementy przekształcić i (lub) przepisać. Metody nazywają się "fold,foldRight,foldLeft" i wyglądają mniej więcej tak :
def foldLeft[B](z: B)(op: (B, A) => B): B
Mamy element zerowy oraz przepis na doklejanie kolejnych kawałków .Elementy to A zaś element zerowy to B także nie muszą mieć ze sobą za wiele wspólnego. Metoda jest na tyle potężna i uniwersalna, ze można przy jej pomocy zaimplementować większość możliwych operacji na kolekcjach i nawet ma swoją stronę an wikipedii : https://en.wikipedia.org/wiki/Fold_(higher-order_function)
Czy ktoś z was ma swoją stronę na wikipedii? No właśnie...
No i w Javie8 tego nima (albo ja nie mogę tego znaleźć). Za to jest coś innego. W sensie inna operacja i pomimo, że wygląda dziwnie to niesie ze sobą coś równie silnego.
Coś innego
Pierwszy wariant to reduce z tzw. BinaryOperatorem, który jest funkcją (A,A)=>A tyle, że brzmi bardziej obiektowo i zwiększa pule typów dodanych do Javy8
Optional<T> reduce(BinaryOperator<T> accumulator);Zwraca Optional gdyż w przypadku pustego Streama nic tam nie ma (czyżby rym?).
Druga opcja dostarcza element domyślny nazwany identity i już nie potrzeba Optionala bo wiemy, ze tam coś zawsze jest.
T reduce(T identity, BinaryOperator<T> accumulator);To co jest warte uwagi to to, że tam je ino tylko jeden typ T.
No i na pewno teraz będzie jakaś sygnatura funkcji z identity o innym typie. No ma sens by tak było.Ma to sens .. ale nima. No prawie nima bo od razu jedziemy z czymś takim.
<U> U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner);To nie jest fold. To jest bardziej skomplikowane. Ale tam dzieje się coś ciekawego.
Nauka w szeroko pojętym znaczeniu
Wymiar ciekawości rozciąga się poza Javę 8 gdyż teraz na Courserze trwa kurs o programowaniu równoległym w Scali - tak w Scali - i tam tę sygnaturę wyprowadzili krok po kroku. Oczywiście na normalnych funkcjach bez wynalazków "BinaryOperator" czy "BiFunction". Ale to jest znowu taka uwaga aby edukację skalować też w szerz a nie tylko wzwyż - czyli zamiast maksymalnego ubijania jednej tylko technologi (albo nawet i kawałka technologi) tylko dlatego, że akurat "w tym robię an co dzień", poczytać trochę rzeczy pobocznych. Cały czas uważam, że jak kto chce lepiej zrozumieć naturę funkcji w Javie to powinien pouczyć się trochę Haskella bo tam te mechanizmy są naturalne.
Bo młodość jest po to by eksperymentować
Od dzieciństwa bardzo marzyłem by zebrać w jednej kolekcji 10 kolejnych liczb parzystych poczynając od zera. I dzisiaj to zrobimy :
List<Integer> even = new LinkedList<>();
List<Integer> result1 = Stream
.iterate(0, e -> e + 1)
.filter(e -> e % 2 == 0)
.limit(10)
.reduce(even,
(partial, elem) -> {
partial.add(elem);
return partial;
},
(partial1, partial2) -> {
partial1.addAll(partial2);
return partial1;
}
);
Generalnie obliczenia równoległe tego typu nie mają żadnego sensu bo narzut samej maszynerii będzie dużo większy niż gdyby jeden procek to szybko policzył ale po raz kolejny podkreślimy role edukacyjną tego problemu (także podkreślamy). Metoda reduce przyjmuje trzy argumenty :
- Element początkowy - tutaj przekazujemy standardową Listę z Javy, która nazywa się "mutowalna" chociaż pewnie takiego słowa w języku polskim nie ma. Programowanie równoległe i kolekcja mutowalna - no co może pójść źle?
- przepis jak do kolekcji dokładać nowe elementy - pewnie te kawałki pójdą równolegle
- przepis jak połączyć rezultaty cząstkowe
No i na pierwszy rzut oka działa :
System.out.println(result1); //[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]Ale działa tylko dlatego, że źle tego używam. No i pytanie jaka jest tam rola pierwszego parametru skoro i tak dostajemy rezultat z całego działania. Wszystko się wyjaśni kiedy zaczniemy tego mechanizmu używać poprawnie i dostaniemy błąd.
Równoległe
Poniższy rysunek przedstawia jak "mi się wydawało, że to działa". I nawet jeszcze dzisiaj zobaczymy jak przy pomocy pewnej listy reduce tak własnie zadziała. Ale to będzie specjalna lista a nawet nie lista tylko Wektor a w sumie Vector ale nie ten z Javy tylko inny. A ta teraz to standardowa lista - taka mutowalna - wrzucona między kilka wątków - czeka nas rzeź...
Spróbujmy niezależnie zdefiniować dwie funkcje używany w poprzednim przykładzie :
Function<List<Integer>, Integer, List<Integer>> accumulator = (partial, elem) -> { System.out.println("accumulator : " + Thread.currentThread().getName()); partial.add(elem); return partial; }; BinaryOperator<List<Integer>> combiner = (l1, l2) -> { System.out.println("combiner : " + Thread.currentThread().getName()); l1.addAll(l2); return l1; };Dodamy informacje o wątku w którym działają oraz dokonamy obserwacji, że Lista w Javie jest dziwna bo operacje nań wykonane wcale nic nie zwracają i przez to trzeba dodawać dodatkową linię z return. Oczywiście - tutaj mały spoiler - ta obserwacja pojawiła się gdyż cały czas źle tego wszystkiego używamy. Zaraz dojdzie do nas co i jak.
I teraz taki kod:
List<Integer> even2 = new LinkedList<>(); List<Integer> result2 = Stream .iterate(0, e -> e + 1) .filter(e -> e % 2 == 0) .limit(10) .reduce(even2, accumulator,combiner); System.out.println("result2 : "+result2); System.out.println("even2 : "+even2);Generuje taki rezultat :
accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main accumulator : main result2 : [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] even2 : [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]Czyli generalnie wszystko odbywa się w jednym wątku i combiner w ogóle nie jest użyty.
Można to łatwo naprawić dając "parallel" w ciąg wywołań strumienia :
.limit(10)
.parallel()
.reduce(even2, accumulator,combiner);
No i naprawiliśmy problem z ilością wątków i wywołaniem "combinera" :
accumulator : ForkJoinPool.commonPool-worker-3 accumulator : ForkJoinPool.commonPool-worker-4 accumulator : ForkJoinPool.commonPool-worker-6 accumulator : ForkJoinPool.commonPool-worker-5 accumulator : main accumulator : ForkJoinPool.commonPool-worker-1 accumulator : ForkJoinPool.commonPool-worker-6 accumulator : ForkJoinPool.commonPool-worker-2 accumulator : ForkJoinPool.commonPool-worker-4 accumulator : ForkJoinPool.commonPool-worker-3 combiner : ForkJoinPool.commonPool-worker-4 combiner : ForkJoinPool.commonPool-worker-2 combiner : ForkJoinPool.commonPool-worker-1 combiner : ForkJoinPool.commonPool-worker-2 combiner : ForkJoinPool.commonPool-worker-4 combiner : ForkJoinPool.commonPool-worker-3 combiner : ForkJoinPool.commonPool-worker-2 combiner : ForkJoinPool.commonPool-worker-3I przy okazji popsuliśmy wszystko inne :
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method) at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62) at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45) at java.lang.reflect.Constructor.newInstance(Constructor.java:423) at java.util.concurrent.ForkJoinTask.getThrowableException(ForkJoinTask.java:598) at java.util.concurrent.ForkJoinTask.reportException(ForkJoinTask.java:677) at java.util.concurrent.ForkJoinTask.invoke(ForkJoinTask.java:735) at java.util.stream.ReduceOps$ReduceOp.evaluateParallel(ReduceOps.java:714) at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:233) at java.util.stream.ReferencePipeline.reduce(ReferencePipeline.java:484) (...) Caused by: java.lang.ArrayIndexOutOfBoundsException: 240 at java.util.LinkedList.toArray(LinkedList.java:1053) at java.util.LinkedList.addAll(LinkedList.java:408)Jest ReduceOps, AbstractPipeline i kilka innych rzeczy, których przeznaczenia można się jedynie domyślać. Tak czy inaczej nie działa.
To jest ten moment kiedy zaczynasz się zastanawiać : "A może przed włączeniem trzeba było przeczytać dokumentację?". Dokumentacja : https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html w zasadzie ma wydzieloną sekcję Mutable reduction i jasno opisuje, że reduce nie jest do tego. Do rzeczy mutowalnych jest collect a reduce do niemutowalnych. Zaraz przejdziemy do collect ale wcześniej jeszcze jeden eksperyment.
Persystentna Struktura Danych
(słowa persystentna też pewnie nie ma w słowniku)Użyjemy Vector gdyż podobno twórca Javaslang brał inspiracje ze Scali a w Scali Vector jest zaimplementowany jako drzewo i czasem operacje działają na nim szybciej niż na liście... ale czasem wolniej... generalnie trzeba zawsze mierzyć ... dobra tutaj używamy Vectora by było bardziej kolorowo a nie tylko Lista i Lista
import javaslang.collection.Vector; Vector<Integer> even = Vector.empty();
Od razu nasze funkcje się uproszczą gdyż operacje na "trwałych" (może to jest to słowo) strukturach danych zwracają nowy rezultat bo inaczej nie miałoby to żadnego sensu.
BiFunction<Vector<Integer>,Integer,Vector<Integer>> accumulator= (partial, elem)->{ System.out.println("accumulator : "+Thread.currentThread().getName()); return partial.append(elem); }; BinaryOperator<Vector<Integer>> combiner=(l1, l2)->{ System.out.println("combiner : "+Thread.currentThread().getName()); return l1.appendAll(l2); };
I teraz tak napisany kod :
Vector<Integer> result = Stream .iterate(0, e -> e + 1) .parallel() .filter(e -> e % 2 == 0) .limit(10) .reduce(even, accumulator,combiner); System.out.println("even : "+even); System.out.println("result : "+result);Działa poprawnie - nie wiadomo czy szybko - ale poprawnie.
accumulator : ForkJoinPool.commonPool-worker-5 accumulator : ForkJoinPool.commonPool-worker-2 accumulator : ForkJoinPool.commonPool-worker-4 accumulator : ForkJoinPool.commonPool-worker-7 accumulator : ForkJoinPool.commonPool-worker-6 accumulator : main accumulator : ForkJoinPool.commonPool-worker-3 accumulator : ForkJoinPool.commonPool-worker-1 accumulator : ForkJoinPool.commonPool-worker-4 combiner : ForkJoinPool.commonPool-worker-7 combiner : ForkJoinPool.commonPool-worker-2 accumulator : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-1 combiner : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-7 combiner : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-1 combiner : ForkJoinPool.commonPool-worker-1 even : Vector() result : Vector(0, 2, 4, 6, 8, 10, 12, 14, 16, 18)
Ten przykład był po to aby czytelnik zdobył lepszą intuicję w rozumieniu różnic pomiędzy "trwałymi" i "nietrwałymi" (tak to an pewno te słowa!) strukturami danych oraz, że trwałe/niemutowalne nie musi koniecznie oznaczać inta - a można tak pomyśleć bo wiele przykładów na necie liczy sumę, zawsze sumę czegoś.
collect
Metoda collect wspomniana w dokumentacji wygląda tak :
<R> R collect(Supplier<R> supplier, BiConsumer<R, ? super T> accumulator, BiConsumer<R, R> combiner);Supplier i consumer to klasa tzw. "funkcji dziwnych". Pierwsza tworzy coś z niczego a druga nic z czegoś czyli po prostu połyka argument i generuje jakiś "efekt uboczny". No i w sumie to jest to czego byśmy oczekiwali przy operacji na nietrwałej strukturze danych.
List<Integer> even=new LinkedList<>(); BiConsumer<List<Integer>,Integer> accumulator= (partial, elem)->{ System.out.println("accumulator : "+Thread.currentThread().getName()); partial.add(elem); }; BiConsumer<List<Integer>,List<Integer>> combiner=(l1, l2)->{ System.out.println("combiner : "+Thread.currentThread().getName()); l1.addAll(l2); };Kod wygląda podobnie do przykładu z reduce ale już nie trzeba na siłę zwracać listy po dodaniu elementu.
No to wiooooo :
List<Integer> result = Stream .iterate(0, e -> e + 1) .parallel() .filter(e -> e % 2 == 0) .limit(10) .collect(() -> even, accumulator,combiner); System.out.println(result);i znowu jebłoooo
combiner : ForkJoinPool.commonPool-worker-3 accumulator : ForkJoinPool.commonPool-worker-6 accumulator : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-5 combiner : ForkJoinPool.commonPool-worker-6 combiner : ForkJoinPool.commonPool-worker-2 combiner : ForkJoinPool.commonPool-worker-6 combiner : ForkJoinPool.commonPool-worker-2 combiner : ForkJoinPool.commonPool-worker-2 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
Działająca wersja
No to w końcu coś co działa :
(...) .collect(LinkedList::new, accumulator,combiner); (...) combiner : ForkJoinPool.commonPool-worker-4 combiner : ForkJoinPool.commonPool-worker-4 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]Generalnie te porażki i potknięcia doskonale tłumaczą po co potrzebny jest Supplier. Każdy z niezależnych wątków musi mieć swój własny "nietrwały" półprodukt aby nie wchodzić sobie w drogę.
Collectors
Jak ktoś już Javą8 się bawił to wie, że jest 100 razy prostszy sposób na osiągnięcie tego wyniku :
.collect(Collectors.toList());i należy go stosować i zasada DRY tutaj działa. Zapisywanie do listy to częsty i standardowy problem ze standardowym rozwiązaniem - w pracy go używaj. Tutaj słowo klucz to edukacja. Edukacja jest potrzebna aby usunąć symbolikę "abstrakcji kolektora". To trochę tak jak z Hibernate używanym przez ludzi nie znających baz danych. Czasem jak "działa ale nie wiadomo dlaczego" - to jesteśmy o krok od katastrofy. Bo jak nie wiadomo jak to działa to skąd wiadomo czy ten kawałek kodu znaleziony na necie rozwiąże akurat mój problem bez generowania pięciu innych?
Podobnie można podejść do tematu dokumentacji. Tak trzeba czytać. Ale jak sobie tak sam dla siebie eksperymentujesz - to jest to dużo lepszą formą nauki. Jeśli tylko nie pracujesz z zapalnikiem bomby atomowej - zrób sobie laboratorium. Postaraj się przewidzieć, że coś jebnie i faktycznie zweryfikuj. Na pewno w mózgu zostanie więcej niż gdy wszystko się od razu uda. Po to właśnie na Code Retreat usuwa się kod, żeby ludzie przypadkiem nie pomyśleli, że chodzi o kod a nie o czynność jego tworzenia. Jedyne co ma zostać po ćwiczeniu to nowe ścieżki pomiędzy neuronami.
Brak komentarzy:
Prześlij komentarz