Generowanie losowej liczby całkowitej z zakresu

Najprostsza (a co za tym idzie najlepsza) odpowiedź C++ (przy użyciu standardu 2011) to

#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);

Jeśli twój kompilator obsługuje C++0x i korzystanie z niego jest opcją dla ciebie, to nowy standard <random> nagłówek prawdopodobnie spełni Twoje potrzeby. Ma wysoką jakość uniform_int_distribution, która akceptuje minimalne i maksymalne granice (włącznie z potrzebami), i możesz wybierać spośród różnych generatorów liczb losowych, aby podłączyć się do tej dystrybucji.

Oto kod, który generuje milion losowych int s równomiernie rozłożonych w [-57, 365]. Użyłem nowych urządzeń std <chrono> do czasu, jak wspomniałeś wydajność jest głównym problemem dla Ciebie.

#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;
}

Dla mnie (2,8 GHz Intel Core i5) to drukuje:

2.10268 e + 07 losowych liczb na sekundę.

    G g(seed);

Jeśli później okaże się, że int nie obejmuje zakresu potrzebnego dla twojej dystrybucji, można temu zaradzić zmieniając uniform_int_distribution w ten sposób (np. long long):

    typedef std::uniform_int_distribution<long long> D;

Jeśli później okaże się, że minstd_rand nie jest wystarczająco wysokiej jakości generator, który można również łatwo wymienić. Np.:

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

Obliczyłem również (nie pokazałem) pierwsze 4 "momenty" tego rozkładu (używając minstd_rand) i porównałem je do wartości teoretycznych , próbując określić jakość rozkładu:

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

(przedrostek x_ odnosi się do "oczekiwanego")

Podzielmy problem na dwie części:

• Wygeneruj losową liczbę n w zakresie od 0 do (max-min).
• Dodaj min do tej liczby

Okazuje się, że możemy użyć tej intuicji, jeśli jesteśmy skłonni dopuścić pseudo-nondeterminizm do czasu działania naszego algorytmu. Ilekroć rand () zwraca zbyt dużą liczbę, po prostu pytamy o inną liczbę losową, dopóki nie otrzymamy takiej, która jest wystarczająco mała.

Czas pracy jest teraz geometrycznie rozłożony, z wartością oczekiwaną 1/p Gdzie p jest prawdopodobieństwem uzyskania wystarczająco małej liczby przy pierwszej próbie. Ponieważ {[3] } jest zawsze mniejsza niż (RAND_MAX + 1) / 2, wiemy, że p > 1/2, więc spodziewana liczba iteracji będzie zawsze być mniej niż dwa dla dowolnego zakresu. Powinno być możliwe wygenerowanie dziesiątek milionów liczb losowych w czasie krótszym niż sekundę na standardowym procesorze za pomocą tej techniki.

EDIT:

Chociaż powyższe jest technicznie poprawne, odpowiedź DSimon jest prawdopodobnie bardziej przydatna w praktyce. Nie powinieneś tego robić sam. Widziałem wiele implementacji odrzucania próbkowania i często bardzo trudno jest sprawdzić, czy jest poprawny, czy nie.

A może Twister Mersenne? Wdrożenie boost jest dość łatwe w użyciu i jest dobrze Przetestowane w wielu rzeczywistych aplikacjach. Sam wykorzystałem go w kilku projektach naukowych, takich jak sztuczna inteligencja i algorytmy ewolucyjne.

Oto ich przykład, w którym tworzą prostą funkcję do obracania sześciostronnej matrycy:

#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();
}

Mersenne Twister jest " przypadkowym number " generator wymyślony przez Makoto Matsumoto i Takuji Nishimura; ich strona zawiera liczne implementacji algorytmu. Zasadniczo, Mersenne Twister jest bardzo duże przesunięcie liniowo-zwrotne Zarejestruj się. Algorytm działa na 19937 ziaren bitowych, przechowywanych w 624-elementowa tablica 32-bitowych niepodpisanych liczby całkowite. Wartość 2^19937-1 to Mersenne prime; technika dla manipulowanie materiał siewny jest oparty na starszy algorytm "skręcania" - stąd nazwa "Mersenne Twister".

