Сколько чисел в массиве28.07.2015 15:48

Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки Markdown + $inline_formula$ в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил пост про LogLog четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на $inline_formula$ , расскажу больше о математике.

Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.

Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
Всех возможных адресов $inline_formula$ . Столько памяти на роутере нет.

some title

Задача. Есть последовательность целых чисел $inline_formula$ , все числа принимают значения от $inline_formula$ до $inline_formula$ . Требуется в один проход посчитать количество различных чисел, используя $inline_formula$ памяти.

Я расскажу вероятностный приближенный алгоритм Флажолета-Мартина. ТТХ алгоритма:

использует $inline_formula$ памяти!
работает на любом входе;
находит ответ, который отличается от точного не более чем в 3 раза с вероятностью $inline_formula$ :
$%0A%5Cmathbf%7BPr%7D%5Cleft%5B%5C%3B%20%$

вероятность берется по случайным битам алгоритма.

В конце поста я расскажу, почему точные детерминированные алгоритмы требуют $inline_formula$ памяти.

Алгоритм Флажолета-Мартина

Представим, что у нас есть отрезок действительных чисел $inline_formula$ . На отрезок мы независимо случайно кидаем $inline_formula$ точек согласно равномерному распределению. Какое будет расстояние между крайней левой точкой и нулем?

Можно предположить, что точки разделят отрезок на $inline_formula$ меньших подотрезков примерно одинаковой длины. Если аккуратно записать матожидание расстояния и взять интеграл, мы получим

$%0A%5Cmathbf%7BE%7D%5Cleft%5B%5C%3B%5Cmi$

Пусть кто-то кинул случайно несколько точек на отрезок, и $inline_formula$ — расстояние от нуля до крайней левой точки. Можно прикинуть, что всего точек порядка $inline_formula$ .

Идея алгоритма Флажолета-Мартина — случайно бросить все числа последовательности $inline_formula$ на отрезок $inline_formula$ , а затем найти расстояние от нуля до крайней левой точки. Если одинаковые числа будут всегда отображаться в одну точку, а разные независимо распределяться по отрезку, мы сможем прикинуть ответ.

2-независимые хэш-функции

Бросать числа на отрезок мы будем с помощью случайной хэш-функции.

Определение. Семейство хэш-функций $inline_formula$ называется 2-независимым, если для любых $inline_formula$ и $inline_formula$

$%0A%5Cmathbf%7BPr%7D_%7Bh%20%5Cleftarrow$

Смысл определения в следующем. Зафиксируем два каких угодно ключа $inline_formula$ и $inline_formula$ .
Ключи — различные. Посмотрим на случайные величины $inline_formula$ и $inline_formula$ . Случайность задается выбором функции $inline_formula$ . Тогда, по определению, величины $inline_formula$ и $inline_formula$ будут вести себя как независимые.

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

Для примера возьмем простое число $inline_formula$ . Пусть $inline_formula$ . $inline_formula$ — это семейство всех линейных отображений по модулю $inline_formula$ :

$h_%7Ba%2C%20b%7D%28x%29%20%3D%20a%20%5Cc$

для $inline_formula$ . Тогда

$%0A%5Cbegin%7Barray%7D%7Bl%7D%0A%5Cmathb$

Поскольку $inline_formula$ , система имеет ровно одно решение среди $inline_formula$ возможных:

$%0A%5Cbegin%7Barray%7D%7Bl%7D%0Aa%20%3D%$

Поймем два важных момента. Во-первых, хранение такой функции обходится в $inline_formula$ памяти, что очень немного. Во-вторых, если внимательно приглядеться, то можно понять, что вычисления проходят в поле $inline_formula$ , и могут быть обобщены для любого конечного поля.

В тестовом коде я буду использовать поле Галуа $inline_formula$ . В описании далее можно считать, что у нас есть семейство хэш-функций $inline_formula$ , где $inline_formula$ — степень двойки. Хранение одной функции занимает $inline_formula$ памяти.

Алгоритм

Пусть $inline_formula$ — степень двойки.
Перед стартом, алгоритм случайно выбирает хэш-функцию $inline_formula$ из 2-независимого семейства.

Будем бросать элементы последовательности на отрезок $inline_formula$ . Берем очередное значение $inline_formula$ и записываем: ноль, точка, $inline_formula$ в двоичном виде. Например, если $inline_formula$ , то получится число $inline_formula$ .

Обозначим через $inline_formula$ число лидирующих нулей в двоичной записи $inline_formula$ . Пусть $inline_formula$ . Мы знаем, что минимальное значение лежит между $inline_formula$ и $inline_formula$ .

Ответ алгоритма: $inline_formula$ .

def init():
        h = H.sample()
        z = 0
        
