Trzy błędy w Union Find

Ostatnio zajęłam się przerobieniem mojego algorytmu MST tak żeby znajdywał spójne składowe w grafie (Connected Components o których mówiłam wcześniej). Długo szło mi coś nie tak, wreszcie znalazłam trzy błędy przez które mój program nie dawał takich samych wyników jak w Sparku.

  1. Porównywałam napisy zamiast liczb. W ten sposób, „12” było mniejsze od „8” bo jeśli potraktujemy te dwie liczby jako napisy to przecież „12” jest alfabetycznie wcześniej od „8”. Na szczęście dało się to szybko poprawić.
  2. Przy wypisywaniu wyników, nie używałam funkcji find do znajdowania przynależności wierzchołka do komponentu lecz wypisywałam do jakiego wierzchołka jest on bezpośrednio połączony. Jak już znalazłam ten błąd to też łatwo się go dało naprawić, zamiast parent[p], gdzie trzymałam identyfikator komponentu do jakiego wierzchołek należał, trzeba było użyć funkcji find(p) która wywoływała się rekurencyjnie aż doszło się do korzenia w spójnej składowej który był właściwym identyfikatorem komponentu.
  3. Dane które miałam były uszkodzone. Było to 5,5 GB danych zamiast 6,3. Już się zmartwiłam, że będę musiała znowu lecieć na uczelnię i walczyć z pendrivem żeby wgrać ten duży plik do systemu plików hdfs, ale na szczęście odkryłam dzięki stronie [1] taką komendę:
    tar jfx wiki.tar.bz2 -O | hdfs dfs -put – In/wikiNew
    Dzięki fladze -O, pliki nie są wypakowywane lokalnie lesz od razu do strumienia wyjściowego. Następnie wynik jest przekazywany do komendy hdfs dfs -put która pozwala na wgranie plików do hdfs. Zwycięstwo 🙂

Teraz ostatnie poprawki kodu. Właśnie liczę UF dla danych z Wikipedii na czterech maszynach. Jeśli będzie poprawnie, to zaimplementuję jeszcze wzorzec In-Maper Combiner, który wzięłam z artykułu [2], a który jest bardzo ładnie rozpisany na stronie 3.

Jak już to zadziała to będę mogła powrócić do zadania z BFS-em. Cieszę się, że wykryłam błąd z danymi zanim utworzyłam z tych danych listę sąsiedztwa potrzebną na działanie algorytmu BFS. Przeczytałam również wspomniany artykuł o technikach optymalizacji algorytmów grafowych w MapReduce i wykorzystam tam przynajmniej dwie techniki In Mapper Combiner wspomniany powyżej oraz Shimmy. Obydwie techniki będą pasowały do rozwiązań BFS oraz PageRank. Nie wiem jeszcze czy coś sprytnego da się zastosować do APSP i Triangle Count którego chyba się podejmę. Czas pokaże, a jest go mało, więc przekonam się chyba dość szybko.

Do dzieła!

_____

[1] – http://hakunamapdata.com/why-put-is-better-than-copyfromlocal-when-coping-files-to-hdfs/
[2] – Design Patterns for Efficient Graph Algorithms in MapReduce, Jimmy Lin and Michael Schatz
[3] – https://vangjee.wordpress.com/2012/03/07/the-in-mapper-combining-design-pattern-for-mapreduce-programming/

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s