Более эффективный способ генерации этого случайного распределения? - PullRequest
Новая
       11

Более эффективный способ генерации этого случайного распределения?

3 голосов
/ 19 сентября 2011

Существует ли более эффективный, возможно, более математический и менее алгоритмический способ достижения аналогичного распределения случайных чисел с этим? 

unsigned int weighted_random_UINT()
{
    float r2 = 1;
    while(rand() % 4 != 0) // 3/4 chance
    {
        r2 *= fmod(
            ((float)rand()/RAND_MAX)+1, // random float between 1 and 2
            (float)UINT_MAX
        );
    }
    return (unsigned int)r2 - 1;
}

Ниже приведена менее безопасная, но более легко читаемая версия внутренней частиwhile. 

r2 *= ((float)rand()/RAND_MAX)+1;

Визуализация распределения: the distribution visualized
Сравнение между более плавным решением вопроса (1-й график) и более быстрым решением в лучшем ответе (2-й график): сравнение http://with -logic.co.uk / a / graph.png

1 Ответ

5 голосов
/ 19 сентября 2011

Я думаю, вам не нужно проходить через это, но одного раза достаточно, вот так: 

unsigned int weighted_random_UINT()
{
    float r2 = ((float)rand()/RAND_MAX)+1; // random float between 1 and 2
    unsigned int k = 0;
    while(rand() % 4 != 0) // 3/4 chance
    {k = k < UINT_MAX ? k + 1: UINT_MAX;}
    return (unsigned int)fpow(r2,(float)k) - 1;
}

Первая часть - это геометрическое распределение, а последняя - равномерное распределение. А ты хочешь (1+U(0,1))^G(3/4).

Должна быть возможность найти более быстрый способ найти G (3/4).

Edit: Я нашел это в Википедии: http://en.wikipedia.org/wiki/Geometric_distribution#Related_distributions

G(p)=floor(ln(U)/ln(1-p))

Таким образом, вы хотите: 

U^floor(ln(U)/ln(1-3/4))

Что должно быть всего два вызова к рэнду.

...