Buenos ejemplos de MapReduce

Solución:

Map reduce es un marco que se desarrolló para procesar grandes cantidades de datos de manera eficiente. Por ejemplo, si tenemos 1 millón de registros en un conjunto de datos y está almacenado en una representación relacional, es muy costoso derivar valores y realizar cualquier tipo de transformación en estos.

Por ejemplo, en SQL, dada la fecha de nacimiento, averiguar cuántas personas tienen> 30 años para un millón de registros tomaría un tiempo, y esto solo aumentaría en orden de magnitud cuando aumenta la complejidad de la consulta. Map Reduce proporciona una implementación basada en clústeres donde los datos se procesan de manera distribuida

Aquí hay un artículo de Wikipedia que explica qué map-reduce se trata de

Otro buen ejemplo es Finding Friends a través de map reduce puede ser un ejemplo poderoso para comprender el concepto y un caso de uso bien utilizado.

Personalmente, encontré este enlace bastante útil para comprender el concepto

Copiando la explicación proporcionada en el blog (en caso de que el enlace quede obsoleto)

Encontrar amigos

MapReduce es un marco desarrollado originalmente en Google que permite la computación distribuida a gran escala en varios dominios. Apache Hadoop es una implementación de código abierto.

Pasaré por alto los detalles, pero todo se reduce a definir dos funciones: una función de mapa y una función de reducción. La función de mapa toma un valor y genera pares clave: valor. Por ejemplo, si definimos una función de mapa que toma una cadena y genera la longitud de la palabra como clave y la palabra en sí como el valor, entonces map (steve) devolvería 5: steve y map (savannah) devolverían 8: savannah . Es posible que haya notado que la función de mapa no tiene estado y solo requiere el valor de entrada para calcular su valor de salida. Esto nos permite ejecutar la función de mapa contra valores en paralelo y proporciona una gran ventaja. Antes de llegar a la función de reducción, el marco mapreduce agrupa todos los valores por clave, por lo que si las funciones del mapa generan la siguiente clave: pares de valores:

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

Se agrupan como:

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

Cada una de estas líneas se pasaría entonces como un argumento a la función de reducción, que acepta una clave y una lista de valores. En este caso, podríamos estar tratando de averiguar cuántas palabras de ciertas longitudes existen, por lo que nuestra función de reducción solo contará el número de elementos en la lista y generará la clave con el tamaño de la lista, como:

3 : 3
4 : 3
5 : 2
8 : 2

Las reducciones también se pueden hacer en paralelo, lo que nuevamente brinda una gran ventaja. Luego podemos mirar estos resultados finales y ver que solo había dos palabras de longitud 5 en nuestro corpus, etc.

El ejemplo más común de mapreduce es contar el número de veces que aparecen palabras en un corpus. Suponga que tiene una copia de Internet (he tenido la suerte de haber trabajado en tal situación) y desea una lista de cada palabra en Internet, así como cuántas veces ocurrió.

La forma en que abordaría esto sería tokenizar los documentos que tiene (dividirlos en palabras) y pasar cada palabra a un mapeador. El mapeador luego escupiría la palabra junto con un valor de 1. La fase de agrupación tomará todas las claves (en este caso palabras) y hará una lista de unos. Luego, la fase de reducción toma una clave (la palabra) y una lista (una lista de unos por cada vez que la clave apareció en Internet) y suma la lista. Luego, el reductor genera la palabra, junto con su recuento. Cuando todo esté dicho y hecho, tendrá una lista de cada palabra en Internet, junto con cuántas veces apareció.

Fácil, ¿verdad? Si alguna vez has leído sobre mapreduce, el escenario anterior no es nada nuevo … es el “Hola, mundo” de mapreduce. Así que aquí hay un caso de uso del mundo real (Facebook puede o no hacer lo siguiente, es solo un ejemplo):

Facebook tiene una lista de amigos (tenga en cuenta que los amigos son algo bidireccional en Facebook. Si soy su amigo, usted es mío). También tienen mucho espacio en disco y atienden cientos de millones de solicitudes todos los días. Han decidido precalcular los cálculos cuando pueden para reducir el tiempo de procesamiento de las solicitudes. Una solicitud de procesamiento común es la función “Tú y Joe tienen 230 amigos en común”. Cuando visitas el perfil de alguien, ves una lista de amigos que tienes en común. Esta lista no cambia con frecuencia, por lo que sería un desperdicio volver a calcularla cada vez que visitara el perfil (seguro que podría usar una estrategia de almacenamiento en caché decente, pero entonces no podría seguir escribiendo sobre mapreduce para este problema). Usaremos mapreduce para poder calcular los amigos comunes de todos una vez al día y almacenar esos resultados. Más adelante es solo una búsqueda rápida. Tenemos mucho disco, es barato.

Suponga que los amigos se almacenan como Persona->[List of Friends], nuestra lista de amigos es entonces:

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

Cada línea será un argumento para un asignador. Para cada amigo en la lista de amigos, el asignador generará un par clave-valor. La clave será un amigo junto con la persona. El valor será la lista de amigos. La clave se ordenará para que los amigos estén en orden, haciendo que todas las parejas de amigos vayan al mismo reductor. Esto es difícil de explicar con texto, así que hagámoslo y veamos si puedes ver el patrón. Una vez que todos los mapeadores hayan terminado de ejecutarse, tendrá una lista como esta:

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

Cada línea se pasará como argumento a un reductor. La función de reducción simplemente intersecará las listas de valores y generará la misma clave con el resultado de la intersección. Por ejemplo, reduce ((AB) -> (ACDE) (BCD)) dará como resultado (AB): (CD) y significa que los amigos A y B tienen a C y D como amigos en común.

El resultado después de la reducción es:

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

Ahora, cuando D visita el perfil de B, podemos buscar rápidamente (B D) y ver que tienen tres amigos en común, (A C E).

Uno de los mejores ejemplos de implementación MapReduce similar a Hadoop.

Sin embargo, tenga en cuenta que se limitan a implementaciones basadas en valores clave de la idea de MapReduce (por lo que su aplicabilidad es limitada).

Un conjunto de operaciones familiares que puede hacer en MapReduce es el conjunto de operaciones SQL normales: SELECT, SELECT WHERE, GROUP BY, ect.

Otro buen ejemplo es la multiplicación de matrices, donde se pasa una fila de M y el vector completo x y se calcula un elemento de M * x.

---

---

Utiliza Nuestro Buscador