Быстрый взвешенный случайный выбор из очень большого набора значений
В настоящее время я работаю над проблемой, требующей случайного выбора элемента из набора. Каждый из элементов имеет вес (вероятность выбора), связанный с ним.
Моя проблема в том, что для множеств с небольшим количеством элементов, скажем, 5-10, сложность (время выполнения) решения я была приемлемой, однако, поскольку количество элементов увеличивается, скажем, для 1K или 10K и т.д., выполняется время становится неприемлемым.
Моя текущая стратегия:
- Выберите случайное значение X с диапазоном [0,1)
- Итерации элементов суммирования их веса до тех пор, пока сумма будет больше, чем X
- Элемент, который вызвал сумму, превышающую X, выбирается и возвращается
Для больших множеств и большого количества выборов этот процесс начинает проявлять квадратичное поведение, короче говоря, существует более быстрый способ? возможно, лучший алгоритм?
Ответы
Ответ 1
Предполагая, что вес элементов фиксирован, вы можете работать с заранее вычисленными суммами. Это похоже на работу с функцией кумулятивной вероятности напрямую, а не с функцией плотности.
Затем поиск может быть реализован как двоичный поиск и, следовательно, log (N) в количестве элементов.
Для двоичного поиска явно требуется random_access для контейнера весов.
В качестве альтернативы используйте методы std::map<>
и upper_bound()
.
#include <iostream>
#include <map>
#include <stdlib.h>
int main ()
{
std::map<double, char> cumulative;
typedef std::map<double, char>::iterator It;
cumulative[.20]='a';
cumulative[.30]='b';
cumulative[.40]='c';
cumulative[.80]='d';
cumulative[1.00]='e';
const int numTests = 10;
for(int i = 0;
i != numTests;
++i)
{
double linear = rand()*1.0/RAND_MAX;
std::cout << linear << "\t" << cumulative.upper_bound(linear)->second << std::endl;
}
return 0;
}
Ответ 2
Вы хотите использовать алгоритм Уокер. С N элементами существует настройка
стоимость O (N). Однако стоимость выборки равна O (1). См
- A. J. Walker, Эффективный метод генерации
Дискретные случайные переменные и общие распределения, ACM TOMS 3, 253-256
(1977).
- Knuth, TAOCP, Vol 2, Sec 3.4.1.A.
Класс RandomSelect RandomLib
реализует этот алгоритм.
Ответ 3
Если у вас есть достаточно быстрый способ выборочного случайного элемента, вы можете использовать выборку отбраковки; все, что вам нужно знать, это максимальный вес. Он будет работать следующим образом: предположим, что максимальный вес равен М. Выберем число X равномерно в [0,1]. Обрабатывайте элементы несколько раз, пока не найдете тот, вес которого не меньше M * X; выберите этот.
Или приблизительное решение: выбирайте 100 элементов равномерно случайным образом; выберите один пропорциональный вес в этом наборе.