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

<p>мне нужна функция, которая генерирует случайное целое число в заданном диапазоне (включая значения границ). у меня нет необоснованных требований к качеству/случайности, у меня есть четыре требования:</p><ul> <li>мне нужно, чтобы это было быстро. мой проект должен генерировать миллионы (а иногда даже десятки миллионов) случайных чисел, и моя текущая функция генератора оказалась узким местом.</li> <li>мне нужно, чтобы он был достаточно равномерным (использование rand () прекрасно).</li> <li>диапазон минимальных и максимальных значений может быть от <0, 1> до <-32727, 32727>.</li> <li>это должно быть посеянным.</li> </ul><p>в настоящее время у меня есть следующий код c++:</p><pre><code>output = min + (rand() * (int)(max - min) / rand\_max) </code></pre><p>проблема в том, что он не является действительно единообразным - max возвращается только тогда, когда rand () = rand\_max (для visual c++ это 1/32727). это основная проблема для небольших диапазонов, таких как <-1, 1>, где последнее значение почти никогда не возвращается.</p><p>поэтому я взял перо и бумагу и придумал следующую формулу (которая основывается на трюке округления целых чисел (int) (n + 0,5)):</p><p><img src="https://i.stack.imgur.com/2c4jz.png" alt="enter image description here"></p><p>но это все еще не дает мне равномерное распределение. повторные прогоны с 10000 выборками дают мне соотношение 37:50:13 для значений значений -1, 0,1.</p><p>не могли бы вы предложить лучшую формулу? (или даже целая функция генератора псевдослучайных чисел)</p>

<p>быстрое, несколько лучшее, чем у вас, но все еще не правильно распределенное решение</p><pre><code>output = min + (rand() % static\_cast<int>(max - min + 1)) </code></pre><p>за исключением случаев, когда размер диапазона является степенью 2, <strong> этот метод производит <a href="https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/">смещенное неравномерное распределение</a> числа </strong> независимо от качества из <code>rand()</code>. для всесторонней проверки качества этого метода, пожалуйста <a href="https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/">прочитайте это</a> .</p>

<p>самый простой (и, следовательно, лучший) ответ c++ (используя стандарт 2011 года)</p><pre><code>#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); </code></pre><p>не нужно заново изобретать колесо. не нужно беспокоиться о предвзятости. не нужно беспокоиться об использовании времени в качестве случайного семени.</p>

<p>если ваш компилятор поддерживает c++ 0x и его использование является опцией для вас, тогда новый стандартный заголовок <code><random></code>, вероятно, удовлетворит ваши потребности. он имеет высококачественный <code>uniform\_int\_distribution</code>, который принимает минимальные и максимальные границы (включительно по мере необходимости), и вы можете выбрать один из различных генераторов случайных чисел для подключения к этому распределению.</p><p>вот код, который генерирует миллион случайных <code>int</code>s, равномерно распределенных в [-57, 365]. я использовал новые возможности std <code><chrono></code> для определения времени, так как вы упомянули, что производительность является для вас серьезной проблемой.</p><pre><code>#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; } </code></pre><p>для меня (intel core i5 2,8 ггц) это распечатывает:</p><p>2.10268e + 07 случайных чисел в секунду.</p><p>вы можете заполнить генератор, передав int в его конструктор:</p><pre><code> g g(seed); </code></pre><p>если позже вы обнаружите, что <code>int</code> не охватывает диапазон, необходимый для вашего распространения, это можно исправить, изменив <code>uniform\_int\_distribution</code> следующим образом (например, на <code>long long</code>):</p><pre><code> typedef std::uniform\_int\_distribution<long long> d; </code></pre><p>если позже вы обнаружите, что <code>minstd\_rand</code> не достаточно качественный генератор, его также можно легко заменить. например.:</p><pre><code> typedef std::mt19937 g; // now using mersenne\_twister\_engine </code></pre><p>имея отдельный контроль над генератором случайных чисел, и случайное распределение может быть довольно освобождающим.</p><p>я также вычислил (не показано) первые 4 "момента" этого распределения (используя <code>minstd\_rand</code>) и сравнил их с <a href="http://en.wikipedia.org/wiki/uniform\_distribution\_(discrete)">теоретическими значениями</a> в попытке количественно оценить качество распределения:</p><pre><code>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 </code></pre><p>(префикс <code>x\_</code> обозначает "ожидаемый")</p>

<p>давайте разделим проблему на две части:</p><ul> <li>сгенерируйте случайное число <code>n</code> в диапазоне от 0 до (max-min).</li> <li>добавить мин к этому числу</li> </ul><p>первая часть, очевидно, самая сложная. давайте предположим, что возвращаемое значение rand () совершенно одинаково. использование по модулю добавит смещение к первым числам <code>(rand\_max + 1) % (max-min+1)</code>. поэтому, если бы мы могли волшебным образом изменить <code>rand\_max</code> на <code>rand\_max - (rand\_max + 1) % (max-min+1)</code>, больше не было бы никакого смещения.</p><p>оказывается, что мы можем использовать эту интуицию, если мы хотим допустить псевдо-недетерминизм во время выполнения нашего алгоритма. всякий раз, когда rand () возвращает слишком большое число, мы просто запрашиваем другое случайное число, пока не получим достаточно маленькое число.</p><p>время выполнения теперь <a href="http://en.wikipedia.org/wiki/geometric\_distribution">геометрически распределено</a> , с ожидаемым значением <code>1/p</code>, где <code>p</code> - вероятность получения достаточно малого числа с первой попытки. так как <code>rand\_max - (rand\_max + 1) % (max-min+1)</code> всегда меньше, чем <code>(rand\_max + 1) / 2</code>, мы знаем, что <code>p > 1/2</code>, поэтому ожидаемое количество итераций всегда будет меньше двух для любого диапазона. с помощью этой методики должна быть возможность генерировать десятки миллионов случайных чисел менее чем за секунду на стандартном процессоре.</p><p>правка:</p><p>хотя вышесказанное является технически правильным, ответ dsimon, вероятно, более полезен на практике. вы не должны реализовывать это самостоятельно. я видел много реализаций выборки отклонения, и часто очень трудно понять, правильно это или нет.</p>

