Вычислите медиану миллиарда чисел

sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"

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

Машину 1 следует называть «управляющей машиной», и ради аргументации она либо начинает со всех данных, либо отправляет их равными посылками в остальные 99 машин, иначе данные начинают равномерно распределяться между машинами, и он отправляет 1/99 своих данных каждой из остальных. Перегородки не обязательно должны быть равными, просто закрытые.

Машины друг друга сортируют свои данные и делают это таким образом, чтобы сначала находить более низкие значения. Так, например, быстрая сортировка, всегда сначала сортируя нижнюю часть раздела [*]. Он записывает свои данные обратно в управляющую машину в порядке возрастания, как только может (используя асинхронный ввод-вывод, чтобы продолжить сортировку, и, возможно, с включенным Нэглом: немного поэкспериментируйте).

Управляющая машина выполняет 99-стороннее объединение данных по мере их поступления, но отбрасывает объединенные данные, просто сохраняя подсчет количества значений, которые он видел. Медиана вычисляется как среднее из 1/2 миллиардного и 1/2 миллиардного плюс один значений.

Это проблема "самого медленного в стаде". Алгоритм не может завершиться до тех пор, пока сортировочная машина не отправит каждое значение меньше медианы. Есть разумная вероятность, что одно из таких значений будет довольно высоким в своем пакете данных. Таким образом, как только начальное разбиение данных завершено, расчетное время выполнения представляет собой комбинацию времени на сортировку 1/99 данных и их отправку обратно в управляющий компьютер и время, в течение которого элемент управления считывает 1/2 данных. . «Комбинация» находится где-то между максимумом и суммой этих времен, вероятно, близкой к максимуму.

Я считаю, что для того, чтобы отправлять данные по сети быстрее, чем их сортировка (не говоря уже о простом выборе медианы), она должна быть чертовски быстрой сетью. Возможно, будет лучше, если можно будет предположить, что сеть работает мгновенно, например, если у вас есть 100 ядер с равным доступом к оперативной памяти, содержащей данные.

Поскольку сетевой ввод-вывод, скорее всего, будет ограниченным, вы можете использовать некоторые уловки, по крайней мере, для данных, возвращающихся на управляющую машину. Например, вместо отправки «1,2,3, .. 100» сортировочная машина могла бы отправить сообщение, означающее «100 значений меньше 101». Затем управляющая машина могла бы выполнить модифицированное слияние, в котором она находит наименьшее из всех этих верхних значений, а затем сообщает всем сортировочным машинам, что это было, чтобы они могли (а) сообщить управляющей машине, как много значений для «подсчета» ниже этого значения и (б) возобновить отправку отсортированных данных с этой точки.

В более общем плане, вероятно, существует умная игра в угадывание «вызов-ответ», в которую управляющая машина может играть с 99 сортировочными машинами.

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

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

Ненавижу быть здесь противником, но я не верю, что сортировка требуется, и я думаю, что любой алгоритм, включающий сортировку числа на миллиард / 100, будет медленным. Рассмотрим алгоритм на одном компьютере.

1) Выберите случайным образом 1000 значений из миллиарда и используйте их, чтобы получить представление о распределении чисел, особенно о диапазоне.

2) Вместо сортировки значений распределите их по сегментам на основе только что рассчитанного распределения. Количество ведер выбирается таким образом, чтобы компьютер мог с ними справляться эффективно, но в остальном оно должно быть настолько большим, насколько это удобно. Диапазоны сегментов должны быть такими, чтобы в каждый сегмент входило примерно одинаковое количество значений (это не критично для алгоритма, но способствует повышению эффективности. 100 000 сегментов могут быть подходящими). Обратите внимание на количество значений в каждом сегменте. Это процесс O (n).

3) Выясните, в каком диапазоне сегментов лежит медиана. Это можно сделать, просто изучив общее количество в каждой корзине.

4) Найдите фактическую медиану, изучив значения в этом сегменте. Вы можете использовать здесь сортировку, если хотите, поскольку вы сортируете только 10 000 чисел. Если количество значений в этом сегменте велико, вы можете снова использовать этот алгоритм, пока у вас не будет достаточно маленького числа для сортировки.

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

Общий процесс составляет O (n), поскольку шаги 3 и 4 тривиальны, при условии, что количество сегментов достаточно велико.

Как ни странно, я думаю, что если у вас достаточно компьютеров, вам лучше сортировать, чем использовать 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) на одном ядре, если M >> log (n / M) и M ^ 3 log M ], что верно для описанного вами сценария.