Co to jest Map / Reduce?

Dużo słyszę o mapowaniu / zmniejszaniu, szczególnie w kontekście masowo równoległego systemu obliczeniowego Google. Co to właściwie jest?

Ze streszczenia strony publikacji Google MapReduce :

MapReduce to model programowania i skojarzona z nim implementacja do przetwarzania i generowania dużych zestawów danych. Użytkownicy określają funkcję mapowania, która przetwarza parę klucz / wartość w celu wygenerowania zestawu pośrednich par klucz / wartość oraz funkcję redukcji, która łączy wszystkie wartości pośrednie skojarzone z tym samym kluczem pośrednim.

Zaletą MapReduce jest to, że przetwarzanie może być wykonywane równolegle na wielu węzłach przetwarzania (wielu serwerach), więc jest to system, który można bardzo dobrze skalować.

Ponieważ jest ona oparta z funkcjonalnego programowania modelu, mapa reducekroki każdy nie ma żadnych skutków ubocznych (stanu i wyników z każdej podsekcji z mapprocesu nie zależy od innego), więc zbiór danych jest odwzorowywany i zmniejszona każdy może być oddzielona w wielu węzłach przetwarzania.

Joel's Czy twój język programowania może to zrobić? Artykuł omawia, w jaki sposób zrozumienie programowania funkcjonalnego było niezbędne w Google, aby stworzyć MapReduce, która napędza jego wyszukiwarkę. To bardzo dobra lektura, jeśli nie znasz programowania funkcjonalnego i tego, jak umożliwia ono skalowalny kod.

Zobacz też: Wikipedia: MapReduce

Powiązane pytanie: Proszę wyjaśnić po prostu mapreduce

MapReduce Explained .

To wyjaśnia lepiej niż to, co potrafię. Czy to pomaga?

Mapa to funkcja, która stosuje inną funkcję do wszystkich elementów na liście, aby utworzyć inną listę ze wszystkimi zwracanymi wartościami. (Innym sposobem powiedzenia „zastosuj f do x” jest „wywołaj f, przekazując x”. Czasami więc lepiej jest powiedzieć „zastosuj” zamiast „wywołaj”).

Oto jak mapa jest prawdopodobnie napisana w C # (nazywa się Selecti znajduje się w standardowej bibliotece):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func)
{
    foreach (T item in list)
        yield return func(item);
}

Ponieważ jesteś kolesiem z Javy, a Joel Spolsky lubi opowiadać ZNACZNIE NIEUCZCIWE KŁAMSTWA o tym, jak kiepska jest Java (właściwie nie kłamie, jest do niczego, ale próbuję cię przekonać), oto moja bardzo trudna próba wersja Javy (nie mam kompilatora Javy i niejasno pamiętam wersję Javy 1.1!):

// represents a function that takes one arg and returns a result
public interface IFunctor
{
    object invoke(object arg);
}

public static object[] map(object[] list, IFunctor func)
{
    object[] returnValues = new object[list.length];

    for (int n = 0; n < list.length; n++)
        returnValues[n] = func.invoke(list[n]);

    return returnValues;
}

Jestem pewien, że można to poprawić na milion sposobów. Ale to podstawowa idea.

Reduce to funkcja, która zamienia wszystkie elementy na liście w jedną wartość. Aby to zrobić, należy mu nadać inną funkcję, funcktóra zamienia dwa elementy w jedną wartość. To zadziałałoby, dając pierwsze dwa elementy func. Następnie wynik tego wraz z trzecią pozycją. Następnie wynik tego z czwartą pozycją i tak dalej, aż wszystkie elementy znikną i zostanie nam jedna wartość.

W C # wywoływana jest redukcja Aggregatei ponownie znajduje się w bibliotece standardowej. Przejdę od razu do wersji Java:

// represents a function that takes two args and returns a result
public interface IBinaryFunctor
{
    object invoke(object arg1, object arg2);
}

public static object reduce(object[] list, IBinaryFunctor func)
{
    if (list.length == 0)
        return null; // or throw something?

    if (list.length == 1)
        return list[0]; // just return the only item

    object returnValue = func.invoke(list[0], list[1]);

    for (int n = 1; n < list.length; n++)
        returnValue = func.invoke(returnValue, list[n]);

    return returnValue;
}

Te wersje Javy wymagają dodania do nich ogólnych, ale nie wiem, jak to zrobić w Javie. Ale powinieneś być w stanie przekazać im anonimowe klasy wewnętrzne, aby zapewnić funktory:

string[] names = getLotsOfNames();

