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кб памяти. Против гигабайта в фильтре блума.
где вы это прочитали? фильтр Блума тем и прекрасен, что не требует 1Гб памяти чтобы хранить информацию об 1 млрд встреченнных уникальных объектов.
А чем эта структура отличается от обычной hashmap?
Спасибо за статью!
Это означает, что каждый раз, когда маршрутизатор получает пакет на скорости более 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вует»;
Что такое фильтр Блума?