Вот почему 86-я оригинальная статья

В предыдущей статье я писал о фильтрах Блума:

Ой, эту ужасную типографику невозможно передать словами. …

По сути, написание статей — это то же самое, что написание кода.

Когда я увидел кусок кода горячими глазами, я был готов выплюнуть аромат: Какая плохая ручка написала этот код?

В итоге при ближайшем рассмотрении автором кода оказывается на самом деле он сам.

Я даже не могу в это поверить, но я должен открыть его и взглянуть на запись коммита git.

Я обнаружил, что это действительно был код, который я сам набрал и отправил несколько месяцев назад.

Так молча поменял.

Когда это происходит, я часто успокаиваю себя: все в порядке, это хорошо, это показывает, что я делаю успехи.

Хорошо, давайте поговорим об этом.

Я сказал, что я говорил о внутренних принципах работы фильтра Buron в посте, я сказал, что это неясно.

На самом деле мне просто лень писать, это дело не сложное, что тут непонятного?

Фильтр Блума

Фильтр Блума имеет большой эффект в разумном сценарии использования.Поскольку сценарий использования находится в сценарии с большим объемом данных, эта вещь похожа на шип.Хотя он не использовался на земле, надо сказать по прямой.

Обычно используется в интервью: например, оценка повторяющихся данных в больших наборах, проблемы с проникновением в кэш и т. Д.

Давайте поделимся реальным случаем использования фильтра Блума в коротких видеопродуктах Tencent:

https://toutiao.io/posts/mtrvsx/preview

Так как же фильтр Блума соответствует вышеуказанным требованиям?

Во-первых, фильтр Блума не хранит необработанные данные, потому что его функция состоит только в том, чтобы сообщить вам, существует элемент или нет. Нет необходимости знать, какие элементы входят в фильтр Блума.

Конечно, если мы знаем, какие элементы находятся внутри контейнера, мы можем знать, существует ли элемент.

Однако таким образом нам необходимо хранить все появившиеся элементы, а в случае большого объема данных такое хранение занимает много места.

Как фильтр Блума не хранит элементы и не знает, существует ли элемент?

На самом деле сломать его очень просто: длинный массив плюс несколько алгоритмов хеширования.

На приведенной выше схеме показаны три разных алгоритма хеширования и массив длиной 10. Массив хранит биты, только 0 и 1. Изначально 0.

Предположим, теперь есть элемент [почему], чтобы пройти через этот фильтр Блума.

Во-первых [почему] После трех алгоритмов Hash получаются три разных числа.

Алгоритм Hash может гарантировать, что результирующее число находится в диапазоне от 0 до 9, то есть не превышает длину массива.

Предположим, что результаты расчетов следующие:

• Hash1(why)=1
• Hash2(why)=4
• Hash3(why)=8

Это соответствует картинке:

В это время, если есть другой элемент [почему], нижний индекс, полученный алгоритмом хеширования, по-прежнему равен 1, 4, 8, и обнаруживается, что соответствующая позиция массива равна 1. Указывает на то, что этот элемент, скорее всего, появился.

Примечание здесь, что очень вероятно. Что будут какие-то ложные позитивы.

Сначала мы сохраняем элемент [jay].

• Hash1(jay)=0
• Hash2(jay)=5
• Hash3(jay)=8

На этом этапе мы объединяем два элемента, и у нас есть следующая картина:

Позиция, где индекс равен 8, является особой, и оба элемента указывают на нее.

Эта картинка выглядит немного неудобным вот так, я ее украсю:

Ну, теперь массив выглядит так:

Ты сказал, ты только смотришь на это, ты можешь знать, почему и Джей раньше был в этом фильтре?

Не говорите, что не знаете, даже если не знаете самого фильтра.

Теперь, предполагая, что есть еще один элемент [Лесли], после трех алгоритмов хеширования результаты расчета следующие:

• Hash1(Leslie)=0
• Hash2(Leslie)=4
• Hash3(Leslie)=5

Через приведенные выше элементы вы можете узнать, что все три позиции 0, 4 и 5 в это время равны 1.

Фильтр Блума почувствует, что элемент мог появиться раньше. Так что звонившему будет возвращено: [Лесли] появилась.

Но как насчет реальной ситуации?

На самом деле, наши сердца чисты, [Лесли] никогда не был там.

