W wielu rzeczywistych scenariuszach liczność wartości w zbiorze danych będzie stosunkowo niewielka. W takich przypadkach, problem może być skutecznie rozwiązany z dwóch miejsc pracy mapreduce:
- Obliczanie częstotliwości wartości w zbiorze danych (Word Count pracy, w zasadzie)
- Identity odwzorowujący + reduktor, który oblicza medianę podstawie < wartości - częstotliwość> pary
Zadanie 1. znacznie ograniczy ilość danych i może być wykonane w pełni równolegle. Redukcja zadania 2. będzie wymagać przetworzenia tylko elementów n (n = cardinality of your value set) zamiast wszystkich wartości, tak jak w przypadku podejścia naiwnego.
Poniżej przykład reduktora zadania 2. Jest to skrypt Pythona, który może być użyty bezpośrednio w streamingu Hadoop. Przyjmuje wartości w zbiorze są ints, ale może być łatwo przyjęte 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))
Ta odpowiedź buduje się na szczycie sugestią początkowo pochodzące z answer z Chris White. Odpowiedź sugeruje użycie sumatora jako środka do obliczania częstotliwości wartości. Jednak w MapReduce nie można zagwarantować, że kombinatory będą zawsze wykonywane. Ma to pewne skutki uboczne:
- reduktor będzie musiał najpierw obliczyć końcową wartość < - częstotliwość> pary, a następnie obliczyć medianę.
- W najgorszym scenariuszu, sumatory zostanie nigdy wykonany i reduktor nadal będą musiały walczyć z przetwarzaniem Wszystkie indywidualne wartości
Znalezienie dokładnych quantiles może być bardzo kosztowne w tym podejściu Amy być lepiej niż naiwnego podejścia choć . Krok 1 do 4 pomaga w dzieleniu zestawu na pół i rozwiązaniu tego samego problemu na mniejszej przestrzeni. Ale w tym podejściu może zająć logn iteracje od kroku 1 do kroku 4, aby faktycznie uzyskać kwantyl. – Sourabh