Krótkie podsumowanie DSP2017

Tym razem będzie krótka nietechniczna notka 🙂

Ponownie udało mi się dotrwać do końca konkursu Daj Się Poznać! 🙂

Napisałem 20 postów, z czego:

  • 10 na temat projektu, który tworzyliśmy razem w ramach konkursu :),
  • 9 na temat związane z Javą lub około programistyczne,
  • 1 na temat moich wrażeń z warsztatów programistycznych.

Co do założeń projektu to udało się ukończyć ‚core’ aplikacji – czyli w sumie najważniejszą część, ta która wykrywa nam plagiaty 🙂

Niestety nie udało się skończyć (a właściwie zacząć ;)) REST API, które wystawiałoby odpowiednie metody do wykonania obliczenia prawdopodobieństwa oraz samego GUI. Mam nadzieję, że mimo wszystko te części i tak powstaną 🙂

To by było na tyle 🙂 Do usłyszenia w kolejnych wpisach! 🙂

Testowania część druga!

Dzisiaj przetestujemy nasz algorytm po raz kolejny!

Zestaw testowy

Tym razem jako zestaw testowy posłużą nam kody źródłowe z kursu programowania z moich studiów. Podczas kursu trzeba było między innymi napisać programy, które rozłożą liczbę na czynniki pierwsze oraz wyliczą sito Eratostenesa. I właśnie kody źródłowe do tych dwóch zadań poddamy testom.

Udało mi się skolekcjonować po 5 różnych rozwiązań dla każdego z tych zadań. Wszystkie kody źródłowe są dostępne tutaj.

Testowanie

Przetestujmy kody źródłowe dla każdego zadania osobno.

Rozkład liczby na czynniki pierwsze

Zacznijmy najpierw od wczytania kodów źródłowych i wyliczenia prawdopodobieństw.

Po wywołaniu powyższego kodu otrzymaliśmy następujące wyniki:

Przeglądając wyniki możemy zauważyć, że kody źródłowe programów 4 i 5 zostały wskazane jako bardzo podobne do siebie. Zachęcam, aby przejrzeć te kody oraz porównać również z innymi. Łatwo możemy zauważyć, że te dwa kody źródłowe wykazują bardzo dużo cech wspólnych 😉

Podobnie sprawa wygląda w przypadku kodów 1 i 2, lecz podobieństwo jest już trochę mniej widoczne.

Sito Eratostenesa

Kolejnym zestawem będą programy, które implementują algorytm Sita Eratostenesa. Podobnie jak poprzednio zacznijmy od wczytania kodów źródłowych i wyliczenia podobieństw pomiędzy nimi.

I wyniki, które otrzymaliśmy po uruchomieniu powyższego kodu:

Tutaj możemy dostrzec, że największe prawdopodobieństwo plagiatu zachodzi pomiędzy programami 1 i 2. I ponownie gdy obejrzymy oba kody źródłowe znajdziemy widoczne podobieństwo.

Podsumowanie

Dzisiaj przetestowaliśmy nasz algorytm na zestawie kodów źródłowych z moich studiów. Analizując wyniki mogliśmy wskazać kody, które wykazywały nieprzeciętne podobieństwo 😉 Wydaje się, że algorytm działa dosyć dobrze i całkiem nieźle wskazuję podobne kody źródłowe.

XStream, czyli taka lepsza serializacja!

Dzisiaj omówimy bibliotekę służącą do serializacji obiektów w Javie – XStream.

Serializacja w Javie

Po co nam biblioteka do serializacji skoro sama Java dostarcza nam taki mechanizm? Spójrzmy zatem jak to wygląda w Javie.

Na początku stwórzmy sobie prostą klasę z kilkoma polami, której instancje będziemy serializować.

Teraz stwórzmy instancje naszej klasy i ją zserializujmy, a następnie zdeserializujmy.

Jak widzimy sama serializacja jest dosyć prosta i możemy ją łatwo wykonać w kilku liniach kodu.

Zerknijmy teraz do naszego pliku, który zawiera zserializowany obiekt.

Jak widzimy nie jest to zbyt czytelne 😉

Niestety z tego pliku nie jesteśmy w stanie w łatwy sposób odczytać zserializowanych wartości, nie mówiąc o ich edycji.

XStream w akcji!

I tutaj z pomocą przychodzi XStream!

Na początku musimy dodać zależność do naszego projektu:

Zróbmy teraz najprostszą serializacje i deserializacje naszego obiektu.

Jak widać operacje te przy użyciu XStream również możemy wykonać przy użyciu kilku linii kodu.

