Рассчитайте медиану из миллиарда чисел

Question

Если у вас есть один миллиард чисел и сто компьютеров, как лучше всего определить медиану этих чисел?

Одно из решений, которое у меня есть:

• Разделите набор поровну между компьютерами.
• Сортировать их.
• Найдите медианы для каждого набора.
• Сортировка наборов по медиане.
• Слияние двух подходов за раз от самой низкой до самой высокой медианы.

Если у нас есть m1 < m2 < m3 ..., то сначала объединяем Set1 и Set2 и в результирующем наборе мы можем отбросить все числа, меньшие медианы Set12 (объединены). Так что в любой момент времени у нас есть равные по размеру наборы. Кстати, это не может быть сделано в параллельной манере. Есть идеи?

Answer 1

Я думаю, что ответ Стива Джессопа будет самым быстрым.

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

Divide the numbers into 100 computers (10 MB each). 
Loop until we have one element in each list     
    Find the meadian in each of them with quickselect which is O(N) and we are processing in parallel. The lists will be partitioned at the end wrt median.
    Send the medians to a central computer and find the median of medians. Then send the median back to each computer. 
    For each computer, if the overall median that we just computed is smaller than its median, continue in the lower part of the list (it is already partitioned), and if larger in the upper part.
When we have one number in each list, send them to the central computer and find and return the median.

Answer 2

Предположим, вы знаете, что число различных целых чисел составляет (скажем) 4 миллиарда, затем вы можете объединить их в группы по 64 КБ и получить распределенное число для каждого сегмента от каждой машины в кластере (100 компьютеров). Объедините все это. Теперь найдите корзину, у которой есть медиана, и на этот раз попросите только корзины для элементов 64k, которые будут лежать в вашем целевом ведре. Это требует O (1) (в частности, 2) запросов к вашему «кластеру». : D

Answer 3

Я бы сделал это так:

в начале все 100 работают, чтобы найти самое большое и самое низкое число; каждый компьютер имеет свою часть базы данных / файл, который он запрашивает;

при обнаружении наибольшего и наименьшего чисел один компьютер считывает данные и распределяет каждое число равномерно между остальными 99; числа распределены равными интервалами; (один может принимать от -100 миллионов до 0, другой - от 0 до 100 миллионов и т. д.);

При получении номеров каждый из 99 компьютеров уже сортирует их;

Тогда легко найти медиану ... Посмотрите, сколько чисел есть у каждого компьютера, сложите их все (сумма, сколько есть чисел, а не сами числа), разделите на 2; подсчитать, в каком компьютере число, и по какому индексу;

:) вуаля

P.S. Кажется, здесь много путаницы; МЕДИАНА - это ЧИСЛО В СРЕДНЕМ СОРТИРОВАННОГО СПИСКА ЧИСЕЛ!

Answer 4

Моя копейка, после всего, что уже воспитывалось другими:

Нахождение медианы на одной машине - O (N): https://en.wikipedia.org/wiki/Selection_algorithm.

Отправка N номеров на 100 машин также является O (N). Итак, чтобы сделать использование 100 машин интересным, либо связь должна быть относительно быстрой, либо N настолько велико, что ни одна машина не может справиться с этим, в то время как N / 100 выполнимо, или мы просто хотим рассмотреть математическую проблему, не беспокоясь о datacommunication.

Если говорить кратко, то я предполагаю, что в разумных пределах мы можем отправлять / распространять номера, не влияя на анализ эффективности.

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

1. Каждая машина получает N / 100 чисел, вычисляет свою медиану и отправляет эту информацию мастеру.
2. Мастер составляет отсортированный список всех различных медиан и отправляет его обратно на каждую машину, определяя упорядоченную последовательность сегментов (на каждой машине одинаково), по одному на каждое значение медианы (сегмент с одним значением) и один для каждый интервал между соседними медианами. Конечно, есть также нижние и верхние сегменты для значений ниже самой низкой медианы и выше самой высокой.
3. Каждая машина вычисляет, сколько чисел попадает в каждое ведро, и передает эту информацию мастеру.
4. Мастер определяет, какое ведро содержит медиану, сколько нижних значений (всего) падает ниже этого ведра и сколько выше.
5. Если выбранный интервал является интервалом с одним значением (одним из медиан) или наоборот, выбранный интервал содержит только 1 (N нечетных) или 2 (N четных) значений, которые мы сделали. В противном случае мы повторяем шаги выше со следующими (очевидными) модификациями:
6. Только числа из выбранного сегмента распределяются от мастера к 100 машинам и, более того,
7. Мы не собираемся вычислять (на каждой машине) медиану, а k-е значение, где мы учитываем, сколько старших чисел было отброшено из общего числа и сколько меньших чисел. Концептуально каждая машина также имеет свою долю отброшенных низких / высоких чисел и учитывает ее при вычислении новой медианы в наборе, который (концептуально) включает (свою долю) отброшенных чисел.

Время-сложность:

1. Немного размышлений убедит вас, что на каждом шаге общее количество анализируемых значений уменьшается как минимум в два раза (2 - довольно больной случай; вы можете ожидать значительно лучшего сокращения). Отсюда получаем:
2. Предполагая, что для нахождения медианы (или k-го значения), которая является O (N), требуется c * N время, когда коэффициент c не слишком сильно меняется с N, так что мы можем принять его как константу для момент, мы получим наш окончательный результат в самое большее 2 * c * N / 100 раз. Таким образом, использование 100 машин дает нам коэффициент ускорения 100/2 (как минимум).
3. Как отмечалось вначале: время, необходимое для обмена номерами между машинами, может сделать более привлекательным просто делать все на одной машине. Однако, если мы перейдем к распределенному подходу, общее количество номеров, которые должны быть переданы на всех этапах вместе, не будет превышать 2 * N (N в первый раз, <= N / 2 во второй раз, <= половина этого третье и т. д.) </li>

Answer 5

1. Разделите 1 миллиард чисел на 100 машин. Каждая машина будет иметь 10 ^ 7 чисел.

2. Для каждого входящего номера на машину, сохранить номер в карте частот, число -> кол. Также сохраните минимальный номер на каждой машине.

3. Найти медиану в каждой машине: начиная с минимального числа в каждой машине, суммировать счет до достижения медианного индекса. Медиана в каждой машине, будет ок. меньше и больше 5 * 10 ^ 6 чисел.

4. Найти медиану всех медиан, которая будет меньше и больше, чем ок. 50 * 10 ^ 7 чисел, что является медианой 1 миллиарда чисел.

Теперь некоторая оптимизация 2-го шага: вместо сохранения в карте частот, сохраните счетчики в массиве переменных битов. Например: скажем, начиная с минимального числа в машине, это счетчики частоты:

[min number] - 8 count
[min+1 number] - 7 count
[min+2 number] - 5 count

Вышеуказанное может быть сохранено в битовом массиве как:

[min number] - 10000000
[min+1 number] - 1000000
[min+2 number] - 10000

Обратите внимание, что в целом это будет стоить около 10 ^ 7 бит для каждой машины, поскольку каждая машина обрабатывает только 10 ^ 7 чисел. 10 ^ 7 бит = 1,25 * 10 ^ 6 байт, что составляет 1,25 МБ

Таким образом, при вышеупомянутом подходе каждой машине потребуется 1,25 МБ места для вычисления локальной медианы. И медиана медиан может быть вычислена из этих 100 локальных медиан, в результате чего медиана составляет 1 миллиард чисел.