Путаница в многопоточности в переполнении стека

Я пытаюсь смоделировать проблему вероятности, в которой есть N клиенты и N сервера. Каждый клиент случайным образом отправляет запрос на любой сервер, поэтому каждый сервер может получать любое количество запросов, мне нужно рассчитать ожидаемое количество максимальных запросов, которые может получить любой сервер.

Я пытаюсь смоделировать это, запустив 10000 итераций, где в каждой итерации каждый клиент выбирает случайный сервер и отправляет запрос на него, серверы представлены в виде целочисленного массива размера N.

Клиент выбирает случайное число, а затем значение по этому индексу в массиве сервера увеличивается.
Как, для лучших результатов вопрос говорит N должно быть около 106.

Поэтому, чтобы сделать это немного быстрее, я использовал многопоточность, в которой каждый поток выполняет 100 итераций, а всего 10 потоков.

Но многопоточный код дает совсем другие результаты, чем в обычном коде.
Ниже приведены фрагменты кода с выводом для них обоих.

Нормальная версия

 #include <iostream>
#include <random>
#include <chrono>

#define N 1000000
#define iterations 1000

int servers[N];

// This array's i'th index will contain count of in how many
// iterations was i the maximum number of requests received by any  server
int distr[N+1]={0};

int main(int argc, char const *argv[])
{
// Initialising
auto start = std::chrono::high_resolution_clock::now();

std::srand(time(NULL));

// Performing iterations
for(int itr=1; itr<=iterations; itr++)
{
for(int i=0;i<N;i++)
{
servers[i]=0;
}

for(int i=1;i<=N;i++)
{
int index = std::rand()%N;
servers[index]++;
}

int maxRes = -1;
for(int i=0;i<N;i++)
{
maxRes = std::max(maxRes, servers[i]);
}
distr[maxRes]+=1;
}

for(int i=0;i<=15;i++)
{
std::cout<<(double)distr[i]<<std::endl;
}

auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
std::cout<<duration.count()<<" milliseconds"<<std::endl;

return 0;
}

Выход

0
0
0
0
0
0
0
359
552
79
10
0
0
0
0
0
1730 milliseconds

Многопоточная версия

#include <iostream>
#include <random>
#include <chrono>
#include <thread>
#include <fstream>

#define N 100000
#define iterations 1000
#define threads 10

// This array's i'th index will contain count of in how many
// iterations was i the maximum number of requests received by any server
std::atomic<int> distr[N] = {};

void execute(int number)
{
// Performing iterations
int servers[N]={0};
for(int itr=1; itr<=number; itr++)
{

for(int i=1;i<=N;i++)
{
int index = std::rand()%N;
servers[index]++;
}

int maxRes = -1;
for(int i=0;i<N;i++)
{
maxRes = std::max(maxRes, servers[i]);
servers[i]=0;
}

distr[maxRes] += 1;
}
}

int main(int argc, char const *argv[])
{
// Initialising
auto start = std::chrono::high_resolution_clock::now();

std::srand(time(NULL));

std::thread t[threads];
for(int i=0;i<threads;i++)
{
t[i] = std::thread(execute, iterations/threads);
}

for(int i=0;i<threads;i++)
{
t[i].join();
}

for(int i=0;i<=15;i++)
{
double temp = (double)distr[i];
std::cout<<i<<"\t"<<distr[i]<<std::endl;
}

auto stop = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
std::cout<<duration.count()<<" milliseconds"<<std::endl;

return 0;
}

Выход

0   0
1   0
2   0
3   0
4   0
5   0
6   0
7   7
8   201
9   421
10  267
11  68
12  2
13  2
14  4
15  0

1385 milliseconds

Принимая во внимание, что я запускал нормальный код много раз, и каждый раз счетчик для максимума = 9> 500, а разброс данных не так велик, я имею в виду только максимум = 8,9,10,11 имеют значимые значения, все — нули ,

Может кто-нибудь объяснить, пожалуйста, что я делаю не так?

Заранее спасибо!

1

Решение

Я не вижу «очень разных результатов», они просто несколько отличаются, поэтому кажется, что это что-то немного неуловимое. Я заметил, что вы не сеете каждую ветку отдельно — это может иметь к этому отношение.

PS: вы не должны использовать rand() % N если вы хотите равномерное распределение. Зачем? Увидеть это объяснение Стивен Лававей. Как предполагают комментаторы, перекос может быть небольшим, когда N маленький, но все же.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]