niedziela, 31 lipca 2011

Przywitanie gości, czyli znowu o inżynierii oprogramowania

Skończył się czwarty tydzień praktyk, a przez to skończyły się same praktyki. Czy to oznacza, że nie musimy już trzymać się rygoru przychodzenia codziennie o 8 rano? Tak. A czy oznacza też, że już nie pracujemy? Nie.

Pracować nadal trzeba, bo projekt jest nadal nieskończony, ale to akurat było w planie. Problem w tym, iż wydaje mi się, że prace idą odrobinę wolniej, niż to sobie zakładaliśmy – wniosek z tego taki, że trzeba będzie je przyspieszyć (elementarne, drogi Watsonie). I nie myśleć o pisaniu własnego Minecrafta (tak nas wzięło, gdyż w gruncie rzeczy większość obiektów w tej grze to po prostu sześciany, co banalnie łatwo przygotować).

Ostatni tydzień przyniósł też parę dyskusji o wykorzystaniu różnych dziwnych rozwiązań w projekcie – między innymi chyba trzeba będzie się zapoznać bliżej z sieciami neuronowymi oraz przypomnieć sobie założenia algorytmów genetycznych. Swoją drogą, jako człowiek – delikatnie mówiąc – nieprzepadający za biologią (nie twierdzę, że to nieużyteczna nauka, tylko strasznie pamięciowa) troszkę boję słysząc nazwy “algorytm genetyczny”, “sztuczny mózg” czy “do pierwszego starczy”. Wiem, że to niegroźne, ale brzmi strasznie biologicznie.

Prawdziwą atrakcją okazał się jednak zapowiedziany wcześniej najazd drugiej grupy z SDS. Tak się bowiem składa, że nasz pokój przeznaczony jest dla dwóch grup piszących różne inżynierki i widać, że będzie trzeba troszkę się skondensować, aby się pomieścić choć pokój jest dość duży. Cóż, z tego co mi wiadomo, będziemy się na razie raczej mijać aniżeli siedzieć razem, zatem nie powinno być tak źle. Na razie.

Nie zapominajmy też, że są wakacje, a wakacje oznaczają odpoczynek (czyli więcej czasu na zajęcie się MTG czy futbolem, bo NBA chwilowo ma lokaut (a w NFL się skończył parę dni temu)). Nie będziemy zatem teraz ciągle siedzieć w pracy, co sprawia, że będziemy tam chodzić po to, aby rzeczywiście pracować pełną parą, gdy tylko tego będziemy chcieli lub będziemy czuć wenę. A zostało jeszcze sporo do zrobienia.

Z innej beczki – osoby, które mnie znają, wiedzą, iż nie przepadam za serwisami typu Facebook, które skupiają sporą liczbę użytkowników różnej maści, którzy to w mniejszym czy większym stopniu udostępniają informacje, których w normalnych warunkach nikomu by nie przekazali. Doszło do takiego paradoksu, że na wszystkie spotkania czy zgromadzenia ludzie umawiają się na Facebooku, “bo wszyscy tam siedzą”. A guzik prawda, posiadanie tam konta nie jest obowiązkiem. Nie twierdzę, że to nieprzydatne, ale w granicach rozsądku. Za to, jak pewnie też już wiecie, Google wypuściło do szerszego użytkowania testową wersję serwisu Google+, który również ma być portalem społecznościowym o nieco większym bezpieczeństwie i braku inwazyjności. Nie ukrywam – skusiłem się, zwłaszcza, że lubię googlowe narzędzia i choć na razie niewiele się na tym serwisie dzieje, to fajnie jest sobie tam siedzieć od czasu do czasu. Zamierzam tam głównie rozwijać nieco tę magicową część mojego żywota, a zatem troszkę łączyć użytkowników karciankowego działu Poltera oraz innych Magicowców. Od czasu do czasu umieszczę też dziwne notki związane z programowaniem. O ile mi starczy cierpliwości. I serwis nie padnie. I mi się będzie chciało.

Pozdrawiam i dziękuję - SceNtriC

piątek, 22 lipca 2011

Folia na drzwiach, czyli znowu o inżynierii oprogramowania