Это случай ложных срабатываний.

Это сказано ранее:Фильтры Блума говорят, что элементы, которые существуют, не обязательно существуют.

После вычисления элемента по определенному хешу, если значение в соответствующей позиции равно 0, это означает, что элемент не должен существовать.

Но у него есть фатальный недостаток, то есть он не поддерживает удаление.

Зачем?

Предположим, вы хотите удалить [почему], тогда вам нужно установить три позиции 1, 4 и 8 на 0.

Но если подумать, [Джей] тоже указывает на позицию 8.

Если убрать [почему], позиция 8 станет 0, это не эквивалентно [сойке] тоже убрать?

Почему фатально не поддерживать удаление?

Вы подумайте еще раз, фильтр Блума изначально используется в сценариях с большими объемами данных.С течением времени в массиве этого фильтра становится все больше и больше 1 позиций, и в результате получается ложноположительный показатель. Так что приходится перестраивать.

Поэтому в примере с Tencent, приведенном в начале статьи, есть такое предложение:

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

Поскольку длина массива в фильтре в реальной сцене очень велика, после нескольких различных хеш-функций диапазон полученного индекса массива в памяти может быть очень большим. Если размах большой, то он прерывистый. Прерывистое, это приведет к низкой частоте попаданий в строку кэша ЦП.

Эта вещь, так сказать. Просто запомните его в качестве сочинения восьми частями.

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

Если вы хотите поиграть с фильтром Блума, вы можете посетить этот веб-сайт:

https://www.jasondavies.com/bloomfilter/

Вставка слева, запрос справа:

Что делать, если вы хотите, чтобы фильтр Блума поддерживал удаление?

Есть один, который называется Counting Bloom Filter.

Он заменяет биты массива массивом счетчиков, так что однобитовое пространство расширяется до счетчика.

За счет увеличения в несколько раз места для хранения в фильтр Блума добавляется операция удаления.

Это тоже решение.

Но есть лучшее решение, и это фильтр с кукушкой.

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

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html

кукушка

Фильтр с кукушкой впервые появился в статье, опубликованной в 2014 году: «Фильтр с кукушкой: практически лучше, чем цветение».

https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

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

Поскольку это слово является ключевым словом бумаги, оно выглядит целых 52 раза в тексте.

Хеширование с кукушкой впервые появилось в этой статье 2001 года:

https://www.cs.tau.ac.il/~shanir/advanced-seminar-data-structures-2009/bib/pagh01cuckoo.pdf

В основном посмотрите на это место бумаги:

Как это работает, резюмируя так:

Он имеет две хеш-таблицы, обозначенные как T1, T2.

Две хэш-функции, обозначенные как h1, h2.

При вставке несуществующего элемента его позиция в таблице T1 будет вычисляться первой по h1, и если позиция пуста, его можно будет вставить.

Если позиция не пуста, ее позиция в таблице Т2 рассчитывается по h2, и если позиция пуста, ее можно поставить.

Если позиция не пуста, просто удалите элемент в текущей позиции и вставьте текущий элемент.

Также возможен случайный кик одной из двух позиций, в любом случае будет выкинут один элемент.

А как насчет выброшенных элементов?

Ничего страшного, у него тоже есть другое место.

Псевдокод в статье выглядит так:

Не понял не беда, рисуем схему:

На картинке выше показано что-то вроде этого:

Я хочу вставить элемент x после двух хеш-функций, две его позиции — это позиция 2 таблицы T1 и позиция 1 таблицы T2.

Обе позиции заняты, затем случайным образом пинаем y с позиции 2 на столе T1.

А другую позицию y занимает элемент z.

Итак, вы выгнали Z без пощады.

z обнаруживает, что его запасная позиция все еще пуста (хотя эта запасная позиция также является запасной позицией элемента v), и быстро занимает ее.

Итак, когда вставлен x, график выглядит так:

Изображение выше на самом деле является источником бумаги:

Такое решение, похожее на матрешку, кажется осуществимым, но всегда существует проблема зацикливания ударов, которые не могут поставить x.

Например, (b) на рисунке выше.

Когда это происходит, это означает, что хэш кукушки достиг предела, и его следует расширить или оптимизировать хэш-функцию.

Так что, когда вы еще раз посмотрите на псевдокод, вы поймете, в чем смысл MaxLoop в нем.