Na samym początku musimy stworzyć instancje XStream, a następnie wywołać na niej odpowiednio metody toXML lub fromXML. Pierwsza metoda przyjmuje jako parametry obiekt, który ma być zserializowany oraz OutputStream, do którego zserializowany obiekt ma być zapisany. Druga metoda natomiast na wejście przyjmuje InputStream, z którego ma być odczytany zserializowany obiekt, a na wyjściu otrzymujemy nasz zdeserializowany obiekt.

Zajrzyjmy teraz do pliku z zserializowanym obiektem.

Jak widać plik jest w formacie XML (co mogła sugerować nazwa metody toXML ;)). Z pliku możemy odczytać, która klasa jest zserializowana – pl.lantkowiak.SerializableClass. Widzimy też pełną strukturę klasy wraz z wartościami poszczególnych pól. Dzięki temu bez problemu możemy odczytać jak wygląda zapisany obiekt, a w razie potrzeby możemy go bez problemy edytować.

Podsumowanie

Dzisiaj zapoznaliśmy się z biblioteką XStream, której możemy użyć do serializacji obiektów do XMLa, dzięki czemu zserializowany obiekt będzie dla nas czytelny i łatwy do modyfikacji.

XStream posiada jeszcze bardziej zaawansowane opcje, z którymi warto się w przyszłości zapoznać 🙂

Przetestujmy skuteczność algorytmu – część pierwsza!

Dzisiaj zajmiemy się przetestowaniem naszego algorytmu do wykrywania plagiatów w praktyce. Miejmy nadzieję, że to chociaż trochę zadziała 😉

Zestaw testowy

Musimy najpierw zacząć od przygotowania danych, na których będziemy testować naszą aplikacje.

Dzisiaj przygotujemy specjalnie spreparowane kody źródłowe i zobaczymy jak z nimi poradzi sobie nasza aplikacja.

Zacznijmy od stworzenia naszej wyjściowej klasy, która będzie zawierała kilka pól oraz metod.

Będzie to nasz wyjściowy kod, od którego będziemy robić wszystkie modyfikacje.

Wykonajmy następujące modyfikacje kodu:

  1. Zmieńmy nazwy metod i pól
  2. Przenieśmy operacje z metod do metody main, a same metody usuńmy
  3. Dodajmy kilka nieużywanych metod
  4. Czwartym kodem do porównania, będzie kopia oryginalnego kodu

Testujemy!

Stwórzmy prostą metodę, która wczyta nasze kody źródłowe oraz wywoła naszą aplikacje i wyliczy prawdopodobieństwo.

Omówmy wyniki!

Pora na krótką analizę wyników.

  1. Zmienione nazwy metod i pól
    Program zwrócił następujący wynik:

    Tutaj możemy zauważyć, że program poradził sobie całkiem nieźle. Wskaźniki są bardzo bliskie 1, więc możemy z dużą dozą prawdopodobieństwa stwierdzić, że porównywane programy zawierają ten sam kod.
  2. Kod z metod przeniesiony do głównej metody
    Zwrócony wynik:

    Tutaj niestety algorytm poradził sobie dużo gorzej. Wystarczyła drobna zmiana w kodzie i stopień wykrywalności jest o wiele mniejszy. Może to byś spowodowane tym, że testowany kod jest krótki i nawet takie małe zmiany znacząco wpływają na wyniki. Warto na pewno się temu przyjrzeć w przyszłości.
  3. Kod z nieużywanymi metodami
    Wyliczone podobieństwo:

    Na tym przykładzie możemy zobaczyć w praktyce wykorzystanie wskaźników px oraz py. O ile główny wskaźnik wynosi tylko 0.63 i nie musi wydawać się podejrzany, o tyle wartość wskaźnika px (0.92) mocno wskazuje, że jeden z porównywanych kodów zawiera dużą część drugiego kodu, oraz że mógł zajść plagiat.
  4. Porównanie dwóch identycznych kodów źródłowych
    Wynik:

    Tutaj podobnie jak w pierwszym przypadku algorytm poradził sobie bardzo dobrze i wyliczył wskaźniki bliskie 1.

Podsumowanie

Dzisiaj wykonaliśmy pierwsze testy naszego algorytmu. Do testów użyliśmy kilka spreparowanych kodów źródłowych. Pierwsze wyniki wskazują, że algorytm jakieś prawdopodobieństwo wylicza 😉

W następnym wpisie odnośnie PlagDetectora przeprowadzimy testy na kodach źródłowych z28za czasów studenckich 😉

Wrażenia z warsztatów ReactJS

