Вычисление медианы на карте уменьшает

Ответ 1

Попытка найти среднее число (среднее число) в серии потребует, чтобы 1 редуктор передавал весь диапазон чисел, чтобы определить, какое значение является "средним".

В зависимости от диапазона и уникальности значений в вашем наборе входных данных вы можете ввести объединитель для вывода частоты каждого значения - уменьшение количества выходов карты, отправленных на ваш единственный редуктор. Затем ваш редуктор может использовать пары значений/частоты для идентификации медианы.

Другой способ, которым вы могли бы масштабировать это (опять же, если вы знаете диапазон и грубое распределение значений), - это использовать пользовательский разделитель, который распределяет ключи по диапазонам (0-99 перейти к редуктору 0, 100-199 к редуктору 2, и так далее). Тем не менее это потребует некоторой дополнительной работы для изучения выходов редуктора и выполнения окончательного медианного расчета (зная, например, количество ключей в каждом редукторе, вы можете рассчитать, какой выход редуктора будет содержать медиану и при каком смещении)

Ответ 2

Вам действительно нужны точные медианные и квантильные числа?

В большинстве случаев вам лучше всего получать приблизительные значения и работать с ними, в частности, если вы используете это для, например, разделение данных.

Фактически вы можете использовать приблизительные квантили, чтобы ускорить поиск точных квантилей (фактически в O(n/p) время), вот примерный план стратегии:

• Попросите сопоставителя для каждого раздела вычислить нужные квантили и вывести их в новый набор данных. Этот набор данных должен быть в несколько раз меньше (если вы не попросите слишком много квантилей!)
• В этом наборе данных снова вычислите квантилиты, похожие на "медиану медианов". Это ваши первоначальные оценки.
• Перегруппируйте данные в соответствии с этими квантилями (или даже дополнительные разделы, полученные таким образом). Цель состоит в том, что в конечном итоге истинный квантиль гарантированно находится в одном разделе, и в каждом разделе должно быть не более одного из желаемых квантилей.
• Внутри каждого из разделов выполните QuickSelect (в O(n)), чтобы найти истинный квантили.

Каждый из шагов находится в линейном времени. Самым дорогостоящим шагом является часть 3, так как это потребует перераспределения всего набора данных, поэтому он генерирует сетевой трафик O(n). Вероятно, вы можете оптимизировать процесс, выбрав "альтернативные" квантиля для первой итерации. Скажем, вы хотите найти глобальную медиану. Вы не можете легко найти его в линейном процессе, но вы, вероятно, можете сузить его до 1/kth набора данных, когда он разбит на k разделов. Поэтому вместо того, чтобы каждый node сообщать о своей медиане, каждый node дополнительно сообщает объекты в (k-1)/(2k) и (k + 1)/(2k). Это должно позволить вам сузить диапазон значений, где истинная медиана должна лежать отчетливо. Итак, на следующем шаге вы можете каждый node отправлять те объекты, которые находятся в пределах требуемого диапазона, одному мастеру node и выбирать только медиану только в этом диапазоне.

Ответ 3

O ((n log n)/p), чтобы отсортировать его, а затем O (1), чтобы получить медиану.

Да... вы можете получить O (n/p), но вы не можете использовать функцию сортировки вне коробки в Hadoop. Я бы просто сортировал и получал элемент центра, если вы не можете оправдать 2-20 часов разработки, чтобы закодировать параллельный k-й алгоритм.

Ответ 4

Во многих реальных сценариях мощность значений в наборе данных будет относительно небольшой. В таких случаях проблема может быть эффективно решена с помощью двух заданий MapReduce:

• Рассчитать частоту значений в вашем наборе данных (в основном, Word Count job)
• Модуль отображения идентичности + редуктор, который вычисляет медиану на основе < значение - частотa > пары

Работа 1. значительно сократит объем данных и может быть выполнена полностью параллельно. Редуктор задания 2. должен обрабатывать только теги n (n= cardinality of your value set) вместо всех значений, как с наивным подходом.

Ниже приведен пример сокращения задания 2. Это python script, который можно использовать непосредственно в потоке Hadoop. Предполагает, что значения в вашем наборе данных ints, но могут быть легко приняты для 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))

Этот ответ основывается на предположении, исходящем из ответа Криса Уайта. Ответ предполагает использование объединителя в качестве среднего для вычисления частот значений. Однако в MapReduce комбайнеры не гарантируются всегда. Это имеет некоторые побочные эффекты:

• редуктор сначала должен вычислить конечный < значение - частотa > пары, а затем вычислить медианную.
• В худшем случае комбинаторы никогда не будут выполнены, и редуктору все равно придется бороться с обработкой всех отдельных значений.