Pull to refresh

Comments 22

Предлагаю под этим комментарием давать названия и ссылки на другие «вероятностные» структуры данных, которые могут быть полезны.

Спасибо всем ниже написавшим.

Самая крышесносная на мой взгляд это HyperLogLog. Позволяет посчитать количество уникальных объектов (не точно, с парой процентов погрешности) используя всего пару килобайт памяти.

Откровенно говоря, с помощью фильтра Блума и счетчика можно сделать тоже самое.

— Сам себе отвечаю. Список алгоритмов из моего же вопроса на Тостере: qna.habr.com/q/91971

Здесь буду собирать ссылки на вероятностные алгоритмы:
1. Фильтр блума ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D
2. MinHash habrahabr.ru/post/115147
3. LogLog habrahabr.ru/post/119852
4. habrahabr.ru/post/250673 — Поиск похожих документов с MinHash + LHS
5. en.wikipedia.org/wiki/Count%E2%80%93min_sketch — приближенный сбор частот событий в потоке.
Откровенно говоря, с помощью фильтра Блума и счетчика можно сделать тоже самое.

Конечно же нет.


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


А во-вторых потребляемый объем памяти разительно отличается. Как я писал ниже, фильтр блума требует O(n) памяти. Допустим у нас 1 милиард уникальных объектов, это порядка гигабайта памяти если выделить в среднем по одному байту на объект (но лучше по 2 байта).
А теперь сравниваем с HyperLogLog, на вики пишут про 1.5 килобайта при средней ошибке в 2%. В реальности при таких вводных ошибка частенько будет больше 5%. Например, чтобы почти всегда ошибка была в пределах 1% (но в большинстве случаев меньше) нужно около 20кб памяти. Против гигабайта в фильтре блума.

> фильтр блума требует O(n) памяти. Допустим у нас 1 милиард уникальных объектов, это порядка гигабайта памяти

где вы это прочитали? фильтр Блума тем и прекрасен, что не требует 1Гб памяти чтобы хранить информацию об 1 млрд встреченнных уникальных объектов.

А сколько требует? Мне даже стало интересно ваше мнение.
Разберитесь еще раз с алгоритмом и аккуратно подумайте про заполнение битового массива в случайных позициях и вероятности попадать на единички при false positive.
Если не получится придумать, то я подскажу как нагуглить в википедии.

Ок. Моя ошибка.
На самом деле у автора в формуе вероятности коллизии минус пропущен.

А чем эта структура отличается от обычной hashmap?

hashmap хранит элементы. И если возникает коллизия, то дальше будут смотреться все элементы в bucket'е, а это либо o(n) либо n(log(n)) сложность, где n — количество элементов в bucket'е (тех у кого совпал хеш) (зависит от реализации, обычно такие числа). Зато можно сказать и что элемента нет в списке и что элемент есть. Здесь можно только сказать что элемента нет, но зато сложность o(1).

Если в фильтре блума возникают коллизии, то еще не известно что хуже работать будет.

Там будут ложноположительные ответы, т.е. хуже будет в другом смысле.
Странное дело, с хэш-таблицами знаком лет 15, но только сейчас узнал о существовании такого изящного «облегчённого» алгоритма.

Спасибо за статью!
Некоторый недостаток этой статьи в том, что тут не указано, что фильтр блума обладает еще двумя хорошими свойствами — он легко объединяется, как по and, так и по or. А это означает, что его можно хорошо параллелить. И для реально больших данных это делает его еще более полезным.
Вспоминается пост в RU.JAVA «Шиков говорил это еще 5 лет назад» :)
Никогда бы не подумал, что кто-то меня помнит по ru.java )
Это означает, что каждый раз, когда маршрутизатор получает пакет на скорости более 100 Гбит/с, он должен обращаться к своей памяти и выполнять в лучшем случае логарифмический поиск (O(log(n)))

Это не правда, хеш таблица работает в среднем за O(n). Коллизии можно уменьшать разными методами, например так. Так что по скорости тут выигрыша особо и нет, как мне кажется.


По памяти фильтр блума, конечно, меньше (обычно в разы или даже в десятки раз), но это все еще O(n), как и в хеш таблице. Условно говоря, для фильтра блума желательно выделить хотя бы 2 байта на объект, а хеш таблицу можно ужать до 16 байт на объект.

У фильтра Блума есть еще одно неприятное свойство.
Если мы ожидаем определенное количество уникальных объектов и у нас есть требования к вероятности ложноположительных срабатываний, то мы можем расчитать количество требуемой памяти и количеству хеш функций. Так вот, если памяти не выделить с запасом, а уникальных объектов положить больше, чем планировали, то начиная с какого-то момента вероятность ложноположительных срабатываний растет катастрофически.

Но, ведь, увеличение числа хэш-функций увеличит число единиц в массиве.
Если у нас занесен в массив 1 IP, то ложных срабатываний не будет. А если 10?
Но, ведь, увеличение числа хэш-функций увеличит число единиц в массиве.

Верно.


Если у нас занесен в массив 1 IP, то ложных срабатываний не будет.

Не верно.


Допустим, мы выделили массив из 100 бит. Рассмотрим на пальцах случаи:


  • 1 хеш функция. Тогда при добавлении одного элемента у нас 1 единица и 99 нулей. Вероятность ложного срабатывания = 1 / 100.
  • 2 хеш функции. При добавлении одного элемента скорее всего они дадут разные значения и мы установим 2 единицы и 98 нулей. Ложноположительное срабатывание возможно тогда, когда обе хеш функции (независимые) у нового элемента попадут в эти единицы. Вероятность такого события = (2 / 100) ^ 2 = 4 / 10000 = 1 / 2500.

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


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


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

А если разные хэши класть не в одну таблицу, а в разные?
Мне видится, что можно просчитать компромиссное решение решение. Например, уменьшив размер таблиц в 2 раза и увеличив их количество в 2 раза.

Если прикинуть, кол-во записей например по 64 на таблицу (6-бит), то 4 хэша дадут общий индекс на 4 таблицы в 3 (24бит) байта, а общее кол-во элеменов во всех таблицах всего 256, при более чем 16млн возможных вариантах индекса.

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

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


Давайте посмотрим еще раз на пример, таблица из 100 битов, 2 хеш функции, и положем в нее одно значение. Допустим хеши получились разные и мы установим 2 единицы из 100. Вероятность false positive = (2 / 100) ^ 2 = 4 / 10000 = 1 / 2500.


Если я правильно понимаю, то Вы предлагаете вместо одной таблицы размера 100 использовать 2 таблицы по 50, по одной на хеш функцию. Тогда при добавлении одного элемента мы поставим по одной единичке в каждой из таблиц. Вероятность false positive = (1 / 50) ^ 2 = 1 / 2500.


Вроде бы то же самое. НО! В оригинальном алгоритме значения хешей могут совпасть (с вероятностью 1/100 в нашем случае) и мы установим в массив 1 единичку, а не 2. В этом случае вероятность false positive = (1 / 100) ^ 2 = 4 / 10000. Т.е. в среднем оригинальный алгоритм дает лучший результат, чем Ваша модификация. И это при добавлении всего одного элемента.


При добавлении большего количества элементов вероятность колизий (попаданий на уже установленую 1) будет расти и тем самым уменьшать суммарное количество единиц во всем массиве. А это уменьшает вероятность false positive.

Иными словами это обычный

auto filterBloom = new std::set(hash_function);

выбирате crc8, 16, 24, 32, 48, 64 (влияющие на обьем)
и проверяете: if( filter == filter.end() ) std::cout << «значение отсутcвует»;
Sign up to leave a comment.