Qu'est-ce que Map / Reduce?

J'entends beaucoup parler de carte / réduction, en particulier dans le contexte du système de calcul massivement parallèle de Google. Qu'est-ce que c'est exactement?

Extrait du résumé de la page de publication de recherche MapReduce de Google :

MapReduce est un modèle de programmation et une implémentation associée pour le traitement et la génération de grands ensembles de données. Les utilisateurs spécifient une fonction de mappage qui traite une paire clé / valeur pour générer un ensemble de paires clé / valeur intermédiaires, et une fonction de réduction qui fusionne toutes les valeurs intermédiaires associées à la même clé intermédiaire.

L'avantage de MapReduce est que le traitement peut être effectué en parallèle sur plusieurs nœuds de traitement (plusieurs serveurs), c'est donc un système qui peut très bien évoluer.

Étant donné qu'il est basé à partir de la programmation fonctionnelle modèle, la mapet les reduceétapes chaque ne pas avoir d'effets secondaires (l'état et les résultats de chaque sous - section d'un mapprocessus ne dépend pas de l' autre), de sorte que l'ensemble de données étant mis en correspondance et réduit peuvent chacun être séparés sur plusieurs nœuds de traitement.

Joel's Votre langage de programmation peut-il faire cela? L'article explique comment la compréhension de la programmation fonctionnelle était essentielle dans Google pour créer MapReduce, qui alimente son moteur de recherche. C'est une très bonne lecture si vous n'êtes pas familier avec la programmation fonctionnelle et comment elle permet un code évolutif.

Voir aussi: Wikipedia: MapReduce

Question connexe: veuillez expliquer mapreduce simplement

MapReduce expliqué .

Cela explique mieux que ce que je peux. Aide-t-il?

Map est une fonction qui applique une autre fonction à tous les éléments d'une liste, pour produire une autre liste avec toutes les valeurs de retour dessus. (Une autre façon de dire "appliquer f à x" est "appeler f, en lui passant x". Donc, parfois, il semble plus agréable de dire "appliquer" au lieu de "appeler".)

Voici comment la carte est probablement écrite en C # (elle est appelée Selectet se trouve dans la bibliothèque standard):

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

Comme vous êtes un mec Java, et que Joel Spolsky aime dire à DES MENSONGES GROSSEMENT INJUSTE à quel point Java est merdique (en fait, il ne ment pas, c'est merdique, mais j'essaie de vous convaincre), voici ma tentative très difficile de une version Java (je n'ai pas de compilateur Java, et je me souviens vaguement de la version 1.1 de Java!):

// 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;
}

Je suis sûr que cela peut être amélioré de mille façons. Mais c'est l'idée de base.

Réduire est une fonction qui transforme tous les éléments d'une liste en une seule valeur. Pour ce faire, il doit être doté d'une autre fonction funcqui transforme deux éléments en une seule valeur. Cela fonctionnerait en donnant les deux premiers éléments à func. Puis le résultat de cela avec le troisième élément. Ensuite, le résultat de cela avec le quatrième élément, et ainsi de suite jusqu'à ce que tous les éléments aient disparu et qu'il nous reste une valeur.

En C #, la réduction est appelée Aggregateet est à nouveau dans la bibliothèque standard. Je vais passer directement à une version 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;
}

Ces versions de Java ont besoin d'être ajoutées à des génériques, mais je ne sais pas comment faire cela en Java. Mais vous devriez pouvoir leur passer des classes internes anonymes pour fournir les foncteurs:

string[] names = getLotsOfNames();

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

Espérons que les génériques élimineraient les moulages. L'équivalent typeafe en C # est:

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

Pourquoi est-ce «cool»? Les moyens simples de diviser des calculs plus volumineux en petits morceaux, afin qu'ils puissent être reconstitués de différentes manières, sont toujours intéressants. Google applique cette idée à la parallélisation, car la carte et la réduction peuvent être partagées sur plusieurs ordinateurs.

Mais l'exigence clé n'est PAS que votre langage puisse traiter les fonctions comme des valeurs. N'importe quel langage OO peut le faire. L'exigence réelle pour la parallélisation est que les petites funcfonctions que vous passez à mapper et à réduire ne doivent utiliser ou mettre à jour aucun état. Ils doivent renvoyer une valeur qui dépend uniquement du ou des arguments qui leur sont passés. Sinon, les résultats seront complètement foirés lorsque vous essayez d'exécuter le tout en parallèle.

Après avoir été très frustré par les très longs waffley ou les très courts articles de blog vagues, j'ai finalement découvert ce très bon article concis et rigoureux .

Ensuite, je suis allé de l'avant et je l'ai rendu plus concis en traduisant en Scala, où j'ai fourni le cas le plus simple où un utilisateur spécifie simplement les parties mapet reducede l'application. Dans Hadoop / Spark, à proprement parler, un modèle de programmation plus complexe est utilisé qui oblige l'utilisateur à spécifier explicitement 4 autres fonctions décrites ici: 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 et / ou SQL:

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

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

critique de MapReduce

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

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

Map est une méthode JS native qui peut être appliquée à un tableau. Il crée un nouveau tableau à la suite d'une fonction mappée à chaque élément du tableau d'origine. Donc, si vous mappez une fonction (élément) {élément de retour * 2;}, il renverra un nouveau tableau avec chaque élément doublé. Le tableau d'origine ne serait pas modifié.

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

Réduire est une méthode JS native qui peut également être appliquée à un tableau. Il applique une fonction à un tableau et a une valeur de sortie initiale appelée accumulateur. Il parcourt chaque élément du tableau, applique une fonction et les réduit à une valeur unique (qui commence par l'accumulateur). C'est utile car vous pouvez avoir n'importe quelle sortie que vous voulez, il vous suffit de commencer avec ce type d'accumulateur. Donc si je voulais réduire quelque chose en objet, je commencerais par un accumulateur {}.

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

MapReduce:

Pour exécuter quelque chose de grand, nous pouvons utiliser la puissance de calcul de différents ordinateurs dans notre bureau. La partie la plus difficile est de diviser la tâche entre différents ordinateurs.Cela est fait par la bibliothèque MapReduce.

L'idée de base est de diviser le travail en deux parties: une carte et une réduction. Map prend essentiellement le problème, le divise en sous-parties et envoie les sous-parties à différentes machines - de sorte que toutes les pièces fonctionnent en même temps. Réduire prend les résultats des sous-parties et les combine pour obtenir une seule réponse.

L'entrée est une liste d'enregistrements. Le résultat du calcul de la carte est une liste de paires clé / valeur. Réduire prend chaque ensemble de valeurs qui a la même clé et les combine en une seule valeur. Vous ne pouvez pas dire si le travail a été divisé en 100 morceaux ou en 2 morceaux; le résultat final ressemble à peu près au résultat d'une seule carte.

Veuillez regarder une carte simple et réduire le programme:

La fonction de carte est utilisée pour appliquer une fonction sur notre liste d'origine et une nouvelle liste est donc générée. La fonction map () en Python prend une fonction et une liste comme argument. Une nouvelle liste est renvoyée en appliquant une fonction à chaque élément de la liste.

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

La fonction reduction () en Python prend une fonction et une liste comme argument. La fonction est appelée avec une fonction lambda et une liste et un nouveau résultat réduit est renvoyé. Ceci effectue une opération répétitive sur les paires de la liste.

#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