Сколько раз перепишется резервуар
Сервер метрик хранит не все замеры времени ответа, а случайную выборку из k штук — резервуар. Первые k замеров ложатся в резервуар как есть. Замер номер i > k с вероятностью k/i заменяет случайный из лежащих там, иначе выбрасывается. Так в любой момент резервуар — честная выборка из всего, что пришло.
Каждая замена — запись в общую память, которую видят другие потоки сервера, и инженер хочет знать, сколько таких записей ждать. Для каждого вопроса «n k» найдите математическое ожидание числа замен после того, как через резервуар размера k прошли n замеров. Первые k записей, которые заполняют пустой резервуар, заменами не считаются.
Во втором примере — поток из этой статьи, 19 073 землетрясения, и сутки работы сервера с замером каждую миллисекунду при резервуаре в 1028 элементов: такой размер по умолчанию у равномерного резервуара библиотеки метрик Dropwizard.
Вход
В первой строке число вопросов q (1 ≤ q ≤ 104). Дальше q строк по два числа n и k (1 ≤ k ≤ 106, k ≤ n ≤ 1018).
Выход
На каждый вопрос — ожидаемое число замен с абсолютной или относительной погрешностью не больше 10−6.
Примеры
Пример 1
3 10 1 6 2 5 5
1.928968254 1.900000000 0.000000000
Пример 2
2 19073 10 86400000 1028
75.043026271 11656.123452829
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Число замен — сумма индикаторов «замер номер i что-то заменил». Математическое ожидание суммы равно сумме ожиданий, даже если события зависимы.
2Подсказка 2
Получится k·(1/(k + 1) + … + 1/n). При n до 1018 складывать по одному нельзя. Что известно о сумме 1 + 1/2 + … + 1/m при больших m?
3Идея
Замер номер i > k заменяет что-то с вероятностью k/i, поэтому ожидание числа замен — k·(Hn − Hk), где Hm = 1 + 1/2 + … + 1/m — гармоническое число. Малые Hm возьмём из таблицы на миллион значений, большие — по асимптотике Hm = ln m + γ + 1/(2m) − 1/(12m2) + …, где γ ≈ 0,5772 — постоянная Эйлера.
4Разбор
Таблица H1, …, H106 считается один раз и отвечает на все Hk: k не больше миллиона. Для n больше миллиона следующий член ряда, 1/(120n4), меньше 10−25, так что трёх поправок хватает с огромным запасом. Каждый вопрос — O(1).
Проверим на первом примере. При k = 1 и n = 10 ожидание — 1/2 + 1/3 + … + 1/10 ≈ 1,929: единственный элемент резервуара меняется в среднем почти дважды за десять замеров. При k = 2 и n = 6 — 2·(1/3 + 1/4 + 1/5 + 1/6) = 1,9. На потоке землетрясений из статьи выходит 75,0 замены при k = 10 — столько их и насчитывает сцена в среднем. А за сутки, 86,4 миллиона замеров, резервуар из 1028 элементов перепишется всего около 11 656 раз: одна запись на семь с лишним тысяч замеров, и чем дольше работает сервер, тем реже.
Отсюда и оценка «на салфетке»: k·ln(n/k). Рост она передаёт верно, но теряет поправки: при малых k и n ошибается заметно — в первом примере даёт ln 10 ≈ 2,303 вместо 1,929. Это же число — сколько раз алгоритм L из статьи вообще обращается к генератору: он прыгает только к тем элементам, которые войдут в резервуар.
4+Решение
5Сложность
O(106) на таблицу и O(1) на вопрос.
6Типичные ошибки
- Оценка k·ln(n/k). Верна по порядку, но не до 10−6: уже первый пример.
- Складывать до n. 1018 слагаемых не сложить, а 104 вопросов по миллиону слагаемых — уже 1010 действий.
- Асимптотика для маленьких m. При m = 1 ряд даёт 1,0772 − 0,0833 ≈ 0,994 вместо 1: для малых значений нужна таблица.
- Считать начальное заполнение. Первые k записей заменами не считаются; при n = k ответ 0.