Смысл этого MaxLoop — порог, установленный, чтобы избежать слишком большого количества выполнений процесса выбивания друг друга.

На самом деле, я понимаю, что Bayu Bird Hash — это своего рода операция Sao по разрешению конфликта Hash.

Если вы хотите начать играть, вы можете посетить этот сайт:

http://www.lkozma.net/cuckoo_hashing_visualization/

После 16 пинков (MaxLoop) и без вставки он сообщит вам, что ему нужно перефразировать и расширить массив:

Гашиш с кукушкой именно такой.

Далее мы смотрим на фильтр с кукушкой.

фильтр с кукушкой

На первой странице газеты Cuckoo Filter «Фильтр с кукушкой: практически лучше, чем цветение» есть такой абзац.

Прямо перед фильтром Блума: я фильтр с кукушкой, только немного лучше, чем ваш.

Подойди и укажи на слабость других:

Большим ограничением стандартного фильтра Блума является то, что он не может удалять уже существующие данные. Если вы используете его варианты, такие как Counting Bloom Filter, но пространство растягивается в 3-4 раза, бла-бла-бла...

А я другой:

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

Courier Filter - это практичная структура данных, которая обеспечивает четыре преимущества:

• 1. Поддержка динамического добавления и удаления элементов.
• 2. Обеспечивает более высокую производительность поиска, чем традиционные фильтры Блума, даже когда он близок к заполнению (например, когда использование пространства достигает 95%).
• 3. Легче реализовать, чем альтернативы, такие как факторный фильтр (другой фильтр).
• 4. Если требуемый уровень ошибок меньше 3%, он занимает меньше места, чем фильтр Блума во многих практических приложениях.

API фильтра с кукушкой — это не что иное, как вставка, запрос и удаление.

Наиболее важным из которых является вставка, взгляните на:

В той части статьи, вы, наверное, заглянули, и не беда, если вы ее не понимаете, разве я не проанализировал ее для вас сразу.

Вставьте псевдокод детали, вы можете увидеть небольшую тень хэша с кукушкой, потому что он основан на этой штуке.

Так где же самые большие изменения?

Это не что иное, как изменение хеш-функции.

Я был ошеломлен, когда увидел это, и подумал про себя: а как насчет такой неряшливой операции?

Прежде всего, вспомним хэш с кукушкой, в котором хранится исходное значение вставленного элемента, например x, x будет проходить через две хеш-функции, если мы помним длину массива как L, то он такой:

• p1 = hash1(x) % L
• p2 = hash2(x) % L

А как фильтр с кукушкой вычисляет позицию?

• h1(x) = hash(x),
• h2(x) = h1(x) ⊕ хеш (отпечаток пальца x).

Мы видим, что при вычислении h2 (позиция 2) вычисление хэша выполняется по отпечатку пальца x.

Концепция «отпечатка пальца» будет обсуждаться позже, а сначала мы сосредоточимся на вычислении позиции.

Операция XOR в приведенном выше алгоритме обеспечивает важное свойство: позицию h2 можно вычислить по «отпечаткам пальцев», хранящимся в позициях h1 и h1.

Говоря человеческим языком: если мы знаем позицию (h1) элемента и информацию «отпечатка пальца», хранящуюся в этой позиции, мы можем знать альтернативную позицию (h2) «отпечатка пальца».

Две позиции являются двойными из-за используемой операции XOR.

Пока гарантируется хэш(отпечаток пальца x) !=0, тогда может быть гарантировано h2!=h1, и может быть гарантировано отсутствие проблемы с бесконечным циклом, связанной с пинком самого себя.

Кроме того, зачем вам необходимо выполнить операцию XOR после выполнения расчета хеша на «отпечатке пальца»?

В работе приводится контрдоказательный метод: если вычисление хеша не производится, полагая, что длина «отпечатка пальца» составляет 8 бит, то вычисляется двойная позиция, а самая дальняя от текущей позиция всего 256.

Почему, в газете написано:

Потому что, если длина «отпечатка пальца» составляет 8 бит, операция XOR изменит только младшие 8 бит текущей позиции h1(x), а старшие биты не изменятся.

Даже если изменить все младшие 8 бит, вычисленная позиция будет такой, как я только что сказал: самые дальние 256 бит.

