При проектировании больших масштабируемых систем эта идея очень поможет.
Как вы можете проверить, является ли элемент членом чрезвычайно большого набора данных? Возьмем, к примеру, свой аккаунт на Medium. На Medium миллионы пользователей. Итак, когда новый пользователь пытается создать имя пользователя, как Medium может проверить, существует ли уже это имя пользователя? Если бы поиск по всем именам пользователей был бы чрезвычайно дорогим. Для небольших наборов вы можете использовать HashSet для поиска. Однако перед поиском вам придется загрузить весь этот набор данных в память. Это будет медленно и дорого. Так как же простым и экономичным способом проверить, является ли элемент членом очень большого набора данных?
Ниже приведен отрывок из моего ежедневного информационного бюллетеня Простые технологии — ответ на этот вопрос. Сообщение было скопировано, чтобы дать вам представление о том, на что похож информационный бюллетень. Если вам интересно больше таких произведений, подпишитесь на рассылку. Подробности в конце.
Представьте, что у вас есть очень большой набор данных. Много-много членов, причем каждый член очень сложен. Возможно, ваша платформа социальных сетей взлетела, и у вас есть миллионы пользователей с причудливыми именами (и даже более сложными идентификаторами пользователей).
Теперь каждый раз, когда вы хотите проверить, является ли новый идентификатор частью набора, что вы будете делать? LinkedList и Arrays будут слишком медленными. Попытки нужно будет постоянно обновлять и балансировать, что делает их проблематичными. Почему бы не попробовать карты/наборы Hash? Все всегда говорят, что у них O(1) вставка, поиск и т.д.
Однако вспомните статью о хешировании, которую мы сделали. Помните, что хэши реализованы поверх массивов. Если бы вам приходилось каждый раз обращаться к базовому хранилищу, ваши расходы взлетели бы до небес. Помните, что хранение больших объемов данных обходится дешево. Загрузка его для работы обходится намного дорожеr. Итак, как мы можем проверить членство, не убивая наши финансы? Об этом мы и узнаем.
Плодовые мушки используют модифицированную версию фильтров Блума для обнаружения новизны запахов с дополнительными функциями, включая сходство нового запаха с запахом ранее испытанных экземпляров и время, прошедшее с момента предыдущего восприятия того же запаха.[11]
– Это первый пример использования фильтра Блума в Википедии.
Основные моменты
- Что такое фильтры Блума.Фильтры Блума – это вероятностные структуры данных, предназначенные для эффективной проверки членства.
- Как они работают (вставка) –Имейте битовый массив размера m (все значения инициализированы до 0). Есть k хэш-функций, каждая из которых сопоставляется со значениями индекса в массиве (начиная с 0-(m-1) ). Получив ввод, пропустите его через все хеш-функции. Это дает нам k различных значений. Просмотрите массив и установите все индексы равными 1.
- Запросы – получение входных данных, прохождение через наши k функций. Если какой-либо из индексов имеет значение 0, то мы не видели этот ввод.
- Ложные срабатывания/отрицательные результаты — фильтры Блума являются вероятностными. Они могут сообщить вам, что элемент вероятно находится в хранилище. Иногда они говорят «да» элементам, которых не существует. У них нет ложноотрицательных результатов. Они никогда не скажут элемент DNE, если это так.
- Регенерация.По мере того, как мы начинаем добавлять больше значений, частота ложных срабатываний будет расти. В конце концов, каждый запрос вернет true. Как только наш фильтр заполнится до предела, имеет смысл создать фильтр большего размера или заменить его. Забавный факт: фильтр любого фиксированного размера можно использовать для бесконечного числа элементов. Не делайте этого, оставьте это как пустяки.
- Хранение. Фильтры Блума на самом деле не хранят элементы в базе данных. Вам нужно что-то еще для этого. Они просто удешевляют процесс поиска. Компромисс в том, что мы будем
Фильтры Блума — одна из самых важных структур данных, реализуемых в настоящее время. Существует множество вариантов фильтра, каждый из которых предназначен для решения определенных задач. Например, Сети доставки контента используют их для оптимизации хранилища, используемого в кеше.
Фильтры Блума — отличный инструмент в вашем наборе инструментов. Независимо от того, являетесь ли вы разработчиком программного обеспечения, пытающимся создать удивительно масштабируемые системы, инженером по машинному обучению, ищущим простой способ проверить сходство между двумя векторами поведения пользователя, или бэкэнд-братом, стремящимся оптимизировать протоколы поиска и запросов, фильтры Блума помогут вам. быть очень полезным для ваших нужд.
Чтобы узнать больше о подобных статьях, ознакомьтесь с моим информационным бюллетенем Интервью по технологиям — это просто. Tech Made Simple — лучший ресурс для людей, которые хотят построить блестящую карьеру в сфере технологий. Это поможет вам концептуализировать, создавать и оптимизировать ваши решения. Он охватывает все: от технических аспектов, от проектирования систем, концепций информатики и решения проблем Leetcode до подробных руководств по работе в сети и построению вашей карьеры. Сэкономьте свое время, усилия и деньги, найдя все необходимое в одном месте. Используйте ссылку здесь, чтобы получить скидку 20 % на срок до целого года.
Я создал Технологические интервью, сделанные просто, используя новые методы, полученные в результате обучения нескольких людей в ведущих технологических компаниях. Информационный бюллетень предназначен для того, чтобы помочь вам добиться успеха, избавив вас от часов, потраченных впустую на работу с Leetcode. У меня есть политика 100% удовлетворенности, поэтому вы можете попробовать ее без риска для себя. Вы можете прочитать FAQ и узнать больше здесь
Не стесняйтесь обращаться, если у вас есть какие-либо интересные работы/проекты/идеи для меня. Всегда рад вас выслушать.
Для денежной поддержки моей работы следуют мои Venmo и Paypal. Любая сумма приветствуется и очень помогает. Пожертвования открывают эксклюзивный контент, такой как анализ бумаги, специальный код, консультации и специальные тренировки:
Венмо: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Свяжитесь со мной
Воспользуйтесь ссылками ниже, чтобы ознакомиться с другим моим контентом, узнать больше о репетиторстве или просто поздороваться. Кроме того, ознакомьтесь с бесплатной реферальной ссылкой Robinhood. Мы оба получаем свободный сток (денег вкладывать не надо), и никакого риска для вас нет. Таким образом, если вы не используете его, вы просто потеряете бесплатные деньги.
Ознакомьтесь с другими моими статьями на Medium. : https://rb.gy/zn1aiu
Мой Ютуб: https://rb.gy/88iwdd
Свяжитесь со мной в LinkedIn. Подключаемся: https://rb.gy/m5ok2y
Мой Инстаграм: https://rb.gy/gmvuy9
Мой Твиттер: https://twitter.com/Machine01776819
Если вы готовитесь к программированию/техническим интервью: https://codinginterviewsmadesimple.substack.com/
Получите бесплатный сток на Robinhood: https://join.robinhood.com/fnud75