Przyszedł zatem czas na refleksje dotyczące trzeciego tygodnia praktyk. Tytuł jest nieprzypadkowy, gdyż z okazji wakacji budynek, w którym stacjonujemy, został poddany diabelskiemu zjawisku zwanego remontem. Oczywiście, nie cały budynek – jedynie jedno piętro, a konkretnie to, na którym się znajdujemy. Tak po prostu, aby było wesoło. Oprócz cudownego dźwięku wwiercającej się w sąsiednią ścianę wiertarki oraz wszechobecnego brudu (który potem nanosimy do naszego pokoju), pewnego dnia po przyjściu do pracy ujrzałem nasze zafoliowane drzwi i stojącego nieopodal robotnika komunikującego, iż dzisiaj niestety będą gipsować i na razie do pokoju nie wejdziemy. Jak się okazało, po południu już można było wejść, jednak cały dzień przesiedziałem u innej grupy w pokoju (dziękuję za gościnę), oddając się tak zwanemu researchowi, czyli badaniu czeluści Internetu w poszukiwaniu “ctheghoś”. Żeby nie było nieporozumień – nie mam pretensji do nikogo. Robotnicy wykonują swoją pracę, a budynki uczelniane (czy szkolne) zwykle remontuje się w okresie wakacyjnym. Szkoda tylko, że musimy w tym uczestniczyć.

Im dalej w las z praktykami, tym lżej się je znosi. Może dlatego, że jest coraz poważniejsza praca nad inżynierką i człowiekowi po jakimś czasie kończą się pomysły, a jak się kończą pomysły, to przychodzą inne dziwne rzeczy do głowy, a jak przychodzą inne dziwne rzeczy do głowy, to zwykle kończy się to dyskusjami o pokładełku Kiryśnika (swoją drogą polecam akwarystom, bardzo wdzięczne i sympatyczne rybki, szczególnie jak przez szybę zobaczą jadłopodawcę) czy eksplorowaniu Youtube. A problemów jest niestety sporo, gdyż – jak już wspominałem – wymyślamy pewien(ne) algorytm(y), który(e) ma(ją) yntelygnetnie rozpoznawać pewne wzorce. Sporo się przy tym nauczymy, ale też sporo pomarudzimy i się “podepresjonujemy”. Taki urok pracy.

Najważniejszą zmianą związaną z inżynierią oprogramowania w tym tygodniu stały się codzienne stand-up meetings, czyli spotkania informacyjne na stojąco, które zaproponowałem wprowadzić, abyśmy mieli jeszcze lepszy przepływ informacji. Dwie osoby z naszej czwórki zajmują się jednym zagadnieniem, a dwie pozostałe – tym drugim. Jedna dwójka niewiele wie o postępach drugiej dwójki, zatem 5-minutowe rozmowy o tym, co zrobiliśmy i co zamierzamy robić powinny być przydatne, aby mieć ogólny obraz sytuacji (lub stanu globalnego – jak kto woli, co dla kogo mądrzej brzmi). Dzięki takim spotkaniom okazało się zresztą, że niektórzy szli ze swoim zagadnieniem w nieco innym kierunku – przy mniejszej integracji z resztą systemu – a problem pojawił się dosyć wcześnie, dzięki czemu można jeszcze raz przedyskutować założenia i pomyśleć nad rozwiązaniem. Oprócz tego pojawili się również nasi opiekunowie (pozdrawiamy) i spotkanie, na którym przedyskutowano pewne kwestie sporne. W przyszłym tygodniu też takie się odbędzie – tego typu obrady są o tyle potrzebne, że opiekunowie dysponują dużo większą wiedzą i rozeznaniem, zatem zawsze służą radą i nas nakierowują, jeśli zboczymy z trasy. Przy okazji jest też zawsze dużo humoru, a to zawsze się przyda – naprawdę lepiej się pracuje, jeżeli dobrze się wszyscy bawią.

W najbliższym czasie czeka nas także zmierzenie się z innym problemem logistycznym – do naszego pokoju wprowadza się druga grupa “inżynierkowa”, w efekcie czego w pomieszczeniu zrobi się ciut ciaśniej i nieco więcej zamieszania, bowiem dojdzie kolejne biurko i komputery. Zobaczymy jak to będzie – prawdopodobnie będziemy się wymieniać składem w pokoju, bo przepływ informacji jednej grupy może przeszkadzać przepływowi drugiej, a rozmowy przez ciche komunikatory internetowe nie będą aż tak efektywne (za to będą skutecznie rozpraszać).

Dzisiaj krótko, ale chciałem napisać w końcu coś luźniejszego. Troszkę nie czuję tych wakacji, ale chyba nie jestem w tym odosobniony. Za to niezmiernie usatysfakcjonowany, nawet, kiedy nie wychodzi.

Pozdrawiam i dziękuję - SceNtriC

sobota, 16 lipca 2011

Internet dla mas, czyli znowu o inżynierii oprogramowania

Ponad tydzień temu podzieliłem się z Wami moimi pierwszymi wrażeniami z realizacji projektu w war-roomie, zatem wypadałoby pociągnąć ten wątek w choćby minimalnym stopniu. Zwłaszcza, że w końcu uzyskaliśmy dostęp do internetu, z czego jesteśmy bardzo, ale to bardzo zadowoleni. W końcu można wczytywać filmy z YouTube z niezłą prędkością. Za to na korytarzu rozpoczął się totalny remont, zatem podróż do i z pokoju przez jakiś czas wiązała się z przymusowym ubieleniem (bynajmniej nie w Perwollu ani Vizirze), wchodzeniu do sali i komentarzem “o kurdę, ale naniosłem”.

