Медиана понимания медианных алгоритмов
Я искал в Интернете и посетил вики-страницу для алгоритма медианы медианы. Но, похоже, не могу найти явного утверждения в моем вопросе:
Если кто-то имеет очень большой список целых чисел (размер ТБ) и хочет распределить медиану этого списка распределенным образом, разбить список на подсписки разных размеров (или равных на самом деле не имеет значения), затем приступить к вычислению медиан этих меньших подсписков, а затем вычислить медиану этих медиан, чтобы получить медиану исходного большого списка?
Кроме того, верно ли это утверждение для любой k-й статистики? Я был бы заинтересован в ссылках на исследования и т.д. в этой области.
2 ответа
Ответ на ваш вопрос - нет.
Если вы хотите понять, как на самом деле выбрать статистику k-го порядка (включая, конечно, медиану) в параллельной настройке (распределенная настройка, конечно, не сильно отличается), взгляните на эту недавнюю работу, в которой я предложил Новый алгоритм, улучшающий предыдущее состояние алгоритма параллельного выбора:
Детерминированные параллельные алгоритмы отбора на крупнозернистых мультикомпьютерах
Здесь мы используем две взвешенные 3-медианы в качестве опорных точек и разделим их вокруг, используя пятистороннее разбиение. Мы также реализовали и протестировали алгоритм с использованием MPI. Результаты очень хорошие, учитывая, что это детерминированный алгоритм, использующий алгоритм выбора O(n) в худшем случае. Использование рандомизированного алгоритма быстрого выбора O(n) обеспечивает чрезвычайно быстрый параллельный алгоритм.
Если кто-то имеет очень большой список целых чисел (размер ТБ) и хочет распределить медиану этого списка распределенным образом, разбить список на подсписки разных размеров (или равных на самом деле не имеет значения), затем приступить к вычислению медиан этих меньших подсписков, а затем вычислить медиану этих медиан, чтобы получить медиану исходного большого списка?
Нет. Фактическая медиана всего списка не обязательно является медианой любого из подсписков.
Медиана медиан может дать вам хороший выбор точки для быстрого выбора, поскольку она ближе к фактической медиане, чем случайно выбранный элемент, но вам придется выполнить оставшуюся часть алгоритма быстрой выборки, чтобы найти фактическую медиану в большом списке.,