Zufällige Ganzzahl aus einem Bereich generieren

Ich benötige eine Funktion, die eine zufällige Ganzzahl in einem bestimmten Bereich (einschließlich Randwerten) generiert. Ich habe keine unangemessenen Qualitäts- / Zufallsanforderungen, ich habe vier Anforderungen:

• Ich brauche es, um schnell zu sein. Mein Projekt muss Millionen (oder manchmal sogar Dutzende Millionen) Zufallszahlen generieren, und meine aktuelle Generatorfunktion hat sich als Engpass erwiesen.
• Ich brauche es, um einigermaßen einheitlich zu sein (die Verwendung von rand () ist vollkommen in Ordnung).
• Die Min-Max-Bereiche können zwischen <0, 1> und <-32727, 32727> liegen.
• es muss siedbar sein.

Ich habe derzeit folgenden C ++ - Code:

output = min + (rand() * (int)(max - min) / RAND_MAX)

Das Problem ist, dass es nicht wirklich einheitlich ist - max wird nur zurückgegeben, wenn rand () = RAND_MAX ist (für Visual C ++ ist es 1/32727). Dies ist ein großes Problem für kleine Bereiche wie <-1, 1>, in denen der letzte Wert fast nie zurückgegeben wird.

Also griff ich nach Stift und Papier und fand die folgende Formel (die auf dem ganzzahligen Rundungstrick (int) (n + 0,5) aufbaut):

Aber es gibt mir immer noch keine gleichmäßige Verteilung. Wiederholte Läufe mit 10000 Proben ergeben ein Verhältnis von 37:50:13 für die Werte -1, 0,1.

Könnten Sie bitte eine bessere Formel vorschlagen? (oder sogar ganze Pseudozufallszahlengeneratorfunktion)

Eine schnelle, etwas bessere als Ihre, aber immer noch nicht richtig gleichmäßig verteilte Lösung ist

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

Außer wenn die Größe des Bereichs eine Potenz von 2 ist, erzeugt dieses Verfahren unabhängig von der Qualität von voreingenommene ungleichmäßig verteilte Zahlenrand() . Lesen Sie dies bitte, um einen umfassenden Test der Qualität dieser Methode zu erhalten .

Die einfachste (und damit beste) C ++ - Antwort (unter Verwendung des 2011er Standards) lautet

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

Das Rad muss nicht neu erfunden werden. Sie müssen sich keine Sorgen um Voreingenommenheit machen. Sie müssen sich keine Sorgen machen, Zeit als Zufallssamen zu verwenden.

Wenn Ihr Compiler C ++ 0x unterstützt und die Verwendung für Sie eine Option für Sie ist, entspricht der neue Standardheader <random>wahrscheinlich Ihren Anforderungen. Es hat eine hohe Qualität, uniform_int_distributiondie minimale und maximale Grenzen akzeptiert (einschließlich nach Bedarf), und Sie können zwischen verschiedenen Zufallszahlengeneratoren wählen, um diese Verteilung anzuschließen.

Hier ist Code, der eine Million Zufallszahlen erzeugt, die intgleichmäßig in [-57, 365] verteilt sind. Ich habe die neuen Standardfunktionen verwendet <chrono>, um die Zeit zu bestimmen , da die von Ihnen erwähnte Leistung ein wichtiges Anliegen für Sie ist.

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

Für mich (2,8 GHz Intel Core i5) druckt dies aus:

2.10268e + 07 Zufallszahlen pro Sekunde.

Sie können den Generator festlegen, indem Sie ein int an seinen Konstruktor übergeben:

    G g(seed);

Wenn Sie später feststellen, dass intdies nicht den Bereich abdeckt, den Sie für Ihre Distribution benötigen, können Sie dies beheben, indem Sie Folgendes ändern uniform_int_distribution(z. B. in long long):

    typedef std::uniform_int_distribution<long long> D;

Wenn Sie später feststellen, dass der minstd_randGenerator nicht hoch genug ist, kann er auch problemlos ausgetauscht werden. Z.B:

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

Eine getrennte Kontrolle über den Zufallszahlengenerator und die Zufallsverteilung kann ziemlich befreiend sein.

Ich habe auch die ersten 4 "Momente" dieser Verteilung berechnet (nicht gezeigt) (unter Verwendung minstd_rand) und sie mit den theoretischen Werten verglichen , um die Qualität der Verteilung zu quantifizieren:

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