Dzisiaj opowiem o swoich wrażeniach z warsztatów ReactJS, na których ostatnio byłem.

Jakie warsztaty?

Warsztaty, o których miałem przyjemność być to  „React.js dla programistów znających JS”. Spotkanie był organizowane przez DevMeetings, we Wrocławiu. Celem warsztatów, jak sama nazwa wskazuję ;), było wprowadzenie nas do Reacta oraz zbudowanie naszej pierwszej aplikacji w Reactie.

Jaki był materiał?

Teraz kilka słów o samym materiale, który był poruszony w czasie warsztatów.

Krótkie przypomnienie JSa

Na początku zostało przypomniane kilka użytecznych funkcji JSowych, które miały się przydać w dalszej części kursu. Przypomnieliśmy sobie o takich funkcjach jak:

  • map
  • filter
  • arrow functions
  • classes

I w końcu React!

Czyli pora na mięso 🙂

  • pierwsza funkcja w ReactJS
  • Komponenty
  • Klasy
  • Obsługa eventów
  • Obiekty stanowe
  • Routing

    Redux

    Czyli dodatek do Reacta, który służy do zarządzania stanem. aplikacji. Został on wspomniany raczej na zasadzie ciekawostki czego się używa w poważnych aplikach ;). My nie mieliśmy okazji go używać na warsztatach.

Moje wrażenia

I na końcu kilka słów o moich subiektywnych wrażeniach z warsztatów 🙂

Był to dla mnie pierwszy kontakt z Reactem. Na tych kilku-godzinnych warsztatach dostałem wystarczająco informacji, żeby mieć jakiekolwiek pojęcie z czym to się je. Warsztaty dla mnie były prowadzone w fajnej formie i wyglądało na to, że prowadzący się zna na rzeczy 🙂

Jedynym minusem, który odnotowałem był brak wcześniejszej informacji o wymaganych toolach. Przez to na początku straciliśmy około 30 minut czekając, aż wszystkie osoby będą miały zainstalowane nodeJS itd. Po za tą drobnostką wszystko było ok 🙂

Podsumowując – jestem zadowolony z warsztatów i w przyszłości z chęcią pójdę na nie jeszcze raz jak pojawi się interesujący temat 🙂

Wyliczmy podobieństwo!

W poprzednim wpisie dotyczącym PlagDetectora zajmowaliśmy się kompresją tokenów. Dzisiaj zajmiemy się trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobieństwa pomiędzy kodami źródłowymi.

Mała powtórka

Na początku wróćmy do wpisu gdzie omawialiśmy cały algorytm i przypomnijmy sobie kilka wzorów.

Wartość aproksymacji Kołmogorowa będziemy przybliżać przy pomocy poniższego wzoru.
{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}.

Przez {\emph{K(x)}} będziemy rozumieć wielkość (w bajtach) skompresowanego kodu źródłowego i będziemy oznaczać jako {\emph{Comp(x)}}. W związku z tym wzór na przybliżenie aproksymacji Kołmogorowa przyjmie postać:

{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}.

Wartość {\emph{Comp(x|y)}} obliczymy w następujący sposób:
{Comp(x|y) = Comp(xy) - Comp(y)}.

Zatem ostatecznie wartość aproksymacji Kołmogorowa obliczymy z następującego wzoru:
{d(x,y) = 1 - \frac{Comp(x)+Comp(y)-Comp(x|y)}{Comp(xy)}}.

Tak obliczona wartość aproksymacji złożoności Kołmogorowa przeliczymy na współczynnik {\emph{D}} według wzoru:
{D = 1 - d(x,y)}.

I ten właśnie wskaźnik będzie naszym głównym wyznacznikiem, którego będziemy używać do oceny prawdopodobieństwa zajścia plagiatu.  Im wartość {\emph{D}} jest większa, tym prawdopodobieństwo plagiatu jest większe.

Dodatkowo dla każdej pary programów obliczymy wartości {\emph{px}} oraz {\emph{py}}. Wartości te będą przedstawiać procentową zawartość informacji z jednego kodu źródłowego zawartych w drugim. Wartości te obliczymy używając następujących wzorów:
{px=\frac{D(\alpha + 1)}{D+1}},
{py=\frac{D(\frac{1}{\alpha} + 1)}{D+1}}, gdzie:
{\alpha = \frac{Comp(y)}{Comp(x)}}.

Wskaźniki {\emph{px}} i {\emph{py}} posłużą nam jako dodatkowa informacja, wskazująca na zawartość jednego ciągu w drugim. Wartości te pomogą nam wskazać zajście plagiatu, w przypadku gdy jeden z programów zawiera w sobie kod drugiego, lecz sam program jest o wiele bardziej rozbudowany i wartość współczynnika {\emph{D}} może nie wskazać zajścia plagiatu.

