¿Qué es Map / Reduce?

Escucho mucho sobre map / reduce, especialmente en el contexto del sistema de cómputo masivamente paralelo de Google. ¿Qué es exactamente?

Del resumen de la página de publicación de la investigación MapReduce de Google :

MapReduce es un modelo de programación y una implementación asociada para procesar y generar grandes conjuntos de datos. Los usuarios especifican una función de mapa que procesa un par clave / valor para generar un conjunto de pares clave / valor intermedios, y una función de reducción que fusiona todos los valores intermedios asociados con la misma clave intermedia.

La ventaja de MapReduce es que el procesamiento se puede realizar en paralelo en múltiples nodos de procesamiento (múltiples servidores) por lo que es un sistema que puede escalar muy bien.

Dado que se basa en el modelo de programación funcional , los pasos mapy reduceno tienen efectos secundarios (el estado y los resultados de cada subsección de un mapproceso no dependen de otro), por lo que el conjunto de datos que se mapea y reduce se puede separar cada uno sobre múltiples nodos de procesamiento.

Joel's ¿Puede su lenguaje de programación hacer esto? Este artículo analiza cómo comprender la programación funcional fue esencial en Google para crear MapReduce, que impulsa su motor de búsqueda. Es una muy buena lectura si no está familiarizado con la programación funcional y cómo permite el código escalable.

Véase también: Wikipedia: MapReduce

Pregunta relacionada: explique mapreduce simplemente

MapReduce explicado .

Explica mejor de lo que puedo. Te ayuda?

Map es una función que aplica otra función a todos los elementos de una lista, para producir otra lista con todos los valores devueltos. (Otra forma de decir "aplicar f a x" es "llamar f, pasándola x". Por eso, a veces suena mejor decir "aplicar" en lugar de "llamar").

Así es como el mapa probablemente está escrito en C # (se llama Selecty está en la biblioteca estándar):

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

Como eres un tipo de Java, y a Joel Spolsky le gusta contar MENTIRAS GROSSLY INJUSTAS sobre lo malo que es Java (en realidad, él no está mintiendo, es una mierda, pero estoy tratando de conquistarte), aquí está mi intento muy rudo de una versión de Java (no tengo un compilador de Java, y recuerdo vagamente la versión 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;
}

Estoy seguro de que esto se puede mejorar en un millón de formas. Pero es la idea básica.

Reducir es una función que convierte todos los elementos de una lista en un solo valor. Para hacer esto, necesita tener otra función funcque convierta dos elementos en un solo valor. Funcionaría dándole los dos primeros elementos a func. Luego, el resultado de eso junto con el tercer elemento. Luego, el resultado de eso con el cuarto elemento, y así sucesivamente hasta que todos los elementos hayan desaparecido y nos quedemos con un valor.

En C # se llama a reduce Aggregatey vuelve a estar en la biblioteca estándar. Pasaré directamente a una versión de 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;
}

Estas versiones de Java necesitan que se les agreguen genéricos, pero no sé cómo hacerlo en Java. Pero debería poder pasarles clases internas anónimas para proporcionar los functores:

string[] names = getLotsOfNames();

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

Con suerte, los genéricos eliminarían los yesos. El equivalente de seguridad de tipos en C # es:

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

¿Por qué es esto "genial"? Las formas sencillas de dividir cálculos más grandes en partes más pequeñas, para que puedan volver a juntarse de diferentes maneras, siempre son geniales. La forma en que Google aplica esta idea es mediante la paralelización, porque tanto el mapa como la reducción se pueden compartir en varias computadoras.

Pero el requisito clave NO es que su idioma pueda tratar las funciones como valores. Cualquier idioma de OO puede hacer eso. El requisito real para la paralelización es que las pequeñas funcfunciones que pase a mapear y reducir no deben usar ni actualizar ningún estado. Deben devolver un valor que dependa solo de los argumentos que se les pasen. De lo contrario, los resultados se estropearán por completo cuando intente ejecutar todo en paralelo.

Después de sentirme más frustrado con un waffley muy largo o con publicaciones de blog vagas y muy cortas, finalmente descubrí este muy buen artículo conciso riguroso .

Luego seguí adelante y lo hice más conciso traduciendo a Scala, donde proporcioné el caso más simple donde un usuario simplemente especifica las partes mapy reducede la aplicación. En Hadoop / Spark, estrictamente hablando, se emplea un modelo de programación más complejo que requiere que el usuario especifique explícitamente 4 funciones más descritas aquí: 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 y / o SQL:

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

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

crítica de MapReduce

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

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

Map es un método JS nativo que se puede aplicar a una matriz. Crea una nueva matriz como resultado de alguna función asignada a cada elemento de la matriz original. Entonces, si mapeó una función (elemento) {elemento de retorno * 2;}, devolvería una nueva matriz con cada elemento duplicado. La matriz original no se modificaría.

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

Reducir es un método JS nativo que también se puede aplicar a una matriz. Aplica una función a una matriz y tiene un valor de salida inicial llamado acumulador. Recorre cada elemento de la matriz, aplica una función y los reduce a un solo valor (que comienza como el acumulador). Es útil porque puedes tener cualquier salida que desees, solo debes comenzar con ese tipo de acumulador. Entonces, si quisiera reducir algo a un objeto, comenzaría con un acumulador {}.

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

Mapa reducido:

Para ejecutar algo grande, podemos usar la potencia de cálculo de diferentes computadoras en nuestra oficina. La parte difícil es dividir la tarea entre diferentes computadoras, lo hace la biblioteca MapReduce.

La idea básica es que divida el trabajo en dos partes: un mapa y una reducción. Map básicamente toma el problema, lo divide en subpartes y envía las subpartes a diferentes máquinas, por lo que todas las piezas se ejecutan al mismo tiempo. Reducir toma los resultados de las subpartes y los vuelve a combinar para obtener una única respuesta.

La entrada es una lista de registros. El resultado del cálculo del mapa es una lista de pares clave / valor. Reducir toma cada conjunto de valores que tiene la misma clave y los combina en un solo valor. No se puede saber si el trabajo se dividió en 100 piezas o en 2 piezas; el resultado final se parece mucho al resultado de un solo mapa.

Mire el mapa simple y reduzca el programa:

La función de mapa se usa para aplicar alguna función en nuestra lista original y, por lo tanto, se genera una nueva lista. La función map () en Python toma una función y una lista como argumento. Se devuelve una nueva lista aplicando la función a cada elemento de la lista.

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

La función reduce () en Python toma una función y una lista como argumento. La función se llama con una función lambda y una lista y se devuelve un nuevo resultado reducido. Esto realiza una operación repetitiva sobre los pares de la lista.

#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