Bezbolesne wprowadzenie do MapReduce
16.12.2009 - Paweł Ledwoń
PrzykładyZliczanie słówNajprostszym 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. Rozproszony grepKolejnym 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. SortowanieJednym 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:
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ć. (3 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com