it-swarm-ru.tech

Генерация случайного целого числа из диапазона

Мне нужна функция, которая генерирует случайное целое число в заданном диапазоне (включая значения границ). У меня нет необоснованных требований к качеству/случайности, у меня есть четыре требования:

  • Мне нужно, чтобы это было быстро. Мой проект должен генерировать миллионы (а иногда даже десятки миллионов) случайных чисел, и моя текущая функция генератора оказалась узким местом.
  • Мне нужно, чтобы он был достаточно равномерным (использование Rand () прекрасно).
  • диапазон минимальных и максимальных значений может быть от <0, 1> до <-32727, 32727>.
  • это должно быть посеянным.

В настоящее время у меня есть следующий код C++:

output = min + (Rand() * (int)(max - min) / Rand_MAX)

Проблема в том, что он не является действительно единообразным - max возвращается только тогда, когда Rand () = Rand_MAX (для Visual C++ это 1/32727). Это основная проблема для небольших диапазонов, таких как <-1, 1>, где последнее значение почти никогда не возвращается.

Поэтому я взял перо и бумагу и придумал следующую формулу (которая основывается на трюке округления целых чисел (int) (n + 0,5)):

enter image description here

Но это все еще не дает мне равномерное распределение. Повторные прогоны с 10000 выборками дают мне соотношение 37:50:13 для значений значений -1, 0,1.

Не могли бы вы предложить лучшую формулу? (или даже целая функция генератора псевдослучайных чисел)

144
Matěj Zábský

Быстрое, несколько лучшее, чем у вас, но все еще не правильно распределенное решение

output = min + (Rand() % static_cast<int>(max - min + 1))

За исключением случаев, когда размер диапазона является степенью 2, этот метод производит смещенное неравномерное распределение числа независимо от качества из Rand(). Для всесторонней проверки качества этого метода, пожалуйста прочитайте это .

94
Mark B

Самый простой (и, следовательно, лучший) ответ C++ (используя стандарт 2011 года)

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

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

268
Walter

Если ваш компилятор поддерживает C++ 0x и его использование является опцией для вас, тогда новый стандартный заголовок <random>, вероятно, удовлетворит ваши потребности. Он имеет высококачественный uniform_int_distribution, который принимает минимальные и максимальные границы (включительно по мере необходимости), и вы можете выбрать один из различных генераторов случайных чисел для подключения к этому распределению.

Вот код, который генерирует миллион случайных ints, равномерно распределенных в [-57, 365]. Я использовал новые возможности std <chrono> для определения времени, так как вы упомянули, что производительность является для вас серьезной проблемой.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_Rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second.\n";
    return c;
}

Для меня (Intel Core i5 2,8 ГГц) это распечатывает:

2.10268e + 07 случайных чисел в секунду.

Вы можете заполнить генератор, передав int в его конструктор:

    G g(seed);

Если позже вы обнаружите, что int не охватывает диапазон, необходимый для вашего распространения, это можно исправить, изменив uniform_int_distribution следующим образом (например, на long long):

    typedef std::uniform_int_distribution<long long> D;

Если позже вы обнаружите, что minstd_Rand не достаточно качественный генератор, его также можно легко заменить. Например.:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

Имея отдельный контроль над генератором случайных чисел, и случайное распределение может быть довольно освобождающим.

Я также вычислил (не показано) первые 4 "момента" этого распределения (используя minstd_Rand) и сравнил их с теоретическими значениями в попытке количественно оценить качество распределения:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

(Префикс x_ обозначает "ожидаемый")

60
Howard Hinnant

Давайте разделим проблему на две части:

  • Сгенерируйте случайное число n в диапазоне от 0 до (max-min).
  • Добавить мин к этому числу

Первая часть, очевидно, самая сложная. Давайте предположим, что возвращаемое значение Rand () совершенно одинаково. Использование по модулю добавит смещение к первым числам (Rand_MAX + 1) % (max-min+1). Поэтому, если бы мы могли волшебным образом изменить Rand_MAX на Rand_MAX - (Rand_MAX + 1) % (max-min+1), больше не было бы никакого смещения.

Оказывается, что мы можем использовать эту интуицию, если мы хотим допустить псевдо-недетерминизм во время выполнения нашего алгоритма. Всякий раз, когда Rand () возвращает слишком большое число, мы просто запрашиваем другое случайное число, пока не получим достаточно маленькое число.

Время выполнения теперь геометрически распределено , с ожидаемым значением 1/p, где p - вероятность получения достаточно малого числа с первой попытки. Так как Rand_MAX - (Rand_MAX + 1) % (max-min+1) всегда меньше, чем (Rand_MAX + 1) / 2, мы знаем, что p > 1/2, поэтому ожидаемое количество итераций всегда будет меньше двух для любого диапазона. С помощью этой методики должна быть возможность генерировать десятки миллионов случайных чисел менее чем за секунду на стандартном процессоре.