Таким образом, хеширование «отпечатка пальца» гарантирует, что удаленные элементы могут быть перемещены в совершенно другое ведро в хеш-таблице, уменьшая коллизии хэшей и улучшая использование таблицы.

Тогда есть еще одна проблема с этой хэш-функцией, вы ее нашли?

Он не зависит от длины массива по модулю, так как же он гарантирует, что вычисляемый индекс должен попасть в массив?

Это подводит нас к еще одному ограничению фильтра с кукушкой.

Он требует, чтобы длина массива была экспоненциально кратна 2.

Двоичный файл, экспоненциально кратный 2, должен выглядеть так: 10000000...(n 0s).

Преимущество этого ограничения в том, что при выполнении операции XOR можно гарантировать, что вычисляемый индекс должен попасть в массив.

Недостатки этого ограничения:

• Фильтр с кукушкой: я поддерживаю операции удаления.
• Floom Filter: мне не нужно ограничивать длину экспоненциальной, кратней 2.
• Фильтр с кукушкой: моя производительность поиска лучше, чем ваша.
• Фильтр Блума: мне не нужно ограничивать длину экспоненциально кратным 2.
• Фильтр с кукушкой: у меня также высокое использование пространства.
• Фильтр Блума: мне не нужно ограничивать длину экспоненциально кратным 2.
• Фильтр с кукушкой: надоело, TMD!

Далее поговорим об «отпечатках пальцев».

Здесь впервые на бумаге появляются «отпечатки пальцев».

«Отпечаток пальца» на самом деле вставляет элементы в хеш-вычисление, а хеш-вычисление — это произведение нескольких битовых позиций.

Фильтр кукушки хранится в «отпечатке пальцев» элементов.

При запросе данных нужно увидеть, есть ли соответствующая информация «отпечатков пальцев» в соответствующем месте:

При удалении данных он просто стирает «отпечаток пальца» в этом месте:

Так как вычисление хеш-функции выполняется на элементах, неизбежно возникнет ситуация, когда «отпечаток пальца» совпадет, то есть будет неверная оценка.

Исходные данные не сохраняются, поэтому точность данных приносится в жертву, но сохраняются только несколько битов, что повышает эффективность использования пространства.

Говоря о утилизации пространства, какое пространство используется утилизация кабушки?

В идеальном случае, то есть до того, как не произойдет коллизии хэшей, его использование пространства составляет не более 50%.

Поскольку конфликта нет, значит как минимум половина позиций пустует.

Помимо хранения только «отпечатков пальцев», как фильтр с кукушкой может улучшить использование пространства?

Посмотрите, что написано в газете:

Предыдущие (а) и (б) очень просты. Это все еще две хэш-функции, но они не используют два массива для хранения данных. Это хэши-кукушки на основе одномерных массивов. многое сказать.

Дело в (с), массив расширяется от одномерного до двухмерного.

Для каждого нижнего индекса можно разместить 4 элемента.

С таким небольшим изменением использование пространства увеличилось с 50% до 98%:

Я спрашиваю, ты боишься?

Первый пункт в статье на скриншоте выше — это констатация факта:

Когда хеш-функция фиксирована на 2, если в индекс можно поместить только один элемент, использование пространства составляет 50%.

Но если индекс может содержать 2, 4 и 8 элементов, использование пространства возрастет до 84%, 95% и 98%.

На этом этапе мы понимаем точки оптимизации фильтра с кукушкой для хэша с кукушкой и соответствующий принцип работы.

Все выглядит так идеально.

Все индикаторы лучше фильтров Блума, а главное поддерживают операции удаления.

Но так ли это хорошо?

Увидев этот абзац в шестом разделе газеты, я промолчал:

Ограничение повторяющихся данных: если фильтр с кукушкой должен поддерживать удаление, он должен знать, сколько раз данные были вставлены. Одни и те же данные не могут быть вставлены kb+1 раз. Где k — количество хэш-функций, а b — количество элементов, которые можно поместить в позиции нижнего индекса.

Например, 2 хеш-функции, двумерный массив, каждый индекс которого может вставлять до 4-х элементов. Затем для одного и того же элемента поддерживается до 8 вставок.

Например следующая ситуация:

Почему было вставлено 8 раз.Если вы снова вставите почему, проблема зацикливается до максимального цикла, а затем вернет ложь.