I teraz kodowanie!

Zacznijmy od klasy, która przechowa nasze wyniki.

Podobnie jak przy tworzeniu klasy do przechowywania wyników kompresji – banał 😉

Teraz pora na obliczenia!

Tym razem nie zobaczymy żadnej magii w kodzie. Mamy tylko zwykłe przepisanie wzoru na Kotlina 😉

Podsumowanie

Dzisiaj zajęliśmy się ostatnim krokiem algorytmu, a mianowicie aproksymacją złożoności Kołmogorowa. Przypomnieliśmy sobie wzory potrzebne do obliczeń, a następnie zaadoptowaliśmy te wzory do naszego kodu. W następnym wpisie wykonamy w końcu nasze 3 kroki razem i przetestujemy działanie algorytmu 🙂

Działanie na kilka frontów – czyli o wątkach słów kilka

Dzisiaj porozmawiamy sobie o działaniu na kilka frontów 😉 Czyli zobaczymy co to jest wątek i z czym to się je 🙂

W tym wpisie zajmiemy się głównie sposobami tworzenia wątków.

Czym zatem jest ten wątek?

Wątek jest niezależną ścieżką wykonania działającą w ramach procesu.

Czym zatem jest proces? Proces jest to egzemplarz wykonywanego programu.

Jak zatem widzimy wątek jest wykonywany w ramach procesu. W ramach jednego procesu może być wykonywanych wiele wątków.

Powinniśmy również wiedzieć, że wątki dzielą zasoby pomiędzy sobą w ramach jednego procesu, natomiast każdy proces ma przydzielone swoje zasoby.

Wątki w Javie

W Javie wątki są reprezentowane przez klasę Thread.

Nowy wątek możemy utworzyć w Javie na 3 sposoby:

  1. Rozszerzając klasę Thread
  2. Implementując interfejs Runnable
  3. Implementując interfejs Callable

Czym się różnią te podejścia?

Rozszerzenie klasy Thread

Aby utworzyć wątek musimy rozszerzyć klasę Thread oraz nadpisać metodę run.

W metodzie run umieszczamy nasz kod, który zostanie wykonany w naszym nowym wątku.

Implementacja interfejsu Runnable

Interfejs Runnable wymaga przez nas zaimplementowania jednej  metody – run.

Podobnie jak w poprzednim przypadku kod, który ma być wykonany w wątku umieszczamy w metodzie run.

Implementacja interfejsu Callable

Interfejs Callable jest generyczny i dostarcza metodę call, która zwraca obiekt typu, którego użyliśmy przy implementacji Callable.

Tym razem kod, który ma się wykonać w nowym wątku umieszczamy w metodzie call. Dodatkowo call wymuszą zwrócenie obiektu. Zwróćmy również uwagę, że Callable deklaruje możliwość rzucenia wyjątku kontrolowanego (checked exception).

Co wybrać?

Poznaliśmy 3 sposoby tworzenia wątków w Javie, ale który powinniśmy używać?

Sposobu pierwszego, czyli rozszerzania klasy Thread będziemy prawdopodobnie używać najrzadziej. Musimy pamiętać, że dziedziczenie powinno spełniać warunek IS-A, czyli klasa pochodna powinna być typem klasy nadrzędnej. Raczej rzadko będziemy spotykać się z sytuacją gdzie tworzona przez nas klasa będzie musiała rozszerzać Thread, aby rozszerzać jej funkcjonalność. Więcej o dziedziczeniu i kompozycji porozmawiamy w jednym z kolejnych wpisów.

Czyli pozostały nam dwie opcje Runnable i Callable. Tutaj powinniśmy dokonać wyboru mając na uwadze różnice pomiędzy tymi interfejsami:

  • metoda run z interfejsu Runnable jest typu void, natomiast metoda call z Callable zwraca wynik obliczeń
  • metoda call pozwala zadeklarować wyjątki kontrolowane (checked exceptions), czego nie pozwala metoda run.

Podsumowanie

Dzisiaj omówiliśmy sposoby tworzenia wątków w Javie. Powinniśmy zapamiętać, że wątek możemy stworzyć na 3 sposoby:

  • rozszerzając klasę Thread,
  • implementując interfejs Runnable,
  • implementując interfejs Callable.

W następnym wpisie związanym z wątkami omówimy sposoby na uruchomienie i zarządzanie naszymi wątkami.

