Bezbolesne wprowadzenie do MapReduce

16.12.2009 - Paweł Ledwoń
TrudnośćTrudność

Przykłady

Zliczanie słów

Najprostszym przykładem, który można wymyślić, jest problem zliczania wystąpień słów. Dane przekazywane do MapReduce to plik tekstowy, w którym szukamy liczby wystąpień każdego ze słów.

Na początku dzielimy plik na wiersze i przekazujemy je do funkcji map jako wartości. Dla każdego słowa z otrzymanego wiersza generujemy parę <słowo, 1>.

Jako argumenty dla wywołań reduce będą przekazywane słowa oraz lista, której wszystkimi elementami są powtórzenia liczby 1. Pochodzą one z par wygenerowanych w fazie map. Długość otrzymanej listy jest liczbą wystąpień danego słowa w dokumencie.

Poniższy aplet demonstruje działanie algorytmu zliczania słów. Suwaki oznaczone literami M i R służą do regulowania liczby zadań map i reduce. Poniżej nich można wpisać dane wejściowe dla aplikacji.

Zakładki reprezentują wykonywane w danej chwili zadania, a ich przebieg jest prezentowany w oddzielnych tabelach. Przyciski "wstecz" i "dalej" służą do wykonywania kolejnych kroków algorytmu.

Kliknięcie w przycisk "odśwież" spowoduje ponowne wczytanie danych i rozpoczęcie obliczeń od początku. Jak sama nazwa wskazuje, przycisk "przykładowe dane" generuje tekst, w którym będą zliczane słowa i odświeża obliczenia.

Na samym dole apletu znajduje się dziennik, w którym znajduje się opis trzech ostatnio wykonanych kroków.

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Rozproszony grep

Kolejnym przykładem z dziedziny algorytmów tekstowych jest wyszukiwanie w pliku linii, w których występuje określony z góry wzorzec. Systemy Unixowe implementują tę funkcjonalność przez polecenie grep.

Na wejściu (ponownie) otrzymujemy listę wierszy z przeszukiwanego pliku. Funkcja map zwraca wiersz, jeżeli został w nim odnaleziony wzorzec. Funkcja reduce nie musi wykonywać już żadnych obliczeń, więc zwraca wiersz, który otrzymała jako swój argument.

Przeglądarka ma wyłączoną obsługę Javy lub Java nie została zainstalowana. Pobierz Javę

Składnia wyrażeń regularnych obsługiwanych przez aplet grep znajduje się w dokumentacji Java Platform, klasy Pattern.

Sortowanie

Jednym z ważniejszych i często spotykanych problemów jest sortowanie danych. Mamy daną listę kluczy i wartości, naszym zadaniem jest ustawić jej elementy zgodnie z pewnym porządkiem ≤. Rozwiązanie opiera się na konstrukcji samego frameworka MapReduce. Wymagane jest od nas zapewnienie wykonania poniższych czterech kroków:

  1. wczytanie danych wejściowych,
  2. podział danych na mniejsze fragmenty do posortowania,
  3. sortowanie fragmentów,
  4. zapisanie posortowanych fragmentów.

Zauważmy, że pomiędzy fazami map i reduce dane są zawsze porządkowane przed grupowaniem, więc nie musimy nawet myśleć o implementacji algorytmu sortowania. Kroki 1, 3 i 4 zapewnia więc samo środowisko MapReduce, zatem jedynym problemem jest odpowiedni podział danych wejściowych na R części. Musimy zapewnić, że posortowane części ułożone są monotonicznie, czyli minimalny klucz z fragmentu i-tego nie jest mniejszy od maksymalnego klucza z fragmentu poprzedniego.

Załóżmy więc, że wszystkie sortowane klucze zawierają się w zbiorze A = [M; N], który jest znany przed wczytaniem danych. Przedział A podzielmy na R równych części A1, A2, …, AR. Elementy rozdzielające te podprzedziały możemy wyliczyć w prosty sposób, więc podział danych będziemy w stanie utworzyć w czasie, który nie będzie miał większego wpływu na czas wykonania całego algorytmu.

Rozwiązanie te jest dobre, o ile wczytywane dane są rozłożone jednostajnie w zbiorze A. W przeciwnym wypadku podział może być nierówny, więc uporządkowanie niektórych części może trwać dużo dłużej niż sortowanie pozostałych. Isnieje lepsze rozwiązanie tego problemu, nad którym jednak w tym artykule nie będziemy się rozwodzić.

4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com