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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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.

Предполагается, что вопрос состоит из 1 000 000 000 целых чисел (x), где 0> = x <= 2 147 483 647, и что ОП ищет (элемент (499 999 999) + элемент (500 000 000)) / 2 (если числа были отсортированы). <strong>Также предполагается, что все 100 компьютеров были равны.

используя мой ноутбук и GigE ...

Я обнаружил, что мой ноутбук может сортировать 10000000 Int32 за 1,3 секунды. Таким образом, приблизительная оценка будет такой, что сортировка по миллиарду будет занимать 100 x 1,3 секунды (2 минуты 10 секунд);).

Оценка односторонней передачи файла 40 МБ по гигабитному Ethernet составляет 0,32 секунды. Это означает, что отсортированные результаты со всех компьютеров будут возвращены примерно через 32 секунды (компьютер 99 не получил свой файл через 30 секунд после запуска). Оттуда не займет много времени, чтобы отбросить самые низкие 499 999 998 номеров, добавить следующие 2 и разделить на 2.

Answer 7

Это может удивить людей, но если числа достаточно малы, чтобы поместиться в 32-битном (или меньше) - просто выполните сортировку по сегментам! Требуется только 16 ГБ оперативной памяти для любого числа 32-битных целых чисел и выполняется в 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 ⁹ ) чисел и запуск с time, например,

time ./median < billion

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

Answer 8

Как ни странно, я думаю, что если у вас достаточно компьютеров, вам лучше сортировать, чем использовать O(n) алгоритмы поиска медианы. (Если, конечно, ваши ядра не очень, очень медленные, я бы просто использовал один и использовал O(n) алгоритм поиска медианы только для 1e9 чисел; хотя, если у вас было 1e12, это могло бы быть менее практичным.)

В любом случае, давайте предположим, что у нас больше, чем log n ядер, чтобы справиться с этой проблемой, и мы не заботимся о потреблении энергии, просто получаем быстрый ответ. Далее предположим, что это SMP-машина со всеми данными, уже загруженными в память. (Например, 32-ядерные машины Sun относятся к этому типу.)

Один поток слепо разбивает список на куски одинакового размера и говорит другим M-потокам отсортировать их. Эти темы старательно делают это, в (n/M) log (n/M) время. Затем они возвращают не только свои медианы, но и, скажем, 25-й и 75-й процентили (извращенные наихудшие случаи лучше, если вы выбираете немного другие числа). Теперь у вас есть 4M диапазонов данных. Затем вы сортируете эти диапазоны и работаете вверх по списку, пока не найдете такое число, что, если вы выберете каждый диапазон, который меньше или содержит число, вы выбросите половину своих данных. Это ваша нижняя граница для медианы. Сделайте то же самое для верхней границы. Это занимает что-то вроде 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 < n, что верно для сценария, который вы описали.

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

Answer 9

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

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

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

Answer 10

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