string commaSeparatedNames = (string)reduce(names, 
   new IBinaryFunctor {
       public object invoke(object arg1, object arg2)
           { return ((string)arg1) + ", " + ((string)arg2); }
   }

Miejmy nadzieję, że leki generyczne pozbędą się odlewów. Odpowiednik bezpieczny dla typów w C # to:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

Dlaczego to jest „fajne”? Proste sposoby dzielenia większych obliczeń na mniejsze części, aby można je było złożyć na różne sposoby, są zawsze fajne. Sposób, w jaki Google stosuje ten pomysł, polega na zrównoleglaniu, ponieważ zarówno mapowanie, jak i redukcja mogą być współdzielone na kilku komputerach.

Ale kluczowym wymaganiem NIE jest to, aby Twój język mógł traktować funkcje jako wartości. Każdy język OO może to zrobić. Rzeczywisty wymóg równoległości polega na tym, że małe funcfunkcje przekazywane do mapowania i zmniejszania nie mogą używać ani aktualizować żadnego stanu. Muszą zwrócić wartość, która jest zależna tylko od przekazanych im argumentów. W przeciwnym razie wyniki zostaną całkowicie schrzanione, gdy spróbujesz uruchomić całość równolegle.

Po tym, jak byłem najbardziej sfrustrowany bardzo długimi waflowymi lub bardzo krótkimi, ogólnikowymi postami na blogu, w końcu odkryłem ten bardzo dobry, rygorystyczny, zwięzły artykuł .

Następnie poszedłem dalej i uczyniłem to bardziej zwięzłym, tłumacząc na Scala, gdzie przedstawiłem najprostszy przypadek, w którym użytkownik po prostu określa mapi reduceczęści aplikacji. Ściśle mówiąc, w Hadoop / Spark zastosowano bardziej złożony model programowania, który wymaga od użytkownika wyraźnego określenia 4 dodatkowych funkcji opisanych tutaj: http://en.wikipedia.org/wiki/MapReduce#Dataflow

import scalaz.syntax.id._

trait MapReduceModel {
  type MultiSet[T] = Iterable[T]

  // `map` must be a pure function
  def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                              (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = 
    data.flatMap(map)

  def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] =
    mappedData.groupBy(_._1).mapValues(_.map(_._2))

  // `reduce` must be a monoid
  def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.flatMap(reduce).map(_._2)

  def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)])
                                   (map: ((K1, V1)) => MultiSet[(K2, V2)])
                                   (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] =
    mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce)
}

// Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster
// Furthermore, the splitting here won't enforce any kind of balance and is quite unnecessary anyway as one would expect
// it to already be splitted on HDFS - i.e. the filename would constitute K1
// The shuffle phase will also be parallelized, and use the same partition as the map phase.  
abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel {
  def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]]

  override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                                       (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = {
    val groupedByKey = data.groupBy(_._1).map(_._2)
    groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1))
    .par.flatMap(_.map(map)).flatten.toList
  }

  override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _)))
    .par.flatMap(_.map(reduce))
    .flatten.map(_._2).toList
}

MapReduce i / lub SQL:

http://www.data-miners.com/blog/2008/01/mapreduce-and-sql-aggregations.html

http://www.data-miners.com/blog/

krytyka MapReduce

http://www.databasecolumn.com/2008/01/mapreduce-a-major-step-back.html

http://www.databasecolumn.com/2008/01/mapreduce-continued.html

Map to natywna metoda JS, którą można zastosować do tablicy. Tworzy nową tablicę w wyniku jakiejś funkcji odwzorowanej na każdy element oryginalnej tablicy. Więc jeśli zamapujesz funkcję (element) {element zwrotny * 2;}, zwróci ona nową tablicę z podwojonym każdym elementem. Oryginalna tablica pozostanie niezmodyfikowana.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map

Reduce to natywna metoda JS, którą można również zastosować do tablicy. Stosuje funkcję do tablicy i ma początkową wartość wyjściową zwaną akumulatorem. Przechodzi przez każdy element tablicy, stosuje funkcję i redukuje je do pojedynczej wartości (która zaczyna się jako akumulator). Jest to przydatne, ponieważ możesz mieć dowolne wyjście, po prostu musisz zacząć od tego typu akumulatora. Więc gdybym chciał zredukować coś do obiektu, zacząłbym od akumulatora {}.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce?v=a

MapReduce:

Aby uruchomić coś dużego, możemy wykorzystać moc obliczeniową innego komputera w naszym biurze. Trudną częścią jest podzielenie zadania na różne komputery, a zajmuje się tym biblioteka MapReduce.

Podstawową ideą jest podzielenie pracy na dwie części: mapę i redukcję. Map zasadniczo podejmuje problem, dzieli go na części podrzędne i wysyła części podrzędne do różnych maszyn - dzięki czemu wszystkie elementy działają w tym samym czasie. Reduce pobiera wyniki z części podrzędnych i łączy je z powrotem w celu uzyskania jednej odpowiedzi.

Dane wejściowe to lista rekordów, a wynikiem obliczeń mapy jest lista par klucz / wartość. Reduce pobiera każdy zestaw wartości, który ma ten sam klucz i łączy je w jedną wartość. Nie można stwierdzić, czy zadanie zostało podzielone na 100 czy 2 części; wynik końcowy wygląda prawie jak wynik pojedynczej mapy.

Proszę spojrzeć na prostą mapę i zredukować program:

Funkcja mapy jest używana do zastosowania jakiejś funkcji na naszej pierwotnej liście i generowana jest nowa lista. Funkcja map () w Pythonie przyjmuje funkcję i listę jako argument. Nowa lista jest zwracana przez zastosowanie funkcji do każdego elementu listy.

li = [5, 7, 4, 9] 
final_list = list(map(lambda x: x*x , li)) 
print(final_list)  #[25, 49, 16, 81]

Funkcja redukuj () w Pythonie przyjmuje funkcję i listę jako argument. Funkcja jest wywoływana z funkcją lambda i listą oraz zwracany jest nowy zredukowany wynik. Powoduje to powtarzalną operację na parach z listy.

#reduce func to find product/sum of list
x=(1,2,3,4)
from functools import reduce
reduce(lambda a,b:a*b ,x) #24