Ниже — полный обзор практических алгоритмов и архитектурных решений для динамического поддержания медианы в стриме чисел при ограниченной памяти, с обоснованием, оценками сложности и вариантами для распределённой среды (учёт сетевой латентности и моделей согласованности).

Постановка задачи и требования

Вход: поток вставок (возможно — удалений или «скользящее окно»). N — число элементов в потоке (растёт).Цель: по запросу возвращать медиану (точно) или элемент с ранком близким к N/2 (с точностью по рангу ± εN).Ограничение: память существенно меньше N (нельзя хранить весь поток).Дополнительно: распределённая обработка (множество узлов), сетевые задержки, баланс между задержкой ответа и точностью/консистентностью.

Категории решений (кратко)

Точное решение (при допущении, что памяти достаточно для хранения всех элементов в структуре): два куча (max-heap + min-heap) или order-statistics tree.Аппроксимационные алгоритмы (стриминг): детерминированные и вероятностные sketch/summary (GK, KLL, t-digest), а также выборка (reservoir sampling) для оценки медианы.Скользящее окно / поддержка удалений: специальные структуры (две кучи + lazy-deletes, balanced BST со счетчиками, или скетчи, поддерживающие «вычитание»/запись времени).

Точное решение: две кучи (двух-кучная схема)
Идея: держать «нижнюю половину» в max-heap L и «верхнюю половину» в min-heap R так, чтобы |size(L)-size(R)| ≤ 1.

Вставка x:Если L пуст или x ≤ top(L) -> вставить в L, иначе в R.Балансировать: если size(L) > size(R) + 1 -> переместить top(L) в R; обратная ситуация аналогично.Получение медианы:Если размеры равны → медиана = (top(L)+top(R))/2 (или любой из двух в дискретном случае в зависимости от определения).Иначе медиана = top(кучи с большим размером).

Временная сложность:

вставка: O(log n) (heap)получение медианы: O(1)
Память: O(n) (храним все элементы в двух кучах)

Плюсы: простая, точная; минус — требует O(n) памяти.

Аппроксимационные скетчи (для ограниченной памяти)
Если память << n — используем summaries/скетчи, гарантирующие ошибку по рангу εN.

4.1. Greenwald–Khanna (GK) — детерминированный ε-approx quantile summary

Гарантия: возвращает элемент с ранком r, где |r - targetRank| ≤ εN.Память: O((1/ε) log(εN)) — детерминированно.Время: вставка амортизировано O(1)–O(log(1/ε)) (зависит от реализации агрегирования и поддержания интервалов).Merge: возможна, но с несложной процедурой (слияние списков с последующей компрессией).Применение: когда требуется детерминированная гарантия по рангу.

4.2. KLL (Karnin–Lang–Liberty) — современный эффективный sketch

Характеристики: вероятностный sketch с гарантией по рангу с высокой вероятностью (с доверительной вероятностью 1-δ).Память: O( (1/ε) log log (1/ε) ) (в среднем, значительно эффективнее GK на практике).Время вставки: амортизированное O(1).Merge: поддерживает эффективное слияние — отличная опция для распределённой агрегации.Практика: часто предпочтительнее GK по памяти и производительности при больших потоках.

4.3. t-digest (для вещественных данных, плотность на концах)

Специализированная для распределений с плотностью; хорош для медиан и экстремальных квантилей.Гарантии менее строгие (статистические), но на практике часто точна.Merge: поддерживает хорошее слияние.

4.4. Reservoir sampling (выборка)

Хранить случайную подвыборку размера k (reservoir), вычислять медиану по образцу.Погрешность: для абсолютной ошибки в ранге ε с вероятностью 1-δ нужен k = O( (1/ε^2) log(1/δ) ).Очень простая и параллелизуемая, но для малых ε требует больших k.

Вывод: для ограниченной памяти и требований на аппроксимацию — KLL (или t-digest при вещественных и «плотностных» требованиях) является практичным выбором; GK — когда важна детерминированная bound.

Сложности и краткие сравнения

Две кучи: точность 0, память O(n), вставка O(log n).GK: память O((1/ε) log(εN)), вставка амортизированно O(1)–O(log(1/ε)), детерминированно.KLL: память O((1/ε) log log (1/ε)) ожидаемо, вставка амортизированно O(1), слияние эффективно, вероятностные гарантии.Reservoir: память O(1/ε^2), вставка O(1), простота, но хуже по памяти при малых ε.

Поддержка удалений / скользящее окно

Точные:Balanced BST с порядковыми статистиками (order-stat tree) — поддержка вставки и удаления O(log n) и извлечение медианы O(log n) или O(1) при хранении указателя. Память O(n).Две кучи + lazy deletion: помечаем элементы как удалённые в хеш-таблице, при top() вытеснённых heap удаляем «мусор» до валидного top. Поддержка удаления — амортизированно O(log n) с дополнительной памятью для меток.Аппроксимации:Некоторые скетчи и структуры (экспоненциальные гистограммы, специальные sliding-window sketches) поддерживают окно с «вытеснением» старых элементов, но реализации сложнее и гарантии меняются.Для KLL можно использовать «производные» подходы с таймстампами, но простого и аккуратного удаления нет — обычно применяют семплирование/бэкендные схемы.

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