def process(a):
        z = max(z, zero(h(a))
        
def answer():
        return 2**(z + 0.5)

Анализ

Я планирую показать, что ответ алгоритма будет в 3 раза больше верного с вероятностью меньшей $inline_formula$ . Аналогично, алгоритм вернет ответ в 3 раза меньше верного вероятностью меньшей $inline_formula$ . Если вы не планируете углубляться в математику, смело переходите к следующей части.

Обозначим через $inline_formula$ множество всех различных чисел последовательности $inline_formula$ , а $inline_formula$ — их количество.

Для анализа алгоритма, нам потребуются два набора случайных величин.

Заметим, что вероятность $inline_formula$ : величина $inline_formula$ равномерно распределена по отрезку $inline_formula$ ; $inline_formula$ — степень двойки; есть всего $inline_formula$ чисел с $inline_formula$ лидирующими нулями.

Значит, матожидание $inline_formula$ . Ограничим сверху дисперсию

$%0A%5Cmathbf%7BD%7D%5Cleft%5B%5C%3BX_%7B$

Заметим, что дисперсия по величинам $inline_formula$ линейна. Для любых двух $inline_formula$ и $inline_formula$

$%0A%5Cmathbf%7BD%7D%5Cleft%5B%5C%3BX_%7B$

$%0A%5Cmathbf%7BE%7D%5Cleft%5B%5C%3B%28X_$

$%0A%5Cleft%28%5Cmathbf%7BE%7D%5Cleft%5B%$

Поскольку $inline_formula$ и $inline_formula$ независимы, то $inline_formula$ . Значит,

$%0A%5Cmathbf%7BD%7D%5Cleft%5B%5C%3BX_%7B$

Более того, $inline_formula$ , поскольку величины $inline_formula$ — 2-независимы.

Теперь рассмотрим величину $inline_formula$ .

$inline_formula$ по линейности матожидания.
$inline_formula$ по линейности дисперсии для 2-независимых величин.

Пусть $inline_formula$ — минимальное число такое, что $inline_formula$ . Событие «алгоритм выдал ответ в 3 раза больше нужного» равносильно событию $inline_formula$ и равносильно событию $inline_formula$ . Применяя неравенство Маркова, ограничим вероятность

$%0A%5Cmathbf%7BPr%7D%5Cleft%5B%5C%3BFM%2$

Пусть $inline_formula$ — максимальное число такое, что $inline_formula$ . Аналогично, событие «алгоритм выдал ответ в 3 раза меньше нужного» равносильно событию $inline_formula$ и равносильно событию $inline_formula$ . Применяя неравенство Чебышёва, получим

$%0A%5Cbegin%7Barray%7D%7Bl%7D%0A%5Cmathb$

Финальный аккорд: медиана

Осталось понять как понизить ошибку. Возьмем случай, когда алгоритм выдает слишком большой ответ. Запустим алгоритм параллельно $inline_formula$ раз и вернем медиану среди ответов. Я утверждаю, что если $inline_formula$ , то алгоритм ошибется с вероятностью не больше $inline_formula$ . Аналогично, ограничив ошибку в другую сторону, получим

$%0A%0A%5Cmathbf%7BPr%7D%5Cleft%5B%5C%3BF$

Почему медиана так работает? По неравенству Чернова. Заведем случайную величину $inline_formula$ . Величина $inline_formula$ равна единице, если ответ алгоритма на $inline_formula$ запуске меньше $inline_formula$ . Вероятность этого события не меньше 0.52.

Если медиана $inline_formula$ запусков алгоритма больше $inline_formula$ , то это значит, что алгоритм хотя бы половину раз выдал ответ больший $inline_formula$ и $inline_formula$ . Тогда по неравенству Хефдинга-Чернова

$%0A%5Cmathbf%7BPr%7D%5Cleft%5B%5C%3B%5Cs$

где $inline_formula$ — некоторая константа. Другой случай показывается аналогично.

Нижняя оценка для точного алгоритма

Давайте представим, что кто-то действительно придумал детерминированный алгоритм, который в один проход находит точное число различных элементов в один проход. Мы покажем, что такой алгоритм должен использовать $inline_formula$ памяти.

Возьмем множество $inline_formula$ размера $inline_formula$ и положим его в качестве начала последовательности. Скормим эту часть алгоритму и посмотрим на его память.

Из одной только памяти алгоритма можно извлечь все множество $inline_formula$ . Если скормить в текущем состоянии число $inline_formula$ , ответ алгоритма не изменится; если $inline_formula$ , то увеличится на 1. Значит, каждому множеству $inline_formula$ должно соответствовать свое уникальное состояние памяти.

Различных подмножеств из $inline_formula$ размера $inline_formula$ примерно $inline_formula$ . Если мы хотим каждому множеству сопоставить битовую строку, нам потребуется $inline_formula$

Что почитать

«Probabilistic Counting Algorithms for Data Base Applications», Flajolet, Martin, 1983, link.
«The space complexity of approximating the frequency moments», Alon, Matias, Szegedy, 1999, link.