Дублирующиеся значения, сгенерированные mt19937
Я работаю с C ++ 11 random библиотека, и у меня есть небольшая программа, которая генерирует пару координат x, y на окружности с единичным радиусом. Вот простая многопоточная программа
#include <iostream>
#include <fstream>
#include <random>
using namespace std;int main()
{
const double PI = 3.1415;double angle, radius, X, Y;
int i;
vector<double> finalPositionX, finalPositionY;
#pragma omp parallel
{
vector <double> positionX, positionY;
mt19937 engine(0);
uniform_real_distribution<> uniform(0, 1);
normal_distribution<double> normal(0, 1);#pragma omp for private(angle, radius, X, Y)
for(i=0; i<1000000; ++i)
{
angle = uniform(engine)*2.0*PI;
radius = sqrt(uniform(engine));
X = radius*cos(angle);
Y = radius*sin(angle);
positionX.push_back(X);
positionY.push_back(Y);
}
#pragma omp barrier
#pragma omp critical
finalPositionX.insert(finalPositionX.end(), positionX.begin(), positionX.end());
finalPositionY.insert(finalPositionY.end(), positionY.begin(), positionY.end());
}ofstream output_data("positions.txt", ios::out);
output_data.precision(9);
for(unsigned long long temp_var=0; temp_var<(unsigned long long)finalPositionX.size(); temp_var++)
{
output_data << finalPositionX[temp_var]
<< "\t\t\t\t"<< finalPositionY[temp_var]
<< "\n";
}
output_data.close();
return 0;
}
Вопрос: Многие из x-координат появляются дважды (то же самое с y-координатами). Я не понимаю этого, так как период mt19937 намного длиннее, чем 1.000.000. У кого-нибудь есть представление о том, что здесь не так?
Заметка: Я получаю такое же поведение, когда не использую многопоточность приложения, поэтому проблема не связана с неправильной многопоточностью.
РЕДАКТИРОВАТЬ Как указано в одном из ответов, я не должен использовать одно и то же начальное число для обоих потоков — но это ошибка, которую я допустил при формулировании этого вопроса, в моей настоящей программе я вижу потоки по-разному.
Решение
Как описано в Эта статья (и более поздняя статья модератором Stack Overflow), истинная случайность не распределяется идеально.
Хорошая случайность:
Плохая случайность:
Я действительно рекомендую прочитать статью, но суммируя ее: ГСЧ должен быть непредсказуемым, что подразумевает, что 100-кратный вызов не должен полностью заполнять сетку 10х10.
Другие решения
Используя основную часть вашего кода, я написал этот несовершенный тест, но из того, что я вижу, распределение довольно равномерное:
#include <iostream>
#include <fstream>
#include <random>
#include <map>
#include <iomanip>
using namespace std;
int main()
{
int i;
vector<double> finalPositionX, finalPositionY;
std::map<int, int> hist;vector <double> positionX, positionY;
mt19937 engine(0);
uniform_real_distribution<> uniform(0, 1);
//normal_distribution<double> normal(0, 1);
for(i=0; i<1000000; ++i)
{
double rnum = uniform(engine);
++hist[std::round(1000*rnum)];
}
for (auto p : hist) {
std::cout << std::fixed << std::setprecision(1) << std::setw(2)
<< p.first << ' ' << std::string(p.second/200, '*') << '\n';
}
return 0;
}
и, как уже говорили другие, не удивительно, что некоторые значения повторяются. Для normal распределение, я использовал следующую модификацию rnum а также hist чтобы проверить это, и это выглядит хорошо:
double rnum = normal(engine);
++hist[std::round(10*rnum)];
Прежде всего — то, что вы получаете одно и то же число дважды, не означает, что оно не случайно. Если вы бросите кубик шесть раз, ожидаете ли вы шесть разных результатов? Смотрите парадокс дня рождения. Это сказанное — вы правы, что вы не должны видеть слишком много повторений в этом конкретном случае.
Я не знаком с «#pragma omp parallel», но я предполагаю, что вы создаете несколько потоков, которые заполняют mt19937 одним и тем же семенем (0). Вы должны использовать разные семена для всех нитей — например, идентификатор потока.