(Das x_Präfix bezieht sich auf "erwartet")

Teilen wir das Problem in zwei Teile:

• Generieren Sie eine Zufallszahl nim Bereich von 0 bis (max-min).
• Fügen Sie dieser Zahl min hinzu

Der erste Teil ist offensichtlich der schwierigste. Nehmen wir an, dass der Rückgabewert von rand () vollkommen einheitlich ist. Wenn Sie Modulo verwenden, werden die ersten (RAND_MAX + 1) % (max-min+1)Zahlen verzerrt. Wenn wir also auf magische Weise verändern könnten RAND_MAXzu RAND_MAX - (RAND_MAX + 1) % (max-min+1), es würde nicht mehr Bias.

Es stellt sich heraus, dass wir diese Intuition verwenden können, wenn wir bereit sind, Pseudo-Nichtdeterminismus in die Laufzeit unseres Algorithmus einzubeziehen. Immer wenn rand () eine zu große Zahl zurückgibt, fragen wir einfach nach einer anderen Zufallszahl, bis wir eine erhalten, die klein genug ist.

Die Laufzeit wird nun geometrisch verteilt mit Erwartungswert , 1/pwo pist die Wahrscheinlichkeit, eine klein genug Zahl auf dem ersten Versuch zu bekommen. Da RAND_MAX - (RAND_MAX + 1) % (max-min+1)immer weniger als ist (RAND_MAX + 1) / 2, wissen wir das p > 1/2, so dass die erwartete Anzahl von Iterationen für jeden Bereich immer weniger als zwei beträgt. Mit dieser Technik sollte es möglich sein, auf einer Standard-CPU in weniger als einer Sekunde zig Millionen Zufallszahlen zu generieren.

BEARBEITEN:

Obwohl das oben Gesagte technisch korrekt ist, ist die Antwort von DSimon in der Praxis wahrscheinlich nützlicher. Sie sollten dieses Zeug nicht selbst implementieren. Ich habe viele Implementierungen von Ablehnungsstichproben gesehen und es ist oft sehr schwierig zu sehen, ob es korrekt ist oder nicht.

Wie wäre es mit dem Mersenne Twister ? Die Boost-Implementierung ist recht einfach zu bedienen und in vielen realen Anwendungen gut getestet. Ich habe es selbst in mehreren akademischen Projekten wie künstlicher Intelligenz und evolutionären Algorithmen verwendet.

Hier ist ihr Beispiel, in dem sie eine einfache Funktion zum Werfen eines sechsseitigen Würfels ausführen:

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

Oh, und hier ist noch ein paar Zuhälter dieses Generators, falls Sie nicht überzeugt sind, dass Sie ihn über den weitaus minderwertigen verwenden sollten rand():

Der Mersenne Twister ist ein "Zufallszahlen" -Generator, der von Makoto Matsumoto und Takuji Nishimura erfunden wurde. Ihre Website enthält zahlreiche Implementierungen des Algorithmus.

Im Wesentlichen ist der Mersenne Twister ein sehr großes Schieberegister mit linearer Rückkopplung. Der Algorithmus arbeitet mit einem 19.937-Bit-Startwert, der in einem 624-Element-Array von 32-Bit-Ganzzahlen ohne Vorzeichen gespeichert ist. Der Wert 2 ^ 19937-1 ist eine Mersenne-Primzahl; Die Technik zur Manipulation des Samens basiert auf einem älteren "Twisting" -Algorithmus - daher der Name "Mersenne Twister".

Ein ansprechender Aspekt des Mersenne Twister ist die Verwendung von Binäroperationen - im Gegensatz zur zeitaufwändigen Multiplikation - zur Erzeugung von Zahlen. Der Algorithmus hat auch eine sehr lange Periode und eine gute Granularität. Es ist sowohl schnell als auch effektiv für nicht kryptografische Anwendungen.

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

Dies ist eine Zuordnung von 32768 Ganzzahlen zu (nMax-nMin + 1) Ganzzahlen. Das Mapping ist ziemlich gut, wenn (nMax-nMin + 1) klein ist (wie in Ihrer Anforderung). Beachten Sie jedoch, dass die Zuordnung nicht funktioniert, wenn (nMax-nMin + 1) groß ist (z. B. können Sie 32768-Werte nicht mit gleicher Wahrscheinlichkeit 30000-Werten zuordnen). Wenn solche Bereiche benötigt werden, sollten Sie anstelle des 15-Bit-Rand () eine 32-Bit- oder 64-Bit-Zufallsquelle verwenden oder Rand () -Ergebnisse ignorieren, die außerhalb des Bereichs liegen.