7.1. Используемые свойства для распределённости

Mergeability: лучше, если локальные структуры можно агрегировать в глобальную посредством операции merge (ассоциативно и коммутативно). KLL, t-digest и GK (с аккуратной реализацией) поддерживают слияние — идеально для распределённых узлов.Асинхронная агрегация: узлы собирают локальные sketch и периодически отправляют на агрегатор / через reduce / gossipping. Это уменьшает сетевой трафик.

7.2. Топологии агрегации

Централизованный: все узлы отправляют локальные sketch на централизованный агрегатор, который сливает их. Простой, но агрегатор — узкое место и точка отказа.Иерархическая/деревянная редукция: узлы сливаются в ближайший промежуточный уровень (reduce tree). Снижает трафик и латентность на дальние узлы.Gossipping/Ring: каждый узел периодически обменивается sketch с соседями; даёт eventual convergence.

7.3. Задержка vs точность

Периодические отправки (батчи): уменьшение сетевого trafика, но агрегатам — более «устаревшие» данные → компенсируется оценкой максимального дрейфа.Pull-on-demand: при запросе на медиану триггерить немедленную агрегацию: высокая задержка ответа.Параметры: частота отправки, размер sketch на узле (ε локально) — надо выбирать, чтобы обеспечить финальную точность. Если локальные sketch с ε_local, то после merge итоговый ε_global зависит от схемы: при правильной настройке и слиянии можно обеспечить требуемый ε_global.

7.4. Модель согласованности

Eventual consistency: приемлема для большинства аналитических задач; проще и быстрее.Strong consistency (линейнаяizability): требуется согласование через consensus (Paxos/Raft) при каждом обновлении или при каждой агрегации — дорого из-за сетевых RTT; обычно не применяется для приблизительных медианных оценок.Практический компромисс: использовать eventual consistency для регулярных апдейтов и обеспечить «строгое» вычисление только по запросу (синхронный barrier/consensus) если крайне нужна точность.

7.5. Обработка латентности и отказов

Асинхронные апдейты + таймстампы и водяные метки (watermarks) — агрегатор знает, с какими временными рамками приёма данных он работает.Репликация sketch на несколько узлов; при слиянии учитываем признаки повторного учёта (например, нумерация батчей).Для критичных приложений: логирование исходных событий в долговременное хранилище (S3) и офлайн-вычисление при необходимости.

Практическая рекомендация (что выбрать в зависимости от требований)

Требуется точная медиана и память достаточна (n хранится): две кучи или order-stat tree.Память ограничена, нужна аппроксимация с гарантией: KLL (лучшее практическое соотношение memory/accuracy и поддерживает merge).Нужна простота и стойкость к распределённости, не строжая гарантия: t-digest (для float) или reservoir sampling (если допускается статистическая погрешность).В распределённой среде: использовать mergeable sketch (KLL/t-digest), иерархическую агрегацию, настраивать частоту и модель согласованности под требования задержки и точности.

Нюансы реализации и практические советы

Выбор ε: малое ε → большая память; часто ε = 0.01 (1% по рангу) — разумный компромисс.Таймстампы и батчи: помечайте батчи, чтобы избежать двойного учёта при повторном отправлении.Типы данных: для целых значений можно дополнительно хранить частотные структуры; для вещественных — t-digest или KLL.Библиотеки и готовые реализации: Apache DataSketches (KLL), t-digest (разные реализации), stream-lib (GK) — можно использовать готовые, они оптимизированы и проверены.Тестирование: проверяйте поведение на краевых распределениях (много одинаковых значений, сильноконцентрированная масса, long-tail).

Пример: высокоуровневый псевдокод (две кучи)

insert(x):
if L.empty() or x ≤ top(L): L.push(x)
else: R.push(x)
if size(L) > size(R) + 1: move top(L) → R
if size(R) > size(L) + 1: move top(R) → Lmedian():
if size(L) == size(R): return (top(L)+top(R))/2
else return top(the larger)

Заключение — выбор и обоснование

Если память реально ограничена и поток большой или распределённый — наиболее практичен KLL sketch (mergeable, малый постоянный memory for given ε, O(1) вставка). Он даёт контролируемую ошибку по рангу и хорошо подходит для иерархической агрегации по сети.Если нужна абсолютная точность и память позволяет — две кучи (или order-stat tree).В распределённой среде проектируйте агрегацию с учётом mergeability, используйте асинхронные обновления + водяные метки; при необходимости жёсткой согласованности используйте согласование через consensus, но ожидайте высоких задержек.

Если хотите, могу:

привести реализацию KLL (псевдокод) и описать процедуру compaction/merge детально;оценить конкретные параметры памяти/ε для ваших входных нагрузок (нужно указать N, допустимую ошибку, частоту запросов и желаемую задержку);показать пример архитектуры для 3-tier Reduce Tree с оценкой сетевого трафика и задержек.