Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Хоть и не люблю такого стиля изложения, но статья понравилась, спасибо.
>>Здравствуй, мой маленький любитель алгоритмов.
>>До свидания, мой маленький.
Воспринимается неоднозначно. Но это мое субъективное имхо.
>>До свидания, мой маленький.
Воспринимается неоднозначно. Но это мое субъективное имхо.
Подумалось, что без этого как-то суховато, тем более статья до академического уровня явно не дотягивает. Ничего плохого не имел в виду, чесслово.
Если ориентироваться на людей с повышенным ЧСВ, то придется вообще ничего не писать и не говорить, а заперется в глубоком бункере и молчать в тряпочку, потому что те, у кого ЧСВ выше среднего обижаются вообще на пустом месте:)
А статья интересная, хотелось бы развития темы в плане насколько фильтр блума может ускорить производительность на некоторых типовых задачах. Например, сравнить производительность проверки данных с «длинным ключем» на массивах данных хотя бы сотни тысяч записей без Фильтра Блума и с ним.
Т.е. интересует с практической стороны, что может получить в плане прироста производительности если перед «тяжелой проверкой» (поиск длинного ключа) поставить «легкую проверку» (Фильтр Блума).
А статья интересная, хотелось бы развития темы в плане насколько фильтр блума может ускорить производительность на некоторых типовых задачах. Например, сравнить производительность проверки данных с «длинным ключем» на массивах данных хотя бы сотни тысяч записей без Фильтра Блума и с ним.
Т.е. интересует с практической стороны, что может получить в плане прироста производительности если перед «тяжелой проверкой» (поиск длинного ключа) поставить «легкую проверку» (Фильтр Блума).
И взяли стиль изложения ксакепа ;-)
Исправил от греха подальше :)
Начало и концец — обращение к «маленьким», а вот изложение непростое…
Идея-то может и проста, но вот такое описание я только с восьмого прочтения переваривать начал.
Хэш-функция выдает значение и что? Устанавливается бит с индексом, равным полученному значению? Или в массив записываются биты полученного числа.
Формулы пронумеровать бы… Последнее выражение для «k»… База логарифма какая?
Заводится массив бит фиксированного размера m и набор из k различных хеш-функций, выдающих значения от 0 до m — 1. При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются соответствующие биты.
Идея-то может и проста, но вот такое описание я только с восьмого прочтения переваривать начал.
Хэш-функция выдает значение и что? Устанавливается бит с индексом, равным полученному значению? Или в массив записываются биты полученного числа.
Формулы пронумеровать бы… Последнее выражение для «k»… База логарифма какая?
И вот еще…
«Соответствующие биты» — соответствующие чему? Можно пример небольшой? Хэш-функций много меньше числа бит в массиве. Все биты не будут установлены по получаемым индексам. А если не все, то какие? Шаблон использовать для массива?
достаточно посчитать значения хеш-функций для потенциального члена и убедиться, что все соответствующие биты установлены в единицу — это и будет ответом «возможно». Если же хотя бы один бит не равен единице, значит множество этого элемента не содержит — ответ «нет», элемент отфильтрован
«Соответствующие биты» — соответствующие чему? Можно пример небольшой? Хэш-функций много меньше числа бит в массиве. Все биты не будут установлены по получаемым индексам. А если не все, то какие? Шаблон использовать для массива?
Про индексы поправил. Основание натуральное.
log означает базу 2, но автор намудрил там. Надо было писать ln 2
0 False, 1 True, 2 Maybe?
if maybe a in seq:
pass
Странное ощущение от статьи: вроде каждое предложение по отдельности понятно, а общая картина смысла не складывается.
Есть какой-то алгоритм, есть структуры, есть код, есть формулы оптимальных параметров и даже вроде примерно понятно, зачем это может быть нужно.
Но понимания сути, как же это внутри работает, статья не даёт — а ведь это главное.
Например, про пузырьковую сортировку мне достаточно знать и понимать общий принцип сравнения/обмена соседних элементов, в результате которого за каждый проход наверх «всплывает» одно значение. Имея в голове ясную пошаговую картинку алготитма, код нетрудно «изобрести» самостоятельно.
Есть какой-то алгоритм, есть структуры, есть код, есть формулы оптимальных параметров и даже вроде примерно понятно, зачем это может быть нужно.
Но понимания сути, как же это внутри работает, статья не даёт — а ведь это главное.
Например, про пузырьковую сортировку мне достаточно знать и понимать общий принцип сравнения/обмена соседних элементов, в результате которого за каждый проход наверх «всплывает» одно значение. Имея в голове ясную пошаговую картинку алготитма, код нетрудно «изобрести» самостоятельно.
Хм, я конечно понимаю, что вы старались и все такое, но если честно, статья не очень понравилось.
На Википедии достаточно одного взгляда на картинку, чтобы понять, о чем речь. У вас же тут килобайта 3 текста из которых я так и не понял, зачем нужно _несколько_ хэш-функций.
На Википедии достаточно одного взгляда на картинку, чтобы понять, о чем речь. У вас же тут килобайта 3 текста из которых я так и не понял, зачем нужно _несколько_ хэш-функций.
Интересно. Хотелось бы, конечно, оценок эффективности, особенно по сравнению с одной хэш-функцией и с отдельным массивом для каждой хэш-функции. Как я понимаю, «фишка» этой реализации в том, что благодаря случайному распределению хэшей при оптимальных параметрах эффективность выше, чем если бы массив был отдельный для каждой хэш-функции.
Честно говоря, долго пытался придумать пример наглядно показывающий, почему при одном массиве и нескольких функциях эффективность выше, чем при одном массиве и одной функции. Ни одной интуитивно понятной аналогии мне так в голову и не пришло, поэтому решил об этом не писать.
Фишка в том, что при заданной вероятности ложного срабатывания, одной функии и конечном кол-ве элементов, которые предполагается запомнить фильтром, эффективность фильтра ниже, поскольку все те «избыточные» биты, которые были введены для удерживания кол-ва ошибок выше определённого потолка, «никак» не используются.
Если ввести вторую функцию, то эти «неиспользуемые» биты разделяются между ними, при этом кол-во необходимых бит на ключ растёт линейно, а точность экспоненциально.
Фишка в том, что при заданной вероятности ложного срабатывания, одной функии и конечном кол-ве элементов, которые предполагается запомнить фильтром, эффективность фильтра ниже, поскольку все те «избыточные» биты, которые были введены для удерживания кол-ва ошибок выше определённого потолка, «никак» не используются.
Если ввести вторую функцию, то эти «неиспользуемые» биты разделяются между ними, при этом кол-во необходимых бит на ключ растёт линейно, а точность экспоненциально.
Плин, «ниже определённого потолка».
После прочтения статьи на википедии сложилось такое «наглядное» представление назначения такой структуры данных:
есть много серверов, которые содержат key-value пары. Для выборки значения по ключу Key мы отправляем запрос на каждый сервер. Без подобного фильтра каждый сервер выполняет полноценный поиск по своему индексу — и эта операция довольно дорогая и будет выполнена на каждом сервере!
Фильтр Блума позволяет с малыми затратами ресурсов выяснить, что этот ключ может быть на 2-х серверах из 10-и — и отправить полноценный запрос лишь на эти два сервера.
Т.о. вопрос «зачем» для меня решен, а «как» — при необходимости приложится.
есть много серверов, которые содержат key-value пары. Для выборки значения по ключу Key мы отправляем запрос на каждый сервер. Без подобного фильтра каждый сервер выполняет полноценный поиск по своему индексу — и эта операция довольно дорогая и будет выполнена на каждом сервере!
Фильтр Блума позволяет с малыми затратами ресурсов выяснить, что этот ключ может быть на 2-х серверах из 10-и — и отправить полноценный запрос лишь на эти два сервера.
Т.о. вопрос «зачем» для меня решен, а «как» — при необходимости приложится.
Почитал, на сколько я понял, фильтр Блума там используется для быстрой проверки на отсутствие слова в словаре исключений. А сами словари в виде trie представлены.
Если я правильно понял, алгоритм эффективен только при определенных обстоятельствах.
Допустим, мы хотим, чтобы наша реализация фильтра Блума отвечала на вопрос принадлежности с пятидесятипроцентной точностью. Тогда оптимальная длина вектора:
m = n* (-ln(0.5)/ln(2)^2) ~ 1.44*n
Но если мы возьмем вектор длинны n (в полтора раза меньший!) то можем просто хранить в нем информацию обо всех элементах множества, то есть отвечать на вопрос о пренадлежности со стопроцентной вероятностью. Ну, конечно, если найдем способ отображения наших элементов в множество натуральных чисел: )
Получается, есть смысл применять алгоритм тогда, когда ни отоброжение, ни индексирование элементов невозможно (затруднительно). При этом, чтобы получить 90% вероятность правильного срабатывания алгоритма, нам нужно выделить массиво бит, чья длинна (m ~ 5*n) в пять раз привышает длинну исходного множества элементов (вот! только теперь я понял смысл фразы «чтобы уменьшить нагрузку в 10 раз, необходимо хранить примерно 5 бит информации на каждый ключ.»!: ))
Вы знаете, следовало бы добавить в статью несколько простых примеов, объяснить «на пальцах»: )
Допустим, мы хотим, чтобы наша реализация фильтра Блума отвечала на вопрос принадлежности с пятидесятипроцентной точностью. Тогда оптимальная длина вектора:
m = n* (-ln(0.5)/ln(2)^2) ~ 1.44*n
Но если мы возьмем вектор длинны n (в полтора раза меньший!) то можем просто хранить в нем информацию обо всех элементах множества, то есть отвечать на вопрос о пренадлежности со стопроцентной вероятностью. Ну, конечно, если найдем способ отображения наших элементов в множество натуральных чисел: )
Получается, есть смысл применять алгоритм тогда, когда ни отоброжение, ни индексирование элементов невозможно (затруднительно). При этом, чтобы получить 90% вероятность правильного срабатывания алгоритма, нам нужно выделить массиво бит, чья длинна (m ~ 5*n) в пять раз привышает длинну исходного множества элементов (вот! только теперь я понял смысл фразы «чтобы уменьшить нагрузку в 10 раз, необходимо хранить примерно 5 бит информации на каждый ключ.»!: ))
Вы знаете, следовало бы добавить в статью несколько простых примеов, объяснить «на пальцах»: )
Спасибо автору за то, что сказали о существовании такой штуки а также спасибо всем комментирующим. Отправился в википедию, дошло.
А в этой статье мне стало непонятно на фразе «При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются биты с соответствующими индексами.» ИМХО эту часть стоит перефразировать, действительно пример или картинку/схему.
А в этой статье мне стало непонятно на фразе «При необходимости добавить элемент к множеству, для элемента считается значение каждой хеш-функции и в массиве устанавливаются биты с соответствующими индексами.» ИМХО эту часть стоит перефразировать, действительно пример или картинку/схему.
Использование этих фильтров в сетевом оборудовании
forums.juniper.net/t5/Data-Center-Technologists/Juniper-QFX10002-Technical-Overview/ba-p/270358
раздел
Hybrid Memory Cube and Bloom Filters
forums.juniper.net/t5/Data-Center-Technologists/Juniper-QFX10002-Technical-Overview/ba-p/270358
раздел
Hybrid Memory Cube and Bloom Filters
К сожалению, в данной реализации хеш-функция может возвращать отрицательные значения.
Это приводит к тому, что фильтр Блума использует удвоенный объем памяти (в JS отрицательный индекс массива корректен)…
Это приводит к тому, что фильтр Блума использует удвоенный объем памяти (в JS отрицательный индекс массива корректен)…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Фильтр Блума