webentwicklung-frage-antwort-db.com.de

Gewichtete Zufallszahlen

Ich versuche eine gewichtete Zufallszahl zu implementieren. Ich stoße gerade mit dem Kopf gegen die Wand und kann das nicht herausfinden.

In meinem Projekt (Hold'em-Handbereiche, subjektive All-in-Equity-Analyse) verwende ich Boosts Zufallsfunktionen. Angenommen, ich möchte eine Zufallszahl zwischen 1 und 3 auswählen (also entweder 1, 2 oder 3). Boosts Mersenne Twister Generator wirkt wie ein Zauber dafür. Ich möchte jedoch, dass die Auswahl wie folgt gewichtet wird:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Hat Boost dafür irgendeine Funktionalität?

85
nhaa123

Es gibt einen einfachen Algorithmus für die zufällige Auswahl eines Artikels, bei dem Artikel individuelle Gewichte haben:

1) Berechnen Sie die Summe aller Gewichte

2) Wähle eine Zufallszahl, die 0 oder größer ist und kleiner als die Summe der Gewichte ist

3) Gehen Sie die Artikel einzeln durch und subtrahieren Sie deren Gewicht von Ihrer Zufallszahl, bis Sie den Artikel erhalten, bei dem die Zufallszahl geringer ist als das Gewicht des Artikels

Pseudocode zur Veranschaulichung:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

Dies sollte einfach an Ihre Boost-Container und dergleichen anzupassen sein.


Wenn sich Ihre Gewichte nur selten ändern, Sie jedoch häufig nach dem Zufallsprinzip auswählen und Ihr Container Zeiger auf die Objekte speichert oder mehr als ein paar Dutzend Elemente lang ist (im Grunde müssen Sie ein Profil erstellen, um zu wissen, ob dies hilft oder behindert). Dann gibt es eine Optimierung:

Durch Speichern der kumulativen Gewichtssumme in jedem Artikel können Sie eine binäre Suche verwenden, um den Artikel auszuwählen, der dem Auswahlgewicht entspricht.


Wenn Sie die Anzahl der Elemente in der Liste nicht kennen, gibt es einen sehr übersichtlichen Algorithmus namens Reservoir Sampling , der zur Gewichtung angepasst werden kann.

146
Will

Aktualisierte Antwort auf eine alte Frage. Sie können dies in C++ 11 ganz einfach mit der std :: lib tun:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Ausgabe auf meinem System:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Beachten Sie, dass der größte Teil des obigen Codes nur zum Anzeigen und Analysieren der Ausgabe bestimmt ist. Die eigentliche Generierung besteht nur aus wenigen Codezeilen. Die Ausgabe zeigt, dass die angeforderten "Wahrscheinlichkeiten" erhalten wurden. Sie müssen die angeforderte Ausgabe durch 1,5 dividieren, da dies die Summe der Anforderungen ist.

47
Howard Hinnant

Wenn sich Ihre Gewichte langsamer ändern als gezeichnet, wird C++ 11 discrete_distribution wird am einfachsten sein:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Beachten Sie jedoch, dass die c ++ 11 discrete_distribution berechnet alle kumulierten Summen bei der Initialisierung. Normalerweise möchten Sie das, weil es die Abtastzeit einmalig beschleunigt O(N) Kosten. Bei einer sich schnell ändernden Verteilung entstehen jedoch hohe Berechnungs nd Speicherkosten) Beispiel: Wenn die Gewichtung angibt, wie viele Elemente vorhanden sind, und Sie jedes Mal, wenn Sie eines zeichnen, entfernen, möchten Sie wahrscheinlich einen benutzerdefinierten Algorithmus.

Wills Antwort --- (https://stackoverflow.com/a/1761646/837451 vermeidet diesen Overhead, zeichnet sich jedoch langsamer ab als C++ 11, da keine binäre Suche verwendet werden kann.

Um dies zu überprüfen, können Sie die entsprechenden Zeilen (/usr/include/c++/5/bits/random.tcc auf meiner Ubuntu 16.04 + GCC 5.3 Installation):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }
13
mmdanziger

Was ich mache, wenn ich Zahlen gewichten muss, ist die Verwendung einer Zufallszahl für das Gewicht.

Zum Beispiel: Ich muss Zufallszahlen von 1 bis 3 mit den folgenden Gewichten generieren:

  • 10% einer Zufallszahl könnten 1 sein
  • 30% einer Zufallszahl könnten 2 sein
  • 60% einer Zufallszahl könnten 3 sein

Dann benutze ich:

weight = Rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

Dabei hat es zufällig 10% der Wahrscheinlichkeiten, 1, 30%, 2 und 60%, 3 zu sein.

Sie können damit nach Ihren Wünschen spielen.

Hoffe ich konnte dir helfen, Viel Glück!

10
Chirry

Bauen Sie einen Beutel (oder std :: vector) mit allen Gegenständen, die kommissioniert werden können.
Stellen Sie sicher, dass die Anzahl der Artikel proportional zu Ihrer Gewichtung ist.

Beispiel:

  • 1 60%
  • 2 35%
  • 3 5%

So haben Sie eine Tasche mit 100 Artikeln mit 60 1, 35 2 und 5 3.
Sortiere nun den Beutel zufällig (std :: random_shuffle)

Entnehmen Sie nacheinander Elemente aus dem Beutel, bis dieser leer ist.
Einmal leer, re-randomisiere den Beutel und beginne erneut.

3
Martin York

Wählen Sie eine Zufallszahl für [0,1], die der Standardoperator () für ein Boost-RNG sein sollte. Wählen Sie den Artikel mit kumulativer Wahrscheinlichkeitsdichtefunktion> = diese Zahl:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Dabei gibt random01 () ein double> = 0 und <1 zurück. Beachten Sie, dass für das oben Gesagte nicht die Wahrscheinlichkeit 1 erforderlich ist. es normalisiert sie für dich.

p ist nur eine Funktion, die einem Element in der Sammlung eine Wahrscheinlichkeit zuweist [begin, end). Sie können es weglassen (oder eine Identität verwenden), wenn Sie nur eine Folge von Wahrscheinlichkeiten haben.

0
Jonathan Graehl