Qu'est-ce que Map/Reduce?

la Carte est une fonction qui applique une fonction à tous les éléments d'une liste, pour produire une liste avec toutes les valeurs de retour sur elle. (Une autre façon de dire "appliquer f à x" est "appeler f, passer x". Alors parfois, il semble plus agréable de dire "appliquer" au lieu de "l'appel".)

c'est ainsi que la carte est probablement écrite en C# (elle s'appelle Select et 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 de Java, et Joel Spolsky aime pour raconter des mensonges grossièrement injustes sur la façon dont Java est merdique (en fait, il ne ment pas, c'est merdique, mais j'essaie de vous convaincre), voici ma tentative très rugueuse à une version Java (je n'ai pas de compilateur Java, et je me souviens vaguement de la version Java 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;
}

je suis sûr que cela peut être amélioré d'un million de 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 donné une autre fonction func qui transforme deux articles en une seule valeur. Cela fonctionnerait en donnant les deux premiers points à func . Le résultat de ce avec la troisième élément. Ensuite, le résultat avec le quatrième article, et ainsi de suite jusqu'à ce que tous les articles ont disparu et il nous reste une valeur.

dans C# reduce est appelé Aggregate et 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 Java ont besoin de génériques pour les ajouter, mais je ne sais pas comment le faire en Java. Mais vous devriez être en mesure de les passer des classes intérieures 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); }
   }

avec un peu de chance, generics se débarrasserait des moulages. L'équivalent de typesafe en C# est:

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

pourquoi c'est"cool"? Des moyens simples de diviser des calculs plus grands en plus petits morceaux, de sorte qu'ils peuvent être assemblés de différentes façons, sont toujours cool. La façon dont Google applique cette idée est à la parallélisation, parce que la carte et réduire peuvent être partagés sur plusieurs ordinateurs.

mais la principale exigence n'est pas que votre langue puisse traiter les fonctions comme des valeurs. N'importe quelle langue OO peut le faire. L'exigence réelle pour la parallélisation est que les petites fonctions func que vous passez à map and reduce ne doivent pas utiliser ou mettre à jour n'importe quel état. Ils doivent retourner une valeur qui dépend seulement de l'argument(s) passé à ils. Dans le cas contraire, les résultats seront complètement faussés lorsque vous tenterez d'exécuter l'ensemble en parallèle.

MapReduce Expliquée .

explique mieux que moi. Est-il utile?

après avoir été très frustré avec soit très long waffley ou des billets de blog très courts et vagues, j'ai finalement découvert ce très bon papier rigoureux et concis .

puis je suis allé de l'avant et l'a rendu plus concis en traduisant en Scala, où j'ai fourni le cas le plus simple où un utilisateur se contente de spécifier les map et reduce parties de l'application. En Hadoop / Spark, à proprement parler, un modèle de programmation plus complexe est employé qui exigent de l'utilisateur de spécifier explicitement 4 plus de 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 original. Ainsi, si vous avez mappé une fonction(element) { return element * 2;}, elle retournerait un nouveau tableau avec chaque élément doublé. Le tableau d'origine irait non modifiée.

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 a une valeur de sortie initiale appelée un accumulateur. Il boucle à travers chaque élément du tableau, applique une fonction, et les réduit à une seule valeur (qui commence comme l'accumulateur). Il est utile parce que vous pouvez avoir n'importe quelle sortie vous le souhaitez, vous venez 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