Если у вас есть миллиард чисел и сто компьютеров, как лучше всего найти медианное значение этих чисел?
Одно из решений, которое у меня есть:
- Разделите набор поровну между компьютерами.
- Сортируйте их.
- Найдите медианы для каждого набора.
- Отсортируйте наборы по медианам.
- Объедините два набора одновременно от самого низкого до самого высокого медианного значения.
Если у нас есть m1 < m2 < m3 ...
затем сначала слияние, Set1
а Set2
в результирующем наборе мы можем отбросить все числа ниже медианы Set12
(слияния). Таким образом, в любой момент времени у нас есть наборы одинакового размера. Кстати, это нельзя делать параллельно. Любые идеи?
Ответы:
Ах, мой мозг только что заработал, теперь у меня есть разумное предложение. Наверное, слишком поздно, если бы это было интервью, но не беда:
Машину 1 следует называть «управляющей машиной», и для аргументации она либо начинает со всех данных и отправляет их равными пакетами на другие 99 машин, либо данные начинают равномерно распределяться между машинами, и это отправляет 1/99 своих данных каждому из остальных. Перегородки не обязательно должны быть равными, просто закрытые.
Каждая другая машина сортирует свои данные и делает это таким образом, чтобы сначала найти более низкие значения. Так, например, быстрая сортировка, всегда сначала сортируя нижнюю часть раздела [*]. Он записывает свои данные обратно в управляющую машину в порядке возрастания, как только может (используя асинхронный ввод-вывод, чтобы продолжить сортировку, и, возможно, с включенным Нэглом: немного поэкспериментируйте).
Управляющая машина выполняет 99-стороннее объединение данных по мере их поступления, но отбрасывает объединенные данные, просто подсчитывая количество значений, которые он видел. Он вычисляет медиану как среднее из 1/2 миллиардного и 1/2 миллиардного плюс одного значений.
Это страдает от проблемы "самого медленного в стаде". Алгоритм не может завершиться до тех пор, пока сортировочная машина не отправит каждое значение, меньшее медианы. Есть разумная вероятность, что одно из таких значений будет довольно высоким в своем пакете данных. Таким образом, как только начальное разбиение данных завершено, расчетное время работы представляет собой комбинацию времени на сортировку 1/99 данных и их отправку обратно в управляющий компьютер и время, в течение которого элемент управления считывает 1/2 данных. , «Комбинация» находится где-то между максимумом и суммой этих времен, вероятно, близкой к максимуму.
Я считаю, что для того, чтобы отправлять данные по сети быстрее, чем их сортировать (не говоря уже о простом выборе медианы), это должна быть чертовски быстрая сеть. Возможно, будет лучше, если можно будет предположить, что сеть работает мгновенно, например, если у вас есть 100 ядер с равным доступом к оперативной памяти, содержащей данные.
Поскольку сетевой ввод-вывод, вероятно, будет ограниченным, вы можете использовать некоторые уловки, по крайней мере, для данных, возвращающихся на управляющую машину. Например, вместо отправки «1,2,3, .. 100», возможно, сортировочная машина может отправить сообщение, означающее «100 значений меньше 101». Затем управляющая машина могла бы выполнить модифицированное слияние, в котором она находит наименьшее из всех этих верхних значений, а затем сообщает всем сортировочным машинам, что это было, чтобы они могли (а) сообщить управляющей машине, как много значений для «подсчета» ниже этого значения и (б) возобновить отправку отсортированных данных с этой точки.
В более общем плане, вероятно, существует умная игра в угадывание «вызов-ответ», в которую управляющая машина может играть с 99 сортировочными машинами.
Однако это включает в себя круговые обходы между машинами, чего избегает моя более простая первая версия. Я действительно не знаю, как вслепую оценить их относительную производительность, и, поскольку компромиссы сложны, я полагаю, что есть гораздо лучшие решения, чем все, что я придумаю себе, если предположить, что это когда-либо будет реальной проблемой.
[*] доступный стек разрешен - ваш выбор, какую часть сделать первой, ограничен, если у вас нет O (N) дополнительного места. Но если у вас достаточно дополнительного места, вы можете выбрать, а если у вас недостаточно места, вы можете, по крайней мере, использовать то, что вам нужно, чтобы срезать некоторые углы, сделав сначала небольшую часть для первых нескольких разделов.
источник
источник
time
команде, примененной ко всему конвейеру, потребовалосьreal=36m24s
(«время настенных часов»),user=113m15s
(«параллельное время», добавлены все ядра). Самая длинная команда, намного опережающая другие, былаsort
, даже если она передавалась на мои четыре ядра на 100%. Потребление оперативной памяти было очень приемлемым.Я не хочу быть здесь противником, но я не верю, что сортировка требуется, и я думаю, что любой алгоритм, включающий сортировку чисел на миллиард / 100, будет медленным. Рассмотрим алгоритм на одном компьютере.
1) Выберите случайным образом 1000 значений из миллиарда и используйте их, чтобы получить представление о распределении чисел, особенно о диапазоне.
2) Вместо сортировки значений распределите их по сегментам на основе только что рассчитанного распределения. Количество ведер выбирается таким образом, чтобы компьютер мог с ними справляться, но в остальном оно должно быть максимально большим. Диапазоны сегментов должны быть такими, чтобы в каждом сегменте было примерно одинаковое количество значений (это не критично для алгоритма, но помогает повысить эффективность. 100 000 сегментов могут быть подходящими). Обратите внимание на количество значений в каждом сегменте. Это O (n) процесс.
3) Выясните, в каком диапазоне ковша лежит медиана. Это можно сделать, просто проверив общее количество в каждой корзине.
4) Найдите фактическую медиану, изучив значения в этом сегменте. Вы можете использовать здесь сортировку, если хотите, поскольку вы сортируете только 10 000 чисел. Если количество значений в этом сегменте велико, вы можете снова использовать этот алгоритм, пока у вас не будет достаточно маленького числа для сортировки.
Этот подход тривиально распараллеливается путем разделения значений между компьютерами. Каждый компьютер сообщает итоги в каждом сегменте на «управляющий» компьютер, который выполняет шаг 3. Для шага 4 каждый компьютер отправляет (отсортированные) значения в соответствующем сегменте на управляющий компьютер (вы также можете выполнять оба этих алгоритма параллельно, но, наверное, того не стоит).
Общий процесс составляет O (n), поскольку шаги 3 и 4 тривиальны при условии, что количество сегментов достаточно велико.
источник
Один миллиард - довольно скучная задача для современного компьютера. Мы говорим о 4 ГБ 4-х байтовых целых ... 4 ГБ ... это оперативная память некоторых смартфонов.
Вывод на моей машине:
Таким образом, это завершается на моей машине менее чем за две минуты (1:43 из которых 0:10 - для генерации случайных чисел) с использованием одного ядра и даже полной сортировки. Ничего особенного.
Это, безусловно, интересная задача для больших наборов чисел. Я просто хочу отметить здесь: один миллиард - это арахис. Так что подумайте дважды, прежде чем начинать бросать сложные решения на удивительно простые задачи;)
источник
(numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2
еслиnumbers.length
четное, иnumbers[numbers.length / 2]
только еслиnumbers.length
нечетное.Оценка порядковых статистик , как медианы и 99 - й процентиль может быть эффективно распределена с алгоритмами , такими как трет-дайджест или Q-дайджест .
Используя любой алгоритм, каждый узел создает дайджест, который представляет распределение значений, хранящихся локально. Дайджесты собираются в одном узле, объединяются (фактически суммируя распределения), и затем можно найти медианное значение или любой другой процентиль.
Такой подход используется в elasticsearch и, предположительно, BigQuery ( исходя из описания функции QUANTILES).
источник
Медиана для этого набора чисел
2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89, 97
67.
Медиана для этого набора чисел
2, 3, 5, 7, 11, 13, 67, 71, 73, 79, 83, 89
40 лет.
Предполагая, что вопрос был о 1000000000 целых чисел (x), где 0> = x <= 2 147 483 647 и что OP искал (элемент (499 999 999) + элемент (500 000 000)) / 2 (если числа были отсортированы). Также предполагается, что все 100 компьютеров были равны.
используя мой ноутбук и GigE ...
Я обнаружил, что мой ноутбук может отсортировать 10 000 000 Int32 за 1,3 секунды. Таким образом, грубая оценка будет такой, что сортировка миллиарда чисел займет 100 x 1,3 секунды (2 минуты 10 секунд);).
Расчетная односторонняя передача файла размером 40 МБ по гигабитному Ethernet составляет 0,32 секунды. Это означает, что отсортированные результаты со всех компьютеров будут возвращены примерно через 32 секунды (компьютер 99 получил свой файл только через 30 секунд после запуска). Оттуда не займет много времени отбросить самые низкие 499 999 998 чисел, сложить следующие 2 и разделить на 2.
источник
a*(1e7)log(1e7) = 1.3sec
=>a = 1.6e-9sec
=>a*(1e9)log(1e9) ~ 167sec
, так что ваша оценка не такая уж плохая.Это может удивить людей, но если числа являются достаточно маленькими целыми числами, чтобы поместиться внутри 32-битного (или меньшего) размера - просто выполните сортировку по корзине! Требуется только 16 ГБ оперативной памяти для любого количества 32-битных int и выполняется за O (n), что должно превосходить любые распределенные системы для разумного n, например миллиарда.
После того, как у вас есть отсортированный список, тривиально выбрать медиану. На самом деле, вам не нужно создавать отсортированный список, это должно сделать только просмотр сегментов.
Ниже показана простая реализация. Работает только для 16-битных целых чисел, но расширение до 32-битных должно быть простым.
Использование текстового файла с миллиардом (10 9 ) чисел и выполнение
time
примерно такдает время работы на моей машине 1 мин. 49 293 с. Большую часть времени, вероятно, также занимает ввод-вывод диска.
источник
Как ни странно, я думаю, что если у вас достаточно компьютеров, вам лучше выполнять сортировку, чем использовать
O(n)
алгоритмы поиска медианы. (Если только ваши ядра не очень, очень медленные, я бы просто использовал один и использовалO(n)
алгоритм поиска медианы только для чисел 1e9; однако, если бы у вас было 1e12, это могло бы быть менее практичным.)В любом случае, давайте предположим, что у нас есть больше, чем log n ядер, чтобы справиться с этой проблемой, и нас не волнует энергопотребление, мы просто быстро получаем ответ. Далее предположим, что это SMP-машина со всеми данными, уже загруженными в память. (К этому типу относятся, например, 32-ядерные машины Sun).
Один поток вслепую разрезает список на части равного размера и приказывает другим M потокам отсортировать их. Эти нити со
(n/M) log (n/M)
временем старательно это делают . Затем они возвращают не только свои медианы, но, скажем, также свои 25-й и 75-й процентили (наихудшие извращенные случаи лучше, если вы выберете немного другие числа). Теперь у вас есть 4 миллиона диапазонов данных. Затем вы сортируете эти диапазоны и двигаетесь вверх по списку, пока не найдете такое число, что, если вы выбросите каждый диапазон, который меньше или содержит это число, вы выбросите половину ваших данных. Это ваша нижняя граница медианы. Сделайте то же самое с верхней границей. Это требует чего-то вродеM log M
времени, и все ядра должны его ждать, так что это действительно напрасная трата времени.M^2 log M
потенциальное время. Теперь у вас есть единственный поток, который сообщает другим, что нужно выбросить все данные за пределы диапазона (вы должны выбрасывать около половины на каждом проходе) и повторять - это тривиально быстрая операция, поскольку данные уже отсортированы. Вам не придется повторять это чаще, чемlog(n/M)
раз, прежде чем будет быстрее просто захватить оставшиеся данные и использовать для них стандартныйO(n)
поиск медианы.Итак, общая сложность - это что-то вроде
O((n/M) log (n/M) + M^2 log M log (n/M))
. Таким образом, это быстрее, чемO(n)
медианная сортировка на одном ядре ifM >> log(n/M)
иM^3 log M < n
, что верно для описанного вами сценария.Я думаю, что это действительно плохая идея, учитывая, насколько она неэффективна, но она быстрее.
источник
n
иM
являются переменными, которые могут масштабироваться произвольно, поэтому один включает оба. В частности, я постулировал этоM
>log n
, что означает, что если вам важно, чтобы это было,n log n
а не простоn
, вы также должны заботиться о немM
.Это можно сделать быстрее, чем алгоритм проголосовал (n log n)
- Алгоритм распределенного выбора статистики порядка - O (n)
Упростите задачу до исходной задачи поиска k-го числа в несортированном массиве.
- Подсчет гистограммы сортировки O (n)
Вы должны предположить некоторые свойства диапазона чисел - может ли диапазон поместиться в памяти? - Внешняя сортировка слиянием - O (n log n) - описано выше.
Вы в основном сортируете числа на первом проходе, а затем находите медиану на втором.
- Если что-либо известно о распределении чисел, могут быть созданы другие алгоритмы.
Для получения дополнительных сведений и реализации см.
Http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html.
источник
Одного компьютера более чем достаточно для решения проблемы.
Но предположим, что есть 100 компьютеров. Единственное сложное, что вам нужно сделать, - это отсортировать список. Разделите его на 100 частей, отправьте по одной части на каждый компьютер, пусть они там будут отсортированы, а затем объедините части.
Затем возьмите число из середины отсортированного списка (т.е. с индексом 5 000 000 000).
источник
Это зависит от ваших данных. В худшем случае это равномерно распределенные числа.
В этом случае вы можете найти медиану за время 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. Обратите внимание, что верх и низ имеют одинаковый размер.
Наполняем ведра числами, подсчитываем сколько попадает в каждое, максимальное и минимальное
Среднее значение попадает в среднее ведро, остальное мы игнорируем
Мы создаем 3 сегмента: 4, 5-6, 7. Низкий начнется со счета 5 и максимум 3, а высокий - минимум 8 и счет 5.
Для каждого числа мы подсчитываем, сколько из них попадает в нижнюю и верхнюю корзины, максимальное и минимальное количество, и оставляем среднюю корзину.
Теперь мы можем вычислить медиану напрямую: у нас есть такая ситуация
так что медиана равна 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), потому что вам действительно нужно посчитать элементы хотя бы один раз.
источник
O(n log n)
в таком случае было бы так. Имеет ли это смысл ? Кстати, мне нравится твоя идеяo(n)+o(n/3)+o(n/9)+...
чего ещеo(n)
и нетo(n log n)
.o(n)
в этом случае, с наивным разбиением.Более простой способ - иметь взвешенные числа.
источник
Разделите 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 минут, чтобы разработать более сложный алгоритм, у меня есть преимущество в 14 минут 45 секунд, чтобы закодировать мое решение и запустить его.
Но я открыто признаю, что это все утверждения, я ничего не измерял.
источник
Это можно сделать на узлах, используя данные, которые не отсортированы по узлам (например, из файлов журнала), следующим образом.
Есть 1 родительский узел и 99 дочерних узлов. Дочерние узлы имеют два вызова API:
Родительский узел вызывает stats () для всех дочерних узлов, отмечая минимум и максимум всех узлов.
Теперь бинарный поиск можно проводить следующим образом:
Есть 1 родительский узел и 99 дочерних узлов. Дочерние узлы имеют два вызова API:
Родительский узел вызывает stats () для всех дочерних узлов, отмечая минимум и максимум всех узлов.
Теперь бинарный поиск можно проводить следующим образом:
Если stats () и compare () могут быть предварительно рассчитаны с помощью сортировки O (N / Mlogn / M), то предварительное вычисление O (N / M) со сложностью памяти O (N) для предварительного расчет. Затем вы можете выполнить compare () за постоянное время, поэтому все (включая предварительные вычисления) будет выполняться за O (N / MlogN / M) + O (logN)
Сообщите мне, если я ошибся!
источник
Как насчет этого: - каждый узел может принимать 1 миллиард / 100 номеров. В каждом узле можно отсортировать элементы и найти медиану. Найдите медиану медиан. мы можем, суммируя количество чисел, меньших медианы-медианы на всех узлах, определить x%: y% -ное разделение, которое составляет медиана-из-медианы. Теперь попросите все узлы удалить элементы меньше медианы медиан (например, 30%: 70% -ное разбиение). 30% чисел удаляются. 70% от 1 миллиарда - это 700 миллионов. Теперь все узлы, которые удалили менее 3 миллионов узлов, могут отправить эти дополнительные узлы обратно на главный компьютер. Главный компьютер перераспределяется таким образом, что теперь все узлы будут иметь почти равное количество узлов (7 миллионов). Теперь, когда проблема уменьшена до 700 миллионов чисел ... продолжается до тех пор, пока мы не получим меньший набор, который можно вычислить за одну операцию.
источник
Давайте сначала разберемся, как найти медиану n чисел на одной машине: я в основном использую стратегию разделения.
Задача: выбор (n, n / 2): найти n / 2-е число из наименьшего числа.
Вы выбираете, скажем, средний элемент k и разделяете данные на 2 подмассива. 1-й содержит все элементы <k, а 2-й содержит все элементы> = k.
если sizeof (1-й подмассив)> = n / 2, вы знаете, что этот подмассив содержит медиану. Затем можно скинуть второй подмассив. Решите эту проблему выбором (размер 1-го подмассива, n / 2) .
В противном случае отбросьте этот 1-й подмассив и решите выбор (2-й подмассив, n / 2 - sizeof (1-й подмассив))
Делайте это рекурсивно.
временная сложность - ожидаемое время O (n).
Теперь, если у нас много машин, на каждой итерации мы должны обрабатывать массив для разделения, мы распределяем массив на разные машины. Каждая машина обрабатывает свой фрагмент массива и отправляет сводку на управляющую машину концентратора, то есть размер 1-го подмассива и размер 2-го подмассива. Хаб-машины суммируют итоги и решают, какой подмассив (1-й или 2-й) обрабатывать дальше, и 2-й параметр выбора и отправляет его обратно на каждую машину. и так далее.
Этот алгоритм можно очень аккуратно реализовать с помощью map reduce?
Как это выглядит?
источник
Думаю, ответ Стива Джессопа будет самым быстрым.
Если узким местом является размер передаваемых по сети данных , существует другой подход.
источник
Я бы сделал так:
вначале все 100 работают, чтобы найти наибольшее и наименьшее число; у каждого компьютера есть своя часть базы данных / файла, которую он запрашивает;
когда обнаруживаются наибольшее и наименьшее числа, один компьютер считывает данные и равномерно распределяет каждое число среди остальных 99; числа распределены равными интервалами; (один может принимать от -100 миллионов до 0, другой - от 0 до 100 миллионов и т. д.);
Получая номера, каждый из 99 компьютеров их уже сортирует;
Затем легко найти медиану ... Посмотрите, сколько чисел есть на каждом компьютере, сложите их все (сумму количества чисел, а не сами числа), разделите на 2; вычислить, в каком компьютере стоит номер, а на каком индексе;
:) вуаля
PS Похоже, здесь много путаницы; МЕДИАНА - ЧИСЛО В СРЕДНЕМ СОРТИРОВАННОМ СПИСКЕ НОМЕРОВ!
источник
Вы можете использовать метод турнирного дерева для поиска медианы. Мы можем создать дерево с 1000 конечными узлами, так что каждый конечный узел представляет собой массив. Затем мы проводим n / 2 турниров между различными массивами. Результатом является значение в корне после n / 2 турниров.
http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/
источник
Если числа не различны и принадлежат только определенному диапазону, то есть они повторяются, тогда мне приходит в голову простое решение: распределить числа между 99 машинами поровну и оставить одну машину главной. Теперь каждая машина выполняет итерацию по заданным числам и сохраняет количество каждого числа в хеш-наборе. Каждый раз, когда число повторяется в наборе чисел, назначенных этому конкретному компьютеру, он обновляет его счетчик в наборе хешей.
Затем все машины возвращают свой хэш-набор на главную машину. Главный компьютер комбинирует хеш-наборы, суммируя количество тех же ключей, найденных в хэш-наборе. Например, в хеш-наборе машины №1 была запись ("1", 7), а в хеш-наборе машины №2 была запись ("1", 9), поэтому главная машина при расчесывании хеш-наборов делает запись («1», 16) и так далее.
После объединения хэш-наборов просто отсортируйте ключи, и теперь вы можете легко найти (n / 2) -й элемент и (n + 2/2) -й элемент из отсортированного хеш-набора.
Этот метод не принесет пользы, если миллиард чисел различны.
источник
Что ж, предположим, вы знаете, что количество различных целых чисел составляет (скажем) 4 миллиарда, затем вы можете разделить их на сегменты по 64 КБ и получить распределенное количество для каждого сегмента с каждой машины в кластере (100 компьютеров). Объедините все эти цифры. Теперь найдите сегмент, в котором есть медиана, и на этот раз запросите сегменты только для 64k элементов, которые будут лежать в вашем целевом сегменте. Для этого требуется O (1) (а именно 2) запросов к вашему «кластеру». : D
источник
Моя копейка стоит, после всего того, о чем уже говорили другие:
Нахождение медианы на одном компьютере - O (N): https://en.wikipedia.org/wiki/Selection_algorithm .
Отправка N номеров на 100 машин тоже O (N). Итак, чтобы сделать использование 100 машин интересным, либо связь должна быть относительно быстрой, либо N настолько велико, что одна машина не может справиться с этим, пока N / 100 выполнимо, либо мы просто хотим рассмотреть математическую задачу, не беспокоясь о передача данных.
Поэтому я предполагаю, что в разумных пределах мы можем отправлять / распределять числа, не влияя на анализ эффективности.
Рассмотрим тогда следующий подход, в котором одна машина назначается «ведущей» для некоторой общей обработки. Это будет сравнительно быстро, поэтому «мастер» также участвует в общих задачах, которые выполняет каждая машина.
Время-сложность:
источник
Разделите 1 миллиард чисел на 100 машин. На каждой машине будет 10 ^ 7 номеров.
Для каждого входящего номера на машину сохраните номер в частотной карте, число -> счетчик. Также сохраните минимальное число в каждой машине.
Найдите медиану на каждой машине: начиная с минимального числа на каждой машине, просуммируйте подсчеты, пока не будет достигнут средний индекс. Медиана на каждой машине будет прибл. меньше и больше 5 * 10 ^ 6 чисел.
Найдите медиану всех медиан, которая будет меньше или больше прибл. 50 * 10 ^ 7 чисел, что является медианой 1 миллиарда чисел.
Теперь некоторая оптимизация 2-го шага: вместо сохранения в частотной карте сохраните счетчики в переменном битовом массиве. Например: Допустим, начиная с минимального числа в машине, это подсчет частоты:
Вышеупомянутое можно сохранить в битовом массиве как:
Обратите внимание, что в целом это будет стоить около 10 ^ 7 бит для каждой машины, поскольку каждая машина обрабатывает только 10 ^ 7 чисел. 10 ^ 7 бит = 1,25 * 10 ^ 6 байт, что составляет 1,25 МБ
Таким образом, при описанном выше подходе каждой машине потребуется 1,25 МБ пространства для вычисления локальной медианы. А медиана медиан может быть вычислена из этих 100 локальных медиан, в результате чего получится 1 миллиард чисел.
источник
Я предлагаю метод приблизительного вычисления медианы. :) Если эти миллиардные числа расположены в случайном порядке, я думаю, что я могу выбрать 1/100 или 1/10 из одного миллиарда случайным образом, отсортировать их с помощью машины 100, а затем выбрать медиану из них. Или давайте разделим миллиард чисел на 100 частей, пусть каждая машина случайным образом выберет 1/10 каждой части и вычислит их медианное значение. После этого у нас будет 100 чисел, и мы сможем легче вычислить медиану из 100 чисел. Просто предложение, я не уверен, правильно ли оно математически. Но я думаю, вы можете показать результат не очень разбирающемуся в математике менеджеру.
источник
Ответ Стива Джессопа неверен:
рассмотрите следующие четыре группы:
{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 уже ошибочно выброшен.
Этот алгоритм поддерживает только случай, когда есть две группы.
источник