Рассчитать фильтр
Сервису нужно много фильтров Блума: для каждого заказчика своё число элементов n и своя допустимая доля ложных срабатываний p. Рассчитайте каждый фильтр по формулам из статьи о фильтре Блума:
- число битов m = ⌈n · ln(1/p) / (ln 2)²⌉ — наименьшее целое, не меньшее этого значения;
- число хешей k = round(m/n · ln 2), но не меньше 1;
- и ожидаемую долю ложных срабатываний настоящего фильтра (1 − e−kn/m)k — она чуть отличается от заказанной, потому что m и k округлены.
Во всех тестах значения далеки от границ округления, так что любой язык с обычной плавающей точкой посчитает одинаково.
Вход
В первой строке число заказов q (1 ≤ q ≤ 3000). В каждой из следующих q строк — целое n (1 ≤ n ≤ 10⁹) и дробное p (0 < p < 1).
Выход
Для каждого заказа строку: m, k и ожидаемую долю ложных срабатываний. Доля проверяется с абсолютной погрешностью 10⁻⁷, печатайте её хотя бы с десятью знаками после точки.
Примеры
Пример 1
4 10000 0.01 10000 0.001 1000000 0.05 500 0.2
95851 7 0.0100390105 143776 10 0.0010000189 6235225 4 0.0502694654 1675 2 0.2020931100
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Задача — аккуратно перенести три формулы в код. Самое опасное место — округления: какое из них вверх, какое к ближайшему?
2Идея
Битов нужно не меньше, чем требует формула, иначе ошибка превысит заказанную — отсюда округление m вверх. А k — это точка минимума ошибки по числу хешей; функция ошибки вблизи минимума пологая, и ближайшее целое к оптимуму лучше, чем отброшенная дробная часть.
3Разбор
Для каждого заказа считаем m = ceil(n·ln(1/p)/ln²2), затем k = max(1, round(m/n·ln 2)) и подставляем оба числа в формулу ошибки. Именно подставляем настоящие m и k, а не берём заказанное p: заказчику важно, что он получит на самом деле.
Заметьте, что при n = 1 и p = 0,5 получится m = 2, k = 1: один хеш в двухбитовом массиве, и ошибка ровно 1 − e−1/2 ≈ 0,39 — меньше заказанной половины, потому что m округлили вверх.
3+Решение
4Сложность
O(1) на заказ, O(q) на всё.
5Типичные ошибки
- int() вместо round() для k. При 9,6 бита на элемент получится 6 хешей вместо 7 — ошибка чуть выше оптимума, и тест это ловит.
- Целочисленное деление.
m / nв Go для целых чисел — целое. Переводите в float64 до деления. - Печать с малой точностью. При p = 10⁻⁹ шесть знаков после точки дадут ноль.