Как обрабатывать поток данных для подсчёта медианы с ограниченной памятью

Что проверяют

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

Как отвечать

Начните с базового решения и его цены. Две кучи: max-heap под нижнюю половину, min-heap под верхнюю, размеры отличаются не больше чем на один. Вставка O(log n), медиана O(1), но память O(n). Для потока, который помещается в память, это правильный ответ, для ограниченной памяти нет.

Дальше варианты по условиям:

• узкий диапазон значений (возраст, оценки, целые миллисекунды): гистограмма счётчиков, память по размеру диапазона, медиана точная и находится проходом по накопленным суммам;
• данные можно перечитать: бинарный поиск по значению, каждый проход считает элементы меньше кандидата. Память O(1), проходов O(log диапазона);
• квантильные скетчи: Greenwald-Khanna с гарантией ошибки по рангу, KLL из Apache DataSketches, t-digest с хорошей точностью на хвостах. Память зависит от точности, а не от длины потока, и скетчи сливаются, поэтому считаются по партициям;
• P²: пять маркеров, постоянная память, без строгой гарантии ошибки;
• резервуарная выборка: равномерная выборка фиксированного размера и медиана по ней.

Назовите готовые инструменты: approxQuantile и percentile_approx в Spark, quantileTDigest в ClickHouse. Для скользящего окна подойдут две кучи с ленивым удалением или SortedList из sortedcontainers.

Где спотыкаются

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

Берут медиану медиан по батчам. Она не равна медиане всего потока и сильно ошибается, когда батчи разного размера или по-разному распределены.

Называют приближённый метод, но не знают, в чём мерить его ошибку. Ошибка скетча задаётся в ранге: ε = 0,01 значит, что ответ стоит в пределах 1% позиций от истинной медианы, а не отличается от неё на 1% по значению.