W tym tygodniu praca zaczęła się na poważnie. Można to głównie poznać po coraz mniej czytelnych notatkach na tablicy - to oznaka, że nasze myśli są coraz bardziej pokręcone i zachowujemy się nienormalnie. Zaczęła się w końcu implementacja niektórych rozwiązań. Jest to o tyle fascynujące, że nasz projekt jest bardziej badawczy aniżeli zwykły projekt inżynierski (co nie znaczy, że tamte są złe), zatem siłą rzeczy niektóre rzeczy trzeba wymyślić. A potem kod wymaga dogłębnej refaktoryzacji, bo myśli wiją się w niesamowity sposób.

Ale nie o tym chciałem pisać - jeśli trafi się jakiś ciekawy problem techniczno-myślowo-implementacyjny, który będzie neutralny (nie będzie za bardzo "odkrywał" projektu), to pewnie o tym napiszę, ale główną misją tych notek jest dyskusja o inżynierii oprogramowania w praktyce.

Najpierw może przypomnę jak wygląda u nas struktura zespołu. Na samej górze jest promotor, który akurat nie bierze większego udziału w samych pracach (co nie oznacza, że nie jest nimi zainteresowany). Pod nim jest nasz główny opiekun (bezpośrednio zainteresowany projektem i jego rozwojem), którego wspiera inny opiekun, notabene koordynator poprzedniej wersji naszego systemu (ponieważ - niestety - rozbudowujemy coś, co zostało już w części napisane - pewnie o tym jeszcze pomarudzę). Kolejnym poziomem są nasi opiekunowie z IV roku, studenci specjalności Software Engineering, u których mnogość dokumentów, jakie muszą sporządzić, przekracza wszelkie oczekiwania wszelkich komisji i urzędników. Właśnie dlatego uważam, że proces powstawania gier komputerowych jest przyjemniejszy - o wiele mniej formalności, a jaka radość i zabawa. Przypadki użycia są dobre, ale uciążliwe w pisaniu, a w grach chodzi tylko o grywalność, fabułę i efekty (w tej kolejności). Ostatnim poziomem w strukturze jesteśmy my, programiści. Czasami odwiedzają nas właśnie opiekunowie - wtedy praca (i przeglądanie Internetu) schodzi na dalszy plan, a zaczyna się panel dyskusyjny o tym, co jest do zrobienia, jak to trzeba zrobić, po co i co to jest ten cholerny futbol amerykański, a także dlaczego tym jajem się tak ciężko rzuca. Przynajmniej jest weselej. Bo wiedzcie, że problemy są z grubsza interesujące w pierwszej fazie, czyli przy myśleniu nad nim, wstępnym projektowaniu. W samym projektowaniu oraz rozwiązywaniu problem staje się coraz mniej fascynujący, aż do pierwszych błędów typu "nie-wiadomo-dlaczego-to-nie-działa", kiedy człowiekowi nic się nie chce, bo nie wie co się dzieje (a Youtube kusi). Gdy w końcu uda się wyjść z takiego bagienka po mniejszych czy większych trudach, następuje znaczny wzrost fascynacji problemem, gdyż w końcu został rozwiązany (wtedy można też się chwalić wszem i wobec co się udało zrealizować). Można powiedzieć, iż jest to rozkład Gaussa, ale odwrócony do góry nogami.

Jak już wspomniałem, pracujemy na poprzedniej wersji systemu. Problemów z tym jest parę:

  • Trzeba zwyczajnie "wbić" się w kod poprzedników, zobaczyć gdzie co jest
  • Trzeba poznać technologię i biblioteki, jakich użyli
  • Jest się trochę "zarażonym" architekturą poprzedniej wersji, nawet tymi niedobrymi elementami
  • W naszym przypadku był problem, gdyż jedna biblioteka była przestarzała i już nie była w użyciu, a nowa nie była z nią zbytnio kompatybilna
  • Był sam problem z importem do nowszej wersji IDE

Na szczęście, okazało się, że nie trzeba wykorzystywać całego kodu poprzedników, a jedynie poprzerabiać, w ostateczności napisać wszystko od nowa. Innym problemem jest technologia Web Services, z którą dotychczas nie mieliśmy do czynienia, a tutaj (i nie tylko tutaj) jest w szerokim użyciu. Na szczęście nie okazuje się to tak strasznie trudne, jak się wydaje, a zawsze lepiej wiedzieć coś więcej.