Правка:

Хотя вышесказанное является технически правильным, ответ DSimon, вероятно, более полезен на практике. Вы не должны реализовывать это самостоятельно. Я видел много реализаций выборки отклонения, и часто очень трудно понять, правильно это или нет.

15
Jørgen Fogh

Как насчет Мерсенн Твистер ? Реализация boost довольно проста в использовании и хорошо протестирована во многих реальных приложениях. Я сам использовал его в нескольких академических проектах, таких как искусственный интеллект и эволюционные алгоритмы.

Вот их пример, где они делают простую функцию, чтобы бросить шестигранный кубик:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

О, и вот еще несколько улучшений этого генератора на тот случай, если вы не уверены, что вам следует использовать его по сравнению с крайне низкой Rand():

Mersenne Twister - это генератор "случайных чисел", изобретенный Макото Мацумото и Такудзи Нисимурой; их сайт включает в себя многочисленные реализации алгоритма.

По сути, Mersenne Twister является очень большим регистром сдвига с линейной обратной связью. Алгоритм работает с начальным разрядом 19 937, хранящимся в массиве из 624 элементов из 32-разрядных целых чисел без знака. Значение 2 ^ 19937-1 представляет собой простое число Мерсенна; Техника манипулирования с семенем основана на более старом алгоритме "скручивания" - отсюда и название "Mersenne Twister".

Привлекательным аспектом Mersenne Twister является использование двоичных операций - в отличие от трудоемкого умножения - для генерации чисел. Алгоритм также имеет очень длительный период и хорошую детализацию. Это быстро и эффективно для некриптографических приложений.

13
Aphex
int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)Rand() / (Rand_MAX+1) * (nMax-nMin+1));
}

Это отображение 32768 целых чисел в (nMax-nMin + 1) целых чисел. Отображение будет довольно хорошим, если (nMax-nMin + 1) мало (как в вашем требовании). Однако обратите внимание, что если (nMax-nMin + 1) велико, отображение не будет работать (например, вы не можете сопоставить 32768 значений с 30000 значениями с равной вероятностью). Если такие диапазоны необходимы - вы должны использовать 32-разрядный или 64-разрядный случайный источник вместо 15-разрядного Rand () или игнорировать результаты Rand (), выходящие за пределы допустимого диапазона.

11
Lior Kogan

Вот непредвзятая версия, которая генерирует числа в [low, high]:

int r;
do {
  r = Rand();
} while (r < ((unsigned int)(Rand_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

Если ваш диапазон достаточно мал, нет причин кэшировать правую часть сравнения в цикле do.

4
Jeremiah Willcock

Я рекомендую библиотека Boost.Random , она очень детализирована и хорошо документирована, позволяет явно указать, какой дистрибутив вы хотите, и в не криптографических сценариях может на самом деле превосходить типичный Реализация библиотеки C библиотеки.

3
DSimon

предположим, что min и max являются значениями типа int, [и] означает, что включают это значение, (и) означает, что не включают это значение, используя выше, чтобы получить правильное значение с помощью c ++ Rand ()

ссылка: для () [] определить, посетить:

https://en.wikipedia.org/wiki/Interval_ (математика)

для определения функций Rand и srand или Rand_MAX посетите:

http://en.cppreference.com/w/cpp/numeric/random/Rand

[мин Макс]

int randNum = Rand() % (max - min + 1) + min

(мин Макс]

int randNum = Rand() % (max - min) + min + 1

[мин Макс)

int randNum = Rand() % (max - min) + min

(мин Макс)

int randNum = Rand() % (max - min - 1) + min + 1
1
Huang Kun

В этой теме выборка отклонения уже обсуждалась, но я хотел предложить одну оптимизацию, основанную на том факте, что Rand() % 2^something не вносит никакого смещения, как уже упоминалось выше.

Алгоритм действительно прост:

  • рассчитать наименьшую степень 2 больше длины интервала
  • рандомизировать одно число в этом "новом" интервале
  • вернуть это число, если оно меньше длины исходного интервала
    • отклонить иначе

Вот мой пример кода:

int randInInterval(int min, int max) {
    int intervalLen = max - min + 1;
    //now calculate the smallest power of 2 that is >= than `intervalLen`
    int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));

    int randomNumber = Rand() % ceilingPowerOf2; //this is "as uniform as Rand()"

    if (randomNumber < intervalLen)
        return min + randomNumber;      //ok!
    return randInInterval(min, max);    //reject sample and try again
} 

Это хорошо работает, особенно для небольших интервалов, потому что степень 2 будет "ближе" к реальной длине интервала, и поэтому число промахов будет меньше.

PS
Очевидно, что избежать рекурсии было бы более эффективно (не нужно рассчитывать сверх и сверх потолка логарифмического ряда ...), но я подумал, что для этого примера это будет более читабельным.

0
Pado