Clase “Combiner" en un trabajo mapreduce

Question

un combinador se ejecuta después de la Mapper y antes de que el reductor, recibirá como entrada todos los datos emitidos por las instancias Mapper en un nodo dado. Entonces emite de salida a los reductores.

y también, si una función de reducir es a la vez conmutativa y asociativa, a continuación, se puede utilizar como un combinador.

Mi pregunta es ¿qué significa la frase "conmutativa y asociativa" quiere decir en esta situación ?

Answer 1

Suponga que tiene una lista de números, 1 2 3 4 5 6.

asociativa aquí significa que usted puede tomar su operación y aplicarlo a cualquier subgrupo, luego aplicarlo al resultado de estos y obtener la misma respuesta:

(1) + (2 + 3) + (4 + 5 + 6) 
    == 
(1 + 2) + (3 + 4) + (5) + (6) 
    == 
... 

Piense en el paréntesis aquí como la ejecución de un combinador.

conmutativa significa que el orden no es importante, por lo que:

1 + 2 + 3 + 4 + 5 + 6 
    == 
2 + 4 + 6 + 1 + 2 + 3 
    == 
... 

Por ejemplo, además, se ajusta a esta propiedad, como se ha visto antes. "Máximo" también se ajusta a esta propiedad, porque el máximo de max es el máximo. max (a, b) == max (b, a).

La mediana es un ejemplo que no funciona: la mediana de las medianas no es la mediana verdadera.

---

No se olvide otra propiedad importante de un combinador: los tipos de entrada de la clave/valor y los tipos de salida de la clave/valor tienen que ser los mismos. Por ejemplo, no puede tomar una cadena: int y devolver una cadena: float.

Muchas veces, el reductor puede producir algún tipo de cuerda en lugar de valor numérico, lo que puede impedir que solo conecte su reductor como combinador.

Answer 2

Para la conmutatividad, digamos que su reductor se puede representar por una función (en el término matemático) llamada f(). Luego, su reductor es conmutativo si f (a, b) = f (b, a) Por ejemplo:

• suma (A, B) es el mismo que la suma (B, A)
• xor (A, B) es el mismo que xor (B, A)
• concat (A, B) es no el mismo que concat (B, A)

Para asociatividad, la propiedad es que f (f (a, b), c) = f (a, f (b, c)). Por ejemplo:

• (A + B) + C es el mismo que A + (B + C)
• (A - B) - C es no el mismo que A - (B - C)

Por lo tanto, en el contexto de Map/Reduce, su reductor debe respetar estas 2 propiedades. Por ejemplo, si su reductor está haciendo solo una suma(), o un máximo(), respeta ambas propiedades, pero algo como mean() o mediana() no lo hace, y por lo tanto no puede usarlo como un combinador.

yo personalmente ver combinadores como mini-reductores que se ejecutan en la memoria después de la fase de mapa como una optimización para reducir el tráfico de red y la conmutatividad/asociatividad realmente tiene sentido si usted ve un map/reduce de esta manera: