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

127

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

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

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

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

Anony
источник
3
@John Boker: на самом деле проблема состоит из двух подзадач: 1) отсортировать список и 2) получить элемент с индексом 5'000'000'000. Я не верю, что числа отсортированы.
Роман
3
@Roman: проблема не обязательно должна состоять из двух описанных вами подзадач, например, быстрого выбора. Но quickselect не распараллеливает, по крайней мере, тривиально. И, конечно, вы правы, если числа предварительно отсортированы, это довольно бессмысленный вопрос.
Стив Джессоп,
5
@fmsf: Я не думаю, что какая-либо англоязычная страна использует длинный миллиард английского языка для каких-либо официальных целей. Например, здесь, в Великобритании, мы прекратили его использовать в 1974 году. Я считаю, что использование «миллиарда» для обозначения миллиона миллионов в английском языке - это извращенный вопрос с подвохом, а не «настоящий миллиард» вообще. Конечно, по-французски это было бы совсем другое дело, но вопрос не во французском.
Стив Джессоп,
5
Сортировать не нужно! en.wikipedia.org/wiki/…
glebm 03
2
1 миллиард чисел - это всего лишь несколько гигабайт данных, для решения этой задачи не нужны ни несколько компьютеров, ни сложные алгоритмы. Не усложняйте слишком много.
user626528

Ответы:

54

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

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

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

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

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

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

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

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

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

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

Стив Джессоп
источник
Пожалуйста, поправьте меня, если я ошибаюсь, почему вы выполняете 99-стороннее слияние данных, поскольку они поступают только для того, чтобы позже их удалить. Вместо этого достаточно вести подсчет чисел по мере их поступления?
sreeprasad
4
@SREEPRASADGOVINDANKUTTY: повторяющийся шаг - отбросить наименьшее значение из всех 99 кандидатов и увеличить счетчик. Совершенно бесполезно просто вести подсчет всех входящих значений без этого 99-этапного шага слияния. Если вы не сравниваете их по мере поступления, вы не знаете, что отбрасываемое вами значение ниже медианы.
Стив Джессоп,
Но разве нет небольшого шанса, что какой-либо из этих разделов содержит только числа, превышающие медианное значение, и, следовательно, любой более низкий раздел, который он возвращает, будет выше, чем медиана, но, поскольку элемент управления не знает этого, он отбрасывает их как меньшие, чем медиана и провал ...?
Gullydwarf 05
@Gullydwarf: многостороннее слияние отбрасывает только наименьшее из 99 значений, которые у него есть, каждое из которых является наименьшим оставшимся значением с одной из других машин. Если одно из разделов полностью больше медианы, то оно не станет наименьшим из этих 99 значений до тех пор, пока не пройдет медиана (на этом мы закончим). Так что не выбрасывается.
Стив Джессоп,
52
sort -g numbers | head -n 500000001 | tail -n 2 | dc -e "1 k ? ? + 2 / p"
DrPizza
источник
2
РЖУНИМАГУ. Это действительно работает или убийца OOM уничтожит его до того, как оно завершится? (на любом разумном компьютере)
Исак Саво
5
Стоит сделать. sort знает, как выполнить сортировку вне ядра, поэтому у него не будет нехватки памяти.
DrPizza
6
@Zagfai Не думаю, что это займет слишком много времени; миллиард чисел составляет всего 4 ГБ для 32-разрядных целых чисел / чисел с плавающей запятой, 8 ГБ для 64-разрядных целых чисел / чисел с плавающей запятой. Ни то, ни другое не кажется слишком утомительным.
DrPizza 03 авг.15,
13
Только что пробовал на Intel i5-4200M @ 3,1 ГГц (4 ядра). Согласно timeкоманде, примененной ко всему конвейеру, потребовалось real=36m24s(«время настенных часов»), user=113m15s («параллельное время», добавлены все ядра). Самая длинная команда, намного опережающая другие, была sort, даже если она передавалась на мои четыре ядра на 100%. Потребление оперативной памяти было очень приемлемым.
Морган Тувери Квиллинг,
12
Затем поработайте на 100 компьютерах, чтобы вы могли быть в 100 раз увереннее в правильности результата :)
dos
27

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

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

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

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

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

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

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

DJClayworth
источник
1
Я думаю, что это что-то среднее между медианой медиан и алгоритмами быстрого выбора. en.wikipedia.org/wiki/Selection_algorithm
Димат 09
На шаге 4 сегменты могут содержать не только 10 000. Может случиться так, что распределение смещено к середине, в котором оно может содержать, скажем, 80% данных, что по-прежнему огромно.
половина
Отредактировано с учетом этого.
DJClayworth
4
Производительность этого алгоритма не равна O (n): большинство чисел может попасть в «среднее» ведро, и он может работать так же плохо, как сортировка всего.
Sklivvz
1
@WULF Отличный вопрос. Это ключ к алгоритму, и шаг 1 обращается к нему. Выборка чисел для установления распределения - лучшее, что я придумал.
DJClayworth
12

