У каждого разработчика есть набор инструментов для решения различных задач. Однако со временем возникает необходимость расширять этот набор, чтобы эффективно справляться с более сложными задачами. В этой статье я хочу познакомить вас с инструментом, которым вы, скорее всего, раньше не пользовались. И хотя он подходит для решения узкого спектра задач, его использование может оказаться весьма полезным. Знакомьтесь — "фильтр Блума" (Bloom filter).
Всем доброго дня.
Мы запустили новый курс — «Алгоритмы для разработчиков», предназначенных для тех подтянуть знания по разнообразным структурам и алгоритмам обработки данных, решению алгебраических задач и задач динамического программирования для различных языков. Так что сегодня мы делимся небольшой заметкой о работе фильтра Блума в Java.
Введение
В этой статье мы рассмотрим структуру фильтра Блума из библиотеки Guava. Фильтр Юлума — это вероятностная структура данных с эффективным использованием памяти, которую мы можем использовать для ответа на вопрос “Содержится ли данный элемент в множестве?”.
В фильтре Блума не бывает ложноотрицательных, поэтому, если он возвращает false, можно быть уверенным на 100%, что этого элемента в множестве нет.
Однако, фильтр Блума может возвращать ложноположительные, поэтому по возвращении true высока вероятность, что элемент действительно есть в множестве, но вероятность не 100%.
Чтобы узнать подробнее о работе фильтра Блума, ознакомьтесь с этим руководством.
На хабре уже немало рассказано про фильтр Блума. Напомню, что это структура данных, которая позволяет проверить принадлежность элемента ко множеству, не храня при этом сам элемент. Существует вероятность ложно-положительного ответа, но отрицательный ответ всегда достоверен. В фильтре с точностью 1% требуется всего лишь несколько бит на элемент.
Эта структура часто применяется для ограничения числа запросов к хранилищу данных, отсекая обращения за элементами, которых там заведомо нет. Кроме того, её можно применять для примерного подсчёта числа уникальных событий, пользователей, просмотров и т.д. Больше примеров интересных применений.
Однако есть трудности, которые могут сдерживать веб-разработчиков от применения фильтра Блума.
Читать полностью »
Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.
Грубо говоря, фильтр Блума возвращает 2 возможных ответа:
Блум проанализировал вероятность таких ошибочных ответов, но его анализ является некорректным.
Читать полностью »
Это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложно-положительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложно-отрицательное.
Это способ проверки существования элемента в огромной выборке.
Читать полностью »
Эта статья написана по мотивам одноименного доклада на Highload++'2012. Предназначена она для руководителей, которые смогут, взглянув на наше тестирование, сравнить его с тестированием в своем проекте, для программистов и системных администраторов, которым представится возможность посмотреть на тестирование как на очень интересную работу, и, конечно, для тестировщиков.
В статье я расскажу, о том, каким на самом деле может быть тестирование, как мы сделали тестирование продуктивной и интересной работой, какие задачи мы решаем, и почему работать у нас хорошо.
Читать полностью »
