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

Question

я получил задал этот вопрос раз и до сих пор не в состоянии понять это:

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

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

Answer 1

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

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

Вот, пожалуйста, один документ (к сожалению, не бесплатный), который может пригодиться: Parallel Selection Algorithms With Analysis on Clusters.

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

Answer 2

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

Answer 3

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