Один миллиард - довольно скучная задача для современного компьютера. Мы говорим о 4 ГБ 4-х байтовых целых ... 4 ГБ ... это оперативная память некоторых смартфонов.

public class Median {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int[] numbers = new int[1_000_000_000];

        System.out.println("created array after " +  (System.currentTimeMillis() - start) + " ms");

        Random rand = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = rand.nextInt();
        }

        System.out.println("initialized array after " + (System.currentTimeMillis() - start) + " ms");

        Arrays.sort(numbers);

        System.out.println("sorted array after " + (System.currentTimeMillis() - start) + " ms");

        if (numbers.length % 2 == 1) {
            System.out.println("median = " + numbers[numbers.length / 2 - 1]);
        } else {
            int m1 = numbers[numbers.length / 2 - 1];
            int m2 = numbers[numbers.length / 2];
            double m = ((long) m1 + m2) / 2.0;
            System.out.println("median = " + new DecimalFormat("#.#").format(m));
        }
}

Вывод на моей машине:

created array after 518 ms
initialized array after 10177 ms
sorted array after 102936 ms
median = 19196

Таким образом, это завершается на моей машине менее чем за две минуты (1:43 из которых 0:10 - для генерации случайных чисел) с использованием одного ядра и даже полной сортировки. Ничего особенного.

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

sfussenegger
источник
это то, что я сказал в своем ответе здесь :-) stackoverflow.com/a/31819222/363437
vidstige
1
@vidstige Я, честно говоря, не читал, но ты прав. мой ответ, безусловно, более практический, хотя люди, кажется, ценят его немного больше;)
sfussenegger
Но это не медиана, медиана - (numbers[numbers.length / 2]+numbers[numbers.length / 2+1])/2если numbers.lengthчетное, и numbers[numbers.length / 2]только если numbers.lengthнечетное.
Sklivvz 05
@Sklivvz правильно, но это не должно заметно влиять на время, необходимое для вычисления медианы.
vidstige 05
1
@Sklivvz ты конечно прав. Я только что обновил расчет медианы. Однако это не меняет остальной части ответа.
sfussenegger 05
10

Оценка порядковых статистик , как медианы и 99 - й процентиль может быть эффективно распределена с алгоритмами , такими как трет-дайджест или Q-дайджест .

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

Такой подход используется в elasticsearch и, предположительно, BigQuery ( исходя из описания функции QUANTILES).

Ричард Пул
источник
5

Медиана для этого набора чисел

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.

dbasnett
источник
3
Недействительный комментарий избирателя? Это помогло бы мне понять, как я могу добиться большего.
dbasnett 01
5
Я не проигрываю, но сортировка миллиарда чисел не займет в 100 раз больше, чем сортировка 10 миллионов, потому что сложность сортировки списка в наихудшем случае составляет O (n log n). Сортировка также на порядки медленнее, когда у вас заканчивается память и вам нужно начать сортировку на диске.
Ричард Пул,
Я думаю, вы на правильном пути; Если целью является получение как можно более быстрого ответа один раз, сортировка на нескольких машинах может быть хорошей идеей. Но если целью является наименьшее среднее время, каждая машина, выполняющая собственный поиск, имеет больше смысла.
Чарли
Предполагая, что у них одинаковый коэффициент (которого, вероятно, нет из-за проблем с памятью), then a*(1e7)log(1e7) = 1.3sec=> a = 1.6e-9sec => a*(1e9)log(1e9) ~ 167sec, так что ваша оценка не такая уж плохая.
bcorso 05
Ваши оценки слишком приблизительны. Во-первых, некоторые алгоритмы сортировки идут как o (n ^ 2) в худшем сценарии (например, обычно используемой быстрой сортировки). Во-вторых, вы выбрали тестовый набор данных размером примерно с ваш кеш L2. Это искажает результаты. В-третьих, вы (как и многие другие респонденты) предполагаете, что «число» означает «целое число». Это может означать float, double или decimal, которые имеют очень разные характеристики производительности.
Sklivvz
5

Это может удивить людей, но если числа являются достаточно маленькими целыми числами, чтобы поместиться внутри 32-битного (или меньшего) размера - просто выполните сортировку по корзине! Требуется только 16 ГБ оперативной памяти для любого количества 32-битных int и выполняется за O (n), что должно превосходить любые распределенные системы для разумного n, например миллиарда.

После того, как у вас есть отсортированный список, тривиально выбрать медиану. На самом деле, вам не нужно создавать отсортированный список, это должно сделать только просмотр сегментов.

