Qu’est-ce que Map / Reduce?

J’entends beaucoup parler de map / reduction, en particulier dans le contexte du système de calcul massivement parallèle de Google. Qu’est-ce que c’est exactement?

De l’abrégé de la page 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 carte 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 noeuds de traitement (plusieurs serveurs). Il s’agit donc d’un système qui peut très bien évoluer.

Comme elle est basée sur le modèle de functional programming , la map et reduce étapes de reduce n’ont aucun effet secondaire (l’état et les résultats de chaque sous-section d’un processus map ne dépendent pas d’autre), chacun étant séparé sur plusieurs nœuds de traitement.

Joel’s Can Votre langage de programmation fait cela? L’article explique comment la compréhension de la functional programming était essentielle dans Google pour concevoir MapReduce, qui propulse son moteur de recherche. C’est une très bonne lecture si vous n’êtes pas familier avec la functional programming et comment elle permet un code évolutif.

Voir aussi: Wikipedia: MapReduce

Question connexe: Veuillez expliquer mapreduce simplement

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

Voici comment la carte est probablement écrite en C # (elle s’appelle Select et se trouve dans la bibliothèque standard):

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

Comme vous êtes un mec de Java, et que Joel Spolsky aime raconter à GROSSLY UNFAIR LIES à quel point Java est minable (en fait, il ne ment pas, c’est de la merde, mais j’essaie de vous convaincre), voici ma tentative une version Java (je n’ai pas de compilateur Java, et je me rappelle 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 manières. Mais c'est l'idée de base.

Reduce est une fonction qui transforme tous les éléments d'une liste en une seule valeur. Pour ce faire, il faut lui atsortingbuer une autre fonction func qui transforme deux éléments en une seule valeur. Cela fonctionnerait en donnant les deux premiers articles à func . Ensuite, le résultat avec le troisième élément. Ensuite, le résultat de cela avec le quasortingème élément, et ainsi de suite jusqu'à ce que tous les éléments soient partis et nous sums restés avec une valeur.

En C #, réduire s'appelle Aggregate et se trouve à nouveau dans la bibliothèque standard. Je vais directement passer à 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 de générateurs, mais je ne sais pas comment faire en Java. Mais vous devriez pouvoir leur transmettre des classes internes anonymes pour fournir les foncteurs:

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

Espérons que les génériques se débarrasseront des moulages. L'équivalent type en C # est:

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

Pourquoi est-ce "cool"? Des moyens simples de décomposer des calculs plus volumineux en morceaux plus petits, de manière à pouvoir les assembler de différentes manières, sont toujours pratiques. La manière dont Google applique cette idée est la parallélisation, car la carte et la réduction peuvent être partagées sur plusieurs ordinateurs.

Mais l'exigence principale n'est PAS que votre langage puisse traiter les fonctions comme des valeurs. Toute langue OO peut le faire. La nécessité réelle de la parallélisation est que les fonctions func peu transmises à la carte et à la réduction ne doivent utiliser ou mettre à jour aucun état. Ils doivent renvoyer une valeur qui ne dépend que du ou des arguments qui leur ont été transmis. Sinon, les résultats seront complètement foirés lorsque vous tenterez d'exécuter le tout en parallèle.

MapReduce Explained .

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

Après avoir été le plus frustré par de très longs waffley ou de très courts messages de blog, j’ai finalement découvert ce très bon article concis .

Ensuite, je suis allé de l’avant et l’ai rendu plus concis en traduisant dans Scala, où j’ai fourni le cas le plus simple où un utilisateur spécifie simplement la map et reduce parties de l’application. Dans Hadoop / Spark, à proprement parler, on utilise un modèle de programmation plus complexe qui exige que l’utilisateur spécifie explicitement 4 fonctions supplémentaires 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 - ie 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 } 

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 sur chaque élément du tableau d’origine. Donc, si vous mappez une fonction (élément) {élément de retour * 2;}, cela 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

Reduce est une méthode JS native qui peut également être appliquée à un tableau. Il applique une fonction à un tableau et possède 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 parce que vous pouvez avoir n’importe quelle sortie, il vous suffit de commencer avec ce type d’accumulateur. Donc, si je voulais réduire quelque chose en object, je commencerais par un accumulateur {}.

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