Czas na trochę kompresji!

W poprzednim wpisie na temat PlagDetectora opisaliśmy tokenizacje kodu źródłowego. Był to pierwszy z trzech etapów całego algorytmu. Dzisiaj zajmiemy się drugim krokiem, czyli kompresją tokenów.

Kilka słów o samej kompresji

Kompresja, jak sama nazwa wskazuje ;), jest to przetworzenie pewnej informacji w taki sposób, aby można było zapisać tą informacje w krótszy sposób. Przez słowo krótszy mam na myśli przy użyciu mniejszej ilości bajtów. Operacją odwrotną do kompresji jest dekompresja.

Rodzaje kompresji

Kompresje możemy podzielić na stratną oraz bezstratną. Jak sama nazwa wskazuje, w przypadku kompresji stratnej tracimy część informacji, dzięki czemu powinniśmy uzyskać większy współczynnik kompresji (przynajmniej w teorii ;)).

Oczywiście istnieje wiele algorytmów kompresji, które możemy przyporządkować do kompresji stratnej lub bezstratnej.

Spójrzmy na poniższy podział algorytmów.

  • Kompresja bezstratna
    • Kodowanie Huffmana
    • Kodowanie arytmetyczne
    • Kodowanie Shannona
    • Algorytmy słownikowe
      • LZ77
      • LZ78
      • LZW
    • PNG
  • Kompresja stratna
    • Kodowanie transformatowe
    • Kompresja falkowa
    • JPEG
    • MPEG

Oczywiście to nie są wszystkie istniejące algorytmy kompresji, ale wydaję mi się, że te najbardziej znane 🙂

Który algorytm wybrać?

Jak widzieliśmy, jest wiele algorytmów kompresji bezstratnej. Który zatem powinniśmy wybrać? Sugerując się tym co wybrali twórcy algorytmu SID (opisanym w jednym z poprzednich wpisów), również skupimy się na kodowaniu słownikowym, a konkretnie LZ77. Czemu własnie LZ77, a nie żaden z innych algorytmów kodowania słownikowego jak LZ78 czy LZW, które są rozwinięciem LZ77 (i często działają lepiej)? Zaraz wszystko powinno się wyjaśnić 🙂

Trochę teorii 🙂

Spójrzmy najpierw jak działa LZ77.

Jak wcześniej wspomnieliśmy, LZ77 jest algorytmem słownikowym? Znaczy to dokładnie tyle, że do zakodowania/odkodowania tekstu używamy słownika. W LZ77 słownik jest dynamiczny, czyli taki słownik, który jest tworzony w trakcie kodowania. Słownik tego typu ma również tę zaletę, że dostosowuje się do charakteru danych. W LZ77 słownikiem jest zakodowana/odkodowana część tekstu.

I teraz sam algorytm w teorii:

  • Dla zakodowanej części długości n i niezakodowanej długości m, czyli dla ciągu {x_1 \ldots x_nx_{n+1} \ldots x_{n+m}} szukamy najdłuższego podsłowa w ciągu ̇ {x_1 \ldots x_n} będącego prefiksem ciągu {x_{n+1} \ldots x_{n+m}} (dopasowanie).
  • Jako kod podajemy trzy liczby:
    • wielkość przesunięcia w lewo
    • ilość kopiowanych znaków
    • kod pierwszej niepasującej litery
  • Jeżeli pojawia się nowa litera, której nie można znaleźć w zakodowanej części to do słownika dodajemy {(0, 0, LITERA)}

Brzmi skomplikowanie, ale przykład powinien nam wszystko wyjaśnić 🙂

Najpierw ustalmy nasze n (bufor słownika) i (bufor kodowania). Przyjmijmy odpowiednio 7 i 8. Spróbujmy teraz zakodować następujący ciąg: abccba-abba.

  • abccba-abba    (0, 0, a)
  • abccba-abba    (0, 0, b)
  • abccba-abba    (0, 0, c)
  • abccba-abba    (1, 1, b)
  • abccba-abba    (5, 1, -)
  • abccba-abba    (7, 2, b)
  • abccba-abba    (0, 0, a)

Zatem ostatecznie nasz zakodowany ciąg ma postać powyższych siedmiu ‚trójek’, czyli: (0, 0, a), (0, 0, b), (0, 0, c), (1, 1, b), (5, 1, -), (7, 2, b), (0, 0, a).

Czemu właśnie LZ77?

I teraz wracamy do kwestii wyboru algorytmu. Dlaczego właśnie LZ77? Tak jak pisaliśmy w jednym z poprzednich wpisów, musimy ustawić nieskończony bufor słownika i bufor kodowania. Wiążę się to oczywiście z wydłużeniem czasu kompresji, ale dzięki temu możemy uzyskać większy stopień kompresji.