<p>как насчет <a href="http://www.boost.org/doc/libs/1\_45\_0/doc/html/boost\_random/tutorial.html#boost\_random.tutorial.generating\_integers\_in\_a\_range">мерсенн твистер</a> ? реализация boost довольно проста в использовании и хорошо протестирована во многих реальных приложениях. я сам использовал его в нескольких академических проектах, таких как искусственный интеллект и эволюционные алгоритмы.</p><p>вот их пример, где они делают простую функцию, чтобы бросить шестигранный кубик:</p><pre><code>#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(); } </code></pre><p>о, и вот еще несколько улучшений этого генератора на тот случай, если вы не уверены, что вам следует использовать его по сравнению с крайне низкой <code>rand()</code>:</p><blockquote> <p>mersenne twister - это генератор "случайных чисел", изобретенный макото мацумото и такудзи нисимурой; их сайт включает в себя многочисленные реализации алгоритма.</p> <p>по сути, mersenne twister является очень большим регистром сдвига с линейной обратной связью. алгоритм работает с начальным разрядом 19 937, хранящимся в массиве из 624 элементов из 32-разрядных целых чисел без знака. значение 2 ^ 19937-1 представляет собой простое число мерсенна; техника манипулирования с семенем основана на более старом алгоритме "скручивания" - отсюда и название "mersenne twister".</p> <p>привлекательным аспектом mersenne twister является использование двоичных операций - в отличие от трудоемкого умножения - для генерации чисел. алгоритм также имеет очень длительный период и хорошую детализацию. это быстро и эффективно для некриптографических приложений.</p> </blockquote>

<pre><code>int randu(int nmin, int nmax) { return nmin + (int)((double)rand() / (rand\_max+1) * (nmax-nmin+1)); } </code></pre><p>это отображение 32768 целых чисел в (nmax-nmin + 1) целых чисел. отображение будет довольно хорошим, если (nmax-nmin + 1) мало (как в вашем требовании). однако обратите внимание, что если (nmax-nmin + 1) велико, отображение не будет работать (например, вы не можете сопоставить 32768 значений с 30000 значениями с равной вероятностью). если такие диапазоны необходимы - вы должны использовать 32-разрядный или 64-разрядный случайный источник вместо 15-разрядного rand () или игнорировать результаты rand (), выходящие за пределы допустимого диапазона.</p>

<p>вот непредвзятая версия, которая генерирует числа в <code>[low, high]</code>:</p><pre><code>int r; do { r = rand(); } while (r < ((unsigned int)(rand\_max) + 1) % (high + 1 - low)); return r % (high + 1 - low) + low; </code></pre><p>если ваш диапазон достаточно мал, нет причин кэшировать правую часть сравнения в цикле <code>do</code>.</p>

<p>я рекомендую <a href="http://www.boost.org/doc/libs/1\_45\_0/doc/html/boost\_random.html">библиотека boost.random</a> , она очень детализирована и хорошо документирована, позволяет явно указать, какой дистрибутив вы хотите, и в не криптографических сценариях может на самом деле <a href="http://www.boost.org/doc/libs/1\_45\_0/doc/html/boost\_random/performance.html">превосходить</a> типичный реализация библиотеки c библиотеки.</p>

<p>предположим, что min и max являются значениями типа int, [и] означает, что включают это значение, (и) означает, что не включают это значение, используя выше, чтобы получить правильное значение с помощью c ++ rand ()</p><p>ссылка: для () [] определить, посетить:</p><p> <a href="https://en.wikipedia.org/wiki/interval\_(mathematics)">https://en.wikipedia.org/wiki/interval\_ (математика)</a> </p><p>для определения функций rand и srand или rand\_max посетите:</p><p> <a href="http://en.cppreference.com/w/cpp/numeric/random/rand">http://en.cppreference.com/w/cpp/numeric/random/rand</a> </p><p>[мин макс]</p><pre><code>int randnum = rand() % (max - min + 1) + min </code></pre><p>(мин макс]</p><pre><code>int randnum = rand() % (max - min) + min + 1 </code></pre><p>[мин макс)</p><pre><code>int randnum = rand() % (max - min) + min </code></pre><p>(мин макс)</p><pre><code>int randnum = rand() % (max - min - 1) + min + 1 </code></pre>

<p>в этой теме выборка отклонения уже обсуждалась, но я хотел предложить одну оптимизацию, основанную на том факте, что <code>rand() % 2^something</code> не вносит никакого смещения, как уже упоминалось выше.</p><p>алгоритм действительно прост:</p><ul> <li>рассчитать наименьшую степень 2 больше длины интервала</li> <li>рандомизировать одно число в этом "новом" интервале</li> <li>вернуть это число, если оно меньше длины исходного интервала <ul> <li>отклонить иначе</li> </ul> </li> </ul><p>вот мой пример кода:</p><pre><code>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 } </code></pre><p>это хорошо работает, особенно для небольших интервалов, потому что степень 2 будет "ближе" к реальной длине интервала, и поэтому число промахов будет меньше.</p><p>ps<br> очевидно, что избежать рекурсии было бы более эффективно (не нужно рассчитывать сверх и сверх потолка логарифмического ряда ...), но я подумал, что для этого примера это будет более читабельным.</p>