MiddleКодИногдаЕщё не отвечали
Случайный выбор сервера пропорционально весам нагрузки
Даны веса нагрузки серверов, сумма которых равна 1, например {0.3, 0.1, 0.6}. Реализуйте chooseServer, чтобы каждый сервер выбирался с вероятностью, равной его весу.
Требования:
- Используйте один равномерный случайный отсчёт в
[0, 1). - На многих вызовах эмпирическое распределение должно совпадать с весами.
int chooseServer(const std::vector<double>& weights, double r) {
// r — равномерное случайное значение в [0, 1); ваш код здесь
}Допишите реализацию.
Строим кумулятивное распределение: идём по весам, накапливая сумму, и возвращаем первый индекс, где сумма превысила r. Это отображает равномерный отсчёт на корзины, размером с вес, так что шанс каждого сервера равен его весу. O(k), или O(log k) с массивом префиксных сумм и бинпоиском.
- ✗Сравнивать
rс каждым сырым весом вместо кумулятивной суммы - ✗Ошибка на единицу на границе, например
<=, из-за чего последняя корзина недостижима - ✗Считать, что равномерный выбор уже учитывает веса
- →Как ускорить повторные отсчёты массивом префиксных сумм и бинпоиском?
- →Что меняется, если веса не суммируются ровно в 1?
Оглавление
Задача
Реализуйте выбор сервера пропорционально весам нагрузки по одному равномерному отсчёту.
Решение
#include <vector>
int chooseServer(const std::vector<double>& weights, double r) {
double acc = 0.0;
for (int i = 0; i < (int)weights.size(); ++i) {
acc += weights[i]; // кумулятивная сумма
if (r < acc) return i; // первая корзина, накрывшая r
}
return (int)weights.size() - 1; // защита от ошибок округления
}Ключевые моменты
- Сравниваем
rс кумулятивной суммой, а не с сырыми весами. - Корзина шириной с вес даёт вероятность, равную весу.
- Граница
r < acc(а не<=) держит распределение корректным.
Оглавление
