Pull to refresh

Сколько чисел в массиве

Reading time4 min
Views18K
Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки 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:


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

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

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


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

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


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

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

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


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

Определение. Семейство хэш-функций 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 будет равномерна распределена по 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 памяти.

Алгоритм


Пусть 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. Принимает значение 1, если количество лидирующих нулей в двоичной записи 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. Ограничим сверху дисперсию


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




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


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

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

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

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


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


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


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


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

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


где 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

Что почитать


  1. «Probabilistic Counting Algorithms for Data Base Applications», Flajolet, Martin, 1983, link.
  2. «The space complexity of approximating the frequency moments», Alon, Matias, Szegedy, 1999, link.
Tags:
Hubs:
Total votes 28: ↑27 and ↓1+26
Comments12

Articles

Information

Website
www.jetbrains.com
Registered
Founded
Employees
501–1,000 employees
Location
Россия