W tym samum wpisie, w kolejnej sekcji, jest opisana część z aproksymacją złożoności Kołmogorowa. W jednym ze wzorów możemy dopatrzeć się, że kompresji będzie również poddana lista składająca się z tokenów z dwóch porównywanych kodów źródłowych. Jakie to ma znaczenie przy wyborze algorytmu kompresji?

Wróćmy do naszego przykładu i zastanówmy się co by się stało jakbyśmy przyjęli, że n i m są nieskończone oraz mieli do zakodowania ciąg: abccba-abbaabccba-abba (podwojony ciąg z naszego przykładu).

Pierwsze sześć kroków kodowania wygląda identycznie, więc możemy zacząć ten przykład od własnie szóstego kroku.

  • abccba-abbaabccba-abba    (7, 2, b)
  • abccba-abbaabccba-abba    (3, 1, a)
  • abccba-abbaabccba-abba    (11, 9, a)

Zauważmy, że do zakodowaniu podwojonego ciągu potrzebowaliśmy tylko jednej ‚trójki’ więcej. I to jest własnie właściwość, na której nam zależy, a której nie mają LZ78 i LZW. Chcemy wykrywać plagiaty, więc powinniśmy założyć, że tokeny porównywanych kodów źródłowych mogą być takie same lub bardzo podobne ;).

I trochę praktyki!

I w końcu trochę kodu! 🙂

Zacznijmy od stworzenia klasy, która będzie nam reprezentować zakodowaną ‚trójkę’.

Banał 😉

Teraz niestety trochę magii…

Powyżej zaimplementowaliśmy algorytm LZ77 z nieograniczonym buforem słownika i kodowania. Użyty algorytm jest napisany dosyć ‚prostacko’, ale działa 🙂 Przy najbliższej okazji wrócimy do niego i go zrefaktorujemy 😉

Podsumowanie

Dzisiaj zajęliśmy się drugim etapem w naszym algorytmie do wykrywania plagiatów., a mianowicie kompresją tokenów. Zobaczyliśmy jak wygląda LZ77 i zobaczyliśmy jak działa. Na koniec w trochę prostacki sposób zaimplementowaliśmy LZ77 z nieograniczonym buforem słownikowym i kodowania w Kotlinie ;). W następnym wpisie związanym z PlagDetectorem zajmiemy się trzecim etapem czyli aproksymacją złożoności Kołmogorowa 🙂

Budowniczy w akcji!

Dzisiaj porozmawiamy trochę o jednym z bardziej popularnych wzorców projektowych, a mianowicie o Budowniczym (Builder). Jest to jeden z kreacyjnych wzorców projektowych.

A na co to komu?

Dzięki użyciu budowniczego możemy z pewnością osiągnąć przynajmniej dwie rzeczy:

  • oddzielimy tworzenie obiektu od jego reprezentacji,
  • nasz kod powinien stać się trochę bardziej przyjazny dla oka 😉

The good old way…

Na początku zobaczmy jak będzie wyglądał zwykły obiekt POJO. Jako przykład stwórzmy klasę, która będzie zawierała wszystkie informacje o mailu, który będzie mógł być później wysłany.

Jak widzimy, nasza klasa ma za zadanie przechowanie informacji o tym do kogo mail będzie wysłany (to), dodatkowych odbiorów (cc), temat maila (subject) oraz jego treść (content).

Stwórzmy teraz instancje naszej klasy:

Co prawda ten kod nie wygląda jeszcze zbyt strasznie, ale wyobraźmy sobie teraz, że do naszej klasy dodajemy jeszcze kilka pól jak bcc, mime type, załączniki i jeszcze kilka innych. Wtedy nasza klasa trochę się rozrośnie i stworzenie instancji tej klasy nie będzie wyglądało zbyt przyjemnie, szczególnie mając na uwadze, że dużo pól naszej klasy ma ten sam typ.

A co jeśli…

Możemy się okazać, że część pól w naszej klasie nie jest obowiązkowa przy tworzeniu naszego obiektu. W naszym przykładzie pole cc nie musi być obowiązkowe. Co w takim przypadku powinniśmy zrobić?

Możemy stworzyć dodatkowy konstruktor bez pola cc 🙂 Tylko co jeśli pól opcjonalnych będziemy mieć kilka? Tworzenie wszystkich kombinacji konstruktorów zdecydowanie odpada.

