Czym jest Map/Reduce?

Map jest funkcją, która stosuje inną funkcję do wszystkich pozycji na liście, aby wytworzyć inną listę ze wszystkimi zwracanymi wartościami. (Innym sposobem na powiedzenie "apply F to x "jest" call f, passing it x". Więc czasami lepiej jest powiedzieć " zastosuj "zamiast"zadzwoń".)

W ten sposób map jest prawdopodobnie napisany w C# (nazywa się Select i znajduje się w bibliotece standardowej):

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

Jako że jesteś kolesiem Javy, a Joel Spolsky lubi opowiadać rażąco niesprawiedliwe kłamstwa o tym, jak gówniana jest Java (właściwie, to nie kłamie, to jest gówniane, ale staram się wygrać), oto moja bardzo szorstka próba wersji Java (Nie mam kompilatora Java, i niejasno pamiętam Java Wersja 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 podać inną funkcję func, która zamienia dwa elementy w jedną wartość. Działałoby to poprzez dawanie pierwsze dwa elementy func. Następnie wynik tego wraz z trzecim punktem. Następnie wynik tego z czwartym elementem, i tak dalej, aż wszystkie elementy znikną i pozostaniemy z jedną wartością.

W C# reduce nazywa się Aggregate i ponownie znajduje się w bibliotece standardowej. Przeskoczę od razu do wersji Javy:

// 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 generyków, ale nie wiem, jak to zrobić w Javie. Ale powinieneś być w stanie przekazać im anonimowe wewnętrzne klasy, 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 generyki pozbędą się odlewów. Odpowiednikiem typów w C# jest:

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 łączyć na różne sposoby, są zawsze fajne. Sposób, w jaki Google stosuje ten pomysł, polega na równoległoboku, ponieważ zarówno Mapa, jak i redukcja mogą być dzielone na kilka komputerów.

Ale kluczowym wymogiem nie jest to, że twój język może 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 funkcje func przekazywane do mapowania i zmniejszania nie mogą używać ani aktualizować żadnego stanu. Muszą zwracać wartość zależną tylko od przekazywanych im argumentów. W przeciwnym razie wyniki będą całkowicie spieprzone, gdy spróbujesz uruchomić całość równolegle.

MapReduce Explained .

To wyjaśnia lepiej niż mogę. Czy to pomaga?

Po tym, jak najbardziej sfrustrowano mnie albo bardzo długimi, albo bardzo krótkimi, niejasnymi wpisami na blogu, w końcu odkryłem tenBardzo dobry, zwięzły papier .

Potem poszedłem do przodu i zrobiłem to bardziej zwięzłe, tłumacząc na Scala, gdzie podałem najprostszy przypadek, w którym użytkownik po prostu określa map i reduce części aplikacji. W Hadoop/Spark, ściśle mówiąc, stosuje się bardziej złożony model programowania, który wymaga od użytkownika wyraźnego podaj 4 więcej 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 jest natywną metodą JS, którą można zastosować do tablicy. Tworzy nową tablicę w wyniku jakiejś funkcji mapowanej do każdego elementu w oryginalnej tablicy. Więc jeśli zmapujesz funkcję (element) { return element * 2;}, zwróci ona nową tablicę z każdym podwojonym elementem. Oryginalna tablica zostałaby niezmodyfikowana.

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

Reduce jest natywną metodą JS, którą można również zastosować do tablicy. Stosuje funkcję do tablicy i ma początkową wartość wyjściową zwaną akumulatorem. Pętla przez każdy element w tablicy, stosuje funkcję i zmniejsza je do pojedynczej wartości (która zaczyna się jako akumulator). Jest to przydatne, ponieważ możesz mieć dowolną wydajność, którą chcesz, po prostu musisz zacząć od tego typu akumulatora. Więc gdybym chciał zredukować coś do przedmiotu, zacząłbym od akumulatora {}.

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