Как считается медиана с помощью MapReduce?

Вычисление медианы с помощью MapReduce — нетривиальная задача, так как медиана требует глобального упорядочивания данных. Основная идея:

1. Map: каждый маппер читает часть данных и создает гистограмму или распределение значений (например, подсчитывает количество элементов в определённых диапазонах).

2. Reduce: редьюсеры агрегируют эти гистограммы, получая общее распределение по всему набору данных.

3. Определение медианы: используя агрегированное распределение, вычисляют позицию медианы (половину общего количества элементов) и находят соответствующий диапазон значений.

4. При необходимости запускают дополнительный MapReduce, чтобы отфильтровать данные, попадающие в этот диапазон, и более точно определить медиану.

Таким образом, медиана вычисляется итеративно, сужая диапазон поиска, используя распределение данных, а не сортируя весь набор целиком.

Примерно так выглядит алгоритм:

Map:
  для каждого элемента emit (ключ_диапазона, 1)

Reduce:
  суммировать количество по ключам

После Reduce:
  вычислить кумулятивное распределение и найти диапазон с медианой

Если диапазон слишком велик:
  повторить MapReduce для элементов в этом диапазоне

Итерации продолжаются, пока не найдется точное значение медианы.