Модель потока: один проход и память меньше данных

Если ты назовёшь ограничения потоковой модели, посчитаешь среднее и дисперсию за один проход и объяснишь, почему точное число различных требует линейной памяти, - листай до «Теперь сам».

Как думаешь, что можно узнать, не запоминая поток

Мимо программы проходит миллиард чисел. Сохранить их негде: памяти - несколько килобайт. Каждое число видно один раз.

Ответь себе до чтения, на какие из вопросов можно ответить точно: чему равна сумма, какое число наибольшее, чему равно среднее, сколько среди чисел разных, какое число стоит посередине по величине? На первые три - можно, хватит двух-трёх переменных. На последние два - нельзя никаким алгоритмом, и это не вопрос изобретательности.

На что это похоже

Контролёр на конвейере. Детали едут мимо, вернуть ни одну нельзя, а в руках у него блокнот на одну страницу. Посчитать детали и их общий вес он может: достаточно двух чисел, которые он правит после каждой детали. Найти самую тяжёлую - тоже: помнить текущего рекордсмена.

А вот ответить, встречалась ли уже деталь с таким серийным номером, он не может, если номеров больше, чем помещается на странице: для этого нужно помнить все виденные номера. Блокнот заставляет выбирать вопросы, и на некоторые из них приходится соглашаться отвечать примерно.

Механизм: состояние, которое обновляется на месте

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

Точно, в нескольких числах, в этой модели считается всё, что обновляется по правилу «новое состояние = функция от старого состояния и одного элемента» с состоянием фиксированного размера:

количество:      n = n + 1
сумма:           s = s + x
наименьшее:      m = min(m, x)
среднее:         a = a + (x − a) / n                      после увеличения n
дисперсия:       накопить (x − a_старое) · (x − a_новое),  в конце разделить на n

Среднее обновляется без хранения суммы: новое среднее отстоит от старого на долю 1/n от расстояния до нового элемента. Формула для дисперсии выглядит странно, но она точная: произведение отклонений от старого и от нового среднего - это ровно прибавка к сумме квадратов отклонений. Проверяется это раскрытием скобок; программа ниже сверяет результат с прямым счётом. «Постоянная память» здесь значит «постоянное число переменных»: самому счётчику n нужно log₂ n бит.

Теперь что не считается точно. Пусть алгоритм точно знает число различных элементов и использует s бит памяти. Скормим ему какое-нибудь подмножество чисел от 1 до N. После этого по его памяти можно восстановить всё подмножество: для каждого числа x от 1 до N подадим его следующим и посмотрим, вырос ли ответ. Вырос - числа x в потоке не было, не вырос - было. Значит, разным подмножествам соответствуют разные состояния памяти. Подмножеств 2ᴺ, а состояний у s бит только 2ˢ: получается s ≥ N. Точный счёт различных требует по биту на каждый возможный элемент - то есть помнить всё. Для точной медианы довод похож: после любой уже пришедшей части поток можно продолжить так - добавив много больших или много малых чисел, - что медианой целого окажется любой из пришедших элементов, поэтому забыть нельзя ни один.

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

У сводок есть ещё одно свойство, которое отличает удобные от неудобных. Сводка объединяема, если из сводок двух частей данных получается сводка всех данных - такая же, как если бы весь поток прошёл через одну. Сумма объединяется сложением, наименьшее - минимумом, фильтр Блума - побитовым ИЛИ, HyperLogLog - максимумом ячеек.

Правило

Потоковый алгоритм: один проход, память много меньше потока, малое время на элемент. Точно за постоянную память считаются количество, сумма, наименьшее и наибольшее, среднее и дисперсия. Точное число различных элементов требует памяти порядка числа возможных значений, точная медиана - порядка самих данных. Приближённый алгоритм задаётся парой ε, δ: ошибка не больше ε с вероятностью не меньше 1 − δ. Объединяемая сводка позволяет считать по частям и на разных машинах.

Разбор: среднее и дисперсия за один проход

Пять тысяч случайных чисел от 1 до 100. Программа ведёт пять переменных состояния. Ради проверки числа дополнительно складываются в список, и во второй части всё пересчитывается обычным способом в два прохода.

import random

random.seed(51)
n = 0
srednee = 0
nakopleno = 0
naimenshee = 1000000
naibolshee = 0
kopiya = []
for i in range(5000):
    x = random.randint(1, 100)
    kopiya.append(x)
    n = n + 1
    otklonenie = x - srednee
    srednee = srednee + otklonenie / n
    nakopleno = nakopleno + otklonenie * (x - srednee)
    naimenshee = min(naimenshee, x)
    naibolshee = max(naibolshee, x)
print(n, round(srednee, 4), round(nakopleno / n, 4), naimenshee, naibolshee)

