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