Niestety, jak dotąd nasza praca z metodologią XP nie ma zbyt wiele wspólnego, ale w gruncie rzeczy nie uważam, aby było to złe – na tym etapie projektu. Poniżej parę moich uwag odnośnie pracy w pierwszym i drugim tygodniu praktyk:

  • Nie programujemy w parach, preferujemy podejście side-by-side, czyli “programowanie obok siebie”. Nie ma co prawda kontroli pisanego kodu, jednak w obecnym stadium, kiedy trzeba poznać wiele technicznych rzeczy (założyć i skonfigurować bazę danych, wczytać się w dokumentacje używanych bibliotek) nie miałoby to po prostu sensu. Side-by-side przyspiesza za to pracę w znacznym stopniu, gdyż każdy ma do dyspozycji swój komputer i zajmuje się konkretną częścią projektu.
  • W naszym czteroosobowym zespole jesteśmy akurat tak podzieleni, że dwie osoby zajmują się jednym głównym “ficzerem” projektu, a dwie pozostałe – drugim głównym “ficzerem”. Ponieważ jedna i druga para siedzi koło siebie, przepływ informacji jest bardzo dobry, gdyż dwie osoby pracujące nad tym samym (w ogólności, gdyż najczęściej każda robi coś innego (np. pierwszy pisze, drugi ogląda Youtube, a potem pierwszy ogląda filmiki, a ten drugi pokazuje mu które)) mają bezpośredni wgląd w swoje monitory.
  • Co prawda nie mamy obowiązku składania scrumowych raportów z poszczególnych dni/tygodni, jednak uznaliśmy, że jest to dobra metoda dokumentowania postępów i ewentualnie wymuszenie na nas korekt, jeśli nie idziemy “tą” drogą. Poza tym, pisząc o tym, co robiliśmy, co nas blokuje i co zamierzamy robić, niejako porządkujemy własną pracę, widzimy, jak daleko już zaszliśmy i czy nie trzeba czasem wzmóc tempa.
  • Nie ma u nas stand-up meetings, czyli codziennych kilku- lub kilkunastominutowych rozmów na stojąco o tym, co nas czeka lub co już zrobiliśmy. To znaczy tego typu rozmowy się odbywają, ale nie są regularne, a jedynie pojawiają się wtedy, kiedy zachodzi taka konieczność. Przy ważniejszych problemach dana osoba mająca problem lub po prostu wątpliwość wstaje, podchodzi do tablicy, po czym zaczyna się przy niej dyskusja, do której dołączają zainteresowane osoby. Zaletą tego jest to, że choć drobna część dyskusji dotrze do ucha osób mniej zainteresowanych, a dodatkowe bodźce w postaci rysunków na tablicy czy chociażby podrzucania piłeczki wzmagają proces myślenia, kojarzenia i zapamiętywania.
  • Właśnie – piłeczka. Niby drobna rzecz, ale bardzo potrzebna, co zresztą widać również przy burzy mózgów pod kierunkiem doktora Chałupy w znanym serialu. Kontakt z odbijającym się kulistym obiektem pożądania, podrzucanie go, ściskanie, odbijanie wpływa pozytywnie na człowieka. W dodatku można się na niej wyżyć, pogryźć ją, rzucić o ścianę i zrobić multum innych rzeczy. Wierzcie mi – taka piłeczka to skarb. Ile razy podczas rozmyślań nad kolejnymi etapami algorytmu zacząłem biegać po pokoju kopiąc piłkę przed sobą, odbijając ją od szafy, sufitu, ściany, aż w końcu wpadał mi pomysł, który mogłem zapisać i ruszyć dalej. Ogólnie przerwy w pracy są bardzo potrzebne, ale trzeba uważać, aby nie zajęły nas w pełni.
  • Wspomniałem o wymyślaniu algorytmu i o tym, że trudno wejść w kod poprzedników, zwłaszcza, jak się nie zna technologii. Integracja nowych pomysłów ze starym kodem jest o tyle utrudniona, iż nie mieliśmy chociażby dostępu do bazy danych, która była niezbędna. Dlatego nie bójcie się pisać osobnych aplikacji, w których będziecie testować Wasze nowe rozwiązania i dostrajać je tak, aby skopiowanie kodu do właściwego projektu i ewentualne drobne przeróbki nie były zbyt bolesne. W tym czasie, kiedy pisany jest nowy kod przez jedną osobę, druga przygotowuje stare źródła do współdziałania z nowoutworzoną bazą danych – tak przynajmniej u nas to wygląda i na razie się sprawdza. Na razie, bo jeszcze nie integrowaliśmy naszych prac. Dlatego pewnie następne notki będą cenzurowane.

