En muchos escenarios del mundo real, la cardinalidad de los valores en un conjunto de datos será relativamente pequeña. En tales casos, el problema se puede resolver de manera eficiente con dos trabajos MapReduce:
- determinar las frecuencias de los valores del conjunto de datos (Word Count trabajo, básicamente)
- Identidad asignador + un reductor que calcula la mediana basado en < valor - frecuencia> pares
Tarea 1. Reduce drásticamente la cantidad de datos y se puede ejecutar completamente en paralelo. El reductor del trabajo 2. solo tendrá que procesar n (n = cardinality of your value set) elementos en lugar de todos los valores, como con el enfoque ingenuo.
A continuación, un ejemplo de reductor del trabajo 2. Es un script de python que se puede usar directamente en la transmisión de Hadoop. Toma valores en el conjunto de datos son ints, pero se pueden adoptar fácilmente para double s
import sys
item_to_index_range = []
total_count = 0
# Store in memory a mapping of a value to the range of indexes it has in a sorted list of all values
for line in sys.stdin:
item, count = line.strip().split("\t", 1)
new_total_count = total_count + int(count)
item_to_index_range.append((item, (total_count + 1, new_total_count + 1)))
total_count = new_total_count
# Calculate index(es) of middle items
middle_items_indexes = [(total_count/2) + 1]
if total_count % 2 == 0:
middle_items_indexes += [total_count/2]
# Retrieve middle item(s)
middle_items = []
for i in middle_items_indexes:
for item, index_range in item_to_index_range:
if i in range(*index_range):
middle_items.append(item)
continue
print sum(middle_items)/float(len(middle_items))
Esta respuesta se acumula en la parte superior de una sugerencia inicialmente procedente del answer de Chris White. La respuesta sugiere usar un combinador como medio para calcular frecuencias de valores. Sin embargo, en MapReduce, no se garantiza que los combinadores siempre se ejecuten. Esto tiene algunos efectos secundarios:
- reductor primero tendrá que calcular el valor final de < -> frecuencia pares y luego calcular la mediana.
- En el peor de los casos, combinadores nunca será ejecutado y el reductor todavía tendrá que luchar con el procesamiento de todos los valores individuales
Encontrar cuantiles exactas podría ser muy costoso en este enfoque amy ser mejor que el enfoque ingenuo, aunque . Los pasos 1 a 4 realmente ayudan a dividir el conjunto en la mitad y a resolver el mismo problema en un espacio más pequeño. Pero en este enfoque, puede tomar iteraciones logn del paso 1 al paso 4 para obtener realmente el cuantil. – Sourabh