Atrakcyjny aspekt Mersenne Twister to wykorzystanie binarnych operacji - w przeciwieństwie do czasochłonne mnożenie - dla generowanie liczb. Algorytm również ma bardzo długi okres i dobrze ziarnistość. Jest szybki i skuteczne w zastosowaniach innych niż kryptograficzne.

int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

Jest to odwzorowanie 32768 liczb całkowitych na (nMax-nMin+1) liczb całkowitych. Mapowanie będzie całkiem dobre, jeśli (nMax-nMin+1) jest mały (jak w wymaganiach). Należy jednak pamiętać, że jeśli (nMax-nMin+1) jest duży, mapowanie nie będzie działać (na przykład - nie można mapować wartości 32768 do wartości 30000 z równym prawdopodobieństwem). Jeśli takie zakresy są potrzebne - powinieneś użyć 32-bitowego lub 64-bitowego źródła losowego, zamiast 15-bitowej metody rand(), lub zignorować wyniki rand (), które są poza zakresem.

Oto bezstronna wersja, która generuje liczby w [low, high]:

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

Jeśli zakres jest stosunkowo mały, nie ma powodu, aby buforować prawą stronę porównania w pętli do.

Polecam Boost.Losowa biblioteka , jest bardzo szczegółowa i dobrze udokumentowana, pozwala jednoznacznie określić, jakiej dystrybucji chcesz, a w scenariuszach nie-kryptograficznych może faktycznie przewyższyć typową implementację rand w Bibliotece C.

Załóżmy, że min i max są wartościami int, [i] oznacza włączenie tej wartości, (i ) oznacza, że nie zawiera tej wartości, użycie powyższego, aby uzyskać właściwą wartość za pomocą C++ rand ()

Odniesienie: for () [] define, visit:

Https://en.wikipedia.org/wiki/Interval_ (matematyka)

Dla funkcji rand i srand lub zdefiniuj RAND_MAX, odwiedź stronę:

Http://en.cppreference.com/w/cpp/numeric/random/rand

[min, max]

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

(min, max]

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

[min, max)

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

(min, max)

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

W tym wątku omówiono już próbkowanie odrzucenia, ale chciałem zaproponować jedną optymalizację opartą na fakcie, że rand() % 2^something nie wprowadza żadnych stronniczości, jak już wspomniano powyżej.

Algorytm jest naprawdę prosty:

• Oblicz najmniejszą moc 2 większą od długości przedziału
• randomizuj jedną liczbę w tym" nowym " przedziale
• Zwróć tę liczbę, jeśli jest mniejsza niż długość oryginalnego interwału
  • Odrzuć inaczej

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
} 

To działa dobrze zwłaszcza dla małych interwałów, ponieważ moc 2 będzie "bliżej" do rzeczywistej długości interwału, a więc liczba chybień będzie mniejsza.

PS
Oczywiście unikanie rekurencji byłoby bardziej efektywne (nie trzeba obliczać ponad i ponad pułapem dziennika..) ale myślałem, że jest bardziej czytelny dla tego przykładu.

Wzór na to jest bardzo prosty, więc spróbuj tego wyrażenia,

 int num = (int) rand() % (max - min) + min;  
 //Where rand() returns a random number between 0.0 and 1.0

Poniższe wyrażenie powinno być bezstronne, jeśli się nie mylę:

std::floor( ( max - min + 1.0 ) * rand() ) + min;

Zakładam tutaj, że rand() daje losową wartość w zakresie od 0,0 do 1,0, nie wliczając 1,0 i że max i min są liczbami całkowitymi z warunkiem, że min