Что хотят услышать интервьюеры:

Медиана не является агрегатом, который можно корректно объединять по частям так же, как сумму или среднее. Локальные медианы не несут достаточно информации о распределении данных, поэтому глобальная медиана может сильно отличаться от результата “медиана от медиан”. Корректный способ — либо собрать данные полностью, либо использовать алгоритмы, которые хранят порядок/квантили с гарантией точности или приближением.

Определение:

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

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

Пример использования:

Допустим, есть три воркера с данными:

Worker 1: [1, 2, 100]
Worker 2: [3, 4, 5]
Worker 3: [6, 7, 8]

Локальные медианы:

Worker 1 → 2
Worker 2 → 4
Worker 3 → 7

Если взять медиану от этих медиан, получится 4.
Но если объединить все данные:

[1, 2, 3, 4, 5, 6, 7, 8, 100]

Глобальная медиана — 5.

То есть “медиана медиан” дала неверный ответ.

Пояснение кода:

Код не требуется: здесь важен не синтаксис, а понимание ограничения алгоритма.

Разложение примера по шагам:

Каждый воркер видит только свою часть данных.
Он вычисляет локальную медиану, но не знает, сколько значений в других партициях меньше или больше этой медианы.
При объединении локальных медиан теряется информация о реальном ранге элементов во всём наборе.
Поэтому итог может быть смещён в сторону одной из партиций, особенно если размеры партиций разные или распределение данных неоднородное.

Ключевые моменты:

Медиана не является “mergeable” агрегатом в простом виде.
Медиана локальных выборок не равна глобальной медиане в общем случае.
Для точного результата нужны либо все данные, либо алгоритмы поиска квантили с дополнительной структурой состояния.
Ошибка особенно заметна при разных размерах партиций и перекошенных распределениях.
Для распределённых систем часто используют приближённые квантильные алгоритмы, если точность не критична.

Почему нельзя просто считать медиану на каждом воркере и потом объединять?