Медиана понимания медианных алгоритмов

Question

Я искал в Интернете и посетил вики-страницу для алгоритма медианы медианы. Но, похоже, не могу найти явного утверждения в моем вопросе:

Если у вас есть очень очень большой список целых чисел (размер ТБ) и он хочет распределить медиану этого списка распределенным образом, разбить этот список на подсписки разных размеров (или равных на самом деле не очень) вопрос), а затем приступить к вычислению медиан этих меньших подсписков, а затем вычислить медиану этих медиан, чтобы получить медиану исходного большого списка?

Кроме того, верно ли это утверждение для любой k-й статистики? Я был бы заинтересован в ссылках на исследования и т.д. в этой области.

Answer 1

Ответ на ваш вопрос - нет.

Если вы хотите понять, как на самом деле выбрать статистику k -го порядка (включая, конечно, медиану) в параллельной настройке (распределенная настройка, конечно, не сильно отличается), посмотрите на это недавняя статья, в которой я предложил новый алгоритм, улучшающий предыдущий современный алгоритм параллельного выбора:

Детерминированные алгоритмы параллельного выбора на крупнозернистых мультикомпьютерах

Здесь мы используем две взвешенные 3-медианы в качестве опорных точек и разделяем их вокруг, используя пятистороннее разбиение. Мы также реализовали и протестировали алгоритм с использованием MPI. Результаты очень хорошие, учитывая, что это детерминированный алгоритм, использующий алгоритм выбора худшего случая O (n). Использование рандомизированного алгоритма QuickSelect O (n) обеспечивает чрезвычайно быстрый параллельный алгоритм.

Answer 2

Если у вас есть очень очень большой список целых чисел (размер ТБ) и он хочет распределить медиану этого списка распределенным способом, то разбить список на подсписки разных размеров (или равных на самом деле не очень) вопрос), затем перейдите к вычислению медиан этих меньших подсписков, а затем вычислите медиану этих медиан, чтобы получить медиану исходного большого списка?

Нет. Фактическая медиана всего списка не обязательно является медианой любого из подсписков.

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