Как оптимизировать выборку отбраковки
У меня есть std :: map mymap, который я пытаюсь сэмплировать на основе значений для каждого ключа. Я установил алгоритм, основанный на выборке отклонения, который, кажется, работает, но он очень медленный (этот алгоритм вызывается тысячи раз в моей программе).
Поэтому мне интересно, будет ли это лучшим подходом или есть что-то более быстрое / более эффективное, чем я мог бы заняться вместо этого.
Вот что у меня так далеко внизу:
std::map<int, float> mymap; //My map that I am sampling
//These three floats are precomputed
int minKey; //Min key in the map.
int maxKey; //Max key in the map.
float maxValue; //Max value in the map.
float x1, x2; //Two random variables;
int key;
float value;
do
{
x1 = (float)rand()/(float)RAND_MAX;
x2 = maxValue * (float)rand()/(float)RAND_MAX;
key = minKey*(1.0-x1) + maxKey*x1; //Linearly interpolate random value to get key;
value = mymap[key]; //Get value;
} while(x2 > value)return std::pair<int, float)(key, value);
^ То, что я делаю выше, — это случайный случайный выбор ключа. Затем создайте другую случайную переменную и сравните ее со значением этого ключа. Если оно больше, повторите процесс. Таким образом, ключи с более высокими значениями выбираются чаще, чем ключи с более низкими значениями. Тем не менее, цикл do-while может многократно повторяться, прежде чем будет найдена приемлемая пара ключ-значение для выборки, и это вызывает довольно узкое место в моем приложении.
РЕДАКТИРОВАТЬ
Кроме того, необходимо ли мне вносить какие-либо корректировки в мои образцы, так как они здесь смещены? Я знаю, что при интеграции в Монте-Карло вы должны разделить значение образца на PDF этого образца … но я не уверен, что это применимо здесь. Если это применимо, как я могу найти PDF?
Решение
Отклонение выборки в первую очередь полезно для непрерывных распределений. Что вам нужно, это образец дискретного распределения. К счастью, это часть STL в C ++ 11. Итак, адаптировано из образца станд :: discrete_distribution:
#include <iostream>
#include <map>
#include <random>
template <typename T>
class sampler
{
std::vector<T> keys;
std::discrete_distribution<T> distr;
public:
sampler(const std::vector<T>& keys, const std::vector<float>& prob) :
keys(keys), distr(prob.begin(), prob.end()) { }
T operator()()
{
static std::random_device rd;
static std::mt19937 gen(rd());
return keys[distr(gen)];
}
};
int main()
{
using T = int;
sampler<T> samp({19, 54, 192, 732}, {.1, .2, .4, .3});
std::map<T, size_t> hist;
for (size_t n = 0; n < 10000; ++n)
++hist[samp()];
for (auto i: hist)
{
std::cout << i.first << " generated " <<
i.second << " times" << std::endl;
}
}
Выход:
19 generated 1010 times
54 generated 2028 times
192 generated 3957 times
732 generated 3005 times
векторы keys а также prob содержать отдельно ключи и значения (вероятности) вашей карты. Это потому что std::discrete_distribution учитывает только вероятности.
Обратите внимание, что operator() не может быть const так как std::discrete_distribution изменяет состояние (естественно) в каждом образце.
Также обратите внимание, что даже если вы осуществляете выборку самостоятельно, используя кумулятивное распределение и бинарный поиск (при этом выборка имеет логарифмическое время в размере вашего домена), существуют более эффективные (постоянные) методы выборки, такие как метод псевдонимов. Я не уверен, какой метод используется
std::discrete_distribution, тем не мение.
Другие решения
Если вы хотите смещать выборку линейно пропорционально значениям, это легко сделать.
Начните с расчета суммы всех значений.
Теперь сгенерируйте одно случайное значение с плавающей точкой между 0 и суммой.
Итерируйте по карте, суммируя значения по мере продвижения. Когда сумма больше, чем случайное значение, рассчитанное ранее, вы нашли свою выборку.
Если вы будете делать это несколько раз на неизменной карте, вы можете создать вектор сумм и выполнить двоичный поиск случайного значения.
Одна возможность использования второго map (или же set) с ключами с неизвестными ошибками (вы кладете все ключи туда, и как только вы отклоняете ключ, потому что он больше, чем начальная случайная переменная, вы удаляете его с карты — и вы ищете ключ в не- заведомо плохой набор, не на всей карте …