Меня недавно задали этот вопрос в интервью.
Есть N чисел, слишком много, чтобы вписаться в память. Они разбиваются на k таблиц базы данных (unsorted), каждый из которых может вписываться в память. Найдите медиану всех чисел.
Не был уверен в ответе на этот вопрос.
Есть несколько потенциальных решений:
Для получения дополнительной информации и реализации см.:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html
Посмотрите на алгоритм "Медиана медиан" в эту статью в википедии.
Связанный вопрос: Медианы медиан в Java.
Объяснение: http://www.ics.uci.edu/~eppstein/161/960130.html
Для медианы медианов вам все равно нужно делать поворот. Это подход к памяти. В этом случае вам необходимо использовать потоковый подход. На первом проходе вы найдете max и min образца. Назовем U и L верхними нижними границами. Затем установите медиану кандидата в среднем по U и L. Со вторым проходом вы считаете вероятность X < кандидат. Если это 0,5, вы закончите, если нет, если он ниже, вы замените L кандидатом, а кандидат - со средним числом кандидатов и верхним. В другом случае, то же, но меняйте роли сверху и снизу. По сути, это бинарный поиск среди возможных медианов. Если вы можете позволить себе дополнительное пространство на диске, вы можете на каждом шаге фильтровать все элементы между U и L и работать только с теми, кто идет вперед, так как медиана гарантированно будет включена. Это сводит сложность вплоть до линейного времени, как и к повороту.
Предположим, что у вас есть мастер node (или вы можете использовать консенсусный протокол для выбора мастера из ваших серверов). Мастер сначала запрашивает серверы для размера своих наборов данных, называет это n, так что он знает, что нужно найти самый большой элемент k = n/2.
Затем мастер выбирает случайный сервер и запрашивает его для случайного элемента из элементов на этом сервере. Мастер передает этот элемент каждому серверу, и каждый сервер разбивает его элементы на те, которые больше или равны вещательному элементу, и те, которые меньше, чем передаваемый элемент.
Каждый сервер возвращает мастеру размер большего раздела, назовите это m. Если сумма этих размеров больше k, мастер указывает каждому серверу игнорировать меньшее, чем заданное для остальной части алгоритма. Если он меньше k, то мастер указывает на игнорирование более крупных наборов и обновлений k = k - m. Если это точно k, алгоритм завершается, и возвращаемое значение является осью, выбранной в начале итерации.
Если алгоритм не заканчивается, повторите процедуру, начиная с выбора нового случайного стержня из остальных элементов.
Анализ:
Пусть n - общее количество элементов, а s - количество серверов. Предположим, что элементы примерно произвольно и равномерно распределены между серверами (каждый сервер имеет элементы O (n/s)). В итерации я мы ожидаем, что мы будем работать с O (n/(s * 2 ^ i)) на каждом сервере, так как размер каждого набора элементов сервера будет приблизительно сокращен пополам (помните, мы предположили грубо случайное распределение элементов ) и O (ов) работают над мастером (для передачи/приема сообщений и добавления размеров вместе). Мы ожидаем, что O (log (n/s)) итераций. Добавление их по всем итерациям дает ожидаемое время выполнения O (n/s + slog (n/s)) и принятие s < sqrt (n), который обычно имеет место, это становится просто (O (n/s)), что является лучшим, на что вы могли бы надеяться.
Заметим также, что это работает не только для поиска медианы, но и для нахождения k-го наибольшего значения для любого значения k.
Еще один способ взглянуть на это - вернуться к определению "медиана". Авторы различаются по своему языку, но в основном медиана - это значение, которое разбивает распределение вероятности на две равные части.
Поэтому вместо того, чтобы тратить много сил на сортировку огромных наборов данных, оцените распределение и найдите середину. Как отмечено выше для некоторых распределений, медиана равна среднему значению, которое быстро и легко вычисляется. Кроме того, если точный ответ не нужен, вы можете использовать эмпирическое соотношение: mean - mode = 3 * (среднее - медиана).
Вот что я сделал бы:
Пример данных, чтобы получить общее представление о распределении.
Используя информацию о распределении, выберите "ведро" (диапазон), достаточно большое, чтобы получить среднюю внутри и достаточно маленькую, чтобы вписаться в память.
С помощью одного прохода (O (N)) подсчитывайте числа перед ковшом (L1_size) после ковша (L3_size) и поместите числа в пределах диапазона в ведро (L2). Вы увидите, содержит ли выбранное ведро медиана. Если нет - перейдите к шагу 2.
Используйте quickselect или другой метод, чтобы найти элемент k = (L1_size + L2_size/2) в ведре.
Требуется выполнить шаги O (N) + O (L2_size).
Мне также задавали тот же вопрос, и я не мог сказать точный ответ, поэтому после интервью я просмотрел несколько книг об интервью и вот что я нашел.
Пример: числа генерируются случайным образом и сохраняются в (расширяющийся) массив. Как бы вы сохранили след медианы?
Наш мозговой штурм структуры данных может выглядеть следующим образом:
• Связанный список? Возможно нет. Связанные списки, как правило, не очень хорошо подходят для доступа и сортировки номеров.
• массив? Возможно, но у вас уже есть массив. Не могли бы вы как-то сохранить элементы отсортированными? Это, вероятно, дорого. Позвольте удержаться от этого и вернуться к нему, если это необходимо.
• Бинарное дерево? Это возможно, поскольку двоичные деревья довольно хорошо справляются с упорядочением. На самом деле, если бинарное дерево поиска идеально сбалансировано, вершина может быть медиана. Но будьте осторожны - если есть четное количество элементов, медиана на самом деле является средним из двух средних элементов. Средние два элемента не могут быть оба наверху. Это, вероятно, работоспособный алгоритм, но давайте вернемся к нему.
• куча? Куча действительно хороша в базовом упорядочении и отслеживании макс и мин. Это действительно интересно - если бы у вас было две кучи, вы могли бы отслеживать большую половину и меньшую половину элементов. Большая половина хранится в минимальной куче, так что самый маленький элемент в большей половине находится в корне. Меньшая половина хранится в максимальной куче, так что самый большой элемент меньшей половины находится в корне. Теперь, с этими структурами данных, у вас есть потенциальные медианные элементы в корнях. Если кучи уже не одного размера, вы можете быстро "перебалансировать" кучи, вытолкнув элемент из одной кучи и вытолкнув его на другую.
Обратите внимание, что чем больше проблем вы делаете, тем более развит ваш инстинкт, к которому будет применяться структура данных. Вы также разработаете более точно настроенный инстинкт относительно того, какой из этих подходов является наиболее полезным.
Если достаточно приблизительного ответа, метод, аналогичный @piccolbo, хорошо работает. Я предполагаю, что все точки являются целыми числами, но если нет, вы можете умножить на десять или сто или что-то еще, чтобы нормализовать данные до целых чисел. Сделайте один проход над данными, вычисляющими среднее значение (среднее арифметическое. Назовите этот номер временной средой, затем сделайте второй проход по данным. Если точка данных меньше предварительной медианной, уменьшите предварительную медиану на единицу. Если данные точка больше, чем предварительная медиана, увеличьте предварительную медиану на единицу. Если точка данных совпадает с временной средой, оставьте временную медианную без изменений. После окончания данных верните предварительную медиану. временная медиана будет изначально меняться время от времени, но в конечном итоге она будет стабилизироваться в очень небольшом диапазоне, который будет очень близок к фактической медианной.