Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Спасибо, даешь больше такого хардкора на Хабре!
1.
2.
Скорее «Если бит is_occupied не выставлен»?
3.
Удалять скорее надо в конце, только если удаланный хеш был единственным в таблице с этим fq.
4. (Мысли вслух) Чтобы работа с таблицей не была совсем адом, слот должен занимать целое число байт, т. е. 8, 16, 24, 32, 40, 48, 56 или 64 бита (больше вряд ли имеет смысл, нереализуемо на языках без интринсиков и т. д.). Значит, остаток будет 5, 13, 21, 29, 37, 45, 53 или 61 бит. Значит, модуль (размер таблицы) должен быть 2^19 или 2^11 (при 32- или 64-битном хеше), 2^27 или 2^35 при 64-битном. Размер 2^3 (8 слотов) или 2^43 и больше — едва ли имеют практический смысл. 2^27 при 32-битном хеше — проще, наверное, просто битсет сделать на 2^32 элемента.
Выбор невелик. Может имеет смысл поменять местами остаток и частное, тогда выбор вариантов вариантов увеличится? Или нет?
5. (Мысли вслух) Не знаю насчет вероятностной структуры данных, замены фильтра Блума и прочих пафосных формулировок, по-моему это просто хеш-таблица целых чисел, где выигрывается ((log 2 от размера таблицы) — 3) бита на слот для хранения информации, за счет серьезного усложнения операций. Имеет ли это какой-то смысл — большой вопрос. Чтобы выигрыш был более-менее заметным, модуль должен быть большим, то есть скорее только 2^27 и 2^35 при 64-битном хеше (выигрыш 24 и 32 бита соответственно, 37,5% и 50%), и только 2^19 при 32 битном хеше (выигрыш 16 бит, 50%).
Вывод: эта структура имеет смысл (в первую очередь, или вообще только), если у вас ~ 2^18 элементов = 250 тысяч при 32-битном хеше, ~ 2^26 = 32 миллиона или 2^34 = 16 миллиардов элементов, при 64-битном хеше.
1.
Давайте разберемся, что делают дополнительные 3 бита, хранящиеся с каждым остатком… дальше биты перечислены в одном порядке, а потом на диаграммах везде они в другом. Сбивает.
2.
Проверяем слот fq в массиве. Если он пустой — элемент не содержится в фильтре.
Скорее «Если бит is_occupied не выставлен»?
3.
Сначала мы выставляем(для вставки, для удаления наоборот убираем) бит занятости для слота A[fq]
Удалять скорее надо в конце, только если удаланный хеш был единственным в таблице с этим fq.
4. (Мысли вслух) Чтобы работа с таблицей не была совсем адом, слот должен занимать целое число байт, т. е. 8, 16, 24, 32, 40, 48, 56 или 64 бита (больше вряд ли имеет смысл, нереализуемо на языках без интринсиков и т. д.). Значит, остаток будет 5, 13, 21, 29, 37, 45, 53 или 61 бит. Значит, модуль (размер таблицы) должен быть 2^19 или 2^11 (при 32- или 64-битном хеше), 2^27 или 2^35 при 64-битном. Размер 2^3 (8 слотов) или 2^43 и больше — едва ли имеют практический смысл. 2^27 при 32-битном хеше — проще, наверное, просто битсет сделать на 2^32 элемента.
Выбор невелик. Может имеет смысл поменять местами остаток и частное, тогда выбор вариантов вариантов увеличится? Или нет?
5. (Мысли вслух) Не знаю насчет вероятностной структуры данных, замены фильтра Блума и прочих пафосных формулировок, по-моему это просто хеш-таблица целых чисел, где выигрывается ((log 2 от размера таблицы) — 3) бита на слот для хранения информации, за счет серьезного усложнения операций. Имеет ли это какой-то смысл — большой вопрос. Чтобы выигрыш был более-менее заметным, модуль должен быть большим, то есть скорее только 2^27 и 2^35 при 64-битном хеше (выигрыш 24 и 32 бита соответственно, 37,5% и 50%), и только 2^19 при 32 битном хеше (выигрыш 16 бит, 50%).
Вывод: эта структура имеет смысл (в первую очередь, или вообще только), если у вас ~ 2^18 элементов = 250 тысяч при 32-битном хеше, ~ 2^26 = 32 миллиона или 2^34 = 16 миллиардов элементов, при 64-битном хеше.
Хотя, по сути дела, кроме 32 бит на слот будет ад даже при целом числе байт на слот, но зато только одно чтение из памяти для получения первого слота (который, по задумке, должно быть чаще всего единственным полученным слотом на операцию, если нет коллизий и кластеров).
Огромное спасибо за замечания!
1, 2 и 3 вроде исправил.
4. Жаль, я потерял линк на реализацию на С от авторов. В других реализациях(например github.com/vedantk/quotient-filter) используются 64-битные хэши.
Как я уже писал, размеры частного и остатка можно менять, всё зависит от ситуации, данных и их количества.
5. Авторы проводят тесты с миллионами элементов, так что структуру действительно нет смысла использовать на очень маленьких выборках. При большом количестве элементов, когда коэффициент заполнения(load factor) становится высоким, можно организовать каскад фильтров. Это описано в [1], стр. 6
1, 2 и 3 вроде исправил.
4. Жаль, я потерял линк на реализацию на С от авторов. В других реализациях(например github.com/vedantk/quotient-filter) используются 64-битные хэши.
Может имеет смысл поменять местами остаток и частное
Как я уже писал, размеры частного и остатка можно менять, всё зависит от ситуации, данных и их количества.
5. Авторы проводят тесты с миллионами элементов, так что структуру действительно нет смысла использовать на очень маленьких выборках. При большом количестве элементов, когда коэффициент заполнения(load factor) становится высоким, можно организовать каскад фильтров. Это описано в [1], стр. 6
4. Я имел ввиду хранить в таблице частное, а индексировать слоты остатком. Хотя нет никакой разницы, наверное. Просто это было бы более натурально с точки зрения обычных хеш-таблиц, где индексируют именно остатком: index = hash % table_size, а что там в качестве операции модуля, целочисленное деление или битовая маска, это вопрос второй. По смыслу, как бы, индекс = остаток это более натурально, чем индекс = частное.
5. При большом заполнении я бы просто взял таблицу побольше. Или авторы тоже подвязываются на всего несколько фиксированных размеров таблиц, которые я перечислил, и используют их для хранения любого числа элементов путем изменения числа таблиц?
5. При большом заполнении я бы просто взял таблицу побольше. Или авторы тоже подвязываются на всего несколько фиксированных размеров таблиц, которые я перечислил, и используют их для хранения любого числа элементов путем изменения числа таблиц?
4. Не знаю, с такой точки зрения на частное — остаток я не смотрел. В принципе, можно и так сделать.
5. Авторы предлагают держать в памяти таблицу размера q0(размер таблицы ограничен размером оперативной памяти). Когда она сильно заполняется, она сливается с таблицей размера q1 > q0, которая хранится на SSD. А таблица в оперативной памяти очищается. Если при слиянии таблица с размером q1 тоже заполнилась, то она сливается с другой таблицей с размером q2 > q1, которая тоже хранится на SSD, а затем очищается. И т. д.
Насколько помню, размер таблиц не фиксирован.
Вообще, этот cascade filter из quotient filters основан на другой структуре — cache-oblivious lookahead array(COLA) (подробнее здесь supertech.csail.mit.edu/papers/sbtree.pdf). Надеюсь, кто-нибудь напишет и об этом)) Я пока не изучал эту тему.
5. Авторы предлагают держать в памяти таблицу размера q0(размер таблицы ограничен размером оперативной памяти). Когда она сильно заполняется, она сливается с таблицей размера q1 > q0, которая хранится на SSD. А таблица в оперативной памяти очищается. Если при слиянии таблица с размером q1 тоже заполнилась, то она сливается с другой таблицей с размером q2 > q1, которая тоже хранится на SSD, а затем очищается. И т. д.
Насколько помню, размер таблиц не фиксирован.
Вообще, этот cascade filter из quotient filters основан на другой структуре — cache-oblivious lookahead array(COLA) (подробнее здесь supertech.csail.mit.edu/papers/sbtree.pdf). Надеюсь, кто-нибудь напишет и об этом)) Я пока не изучал эту тему.
А какой фильтр компактнее, Quotient filter или bloom filter?
(естественно, при одинаковой вероятности ошибки)
(естественно, при одинаковой вероятности ошибки)
Если не ошибаюсь, то Bloom filter.
Хм, в википедии написано, что «одного порядка», но для bloom filter я знаю формулу расчёта, а для этого фильтра пока не нашёл.
m = table_size * slot_size
slot_size = hash_size — log2 table_size + 3
table_size = n_hashes * 2 // (0.5 load factor)
n_hashes = n * (1 — error_p)
error_p = hard_collision_p = 1 — (1 — 1/ 2^hash_size) ^ n
m = n * ((1 — 1/ 2^hash_size) ^ n) * 2 * (hash_size — (log2 n * ((1 — 1/ 2^hash_size) ^ n) * 2) + 3)
slot_size = hash_size — log2 table_size + 3
table_size = n_hashes * 2 // (0.5 load factor)
n_hashes = n * (1 — error_p)
error_p = hard_collision_p = 1 — (1 — 1/ 2^hash_size) ^ n
m = n * ((1 — 1/ 2^hash_size) ^ n) * 2 * (hash_size — (log2 n * ((1 — 1/ 2^hash_size) ^ n) * 2) + 3)
error_p = hard_collision_p = 1 — (1 — 1/ 2^hash_size) ^ nЭто неправда, шанс не получить коллизию для n ключей, если всевозможных вариантов ключей — k, равен:
(1 – 1/k)(1 – 2/k)...(1 – n/k)
а не как у вас:
(1 – 1/k)n
Если взять в качестве примера известный "парадокс дней рождения", то для n = 23 и k = 365, по вашей формуле имеем (364/365)23 ≈ 94%, а на самом деле там около 50%.
Если хотите, то можно оценить это произведение снизу как (1 – n/k)n
m = n * ((1 — 1/ (1/(1 — log n (1 — error_p)))) ^ n) * 2 * (log 2 (1/(1 — log n (1 — error_p))) — (log2 n * ((1 — 1/ (1/(1 — log n (1 — error_p)))) ^ n) * 2) + 3)
Порядок действительно один — O(n), где n — размер фильтра.
Для Bloom filter количество бит, задействованных на хранение одного элемента, <= количество хэш-функций(меньше потому, что 1 бит может быть использован для хранения сразу нескольких элементов — произошла коллизия в одной из хэш-функций). Не знаю, лично я не слышал про кол-во хэш-функций > 15.
Для Quotient filter количество бит, задействованных на хранение одного элемента, ~= 60.
Написал всё это и увидел дополнение
В quotient filter используется только одна хэш-функция. В этом смысле Bloom filter с набором хэш-функций всегда будет впереди. При использовании в Bloom filter только одной хэш-функции получаем 1 бит на элемент, тогда как в quotient filter всё те же ~= 60 бит.
Правда, в quotient filter допускаются коллизии, вставляется просто еще одна копия хэша.
Кстати, формула вероятности ошибки для quotient filter выводится в [1], стр. 4
Это только моё личное мнение, я могу ошибаться.
Для Bloom filter количество бит, задействованных на хранение одного элемента, <= количество хэш-функций(меньше потому, что 1 бит может быть использован для хранения сразу нескольких элементов — произошла коллизия в одной из хэш-функций). Не знаю, лично я не слышал про кол-во хэш-функций > 15.
Для Quotient filter количество бит, задействованных на хранение одного элемента, ~= 60.
Написал всё это и увидел дополнение
(естественно, при одинаковой вероятности ошибки)
В quotient filter используется только одна хэш-функция. В этом смысле Bloom filter с набором хэш-функций всегда будет впереди. При использовании в Bloom filter только одной хэш-функции получаем 1 бит на элемент, тогда как в quotient filter всё те же ~= 60 бит.
Правда, в quotient filter допускаются коллизии, вставляется просто еще одна копия хэша.
Кстати, формула вероятности ошибки для quotient filter выводится в [1], стр. 4
Это только моё личное мнение, я могу ошибаться.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Quotient filter