Ниже показана простая реализация. Работает только для 16-битных целых чисел, но расширение до 32-битных должно быть простым.

#include <stdio.h>
#include <string.h>

int main()
{
    unsigned short buckets[65536];
    int input, n=0, count=0, i;

    // calculate buckets
    memset(buckets, 0, sizeof(buckets));
    while (scanf("%d", &input) != EOF)
    {
        buckets[input & 0xffff]++;
        n++;
    }

    // find median 
    while (count <= n/2)
    {
        count += buckets[i++];
    }

    printf("median: %d\n", i-1);

    return 0;
}

Использование текстового файла с миллиардом (10 9 ) чисел и выполнение timeпримерно так

time ./median < billion

дает время работы на моей машине 1 мин. 49 293 с. Большую часть времени, вероятно, также занимает ввод-вывод диска.

vidstige
источник
Это на самом деле не отвечает на вопрос и основывается на предположениях. Например, вы даже не знаете, что это целые числа.
Sklivvz
Каким образом это не отвечает на вопрос? И да, мой ответ предполагает, что числа целые. Я попытался четко изложить свои предположения.
vidstige 05
Похоже, вы не утверждаете, что наличие целых чисел является предположением, и не говорите, как использовать 100 компьютеров, о которых спрашивает ОП. Вы можете рассчитать медианное значение для одного узла, но это не лучшее решение, если вы не покажете почему. Кроме того, сортировка по основанию не является o (n), если количество цифр меняется, что в этом случае, безусловно, имеет значение, согласно en.wikipedia.org/wiki/Radix_sort#Efficiency , это o (n log n)
Sklivvz
Я начинаю с того, что говорю: «Если целые числа достаточно малы, чтобы поместиться в 32-битное целое число » ... Сортировка по основанию равна O (n) для постоянного размера слова w, как описано в большой ясности в опубликованной вами ссылке. Здесь я предполагаю, что размер слова постоянный
vidstige 05
1
То, что вы делаете с 99 другими компьютерами, не имеет отношения к этому ответу. Вы можете сложить их друг на друга, чтобы сформировать пирамиду, или сжечь. Или просто игнорируйте их.
vidstige 05
3

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

Я думаю, что это действительно плохая идея, учитывая, насколько она неэффективна, но она быстрее.

Рекс Керр
источник
o (n / M log (n / M)), буквально, o (n log n), потому что o (n / M log (n / M)) = 1 / M o (n (log n - log M) ) = о (п войти п). Вы не можете действительно сравнивать это с o (n) таким образом, поскольку «o» в основном означает «пропорционально для большого очень n с некоторой неопределенной константой». Если вы не знаете эти константы, вы не можете сравнивать, однако для достаточно большого N константы не являются доминирующими. Для меньших чисел все ставки отключены, o (1) легко может быть медленнее, чем o (n!).
Sklivvz
@Sklivvz - nи Mявляются переменными, которые могут масштабироваться произвольно, поэтому один включает оба. В частности, я постулировал это M> log n, что означает, что если вам важно, чтобы это было, n log nа не просто n, вы также должны заботиться о нем M.
Рекс Керр,
3

Это можно сделать быстрее, чем алгоритм проголосовал (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.

user1712376
источник
2

Одного компьютера более чем достаточно для решения проблемы.

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

Затем возьмите число из середины отсортированного списка (т.е. с индексом 5 000 000 000).

Римский
источник
3
В любом случае, теперь моя репутация довольно круглая :)
Роман
Слияние - это в лучшем случае O (n), и вы можете найти медианное значение для одного ядра за O (n), так что это, похоже, создает много дополнительной работы без какой-либо выгоды.
Рекс Керр
2

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

В этом случае вы можете найти медиану за время 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), потому что вам действительно нужно посчитать элементы хотя бы один раз.

Sklivvz
источник
1
Разве не худший случай (для вашего алгоритма), когда все числа равны? Если я прав, ни одно из ваших ведер никогда не будет заполнено, кроме среднего, со всеми элементами. Таким образом, вам придется каждый раз проходить все элементы, экспоненциально быстро продвигаясь к середине интервала. Я считаю, что O(n log n)в таком случае было бы так. Имеет ли это смысл ? Кстати, мне нравится твоя идея
Дичи
1
@Dici не совсем: во-первых, вы можете легко сократить сценарий «все то же самое», потому что вы знаете min и max. Как я сказал в ответе, знание дистрибутива может повлиять на ваш выбор; во-вторых, все равно взять o(n)+o(n/3)+o(n/9)+...чего еще o(n)и нет o(n log n).
Sklivvz
С другой стороны, вероятно, существует другой худший сценарий - U-образное распределение. Мне нужно немного подумать над этим, формализовать худший случай, но он мог бы быть хуже, чем o(n)в этом случае, с наивным разбиением.
Sklivvz 05
Ммм да, минимальное и максимальное значения помогут довольно легко справиться со случаем «все то же самое»
Дичи,
2

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

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

