Когда случайного недостаточно: ловушка оператора modulo

Есть приём, который встречался почти в каждой кодовой базе: из набора объектов нужно выбрать один случайный, и каждый должен иметь равные шансы. Прямолинейное решение — взять большое случайное число и привести его к числу вариантов через остаток от деления: choices[random_u64() % 10]. Автор признаётся, что сам не раз так писал, особенно на C, где стандартная библиотека не предлагает ничего, кроме rand().

Проблема в том, что такой код не сохраняет равномерность исходной случайной функции. Нам кажется, что у каждого из десяти объектов шанс 1/10, но это не так.

Почему остаток искажает распределение

Представим, что мы берём число из диапазона [0, 9] и выбираем один из трёх объектов через % 3. Достаточно расписать исходы: значения {0, 3, 6, 9} дают первый объект, {1, 4, 7} — второй, {2, 5, 8} — третий. Четыре входа против трёх: первый вариант выпадает в 40% случаев вместо ожидаемых 33%, а остальные два — лишь в 30%.

Это одна из классических ошибок, особенно когда в распоряжении есть только random_u64(). Корректным решением автор называет функцию random_between(l, h), равномерно выбирающую число в заданном отрезке.

Лучше задавать распределение явно

По мнению автора, random_u64() — слишком низкоуровневый инструмент. На практике нам редко нужно просто число: мы хотим выбрать объект, причём иногда с разными весами. Поэтому разумнее опираться на функцию random_choice(), которой вы сами передаёте варианты и их вероятности. В такой записи ошибочный «перекос» сразу бросается в глаза: если первый вариант получает 0.4, а остальные по 0.3, видно, что что-то не так.

Чтобы избавиться от неустойчивости чисел с плавающей точкой и требования, чтобы веса давали ровно 1.0, многие стандартные библиотеки (например, в Python) используют относительные целочисленные веса. Веса (4, 3, 3) дают в сумме 10, и 3/10 = 0.3, как и ожидалось. Реализуется это просто: при весах 15 + 12 + 3 = 30 берём число из [0, 29] и сопоставляем ему подотрезки — ещё один довод в пользу random_between.

Работа в неверной области

Глубже лежит ошибка мышления: мы оперируем не числами, а случайными величинами. Нелинейные операторы не сохраняют математическое ожидание — f(E[X]) не равно E[f(X)]. Мы думаем, что сохраняем свойство конкретного значения, тогда как сохранять нужно свойства самой функции.

Практический итог

Команда автора — клиенты платформы детерминированного фаззинга Antithesis, где важные пути кода проверяются случайным перебором. Там удобно задавать распределения напрямую: например, пометить загрузки размером Small весом 88, а три крупных варианта — по 4, чтобы примерно ⅞ тестов приходилось на мелкие блобы. Пересмотрев код, они убрали все вызовы random_u64(), заменив их взвешенным random_choice(), и ввели мораторий на новые. В следующий раз, увидев код вроде исходного примера, спросите себя: нельзя ли описать нужное распределение напрямую?

Источник: Lobsters