2024 10 10 битовые маски имба
Битовые маски - ftw
У меня есть коллега, который занимался переписыванием сервиса поиска. По результату родилась гениальная цитата: “Вообще это JSON, но можно упаковать число”. Речь идёт про битовые маски.
Базово перепечатаю с Википедии. Чиселки в компьютере имеют двоичное представление: 4 — это 100, 23 — это 10111. Теперь мы можем каждой позиции придать какую-то значимость. Допустим, в четвёртой позиции мы будем отмечать наличие кондиционера в номере. Дальше для проверки достаточно будет сделать битовую операцию 17 & 16 — и она даст да или нет. Таким образом, в компьютере делается много вещей — маршрутизация трафика, наложение маски на изображение, проверка целостности данных через CRC.
Гораздо интереснее поверх этой структуры — вероятностные алгоритмы. Одна из них — фильтр Блума, про него рассказывал летом на Saint Highload++ (https://www.youtube.com/watch?v=DllZX8D3RqU). Он направлен на то, чтобы быстро убедиться в наличии элемента в каком-то множестве; но не факт, что правильно. Устроено это как хеш плюс обновление битовой маски, а дальше немного математики, чтобы количество ложноположительных стремилось к нужному проценту.
Фильтр Блума не один такой, есть его улучшение — кукушкин фильтр (или фильтр кукушки). По сравнению с Блумом, в нём перед вставкой элемента считается fingerprint/слепок элемента, а также его можно будет удалить. Между двумя этими решениями прошло 44 года, прежде чем решили его так дотюнить. Так что если вам кажется, что в классическом CS все проблемы решены — это не так.
В комментах расскажите, что вы используете из вероятностных структур? Может, пользуетесь готовыми реализациями в Redis или языках?
@chernov_sharit