W takim przypadku możemy przecież stworzyć POJO z setterami/getterami 🙂

I stwórzmy teraz instancje naszej klasy, tylko tym razem bez inicjowania pola cc:

Podejście to pozwala nam stworzyć instancje naszego obiektu tylko z wybranymi przez nas polami. Dzięki setterom jest również trudniej o pomyłkę związaną z kolejnością przekazywanych parametrów do konstruktora.

Czy można zrobić to ładniej?

Wydaję mi się, że można 😉 I właśnie budowniczy przyjdzie nam z pomocą 🙂

Budowniczy pomaga nam w tworzeniu skomplikowanych obiektów poprzez danie możliwości tworzenia (budowania) ich kawałek po kawałku. Stwórzmy zatem budowniczego do naszej klasy 🙂

Zmiany, których dokonaliśmy w naszej klasie to:

  • stworzyliśmy prywatny konstruktor do klasy Mail, aby nikt nie stworzył nam naszego obiektu na lewo ;),
  • dodaliśmy statyczną metodę builder(), która zwraca nową instancje budowniczego,
  • dodaliśmy samego budowniczego.

Klasa budowniczego zawiera w sobie pole z instancją budowanego obiektu, metody odpowiadające ustawianym polom oraz metodę build(), która wieńczy dzieło i zwraca nam naszą zbudowaną instancje klasy Mail. Zwróćmy uwagę, że metody budowniczego zwracają instancje budowniczego. Dzięki czemu możemy zbudować nasz obiekt w sposób ‚płynny’ (fluent interface) 😉

I w ten oto sposób udało nam się stworzyć prostego budowniczego 🙂

A co jeśli… (cz. 2)

Wcześniej zauważyliśmy, że część pól z naszej klasy może być opcjonalna. Warto, żebyśmy też popatrzyli w drugą stronę – część pól z może być konieczna do poprawnego zainicjowania naszego obiektu. W naszej klasie Mail możemy uznać, że pola to, subject i content są obowiązkowe. I co teraz?

The good old way jeszcze raz 😉

Wróćmy na sekundę do podejścia z POJO. Problem ten możemy tutaj rozwiązać poprzez stworzenie konstruktora, który będzie przyjmować obowiązkowe parametry oraz stworzeniem setterów dla parametrów opcjonalnych.

Tylko w tym podejściu znów powraca problem z wieloma parametrami w konstruktorze, które nie wyglądają zbyt ładnie oraz dodatkowo nie jest trudno o pomyłkę.

I wróćmy do budowniczego

A jak możemy ten problem rozwiązać w budowniczym?

Możemy obowiązkowe parametry przekazać do konstruktora budowniczego, ale oczywiście rezygnujemy z tej opcji 😉

Do rozwiązania tego problemu musimy trochę zmodyfikować naszego budowniczego, którego już stworzyliśmy.

Na początku stwórzmy sobie kilka prostych interfejsów.

Zauważmy, że dla każdego obowiązkowego pola stworzyliśmy interfejs, który zawiera dokładnie jedną metodę odpowiadającą za ustawienie tego pola. Zwróćmy uwagę też, że metoda ustawiające dane pole zwraca interfejs do ustawienia kolejnego obowiązkowego pola. Wyjątkiem jest interfejs ContentStep, który ustawia ostatnie obowiązkowe pole i zwraca interfejs OptionalSteps, który zawiera możliwość ustawienia wszystkich opcjonalnych pól oraz metodę build(), która zwraca nam gotowy obiekt.

Teraz musimy użyć tych interfejsów w naszym budowniczym.

Sama implementacja znacząco się nie zmieniła. Teraz nasz builder implementuje stworzone przez nas interfejsy. Musieliśmy też zmienić zwracane typy w metodach budowniczego.

I ostatnia zmiana, którą musieliśmy zrobić to zmiana typu zwracanego w metodzie tworzącej naszego budowniczego, żeby zwracała interfejs do pierwszego obowiązkowego pola.

 

Samo budowanie obiektu nie zmieniło się w porównaniu do tego, jak było w naszym pierwszym budowniczym, ale dzięki tym kilku interfejsom klient używający naszego budowniczego będzie musiał podać wszystkie obowiązkowe pola, żeby utworzyć obiekt.

I to jest właśnie to, co chcieliśmy osiągnąć 🙂

Tokenizacja kodu źródłowego

W tym wpisie opiszę pierwszy etap w wykrywaniu plagiatów w Plag-Detectorze.

O co właściwie chodzi?

Tokenizacja jest terminem występującym często w tematyce związanej z bezpieczeństwem czy też szyfrowaniem. W tym przypadku chodzi o coś trochę innego. Wspomniałem o tym w jednym z poprzednich wpisów.

