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

Question

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

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

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

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

Answer 1

Это зависит от ваших данных. В худшем случае это равномерно распределенные числа.

В этом случае вы можете найти медиану за O (N) времени, как в этом примере:

Предположим, что ваши номера 2,7,5,10,1,6,4,4,6,10,4,7,1,8,4,9,9,3,4,3 (диапазон 1 -10).

Мы создаем 3 ведра: 1-3, 4-7, 8-10. Обратите внимание, что верх и низ имеют одинаковый размер.

Заполняем ведра числами, подсчитываем, сколько выпадает в каждом, максимум и минимум

• низкий (5): 2,1,1,3,3, мин 1, макс 3
• средний (10): 7,5,6,4,4,6,4,7,4,4, минимум 4, максимум 7
• высокий (5): 10, 10, 8, 9, 9, минимум 8, максимум 10

Среднее значение попадает в среднее ведро, остальное мы игнорируем

Мы создаем 3 сегмента: 4, 5-6, 7. Низкий начинается со счета 5 и максимум 3, а высокий - минимум 8 и счет 5.

Для каждого числа мы подсчитываем, сколько выпадает в нижнем и верхнем ведре, максимальном и минимальном, и сохраняем среднее ведро.

• старый низкий (5)
• низкий (5): 4, 4, 4, 4, 4, максимум 4
• средний (3): 5,6,6
• высокий (2): 7, 7, мин. 7
• старый высокий (5)

Теперь мы можем вычислить медиану напрямую: у нас такая ситуация

old low    low          middle  high  old high
x x x x x  4 4 4 4 4 4   5 6 6  7 7   x x x x x

таким образом, медиана составляет 4,5.

Предполагая, что вы немного знаете о распределении, вы можете точно настроить способы определения диапазонов для оптимизации скорости. В любом случае производительность должна идти с O (N), потому что 1 + 1/3 + 1/9 ... = 1,5

Вам нужны min и max из-за краевых случаев (например, если медиана - это среднее значение между максимумом старого минимума и следующим элементом).

Все эти операции можно распараллелить, вы можете передать 1/100 данных каждому компьютеру и вычислить 3 сегмента в каждом узле, а затем распределить блок, который вы храните. Это снова заставляет вас эффективно использовать сеть, потому что каждое число передается в среднем 1,5 раза (поэтому O (N)). Вы даже можете превзойти это, если будете передавать только минимальные числа между узлами (например, если узел 1 имеет 100 чисел, а узел 2 имеет 150 чисел, тогда узел 2 может дать 25 чисел узлу 1).

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

Answer 2

Более простой способ - иметь взвешенные числа.

• Разделить большой набор среди компьютеров
• Сортировка каждого набора
• итерация по малому набору и вычисление весов для повторяющихся элементов
• объединить каждые 2 набора в 1 (каждый уже отсортирован), обновляя веса
• продолжайте объединять наборы, пока не получите только один набор
• перебирайте этот набор, накапливая веса, пока не достигнете OneBillion / 2

Answer 3

Это можно сделать на узлах, используя данные, которые не отсортированы по узлам (скажем, из файлов журнала), следующим образом.

Существует 1 родительский узел и 99 дочерних узлов. Дочерние узлы имеют два вызова API:

• stats (): возвращает min, max и count
• сравнить (median_guess): возвращает значение совпадения счетчика, счетчик меньше значения и счетчик больше значения

Родительский узел вызывает stats () для всех дочерних узлов, отмечая минимум и максимум всех узлов.

Бинарный поиск теперь может выполняться следующим образом:

1. Разбить минимальное и максимальное округление вниз - это среднее значение «угадай»
2. Если число больше, чем число меньше, чем число меньше, установите минимальное значение для предположения
3. Если число больше, чем меньше, чем число меньше, установите максимальное значение для догадки
4. Если счет нечетный, закончить, когда минимальное и максимальное значения равны
5. Если счетчик даже закончен, когда максимум <= минимум + угадать.match_count Это можно сделать на узлах, используя несортированные данные (например, из файлов журнала), следующим образом. </li>