tochnoe_srednee = sum(kopiya) / len(kopiya)
summa_kvadratov = 0
for x in kopiya:
    summa_kvadratov = summa_kvadratov + (x - tochnoe_srednee) ** 2
print(round(tochnoe_srednee, 4), round(summa_kvadratov / len(kopiya), 4))

5000 50.7998 836.0389 1 100
50.7998 836.0389

Среднее 50,7998 и дисперсия 836,0389 совпали с пересчётом по списку до четвёртого знака. Состояние потокового варианта - пять чисел, и осталось бы пятью числами для миллиарда элементов.

Порядок двух строк в цикле важен: otklonenie считается от старого среднего, затем среднее обновляется, и вторая скобка x − srednee берётся уже от нового. Если обе скобки взять от одного и того же среднего, дисперсия получится неверной.

Разбор: пропущенное число и граница точных приёмов

В поток пришли все числа от 1 до 1000, кроме одного, в случайном порядке. Какого нет? Хранить отметки о виденных числах - тысяча бит. Можно обойтись одним числом.

import random

random.seed(52)
n = 1000
chisla = list(range(1, n + 1))
random.shuffle(chisla)
propushchennoe = chisla.pop()

summa = 0
svertka = 0
for x in chisla:
    summa = summa + x
    svertka = svertka ^ x

polnaya_svertka = 0
for x in range(1, n + 1):
    polnaya_svertka = polnaya_svertka ^ x
print(propushchennoe, n * (n + 1) // 2 - summa, polnaya_svertka ^ svertka)

275 275 275

Два способа, оба нашли 275. Первый: сумма всех чисел от 1 до n известна заранее, n(n + 1) / 2, и разность с суммой потока - пропущенное число. Второй: исключающее ИЛИ всех чисел потока и всех чисел от 1 до n; каждое присутствующее число встречается дважды и гасит себя, остаётся отсутствующее.

Приём обобщается ровно настолько, насколько хватает уравнений. Для двух пропущенных чисел нужны два значения - например, сумма и сумма квадратов, - и из них решается система. Для k пропущенных - k значений. А когда пропущено неизвестно сколько чисел, задача превращается в «какие числа были», и работает доказательство из механизма: нужна память на всё. Точные потоковые приёмы существуют там, где ответ определяется несколькими числами-накопителями, и кончаются там, где ответ зависит от состава потока.

Что ломается без этого

Задачу «посчитать различных» решают множеством. На тестовых данных всё работает, на боевых множество вырастает до гигабайт. Память здесь растёт вместе с данными по доказанной причине, а не из-за неудачной реализации.

Среднее считают как сумму, делённую на количество, в числах с плавающей точкой. При миллиардах слагаемых сумма теряет младшие разряды. Обновление a = a + (x − a) / n держит в памяти число масштаба самих данных и устойчивее.

Сводки, которые не объединяются. Среднее без количества объединить нельзя: среднее двух средних - не среднее всех данных, если части разного размера. Объединяется пара «среднее и количество» или «сумма и количество».

Второй проход «на всякий случай». Алгоритм, которому нужно вернуться к началу, - не потоковый. Сетевой трафик, журнал событий, показания датчиков второй раз не придут.

Зачем это в работе

Мониторинг. Счётчики запросов, суммарное время, наибольшая задержка за интервал - классические однопроходные величины; их считает каждый сервер и складывает сборщик метрик, потому что они объединяются. Число уникальных пользователей и 99-й перцентиль времени ответа - значение, быстрее которого обслужены 99% запросов, - так не складываются, и для них сборщики используют приближённые сводки из этой и соседних глав.

Обработка данных, которые не помещаются в память: файл в сотни гигабайт читают один раз подряд, потому что последовательное чтение на порядки быстрее случайного доступа. Алгоритм, которому хватает одного прохода и килобайтов состояния, работает на ноутбуке там, где «загрузить всё и посчитать» требует кластера.

Распределённый счёт. Данные лежат на сотне машин; каждая строит сводку своей части, координатор объединяет сто сводок. По сети едут килобайты вместо терабайтов. Требование объединяемости появляется именно отсюда.

Теперь сам

1. Среднее первых четырёх элементов потока равно 10. Пятым пришло число 20. Чему равно новое среднее по формуле обновления?
2. Одна машина обработала 100 элементов со средним 30, другая - 300 элементов со средним 50. Чему равно среднее всех четырёхсот?
3. В поток пришли числа от 1 до 100, кроме одного; сумма потока равна 4987. Какого числа нет?
4. Алгоритм точно считает число различных элементов среди чисел от 1 до миллиона. Сколько бит памяти ему нужно в худшем случае?
5. Какие из величин можно получить объединением сводок двух серверов без потери точности: наибольшее значение, количество элементов, медиана?