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

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

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

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

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

Ответ 1

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 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 и что OP искал (элемент (499,999,999) + элемент (500 000 000))/2 (если номера были отсортированы). Также предполагается, что все 100 компьютеров были равны.

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

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

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

Ответ 7

Как ни странно, я думаю, что если у вас достаточно компьютеров, вам лучше сортировать, чем использовать алгоритмы медианного поиска O(n). (Если ваши ядра не очень, очень медленные, я бы просто использовал один и использовал алгоритм поиска O(n) для всего лишь 1е9 чисел, если бы у вас было 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, что верно для описанного вами сценария.

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

Ответ 8

Это может удивить людей, но если числа целые, достаточно маленькие, чтобы вписаться в 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 ⁹) чисел и работающим с time таким образом

time ./median < billion

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

Ответ 9

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

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

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

Ответ 10

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

В этом случае вы можете найти медиану в 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, min 1, max 3
средний (10): 7,5,6,4,4,6,4,7,4,4, min 4, max 7
high (5): 10, 10, 8, 9, 9, min 8, max 10

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

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

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

старый низкий (5)
low (5): 4, 4, 4, 4, 4, max 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

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

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

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

Ответ 11

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

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

EDIT: @Roman - хорошо, если вы не можете поверить в это, даже если это правда, тогда нет смысла в том, чтобы я раскрывал правду или ложь предложения. Я хотел сказать, что грубая сила иногда бьется умнее в гонке. Мне потребовалось около 15 секунд, чтобы разработать алгоритм, который я уверен, что я могу реализовать, который будет работать, и который будет адаптирован к широкому диапазону размеров входов и номеров компьютеров и настраивается на характеристики компьютеров и сетей. Если вам понадобится, или кто-либо еще, скажите 15 минут, чтобы разработать более сложный алгоритм, у меня есть преимущество 14m45s, чтобы закодировать мое решение и запустить его.

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

Ответ 12

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

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

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.

Ответ 13

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

Ответ 14

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

Существует 1 родительский node и 99 дочерних узлов. У дочерних узлов есть два вызова api:

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

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

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

Поменяйте минимальное и максимальное округление - это медианная "догадка"
Если значение больше, чем счет больше, чем меньше, установите минимальное значение в предположение
Если значение больше, чем счет меньше, чем счетчик, установите максимальное значение в предположении
Если счетчик является нечетным, когда минимальные и максимальные значения равны
Если счетчик даже заканчивается, когда максимум <= minimum + guess.match_count Это можно сделать на узлах, использующих несортированные данные (скажем, из файлов журналов) следующим образом.

Существует 1 родительский node и 99 дочерних узлов. У дочерних узлов есть два вызова api:

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

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

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

Поменяйте минимальное и максимальное округление - это медианная "догадка"
Если значение больше, чем счет больше, чем меньше, установите минимальное значение в предположение
Если значение больше, чем счет меньше, чем счетчик, установите максимальное значение в предположении
Если счетчик является нечетным, когда минимальные и максимальные значения равны
Если счетчик даже заканчивается, когда максимум <= minimum + guess.match_count

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

Сообщите мне, допустил ли я ошибку!

Ответ 15

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

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

Ответ 16

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

Ответ 17

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

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

Вы выбираете средний элемент k и разделяете данные на 2 подматрицы. первый содержит все элементы < k и 2 содержит все элементы >= k.

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

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

Сделайте это рекурсивно.

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

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

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

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

Ответ 18

Я бы сделал это следующим образом:

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

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

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

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

:) voilla

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

Ответ 19

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

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

Ответ 20

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

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

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

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

Ответ 21

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

Ответ 22

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

Поиск медианы на одной машине - O (N): https://en.wikipedia.org/wiki/Selection_algorithm.

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

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

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

Каждая машина получает N/100 номеров, вычисляет свою собственную медиану и отправляет эту информацию мастеру.
Мастер компилирует отсортированный список всех отдельных медианов и отправляет их обратно на каждую машину, определяя упорядоченную последовательность ведер (на каждой машине то же самое), по одному для каждого медианного значения (одно значение ведра), а один для каждый интервал между соседними медианами. Конечно, есть также нижние и верхние ковши для значений ниже самой низкой медианной и выше самой высокой.
Каждая машина вычисляет, сколько чисел попадает в каждое ведро и передает эту информацию обратно ведущему устройству.
Мастер определяет, в каком ведре содержится медиана, сколько нижних значений (в целом) опускается ниже этого ведра и сколько выше.
Если выбранное ведро представляет собой единичное ведро (одно из медианов), оливковое выделенное ведро содержит только 1 (N нечетных) или 2 (N четных) значений, которые мы выполнили. В противном случае мы повторим описанные выше шаги со следующими (очевидными) изменениями:
Только числа из выбранного ковша (re) распределяются от ведущего к 100 машинам и, кроме того,
Мы не собираемся вычислять (на каждой машине) медианное, а k-е значение, где мы учитываем, сколько более высоких чисел было отброшено от общего числа и сколько меньших чисел. Концептуально каждая машина имеет свою долю отброшенных низких/больших чисел и учитывает это при вычислении новой медианы в наборе, которая (концептуально) включает (свою долю) отброшенные числа.

Время-сложность:

Маленькое мышление убедит вас в том, что на каждом шаге общее количество анализируемых значений сокращается в два раза (в два раза больший случай, вы можете ожидать значительно лучшего снижения). Отсюда получаем:
Предполагая, что поиск медианного (или k-го значения), который является O (N), принимает время c * N, где префактор c не слишком сильно изменяется с N, так что мы можем считать его константой для момент, мы получим наш окончательный результат не более 2 * c * N/100 раз. Поэтому использование 100 машин дает нам коэффициент ускорения 100/2 (не менее).
Как отмечалось ранее: время, связанное с передачей чисел между машинами, может сделать его более привлекательным, чтобы просто делать все на одной машине. Однако, ЕСЛИ мы идем для распределенного подхода, общее количество чисел, которые будут переданы во всех шагах вместе, не будет превышать 2 * N (N в первый раз, <= N/2 во второй раз, <= половина что третий и т.д.).

Ответ 23

Разделите 1 миллиард чисел на 100 машин. Каждая машина будет иметь 10 ^ 7 номеров.
Для каждого входящего номера на машине сохраните номер на частотной карте, число → счет. Также сохраните минимальное число на каждой машине.
Найти медиану в каждой машине: начиная с минимального числа на каждой машине, суммируйте подсчеты до достижения медианного индекса. Медиана в каждой машине будет составлять ок. меньше и больше 5 * 10 ^ 6 чисел.
Найдите медиану всех медианов, которая будет меньше и больше, чем ок. 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 ^ 7bits = 1,25 * 10 ^ 6 байтов, что составляет 1,25 МБ

Таким образом, с помощью вышеупомянутого подхода каждой машине потребуется 1,25 МБ пространства для вычисления локальной медианы. И медиана медианов может быть вычислена из этих 100 локальных медианов, в результате чего медиана составляет 1 миллиард чисел.

Ответ 24

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

Ответ 25

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

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

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

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