Существует 1 родительский узел и 99 дочерних узлов. Дочерние узлы имеют два вызова API:

• stats (): возвращает min, max и count
• сравнивать (median_guess): возвращает значение совпадения счетчика, счетчик меньше значения и счетчик больше значения

Родительский узел вызывает stats () для всех дочерних узлов, отмечая минимум и максимум всех узлов.

Бинарный поиск теперь может выполняться следующим образом:

1. Разбить минимальное и максимальное округление вниз - это среднее значение «угадай»
2. Если число больше, чем число меньше, чем число меньше, установите минимальное значение для предположения
3. Если число больше, чем меньше, чем число меньше, установите максимальное значение для догадки
4. Если счет нечетный, закончить, когда минимальное и максимальное значения равны
5. Если счетчик даже закончен, когда максимум <= минимальный + guess.match_count </li>

Если stats () и compare () можно предварительно рассчитать с помощью сортировки O (N / Mlogn / M), то предварительное вычисление O (N / M) со сложностью памяти O (N) для предварительный расчет. Тогда вы могли бы сделать сравнение () в постоянное время, так что все это (включая предварительный расчет) будет выполняться за O (N / MlogN / M) + O (logN) * ​​1051 *

Дайте мне знать, если я допустил ошибку!

Answer 4

Разделите 10 ^ 9 чисел, 10 ^ 7 на каждый компьютер ~ 80 МБ на каждом. Каждый компьютер сортирует свои номера. Затем компьютер 1 объединяет и сортирует свои номера с номерами компьютеров 2, 3 и 4 и т. Д. Затем компьютер 1 записывает половину чисел обратно в 2, 3 к 4 и т. Д. Затем слияние 1 сортирует номера с компьютеров. 1,2,3,4, пишет их обратно. И так далее. В зависимости от размера оперативной памяти на компьютерах, вам может не хватить записи всех чисел обратно на отдельные компьютеры на каждом шаге, возможно, вы сможете накопить цифры на компьютере 1 за несколько шагов, но вы выполните математику.

О, наконец, получите среднее значение 500000000-го и 500000001-го значений (но проверьте, что там достаточно 00, у меня нет).

РЕДАКТИРОВАТЬ: @Roman - хорошо, если вы не можете в это поверить, даже если это правда, тогда нет смысла в моем раскрытии правды или лжи предложения. Что я хотел сказать, так это то, что грубая сила иногда побеждает умных в гонке. У меня ушло около 15 секунд, чтобы разработать алгоритм, который, я уверен, я смогу реализовать, который будет работать и который можно будет адаптировать к широкому диапазону размеров входов и количеств компьютеров, а также настраивать на характеристики компьютеров и сетевые договоренности. Если вам или кому-то еще понадобится 15 минут, чтобы разработать более сложный алгоритм, у меня есть преимущество в 14m45, чтобы кодировать мое решение и запускать его.

Но я свободно признаю, что это все утверждение, я ничего не измерял.

Answer 5

Если числа не различаются и принадлежат только определенному диапазону, то есть они повторяются, то мне приходит в голову простое решение - равномерно распределить числа между 99 машинами и сохранить одну машину в качестве мастера , Теперь каждая машина перебирает свои заданные числа и сохраняет количество каждого числа в хэш-наборе. Каждый раз, когда число повторяется в наборе номеров, выделенных этому конкретному компьютеру, он обновляет свой счет в хэш-наборе.

Все машины затем возвращают свой хэш-набор на главную машину. Мастер-машина объединяет хэш-наборы, суммируя количество ключей, найденных в хэш-наборе. Например, в хэш-наборе машины # 1 была запись ("1", 7), а в хэш-наборе машины # 2 была запись ("1", 9), поэтому мастер-машина при комбинировании хеш-наборов делает запись («1», 16) и т. Д.

После объединения хеш-наборов просто сортируйте ключи, и теперь вы можете легко найти (n / 2) -й элемент и (n + 2/2) -й элемент из отсортированного хеш-набора.