Poniżej użyję tego samego przykładu, którego użyłem w tamtym wpisie.

Ideą tokenizacji jest zamiana kodu źródłowego na ciąg tokenów. W listingu powyżej można zobaczyć jak może wyglądać przykładowa tokenizacja kawałka kodu.

Jak to zrobić w praktyce?

Oczywiście można by samemu napisać tokenizer, ale byłaby to dość skomplikowana i długa robota. Oczywiście zakładając, że tokenizer powinien uwzględniać gramatykę danego języka. Z pomocą przychodzi nam ANTLR, czyli ANother Tool for Language Recognition.

Dla ANTLRa możemy zdefiniować gramatykę, według której będzie przeprowadzona tokenizacja. Zdefiniowanie gramatyki dla każdego języki również byłoby dosyć karkołomnym zadaniem. Na szczęście większość gramatyk dla popularnych języków programowania została już zdefiniowana i jest dostępna tutaj: https://github.com/antlr/grammars-v4.

Konfiguracja i użycie ANTLRa

Ponieważ jesteśmy leniwi, chcemy żeby wszystko nam się robiło automatycznie. I tak jest w tym przypadku 🙂

Zależności

Konfiguracje musimy standardowo zacząć od dodania zależności do naszego pliku pom.xml.

Gramatyka

Następnie musimy znaleźć interesującą nas gramatykę i wrzucić ja do folderu antlr4, który umieszczamy w katalogu serc/main. Dodatkowo, jeżeli chcemy, żeby kod wygenerowany na podstawie naszej gramatyki był w konkretnym pakiecie to musimy gramatykę wrzucić właśnie pod taką ścieżką. Czyli np. jeżeli chcę, żeby klasy związane z gramatyką były w pakiecie pl.lantkowiak.plagdetector.algorithm.grammar, to powinienem mieć taką strukturę katalogów jak przedstawiona poniżej.

Pluginy

Teraz potrzebujemy dodać do naszego poma kolejne dwa pluginy.

antlr4-maven-plugin

Plugin ten będzie odpowiedzialny za wygenerowanie klas związanych z naszą gramatyką.

build-helper-maven-plugin

Ten plugin sprawia, że nasze wygenerowane źródła będą widoczne w Eclipsie jako klasy, których możemy użyć.

Mały hack

Jeżeli będziemy wykorzystać wygenerowane klasy w naszym kodzie Kotlinowym to nasz projekt niestety się nie zbuduje. Maven nie będzie widział wygenerowanych źródeł. Aby to naprawić musimy w naszym pomie zamienić kolejnością pluginy odpowiedzialne za kompilacje Javy i Kotlina. W wpisie Hello Kotlin pisałem, że plugin do kompilacji kodu Kotlina powinien być przed pluginem Javovym, żeby kod kotlina mógł być użyty w Javie. Niestety póki co musiałem z tego zrezygnować, aby móc zautomatyzować proces generacji kodów źródłowych dla gramatyk ANTLRowych.

Użycie w kodzie

Dla np. gramatyki dla Java 8 ANTLR wygeneruje następujące pliki:

Klasa, która będzie nas interesowała do przeprowadzenia tokenizacji to Java8Lexer.

Ponieważ Plag-Detector będzie wspierał wiele języków programowania stworzyłem enuma, który będzie zawierał wszystkie wspierane języki.

Następnie stworzyłem prostą fabrykę, która na podstawie przekazanego enuma zwróci mi instancje oczekiwanego leexera.

Klasa Lexer jest klasą abstrakcyjną, po której dziedziczą wszystkie lexery wygenerowane przez ANTLRa.

Sama tokenizacja jest już bardzo prosta:

W pierwszej linii metody tworze instancje fabryki, a następnie pobieram lexer. Następnie wywołuję metodę getallTokens(), która zwraca mi listę wszystkich tokenów z przetworzonego kodu źródłowego. Ponieważ do dalszych potrzeb istotne są dla mnie tylko typy tokenów, a nie całe obiekty z nadmiarowymi danymi, mapuję tokeny na ich typ, czyli int. Taką listę intów jest zwracana przez metodę i będzie dalej użyta w procesie wykrywania plagiatów.

Podsumowanie

W tym wpisie przedstawiłem ANTLRa oraz pokazałem jak go skonfigurować. Dodatkowo pokazałem w jaki sposób można użyć ANTLRa, aby dokonać tokenizacji ciągu znaków na wejściu – w naszym przypadku kodu źródłowego.