Jak widzicie, znowu o niczym konkretnym nie napisałem, aczkolwiek mam nadzieję, że rzucam coraz więcej światła na praktyki znane z inżynierii oprogramowania… w praktyce właśnie. Oby dalej nie było gorzej niż jest. I obym miał siłę pisać kolejne notki.

Pozdrawiam i dziękuję - SceNtriC

środa, 6 lipca 2011

Wrażenia z praktyk, czyli znowu o inżynierii oprogramowania – w war-roomie

Ostatni wpis dodałem dość dawno temu i nie był o grach ani grafice komputerowej. Ten dodaję teraz, pewnie znowu okupiony długą przerwą o nim i znowu nie będzie ani o grach ani o grafice komputerowej. W życiu każdego studenta informatyki na Politechnice przychodzi czas, kiedy trzeba realizować pracę inżynierską. Znajdzie się również miejsce na wepchnięcie konieczności odbycia praktyk w jakiejś firmie bądź uczelni. I naprawdę zacną rzeczą jest połączyć te dwie rzeczy w jedną – nie dość, że praktyki spędza się na uczelni (-"Wiesz, pracuję na uczelni”, –“Oj, jakiś ty mądry…”), wśród znajomych twarzy, to jeszcze można umysłowo popracować nad czymś, co i tak trzeba by było robić w semestrze.

Ostatnio pisałem już o programie SDS (Software Development Studio), które działa pod patronatem zespołu Software Engineering w Instytucie Informatyki na Wydziale Informatyki Politechniki Poznańskiej (to już koniec litanii) i w którym chodzi o to, że studenci IV roku (specjalności magisterskiej SE) uczą się zarządzać zespołem niesfornych programistów, a studenci III roku (przyszli inżynierowie – my) uczą się być zarządzanym, jeszcze bardziej niesfornym, a przy okazji trochę się pośmiać i spróbować stworzyć jakiś ciekawy system, który może nawet będzie działał. Sęk w tym, że SDS często umożliwia studentom skorzystanie z jednego z pokojów uczelnianych, dzięki czemu możemy pracować wspólnie w tak zwanym war-roomie, a co za tym idzie – poznać smak prawdziwej pracy.

W związku z powyższym naszło mnie, aby podsumować pierwsze parę dni wspólnej egzystencji i (nie)pracy nad projektem, a także zawrzeć parę swoich uwag, które być może pomogą paru osób w tego typu sytuacjach lub dadzą do myślenia. Dlaczego piszę o (nie)pracy? To się wyjaśni. Choć większość z poniższych uwag to banały, znane każdemu z autopsji, bądź nietrudne do wyobrażenia sobie.

  • Dostaliśmy komputery, działają, wszystko jest dobrze, za wyjątkiem jednej rzeczy, niestety niezbędnej, gdy nie ma się pojęcia o technologiach, a ponadto co chwilę trzeba ściągać biblioteki – nie ma dostępu do Internetu. Przynajmniej przez jakiś czas. W związku z tym, pomijając nasze laptopy z własnym, mobilnym, dostępem do neta (własnym, gdyż dla sieci uczelnianej również nie ma zasięgu w pokoju), nie mamy za bardzo możliwości przerabiania tutoriali i porad, które są zwykle w sieci. Dobrze, że zostaje nam praca umysłowa nad rozbudową schematu bazy danych czy algorytmami – zawsze jest spokój sumienia, że coś robimy. I satysfakcja.
  • Tablica z pisakami i gąbką to bardzo dobra rzecz. Nie dość, że można na niej wyżyć się artystycznie, rozpisać różne przypadki algorytmiczne. Tablica zespala też zespół – wszyscy się przy niej produkują, wychodzi z tego istotny wkład i poczucie, że jesteśmy zespołem.
  • Wróćmy do koncepcji “jesteśmy zespołem”. Jest to dużo ważniejsze niż nawet czterech najlepszych specjalistów z danych dziedzin współpracujących razem, ale nieczujących ze sobą chemii. Wolę wspólną walkę z problemami, wspieranie się, miłą atmosferę, aniżeli szybkie posuwanie się do przodu, ale w dość chłodnym lub neutralnym nastroju. Poczucie zespołowości sprawia, iż przyjemniej siedzi się w pokoju parę godzin dziennie. Nawet krótkie podjechanie z krzesłem do kolegi obok i zapytanie się “co tam robisz ciekawego?” jest potrzebne.
  • Energia. Jestem wielkim miłośnikiem teorii o tym, że energia (w różnej postaci) powoduje, iż można zrobić wiele (jeśli nie wszystko), a ona sama pozwala lepiej się czuć. Kto ogląda Zaklinacza Psów, ten również często słyszy tam słowo “energia”, dzięki której można lepiej zrozumieć psy. W sporcie przed meczami odbywają się rytuały mające zmotywować graczy, podnieść poziom adrenaliny, a przez to nakłonić do lepszej gry i podtrzymania ducha zespołowości. Także w informatyce lepiej tworzy się projekt wiedząc, iż zespół stoi za nami murem, coś nam wychodzi (choćby mała rzecz), a może wyjść jeszcze więcej. Wtedy przebija się pozytywna energia. Tak samo działają wspólne żarty i rozmowy. Wystarczy, że ktoś zacznie rzucać piłką o ścianę, a już skacze adrenalina i rośnie energia. Zwłaszcza u osoby, która stoi na linii rzutu.
  • Nie wolno zapominać o herbacie oraz gorących posiłkach. Na samych kanapkach trudno przeżyć parę godzin, podobnie jak na wodzie mineralnej. Choćby niezdrowa zupka z paczki sprawia, iż jesteśmy mniej senni. Podobnie jak przerwy spędzone na wyszukiwaniu ciekawych filmów na Youtube. A także oczywiście o partyjkach Magic: the Gathering.
  • Wyżej rzeczona tablica może (a nawet powinna) stać się również tak zwanym radiatorem informacji, czyli miejscem, gdzie zapisywane byłyby postępy prac w danej iteracji lub uwagi, które wyniknęły w realizacji postawionych zadań. Nawet systemy śledzenia bugów nie wpływają aż tak motywująco jak widok kolejno odkreślonych zadań na tablicy. One mogą jedynie ułatwić pamiętanie o tym, co należy załatać, ale chwilowo nie ma na to czasu/możliwości/pomysłu.

Cóż, jak już wspomniałem, dla większości są to banały, ale mam nadzieję, że co jakiś czas będzie mi się udawać przemycić tutaj nieco swoich spostrzeżeń i porad, a być może nawet rozwiązań, które wyjdą same w trakcie powstawania projektu. Własny pokój jest o tyle świetnym rozwiązaniem, że ma się spokój, własne komputery i można się w pełni skupić na pracy. Zdaję sobie sprawę, że nie wszyscy mają niestety takie możliwości, ale nie należy się tym przejmować – nawet na odległość sporo z powyższych uwag można zastosować w praktyce.

Pozdrawiam, dziękuję i do napisania – SceNtriC

Ps. Mam nadzieję, że nie odrzuciliście devbloga z RSS-ów tylko dlatego, iż dawno nie był aktualizowany. Przepraszam za brak konsekwencji, ale niestety – nie zawsze znajduję ciekawe tematy, aby pisać. A tych ciekawych tematów brak, bo uczelnia niestety narzuca swoje tempo.

niedziela, 24 kwietnia 2011

A teraz coś o stringach

Jak widać, moja teoretyczna regularność nie ma nic wspólnego z faktycznym stanem rzeczy i odstępy między notkami przypominają bardziej blogi bardziej znanych osób, które piszą coś dłuższego i mądrego raz na jakiś czas. Różnica jest zasadnicza – moje teksty nie są ani długie ani mądre, ale można powiedzieć, że jeden punkt już spełniłem.

Za silnik, a tym samym trawę, zasadniczo się nie brałem – zbyt wiele atrakcji działo się na początku semestru i dzieje się teraz, nie tylko związanych z informatyką. Chociażby udało się przywrócić niektórym wspomnienia o grze Magic: the Gathering i co jakiś organizować “magicowe okienka” na uczelni, aby towarzysko sobie pograć. Tym niemniej największym wydarzeniem były wybory prac inżynierskich, w efekcie czego pod koniec marca następowały istne cuda w dobieraniu się zespołów (“Masz już zespół? Masz? NIE MASZ?! To chodź do nas, chodź, chodź, no choooooodź… Aha, temat Cię nie interesuje…”) czy atakowaniu promotorów/opiekunów/kogokolwiek w celu zdobycia interesującego tematu czy też zdobycia czegokolwiek z puli “jeszcze te mogę robić”.

Była też pewna pula tematów tworzonych w ramach Software Development Studio (SDS). SDS to idea, w której następuje pewna współpraca pomiędzy studentami różnych lat w celu zdobycia dodatkowych umiejętności. Mówiąc mniej enigmatycznie – dwaj studenci IV roku ze specjalności magisterskiej Software Engineering (specjalność inżynierii oprogramowania na Politechnice Poznańskiej jest w języku angielskim) mają za zadanie opiekować się i wspomóc wytwarzanie jednego z wybranych tematów inżynierskich, które z kolei są realizowane przez czterech studentów III roku (to my). Jeżeli doliczymy do tego promotora i dwóch opiekunów z dziekanatu, wychodzi na to, że jest aż 9 osób (tzw. Drużyna Pierścienia). Każdy na tym zyskuje – pracownicy uczelni ciekawy (mam nadzieję) projekt, który można gdzieś dalej pokazać (zwykle projekty w ramach SDS są ważne dla uczelni, wydziału czy instytutu), studenci IV roku doświadczenie w zarządzaniu projektem i grupką czasami energicznie reagujących osób, a my – tytuł inżyniera. Oczywiście, nie wszystkie projekty są takie, ale 7 grup akurat realizuje swoje inżynierki w ramach SDS. Fajna sprawa, gdyż można się sprawdzić w takim grupowym projekcie. No i sam temat też jest bardzo interesujący, choć na razie nie będę o nim mówił, gdyż nie wiem, czy mogę.

Po co ten wstęp? Po prostu chciałem się pochwalić. Przy okazji pozdrawiam wszystkie osoby zaangażowane w projekt i mam nadzieję, że będzie nam się dobrze pracowało.

W niniejszej notce chciałem co nieco powiedzieć o sposobach porównywania łańcuchów (czyli właśnie rzeczonych stringów z tytułu – być może ktoś wszedł z myślą o innych stringach, w sumie też bym tak zrobił). Ostatnio myślałem nad myśleniem o myśleniu o możliwości logicznego porównywania łańcuchów. Kontekst zadania jest taki – mamy dwa tytuły książek czy artykułów i chcemy zobaczyć na ile są sobie bliskie tematycznie. Pewnie wielu z Was słusznie powie tutaj “hej, ale tego nie można sprawdzić samymi łańcuchami”. Owszem, najlepiej by było, jakby uruchomiło się tutaj wiedzę dziedzinową chociażby w rodzaju słów kluczowych. Nie mówię – być może będzie to także wykorzystane, jednak wymagałoby dodatkowych mechanizmów, o których nie wiadomo, czy by się opłaciły.

Tym niemniej pozostańmy przy samych łańcuchach, gdyż z nich też można dużo wyciągnąć. Dlaczego? Weźmy chociażby tytuły publikacji o inżynierii oprogramowania. A konkretnie dwa przykłady publikacji pana profesora Jerzego Nawrockiego (pozdrawiam).

Patrząc na tytuły można już wysnuć całkiem sporo wniosków.

  • Oba dotyczą programowania, a zatem – teoretycznie – informatyki
  • W obu mamy do czynienia w pracą w parach, co w powiązaniu z programowaniem może znaczyć “programowanie w parach”
  • Być może oba teksty dotyczą inżynierii oprogramowania

Wszystkie wnioski uczyniliśmy tylko i wyłącznie na podstawie tytułów, a zatem łańcuchów (ciągów znaków, rzeczonych stringów). Pora sprawdzić to doświadczalnie.

Przez ostatnie dwa dni miałem chęci (przede wszystkim chęci – jak sobie coś ubzduram, bo mnie ekscytuje, to nie ma siły, abym przestał o tym myśleć), aby stworzyć jakiś prosty algorytm porównujący dwa ciągi pod względem podobieństwa. Oczywistym podejściem, na które równie oczywiste jest to, iż na nie nie wpadłem, jest liczenie tzw. odległości, która mówi o tym ile potrzeba operacji, aby jeden ciąg zamienić w drugi. Jednak zapominanie o tak prostych sprawach ma również dobre strony – będzie więcej algorytmów na tym świecie. A przynajmniej na tym blogu. Algorytmów? Owszem – bowiem wpadłem na dwa sposoby mierzenia łańcuchów.

Algorytm porównywania łańcuchów

Operacja porównania ciągów (w obu ignorujemy białe znaki) polega na kolejnym wyszukiwaniu coraz większych podciągów ciągu pierwszego, a następnie szukaniu ich w ciągu drugim. W drugim etapie zamienia się łańcuchy ze sobą i ponownie przeszukuje w poszukiwaniu podciągów. Wynikiem każdego jest procent (a konkretnie wartość z przedziału [0, 1]) trafionych poszukiwań w stosunku do wszystkich, a wynik łączny to średnia z tych dwóch pomiarów.

Powyższy opis wygląda dosyć mętnie, ale udokumentowałem go przykładem, na który składają się słowa “hala” oraz “hola”.

Łańcuch pierwszy (który dzielimy na podciągi i porównujemy z drugim)

Długość podciągu

Rozpatrywany podciąg

Wynik (czy dany podciąg występuje w ciągu drugim)

hala

1

h

TAK

hala

1

a

TAK

hala

1

l

TAK

hala

1

a

TAK

hala

2

ha

NIE

hala

2

al

NIE

hala

2

la

TAK

hala

3

hal

NIE

hala

3

ala

NIE

hala

4

hala

NIE

Trafione: 5/10 = 0,5

hola

1

h

TAK

hola

1

o

NIE

hola

1

l

TAK

hola

1

a

TAK

hola

2

ho

NIE

hola

2

ol

NIE

hola

2

la

TAK

hola

3

hol

NIE

hola

3

ola

NIE

hola

4

hola

NIE

Trafione: 4/10 = 0,4

Wynik końcowy: (0,5 + 0,4) / 2 = 0,45

Jak widać, według tej miary podobieństwo między tymi dwoma wyrazami wynosi 45%, co nie jest zbyt fascynującym wynikiem. Zwłaszcza, że optycznie słowa “hala” i “hola” są do siebie bardzo podobne i choć mają inne znaczenie, to różnica jednej literki może wskazywać na to, że nastąpiła tutaj zwyczajna literówka. Jest tutaj zatem wiele możliwości poprawy – warto na przykład zauważyć, że jeżeli przykładowe słowa byłyby dłuższe i różniłyby się paroma literami, końcowy wynik byłby bliższy jedynce (gdzie 1 oznacza równość ciągów). Troszkę gorzej wygląda to w momencie, kiedy staramy porównać się dwa tytuły (autorstwa innego pana profesora Jerzego Nawrockiego) ze sobą:

1. Permian to Early Triassic magnetostratigraphy from the Central European Basin in Poland: Implications on regional and worldwide correlations

2. The Middle Triassic magnetostratigraphy from the Peri-Tethys basin in Poland

Jak widać, w dość długich tytułach mamy wspólne słowa (magnetostratigraphy czy Poland), aczkolwiek widać, iż zdania są dosyć różne. Rzeczywiście, algorytm podaje wynik porównania 0,203932 – cóż, mogłoby być gorzej. Jeżeli weźmiemy z kolei jeden z poprzednio podawanych tytułów z inżynierii oprogramowania i jeden z tych medycznych, to ich wynik będzie oscylował wokół 0,05-0,1. Tym niemniej, jeśli chcielibyśmy zaklasyfikować publikacje 1. i 2., to byłoby to trudne na podstawie wyniku 0,2. Cóż, trzeba będzie popracować.

Algorytm mapowania znaków

Operacja mapowania znaków polega na szukaniu kolejnych znaków z jednego ciągu w drugim, a następnie usuwaniu tego znaku w obu łańcuchach. Wynikiem jest jeden minus stosunek liter pozostałych (niedopasowanych) do długości jednego ciągu. Jeśli łańcuchy mają różną długość, krótszy jest dopełniany białymi znakami.

Tutaj także mamy przykład – zbadamy mapowanie słów “anarchia” i “arena”. Jak widać, ten drugi wyraz należy dopełnić trzema białymi znakami, aby oba ciągi miały równą długość.

Łańcuch pierwszy

Łańcuch drugi

Rozpatrywany znak

Wynik (czy rozpatrywany znak występuje w łańcuchu drugim)

anarchia

arena

a

TAK

narchia

rena

n

TAK

archia

rea

a

TAK

rchia

re

r

TAK

chia

e

c

NIE

chia

e

h

NIE

chia

e

i

NIE

chia

e

a

NIE

Wynik końcowy: 1 – (4 / 8) = 1 - 0,5 = 0,5

Idea polega na tym, aby zobaczyć, ile liter (formalnie znaków) nie zostanie dopasowanych między dwoma łańcuchami (wliczając w to także spacje). Jak widać, tutaj są to: c, h, i oraz trzecie a, gdyż te litery nie występują w słowie “arena”.

To badanie wydaje mi się rozsądniejsze od poprzedniego, choćby dlatego, że podczas testów wyszły nieco “mądrzejsze” wyniki. Choćby dla publikacji medycznych podanych wcześniej wynik tego algorytmu to 0,55 – na tej podstawie istotnie można wnioskować, że oba teksty zostały napisane dla potrzeb jednej dziedziny nauki. Ten algorytm wymaga jeszcze więcej testów, ale wyniki są obiecujące – jest on także znacznie krótszy i mniej skomplikowany niż poprzedni algorytm.

Tym niemniej myślę, że stosując obie techniki można przygotować prosty klasyfikator dla tytułów czy nazwisk autorów.

Oczywiście, jak to ja, nie pomyślałem o tym, aby wcześniej sprawdzić w Internecie, czy ktoś nie wymyślił czegoś lepszego. Owszem, iż wymyślił, przygotował całą bibliotekę, oparł na wcześniej wspomnianej odległości i całej teorii przestrzeni metrycznych. I wyszło to dużo lepiej – istnieje biblioteka LingPipe, a konkretny tutorial znajduje się tutaj.

Jeżeli macie jakieś uwagi, komentarze, rady czy własne pomysły – jak najbardziej zapraszam do pisania pod notką.

Pozdrawiam i dziękuję - SceNtriC