Нахождение медианы большого набора чисел слишком велико, чтобы поместиться в память

Question

Мне недавно задали этот вопрос в одном из интервью.

Есть N чисел, слишком много, чтобы поместиться в память.Они разбиты по k таблицам базы данных (не отсортированы), каждая из которых может помещаться в память.Найдите медиану всех чисел.

Не совсем уверен насчет ответа на этот вопрос.

Answer 1

Существует несколько потенциальных решений:

• Внешняя сортировка слиянием - O (n log n)Вы в основном сортируете числа на первом проходе, а затем находите медиану на втором проходе.
• Алгоритм распределенного выбора статистики заказов - O (n)Упростите задачу до исходной задачи поиска k-го числа в несортированном массиве.
• Подсчет гистограммы сортировки O (n)Вы должны предположить некоторые свойства, касающиеся диапазона чисел - может ли диапазон поместиться в память?
• Если что-то известно о распределении чисел, могут быть созданы другие алгоритмы.1012 * Для получения более подробной информации и реализации см .:http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

Answer 2

Посмотрите на алгоритм "Медиана медиан" в этой статье в Википедии .

Смежный вопрос: Медиана медиан на Яве .

Объяснение: http://www.ics.uci.edu/~eppstein/161/960130.html

Answer 3

Этот ответ на вопрос о кворе ясно объясняет весь процесс шаг за шагом http://qr.ae/dMkGc. Просто скопируйте его для не-Коранов

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

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

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

Если алгоритм не завершается, начните с выбора нового случайного пивота из оставшихся элементов.

Анализ:

Пусть n - общее количество элементов, а s - количество серверов.Предположим, что элементы примерно случайным образом и равномерно распределены между серверами (каждый сервер имеет O (n / s) элементов).В итерации i мы ожидаем выполнить работу O (n / (s * 2 ^ i)) на каждом сервере, так как размер наборов элементов каждого сервера будет примерно уменьшен вдвое (помните, мы предположили, что распределение элементов примерно случайное) и O (s) работают над мастером (для трансляции / получения сообщений и сложения размеров вместе).Мы ожидаем O (log (n / s)) итераций.Добавление их на всех итерациях дает ожидаемое время выполнения O (n / s + slog (n / s)), и, предполагая, что s << sqrt (n), как это обычно бывает, становится просто (O (n / s)), это лучшее, на что вы могли бы надеяться. </p>

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

Answer 4

Для медианы медиан вам еще нужно сделать поворот. Это подход в памяти. В этом случае вам нужно использовать потоковый подход. На первом проходе вы найдете максимум и минимум образца. Назовите это U и L для верхней нижней границы. Затем установите медиану кандидата на среднее значение U и L. Вторым проходом вы подсчитываете вероятность X <кандидата. Если это .5, вы закончили, если нет, если он ниже, вы заменяете L кандидатом, а кандидат - средним из кандидата и выше. В другом случае тоже самое, но поменяйтесь ролями верхних и нижних. По сути это бинарный поиск среди возможных медиан. Если вы можете позволить себе дополнительное дисковое пространство, вы можете на каждом шаге фильтровать все элементы между U и L и работать только с теми, кто движется вперед, поскольку медиана гарантированно будет включена. Это сводит сложность к линейному времени, так же как и к повороту. </p>

Answer 5

Еще один способ взглянуть на это - вернуться к определению «медиана».Авторы различаются по своему языку, но в основном медиана - это значение, которое разделяет распределение вероятностей на две равные части.

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

Answer 6

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

Пример: числагенерируется случайным образом и сохраняется в (расширяющемся) массиве.Как бы вы могли отслеживать медиану?

Наш мозговой штурм структуры данных может выглядеть следующим образом:

• Связанный список?Возможно нет.Связанные списки, как правило, не очень хорошо подходят для доступа и сортировки номеров.

• Массив?Возможно, но у вас уже есть массив.Не могли бы вы как-то сохранить элементы отсортированными?Это, наверное, дорого.Давайте подождем и вернемся к нему, если это необходимо.

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

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

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

Answer 7

Если приблизительного ответа достаточно, метод, аналогичный @piccolbo, работает хорошо. Я предполагаю, что все точки являются целыми числами, но если нет, вы можете умножить на десять или сто или что угодно, чтобы нормализовать данные в целые числа. Сделайте один проход по данным, вычисляя среднее (среднее арифметическое. Назовите это число предварительной медианой. Затем сделайте второй проход по данным. Если точка данных меньше предварительной медианы, уменьшите предварительную медиану на единицу. Если данные точка больше, чем предварительная медиана, увеличьте предварительную медиану на единицу. Если точка данных совпадает с предварительной медианой, оставьте предварительную медиану без изменений. После окончания данных верните предварительную медиану. предварительная медиана первоначально будет время от времени меняться, но в конечном итоге она стабилизируется в очень небольшом диапазоне, который будет очень близок к фактической медиане.

Answer 8

Вот что я бы сделал:

1. Пример данных, чтобы получить общее представление о распределении.

2. Используя информацию о распределении, выберите «ведро» (диапазон), достаточно большое, чтобы получить медиану внутри, и достаточно маленькое, чтобы поместиться в память.

3. С одним проходом (O (N)) подсчитайте числа перед сегментом (L1_size), после сегмента (L3_size) и поместите числа в пределах диапазона в интервал (L2).Вы увидите, содержит ли выбранное ведро медиану.Если нет - перейдите к шагу 2.

4. Используйте быстрый выбор или другой метод, чтобы найти элемент k = (L1_size + L2_size / 2) в корзине.

Требуется O (N) + O (L2_size) шагов.