Разделите 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 секунд, чтобы закодировать мое решение и запустить его.

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

Знак высокой эффективности
источник
здесь мы просто объединяем все числа. Можем ли мы сделать это лучше, используя: - «мы можем найти медианное значение двух отсортированных списков за время входа в систему. N - длина каждого списка».
anony
1
@anony - пока вы отвечаете на свой вопрос, я закодирую, протестирую и готовлю свое решение. Я ожидаю, что есть способы получше, но иногда распараллеливание простого способа дает мне возможность почесать в затылке действительно сложные проблемы.
High Performance Mark
Вы действительно сделали это за 7 минут? Я не могу в это поверить, даже если это правда. Я выполнил аналогичную задачу (это было задание университета), и на реализацию и тестирование всего удаленного взаимодействия потребовалось около 2 часов (я использовал java RMI).
Роман
Я понимаю, о чем вы говорите, но к тому же DrPizza предлагает еще более быстрое решение, которое заключается в сортировке всех данных на одном узле и игнорировании остальных 99. Никто из нас не знает, насколько дорогие данные Следует рассмотреть возможность передачи, поэтому мы все просто выбираем компромисс, который звучит смутно правдоподобно. Ваше решение передает все данные несколько раз, поэтому я немного подозрительно отношусь к нему, но это определенно решение.
Стив Джессоп,
"смутно правдоподобно" - для меня этого достаточно, @Steve! Особенно в ответ на неопределенно неправдоподобный вопрос.
High Performance Mark
1

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

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

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

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

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

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

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

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

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

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

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

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

Сообщите мне, если я ошибся!

teambob
источник
да, я бы просто сделал двоичный поиск. Сэкономит пропускную способность сети, только позвонив на каждый компьютер несколько раз. Также у каждой машины может быть «стержень», где он меняет местами номера по обе стороны от оси для экономии времени. (точка поворота будет предыдущей оценкой медианы, поэтому в следующий раз нужно будет перебрать только все числа с одной стороны оси поворота)
Роберт
0

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

Anony
источник
По сути, мы всегда уменьшаем проблему, по крайней мере, на 30%, и благодаря этому мы добиваемся большого количества параллельных вычислений. Каждый узел начинается с 10 миллионов и сокращает свой набор данных на 30% на каждой итерации.
anony
На первой итерации ищем 500-миллионное число. Во второй итерации - если количество удаленных чисел составляет 300 миллионов, мы ищем 200-миллионное число и так далее ...
аноним,
2
Похоже, что это на правильном пути, но вы не очень четко объясняете, как избежать случайного выброса медианы с вашим разделением 30% / 70%. Возьмем следующий контрпример: предположим, что ваши первые 29% - это все нули, а все остальные блоки считаются на 1000, и каждый набор блоков на один больше, чем последний. Медиана 30-го процентиля отбрасывает все 29% данных и чуть менее половины 61% данных, что составляет 29 + 30% = 59% данных. Ой, мы просто выбросили истинную медианную величину! Так что, очевидно, вы имеете в виду не это, или, по крайней мере, вы имеете в виду это более умно, чем я интерпретировал.
Рекс Керр
0

Давайте сначала разберемся, как найти медиану 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?

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

хуг
источник
0

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

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

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.
Cem
источник
Вы имеете ввиду по 32 МБ?
Dici
Что вы подразумеваете под продолжением в нижней части списка?
Рутвик Вайла
0

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

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

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

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

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

:) вуаля

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

Johny
источник
0

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

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

Каран Капур
источник
0

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

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

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

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

Эрик Б.
источник
0

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

Гандхарв Гарг
источник
0

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

Нахождение медианы на одном компьютере - O (N): https://en.wikipedia.org/wiki/Selection_algorithm .

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

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

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

  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 во второй раз, <= половина этого числа третий и так далее).
Берт те Велде
источник
-1
  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 миллиард чисел.

Шив
источник
Что, если числа являются плавающими?
Sklivvz 05
-1

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

ленивый мальчик
источник
Очевидно, это неверно, и я настоятельно рекомендую вам никогда не думать, что ваш интервьюер - тупая свинья, которую можно обмануть,
Дичи,
Ха-ха, хорошо, хотя это не меняет того факта, что ваш ответ неверен. Доказать это очень легко
Дичи,
Хорошо, после прочтения лекции о статистике, я думаю, что идея случайным образом выбрать 1/100 или даже 1/1000 из числа одного миллиарда и вычислить их медиану не так уж плоха. Это всего лишь приблизительный расчет.
lazyboy 05
-3

Ответ Стива Джессопа неверен:

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

{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 уже ошибочно выброшен.

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

темный Лорд
источник