Hier ist eine unvoreingenommene Version, die Zahlen generiert in [low, high]:

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

Wenn Ihr Bereich relativ klein ist, gibt es keinen Grund, die rechte Seite des Vergleichs in der doSchleife zwischenzuspeichern.

Ich empfehle die Boost.Random-Bibliothek , sie ist sehr detailliert und gut dokumentiert, lässt Sie explizit angeben, welche Verteilung Sie möchten, und kann in nicht kryptografischen Szenarien eine typische Rand-Implementierung der C-Bibliothek tatsächlich übertreffen .

Angenommen, min und max sind int-Werte. [und] bedeutet, diesen Wert einzuschließen. (und) bedeutet, diesen Wert nicht einzuschließen. Verwenden Sie oben, um mit c ++ rand () den richtigen Wert zu erhalten.

Referenz: für () [] definieren, besuchen:

https://en.wikipedia.org/wiki/Interval_(mathematics)

Informationen zur Rand- und Randfunktion oder zur Definition von RAND_MAX finden Sie unter:

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

[Minimal Maximal]

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

(Minimal Maximal]

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

[Minimal Maximal)

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

(Minimal Maximal)

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

In diesem Thread wurde die Stichprobenauswahl bereits besprochen, aber ich wollte eine Optimierung vorschlagen, die auf der Tatsache basiert, dass rand() % 2^somethingkeine Verzerrung eingeführt wird, wie oben bereits erwähnt.

Der Algorithmus ist wirklich einfach:

• Berechnen Sie die kleinste Potenz von 2 größer als die Intervalllänge
• randomisiere eine Zahl in diesem "neuen" Intervall
• Geben Sie diese Zahl zurück, wenn sie kleiner als die Länge des ursprünglichen Intervalls ist
  • anderweitig ablehnen

Hier ist mein Beispielcode:

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
} 

Dies funktioniert besonders gut für kleine Intervalle, da die Potenz von 2 "näher" an der tatsächlichen Intervalllänge liegt und daher die Anzahl der Fehlschläge geringer ist.

PS
Natürlich wäre es effizienter, die Rekursion zu vermeiden (es ist nicht erforderlich, immer wieder über die Protokollobergrenze zu rechnen.), Aber ich dachte, dass dies für dieses Beispiel besser lesbar ist.

Beachten Sie, dass in den meisten Vorschlägen der anfängliche Zufallswert, den Sie von der Funktion rand () erhalten haben, der normalerweise von 0 bis RAND_MAX reicht, einfach verschwendet wird. Sie erstellen nur eine Zufallszahl daraus, während es eine solide Prozedur gibt, die Ihnen mehr geben kann.

Angenommen, Sie möchten einen [min, max] Bereich mit ganzzahligen Zufallszahlen. Wir beginnen bei [0, max-min]

Nehmen Sie die Basis b = max-min + 1

Beginnen Sie mit der Darstellung einer Zahl, die Sie von rand () in Basis b erhalten haben.

Auf diese Weise haben Sie Floor (log (b, RAND_MAX)), da jede Ziffer in Basis b, außer möglicherweise der letzten, eine Zufallszahl im Bereich [0, max-min] darstellt.

Natürlich ist die endgültige Verschiebung zu [min, max] für jede Zufallszahl r + min einfach.

int n = NUM_DIGIT-1;
while(n >= 0)
{
    r[n] = res % b;
    res -= r[n];
    res /= b;
    n--;
}

Wenn NUM_DIGIT die Anzahl der Ziffern in Basis b ist, die Sie extrahieren können, und das ist

NUM_DIGIT = floor(log(b,RAND_MAX))

dann ist das Obige eine einfache Implementierung des Extrahierens von NUM_DIGIT-Zufallszahlen von 0 bis b-1 aus einer RAND_MAX-Zufallszahl, die b <RAND_MAX liefert.

Die Formel dafür ist sehr einfach. Probieren Sie diesen Ausdruck aus.

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

Der folgende Ausdruck sollte unvoreingenommen sein, wenn ich mich nicht irre:

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

Ich gehe hier davon aus, dass rand () einen zufälligen Wert im Bereich zwischen 0,0 und 1,0 ohne 1,0 liefert und dass max und min ganze Zahlen mit der Bedingung sind, dass min <max.