Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.
- Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
- Всех возможных адресов
. Столько памяти на роутере нет.
Задача. Есть последовательность целых чисел
Я расскажу вероятностный приближенный алгоритм Флажолета-Мартина. ТТХ алгоритма:
- использует
памяти!
- работает на любом входе;
- находит ответ, который отличается от точного не более чем в 3 раза с вероятностью
:
вероятность берется по случайным битам алгоритма.
В конце поста я расскажу, почему точные детерминированные алгоритмы требуют
Алгоритм Флажолета-Мартина
Представим, что у нас есть отрезок действительных чисел
Можно предположить, что точки разделят отрезок на
Пусть кто-то кинул случайно несколько точек на отрезок, и
Идея алгоритма Флажолета-Мартина — случайно бросить все числа последовательности
2-независимые хэш-функции
Бросать числа на отрезок мы будем с помощью случайной хэш-функции.
Определение. Семейство хэш-функций
Смысл определения в следующем. Зафиксируем два каких угодно ключа
Ключи — различные. Посмотрим на случайные величины
Как следствие, если взять всего один ключ
Для примера возьмем простое число
для
Поскольку
Поймем два важных момента. Во-первых, хранение такой функции обходится в
В тестовом коде я буду использовать поле Галуа
Алгоритм
Пусть
Перед стартом, алгоритм случайно выбирает хэш-функцию
Будем бросать элементы последовательности на отрезок
Обозначим через
Ответ алгоритма:
def init():
h = H.sample()
z = 0
def process(a):
z = max(z, zero(h(a))
def answer():
return 2**(z + 0.5)
Анализ
Я планирую показать, что ответ алгоритма будет в 3 раза больше верного с вероятностью меньшей
Обозначим через
Для анализа алгоритма, нам потребуются два набора случайных величин.
. Принимает значение 1, если количество лидирующих нулей в двоичной записи
хотя бы
; иначе —
.
. Величина
больше нуля, если переменная
по завершении алгоритма оказалась не меньше
.
Заметим, что вероятность
Значит, матожидание
Заметим, что дисперсия по величинам
Поскольку
Более того,
Теперь рассмотрим величину
по линейности матожидания.
по линейности дисперсии для 2-независимых величин.
Пусть
Пусть
Финальный аккорд: медиана
Осталось понять как понизить ошибку. Возьмем случай, когда алгоритм выдает слишком большой ответ. Запустим алгоритм параллельно
Почему медиана так работает? По неравенству Чернова. Заведем случайную величину
Если медиана
где
Нижняя оценка для точного алгоритма
Давайте представим, что кто-то действительно придумал детерминированный алгоритм, который в один проход находит точное число различных элементов в один проход. Мы покажем, что такой алгоритм должен использовать
Возьмем множество
Из одной только памяти алгоритма можно извлечь все множество
Различных подмножеств из
Что почитать
Комментарии (12)
impwx
28.07.2015 16:09+13Из постановки задачи никак не следует, что для нее допустимо решение с погрешностью 300%.
SeptiM Автор
28.07.2015 16:16Не следует. Задача определяет цель, к которой мы стремимся. В следующем абзаце я анонсирую, что будет рассказано. В частности, что в точной формулировке задача не имеет решения.
В конце поста я расскажу, почему точные детерминированные алгоритмы требуют
памяти.
SeptiM Автор
28.07.2015 16:18Немного оффтоп, но… Чем для вас является точность? Абсолютная цель или ресурс, которым можно пожертвовать?
impwx
28.07.2015 16:41+3Не поймите меня неправильно, я ни в коем случае не оспариваю необходимость вероятностных алгоритмов, но чем является точность — зависит не от моего личного мнения, а только от задачи. Если нужно показать красивый график — конечно, она не так важна. А если, например, по результатам этого подсчета будет составляться план модернизации сети и закупаться оборудование — то сами понимаете, троекратная переплата может оказаться неприемлемой.
SeptiM Автор
28.07.2015 16:53+4Ага, т.е. вас больше всего беспокоит то, что алгоритм гуляет с 300% ошибкой, которую еще и нельзя регулировать. Это действительно проблема, но решаемая.
Есть усиление этого алгоритма, которое для произвольноговозвращает ответ в пределах
с вероятностью
и использует памяти примерно
. Можно посмотреть тут. Я думал про неё написать, но пост будет перегруженным.
Если будет большой интерес, могу написать пост про усиление.
ishevchuk
28.07.2015 23:14Спасибо за статью!
Совершенно случайно не знаете, используют ли какие-то сетевые железки именно этот алгоритм для подсчета количества соединений?
И если да, то какие?SeptiM Автор
29.07.2015 00:35Спасибо вам! :)
У меня нет знакомых железячников, но в целом, когда речь заходит о поиске аномалий в сетевом траффике на этот результат ссылаются. Причем ссылаются скорее как на первичную идею, которую потом активно допиливали. Обычно используют HyperLogLog или что-то близкое к нему.
Знаю соц. сеть, которая считает лайки HyperLogLog-ом. =)
AlexWinner
29.07.2015 06:50Считаем им уникальных посетителей (правда, сами не реализовывали, просто грузим лог в ElasticSearch, по примерно 1млрд запросов в сутки).
EighthMayer
Прошу прощения, вопрос скорее всего очень глупый (учитывая что я не понял почти ничего из того, что ниже хабраката), но если исходить из «пары проблем», то почему-бы не использовать битовую маску на 2^32 (4294967296) бита (512 мегабайт), где каждый бит соответствует одному адресу?
Если адреса в массиве не уникальны, то можно использовать ещё одну такую-же маску (+512 мегабайт) чтобы полностью обойти это ограничение.
ripatti
Представьте, что у вас нет 512 Мб, а есть только 1 Кб.
SeptiM Автор
Да, можно, но такой метод требует слишком много памяти. Идея в том, как пожертвовать немного точностью, чтобы получить алгоритм, который использует всего пару килобайт. Кроме того, если длина адреса вырастет до 64 бит, первый метод совсем отвалится.