Pull to refresh
  • by relevance
  • by date
  • by rating

Фильтр Блума

Algorithms *
И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

Как фильтр это делает?
Total votes 88: ↑85 and ↓3 +82
Views 52K
Comments 36

Тестирование в Mail.Ru Group

VK corporate blog IT systems testing *
Эта статья написана по мотивам одноименного доклада на Highload++'2012. Предназначена она для руководителей, которые смогут, взглянув на наше тестирование, сравнить его с тестированием в своем проекте, для программистов и системных администраторов, которым представится возможность посмотреть на тестирование как на очень интересную работу, и, конечно, для тестировщиков.

В статье я расскажу, о том, каким на самом деле может быть тестирование, как мы сделали тестирование продуктивной и интересной работой, какие задачи мы решаем, и почему работать у нас хорошо.
Читать дальше →
Total votes 112: ↑76 and ↓36 +40
Views 40K
Comments 32

Количество ложно-положительных срабатываний фильтра Блума [перевод]

Algorithms *Mathematics *
Sandbox

Количество ложно-положительных срабатываний фильтра Блума.


Описание

Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.

Грубо говоря, фильтр Блума возвращает 2 возможных ответа:
  1. элемента нет в векторе
  2. элемент возможно есть в векторе


Блум проанализировал вероятность таких ошибочных ответов, но его анализ является некорректным.
Читать дальше →
Total votes 31: ↑26 and ↓5 +21
Views 6.8K
Comments 5

Фильтр Блума для веб-разработчиков

High performance *Website development *Algorithms *
На хабре уже немало рассказано про фильтр Блума. Напомню, что это структура данных, которая позволяет проверить принадлежность элемента ко множеству, не храня при этом сам элемент. Существует вероятность ложно-положительного ответа, но отрицательный ответ всегда достоверен. В фильтре с точностью 1% требуется всего лишь несколько бит на элемент.

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

Однако есть трудности, которые могут сдерживать веб-разработчиков от применения фильтра Блума.
Читать дальше →
Total votes 17: ↑15 and ↓2 +13
Views 16K
Comments 11

Фильтр Блума в Java с помощью Guava

OTUS corporate blog Programming *Java *Algorithms *
Translation
Всем доброго дня.

Мы запустили новый курс — «Алгоритмы для разработчиков», предназначенных для тех подтянуть знания по разнообразным структурам и алгоритмам обработки данных, решению алгебраических задач и задач динамического программирования для различных языков. Так что сегодня мы делимся небольшой заметкой о работе фильтра Блума в Java.

Введение

В этой статье мы рассмотрим структуру фильтра Блума из библиотеки Guava. Фильтр Блума — это вероятностная структура данных с эффективным использованием памяти, которую мы можем использовать для ответа на вопрос “Содержится ли данный элемент в множестве?”.

В фильтре Блума не бывает ложноотрицательных, поэтому, если он возвращает false, можно быть уверенным на 100%, что этого элемента в множестве нет.

Однако, фильтр Блума может возвращать ложноположительные, поэтому по возвращении true высока вероятность, что элемент действительно есть в множестве, но вероятность не 100%.

Чтобы узнать подробнее о работе фильтра Блума, ознакомьтесь с этим руководством.

Читать дальше →
Total votes 26: ↑19 and ↓7 +12
Views 5.5K
Comments 4

Когда фильтр Блума не подходит

Search engines *Programming *Client optimization *Algorithms *Server optimization *
Translation


Я ещё с университета знал о фильтре Блума — вероятностной структуре данных, названной в честь Бёртона Блума. Но у меня не было возможности её использовать. В прошлом месяце такая возможность появилась — и эта структура буквально очаровала меня. Впрочем, вскоре я нашёл у неё некоторые недостатки. В этой статье — рассказ о моей краткой любовной связи с фильтром Блума.
Читать дальше →
Total votes 50: ↑49 and ↓1 +48
Views 14K
Comments 15