¿Qué es un mapa / Reducir?
https://stackoverflow.com/questions/388321
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He oído mucho acerca de map / reduce, especialmente en el contexto del sistema de cómputo masivamente paralelo de Google. ¿Qué es exactamente?
Solución
Desde el resumen de Google de MapReduce publicación de investigación:
MapReduce es un modelo de programación y una aplicación asociada para el procesamiento y la generación de datos de gran tamaño conjuntos. Los usuarios especifican una función de mapa que procesa un par de claves / valor a generar un conjunto de intermedio pares clave / valor, y una función de reducir que combina todos los valores intermedios asociado con el mismo intermedio la clave.
La ventaja de MapReduce es que el procesamiento se puede realizar en paralelo en varios nodos de procesamiento (varios servidores) por lo que es un sistema que puede escalar muy bien.
Desde que se basa en la modelo de programación funcional , map y reduce pasos cada uno no lo hacen tener efectos secundarios (el estado y los resultados de cada subsección de un proceso map no depende de otro), por lo que el conjunto de datos se asignan y se redujeron se puede separar cada uno a través de múltiples nodos de procesamiento.
Puede su lenguaje de programación hacer esto? pieza analiza cómo la comprensión de la programación funcional era esencial en Google para llegar a MapReduce, que alimenta su motor de búsqueda. Es una muy buena lectura si no está familiarizado con la programación funcional y cómo se permite que el código escalable.
Vea también: Wikipedia: MapReduce
pregunta relacionada: favor explicar mapreduce simplemente
Otros consejos
Se explica mejor que lo que pueda. ¿Ayuda?
Map es una función que corresponde otra función para todos los elementos de una lista, para producir otra lista con todos los valores de retorno sobre el mismo. (Otra forma de decir "aplicar f para x" es "llamada de f, pasándole x". Así que a veces suena más agradable que decir "aplicar" en lugar de "llamada".)
Esta es la forma en mapa es, probablemente escrito en C # (se llama Select y se encuentra 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);
}
A medida que usted es un tipo de Java, y Joel Spolsky le gusta decir mentiras manifiestamente injustos sobre cómo mierda Java es (en realidad, no está mintiendo, que es horrible, pero estoy tratando de ganar más), aquí está mi muy intento áspera en una versión de Java (no tengo compilador de Java, y recuerdo vagamente de Java versión 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;
}
Estoy seguro de que esto puede ser mejorado en un millón de maneras. Pero es la idea básica.
Reducir es una función que convierte todos los elementos de una lista en un solo valor. Para ello, es necesario tener en cuenta otra función que convierte func dos artículos en un solo valor. Que funcionaría dando a los dos primeros elementos que func. A continuación, el resultado de que, junto con el tercer punto. A continuación, el resultado de que, con el cuarto punto, y así sucesivamente hasta que todos los artículos han ido y nos quedamos con un valor.
en C # reducir se llama Aggregate y está de nuevo en la biblioteca estándar. Voy a saltar 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 necesidad genéricos añadiendo a ellos, pero no saben cómo hacerlo en Java. Sin embargo, usted debe ser capaz de pasar a las clases internas anónimas para proporcionar los funtores:
string[] names = getLotsOfNames();
string commaSeparatedNames = (string)reduce(names,
new IBinaryFunctor {
public object invoke(object arg1, object arg2)
{ return ((string)arg1) + ", " + ((string)arg2); }
}
Los genéricos se espera pueda deshacerse de los moldes. El equivalente typesafe en C # es:
string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);
¿Por qué es "cool"? Formas sencillas de romper los cálculos más grandes en pedazos más pequeños, por lo que se pueden poner de nuevo juntos de diferentes maneras, son siempre frescas. La forma en que Google aplica esta idea es la paralelización, debido a que tanto el mapa y reducir pueden ser compartidos a lo largo de varios ordenadores.
Pero lo principal no es que la lengua puede tratar como valores de funciones. Cualquier lenguaje orientado a objetos puede hacer eso. El requisito real para la paralelización es que las pequeñas funciones func que pasan a mapear y reducir no debe utilizar o actualizar cualquier estado. Deben devolver un valor que depende sólo del argumento (s) que se les pasa. De lo contrario, los resultados se pueden atornillar por completo cuando intenta ejecutar todo el asunto en paralelo.
Después de conseguir más frustrado con cualquiera waffley muy largo o entradas de blog vagas muy cortos que finalmente descubrieron esta muy buena rigurosa papel concisa.
Luego fui por delante y lo hizo más concisa, plasmando en Scala, donde yo he proporcionado el caso más simple, donde un usuario simplemente especifica las partes map y reduce de la aplicación. En Hadoop / Spark, en sentido estricto, se emplea un modelo más complejo de programación que requiere que el usuario especifique explícitamente 4 funciones más esbozados 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
}
Map es un método nativo JS que se puede aplicar a una matriz. Se crea una nueva matriz como resultado de alguna función asignada a cada elemento de la matriz original. Así que si asigna una función (elemento) {elemento de retorno * 2;}, devolvería una nueva matriz con cada elemento duplicado. La matriz original iría sin modificar.
Reducir es un método nativo JS que también se puede aplicar a una matriz. Se aplica una función a una matriz y tiene un valor de salida inicial llamado un acumulador. Se bucles a través de cada elemento de la matriz, se aplica una función, y los reduce a un solo valor (que comienza como el acumulador). Es útil porque puede tener cualquier salida que desea, sólo hay que comenzar con ese tipo de acumulador. Así que si quería algo para reducir en un objeto, me gustaría empezar con un acumulador {}.
https: / /developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce?v=a
MapReduce:
Para ejecutar algo grande, podemos usar el poder de cómputo diferente equipo en nuestra oficina. Lo difícil es la de dividir tareas entre los diferentes computers.It se realiza mediante la biblioteca MapReduce.
La idea básica es que se divide el trabajo en dos partes: un mapa, y una Reducir. Mapa toma básicamente el problema, lo divide en sub-partes, y envía los sub-partes a diferentes máquinas - por lo que todas las piezas ejecutar al mismo tiempo. Reducir toma los resultados de las sub-partes y los combina de nuevo juntos para obtener una sola respuesta.
La entrada es una lista de records.Result del mapa cálculo es una lista de pares clave / valor. Reducir toma cada conjunto de valores que tiene la misma clave, y las combina en una sola value.You no se puede saber si el trabajo se dividió en 100 piezas o 2 piezas; el resultado final es más o menos como el resultado de un solo mapa.
Por favor, mira al mapa sencillo y reducen programa:
Función de mapa se utiliza para aplicar alguna función en nuestra lista original y una nueva lista de ahí se genera. La función de mapa () en Python toma en una función y una lista como argumento. Una nueva lista se devuelve mediante la aplicación de 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 en una función y una lista como argumento. La función se llama a una función lambda y una lista y se devuelve un nuevo resultado reducida. Esto realiza una operación repetitiva en 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