Как избежать этой проблемы?

Мы поддерживаем таблицу записей для записи количества вставок каждого элемента.

Хотя логика проста, она не может хранить большой объем данных. Подумайте об этом, как рассчитывается место для хранения этой таблицы?

Больно думать об этом.

Если вы хотите использовать операцию удаления фильтра с кукушкой, то этот дискомфорт вам придется терпеть.

Наконец, давайте посмотрим на сравнительную таблицу различных типов фильтров:

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

прогулочная доска с полостью отходов

Вы знаете, почему это называется «кукушкой»?

Кукушка, также известная как кукушка.

В «Сборнике Материа медика» есть такая запись: «Птица-голубь не может быть гнездом, и она родит ребенка в своем гнезде». Здесь описано паразитическое поведение рододендронов в гнездах. Гнездовой паразитизм означает, что птицы не строят свои собственные гнезда, а откладывают яйца в гнезда других видов птиц, а хозяин заменяет способ размножения насиживания и насиживания Гнездовой паразитизм (паразит и хозяин - один и тот же вид). Среди более чем 10 000 видов птиц сегодня насчитывается более 100 видов гнездового паразитического поведения, среди которых наиболее типичным является рододендроновая кукушка.

То есть он откладывает свои яйца в чужие гнезда и позволяет другим птицам помогать ему высиживать птенцов. О нет, высиживайте птиц.

После того, как маленькая кукушка вылупилась, но и другие естественные яйца гнезда с запуском гнезда, поэтому сосредоточьтесь на матери-птице, кормящей ее.

Боже мой, это слишком жестоко.

Но разве действие «выталкивание птичьего гнезда» не совпадает с описанным выше алгоритмом?

Просто у нас алгоритм чуть симпатичнее: выталкиваемые яйца, то есть выталкиваемые элементы, будут располагаться в другом месте.

Когда я посмотрел данные, я был потрясен, когда узнал, что кукушка есть кукушка.

В них много стихов с кукушками, например, мой любимый «Цзиньсэ» Ли Шанъина, поэта династии Тан:

У Джинсе пятьдесят строк без всякой причины, а одна строка и один столбец посвящены китайскому Новому году.
Жуаншэн Сяо Сон Вентиляторы Бабочка, Император Ван Люст Уход в рододендронах.
В море появляются слезы, луна и жемчужина, а теплый нефрит в голубом поле производит дым.
Это чувство можно вспомнить, но оно уже было утеряно в то время.

с древних времен. Споры о том, о чем идет речь, о «оплакивании смерти» или о «самоповреждении», никогда не прекращались.

Но имеет ли это значение?

Это не имеет значения для меня.

Важно то, что в нужное время и в нужной атмосфере, при воспоминании о прошлом, можно уместно сказать: «Эту ситуацию можно вспомнить, но она тогда была утеряна».

Вместо того, чтобы сказать: Эй, теперь подумайте об этом, много вещей не лелеиша, ТМ действительно сожалеет об этом.

О верно.

Я тоже кое-что обнаружил, пока писал статью.

Фильтр Блума 1970 года, большой парень по имени Бертон Ховард Блум что-то придумал.

Когда я пишу эти вещи, я хочу видеть, как выглядит большой парень.

Но случилось чудо, я переворачивал вверх ногами внутреннюю и внешнюю стены, но фотографий босса не нашел.

Мои поиски закончились, и я нашел этот сайт:

https://www.quora.com/Where-can-one-find-a-photo-and-biographical-details-for-Burton-Howard-Bloom-inventor-of-the-Bloom-filter

Этот вопрос надо задавать девять лет назад, было из народа, то есть в 2012 году, когда:

Это действительно фотография Бертона Ховарда Блума, но не найденного Бертона Ховарда Блума.

Какой удивительный и скромный парень.

Возможно красивый мужчина.

Последнее слово (пожалуйста, обратите внимание)

Если у вас нехватка знаний и знаний, то неизбежно будут ошибки.Если вы найдете что-то не так, вы можете поднять это в фоновом режиме, а я доработаю.

Спасибо за прочтение, настаиваю на оригинальности, очень приветствую и благодарю за внимание.

Я почему, главное пишу код, часто пишу статьи, изредка снимаю видео.