Этот метод не будет полезен, если миллиардные числа различны.

Answer 6

Стив Джессоп неверный ответ:

рассмотрим следующие четыре группы:

{2, 4, 6, 8, 10}

{21, 21, 24, 26, 28}

{12, 14, 30, 32, 34}

{16, 18, 36, 38, 40}

Медиана 21, которая содержится во второй группе.

Медиана четырех групп - 6, 24, 30, 36, общая медиана - 27 *

Итак, после первого цикла четыре группы станут:

{6, 8, 10}

{24, 26, 28}

{12, 14, 30}

{16, 18, 36}

21 уже ошибочно отброшен.

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

Answer 7

Давайте сначала разберемся, как найти медиану из n чисел на одной машине: Я в основном использую стратегию разделения.

Проблема: выбор (n, n / 2): Найти n / 2-е число из наименьшего числа.

Вы выбираете средний элемент k и делите данные на 2 подмассива. 1-й содержит все элементы = k.

если sizeof (1st sub-array)> = n / 2, вы знаете, что этот под-массив содержит медиану. Затем вы можете сбросить 2-й суб-массив. Решить эту проблему выбор (размер 1-го подмассива, n / 2) .

В противном случае отбросьте этот 1-й подмассив и решите выбор (2-й подмассив, n / 2 - sizeof (1-й подмассив))

Делать это рекурсивно.

сложность времени составляет O (n) ожидаемое время.

Теперь, если у нас много машин, на каждой итерации нам нужно обрабатывать массив для разделения, мы распределяем массив по разным машинам. Каждая машина обрабатывает свой кусок массива, и отправляет сводку обратно на управляющую машину-концентратор, то есть размер 1-го подмассива и размер 2-го подмассива. Хаб-машины складывают сводки и решают, какой подмассив (1-й или 2-й) обрабатывать. далее и 2-й параметр выбора и отправляет его обратно на каждую машину. и т. д.

Этот алгоритм может быть реализован очень аккуратно с помощью карты уменьшить?

Как это выглядит?

Answer 8

Как насчет этого: - каждый узел может принимать 1 миллиард / 100 номеров. В каждом узле элементы могут быть отсортированы и медиана может быть найдена. Найдите медиану медиан. мы можем, суммируя число чисел, меньших, чем медиана медианы во всех узлах, определить x%: y%, разделенное медианой медианы. Теперь попросите все узлы удалить элементы, которые меньше медианы медиан (на примере 30%: разделение на 70%). Удалено 30% номеров. 70% от 1 миллиарда составляет 700 миллионов. Теперь все узлы, которые удалили менее 3 миллионов узлов, могут отправлять эти дополнительные узлы обратно на главный компьютер. Основной компьютер перераспределяется таким образом, что теперь все узлы будут иметь практически одинаковое количество узлов (7 миллионов). Теперь, когда проблема уменьшена до 700 миллионов чисел ... продолжается, пока у нас не будет меньшего набора, который можно вычислить на одном компе.

Answer 9

Я предлагаю метод для вычисления приблизительно медианы.:) Если эти один миллиард чисел расположены в случайном порядке, я думаю, что я могу выбрать 1/100 или 1/10 из одного миллиарда чисел случайным образом, отсортировать их по 100 машинам, а затем выбрать медиану из них.Или давайте разделим миллиард чисел на 100 частей, пусть каждая машина выберет 1/10 каждой части случайным образом, вычислив медиану из них.После этого у нас есть 100 чисел, и мы можем легче вычислить медиану из 100 чисел.Просто предложение, я не уверен, что это математически правильно.Но я думаю, что вы можете показать результат не очень хорошему в математике менеджеру.

Answer 10

Вы можете использовать метод дерева турниров для нахождения медианы. Мы можем создать дерево с 1000 оставленными узлами так, чтобы каждый листовой узел был массивом. Затем мы проводим n / 2 турниров между различными массивами. Результатом является корень после n / 2 турниров.

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/