Генерируем случайные числа по "карте вероятностей"

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

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

Применять, как делается в миллионах образцов, srand(time(0)) и затем rand(), которая возвращает число 0 до RAND_MAX, обычно равного всего-то 32767, сегодня, думаю, уже не надо, а лучше функции из <random>. Показано, как при их применении простейшим образом с помощью random_device проинициализировать генератор случайных чисел, чтобы цепочки чисел получались каждый раз разные.

Код проверялся в консоли Visual Studio 2019. Он приведён далее, а после кода - образец вывода программы в консоль.

#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
using namespace std;

typedef vector <pair<string, double> >::const_iterator probabilitiesConstIterator;
typedef vector <pair<string, double> > probabilitiesType;

int main() {
 probabilitiesType probabilities;
 probabilities.push_back(make_pair("half", 1/2.0));
 probabilities.push_back(make_pair("fourth", 1/4.0));
 probabilities.push_back(make_pair("alfa", 1/5.0));
 probabilities.push_back(make_pair("magic", 1 / 20.0));
 
 vector <string> generatedNames;
 vector <int> decider; //"решалка"
 int seed = 65536; //число, по модулю которого нормируем
 for (int i = 0; i < probabilities.size(); i++) {
  if (i == 0) {
   decider.push_back(seed * (probabilities[i].second));
  }
  else {
   int number = 0;
   for (int j = 0; j < i; j++) {
    number += seed * (probabilities[j].second);
   }
   number += seed * probabilities[i].second;
   decider.push_back(number);
  }
 }
 int testsCount = 1e6; //тестов
 random_device rd;
 default_random_engine generator(rd());
 uniform_int_distribution <int> distribution(0, seed-1);

 for (int i = 0; i < testsCount; i++) {
  int randnumber = distribution(generator) % seed;
  int j = 0;
  while (randnumber > decider[j]) j++;
  generatedNames.push_back((probabilities[j]).first);
 }
 cout << "letter  frequency real  frequency expected\n";
 for (probabilitiesConstIterator i = probabilities.begin(); i != probabilities.end(); i++) {
  cout << left << setw(8) << i->first;
  int found = count(generatedNames.begin(), generatedNames.end(), i->first);
  cout << left << setw(16) << found / (double)testsCount
       << left << setw(16) << i->second << endl;
 }
 return 0;
}

letter  frequency real  frequency expected
half    0.499881        0.5
fourth  0.249828        0.25
alfa    0.200352        0.2
magic   0.049939        0.05

13.06.2020, 00:42 [1058 просмотров]