Параллельное вычисление медианы большого массива

Question

Мне однажды задали этот вопрос, но я так и не смог его выяснить:

У вас есть массив N целых чисел, где N велико, скажем, миллиард. Вы хотите вычислить среднее значение этого массива. Предположим, у вас есть m+1 машин (m рабочих, один мастер), на которые можно распределить работу. Как бы вы поступили так?

Поскольку медиана является нелинейным оператором, вы не можете просто найти медиану в каждой машине и затем взять медиану этих значений.

Answer 1

В зависимости от модели параллельных вычислений алгоритмы могут различаться. (Примечание: PDF-файл, указанный в предыдущем предложении, содержит только несколько возможных вариантов).

Поиск медианы - это особый случай поиска элемента i ^th . Эта проблема называется «проблемой выбора», поэтому вам нужно искать в сети параллельный выбор.

Вот одна статья (к сожалению, не бесплатная), которая может быть полезна: Алгоритмы параллельного выбора с анализом на кластерах .

И первая ссылка Google на запрос "Параллельный отбор" дает: http://www.umiacs.umd.edu/research/EXPAR/papers/3494/node18.html, которая фактически использует медиану медиан для общей проблемы, а не только поиск медианы.

Answer 2

Вы можете выполнить очень параллельную сортировку (например, сортировку слиянием) и получить медиану из результата.

Answer 3

Будет ли сортировка массива излишней? Если нет, то разделите массив, а затем объедините результаты вместе - мое предложение.