Efficient way to generate random numbers with weights

Question

I need to frequently generate a large number of random numbers in my project, so I am seeking an efficient way to do this. I have tried two ways: (i) using random() and srand(); (ii) using C++ random library.

I tried on the following example: I need to generate 100000000 numbers, from {0, 1, 2, 3}, with weights {0.1, 0.2, 0.3, 0.4}. And from the example, I found that (i) is faster than (ii). (i) requires ~1.3s while (ii) requires ~4s, both using release builds. Is there any other more efficient way to generate random numbers with weights? This is exactly the bottleneck of my program.

Note that, this is just an example. The codes inside the loop in the example are just part of the codes inside the loop in my program. For example, each time generating random numbers has different weights so it seems that I cannot move std::discrete_distribution outside the loop. I just want to repeat the code and see the execution time.

(i) Using random() and srand()

 vector<int> res; res.resize(100000000); vector<double> weights{0.1, 0.2, 0.3, 0.4}; srand((unsigned int)time(NULL)); for (int i = 0; i < 100000000; ++i) { double tempSum = 0; double randomNnm = (double)(random()/(double)RAND_MAX); for(int j = 0;j < weights.size(); j++) { tempSum += weights[j]; if(randomNnm <= tempSum) { res[i] = j; break; } } }

(ii) Using C++ random library

 vector<int> res; res.resize(100000000); vector<double> weights{0.1, 0.2, 0.3, 0.4}; for (int i = 0; i < 100000000; ++i) { unsigned seed = chrono::system_clock::now().time_since_epoch().count(); default_random_engine randGen(seed); discrete_distribution<int> thisDistribution(weights.begin(), weights.end()); res[i] = thisDistribution(randGen); // get the final value }

Your second (ii) version is seeding and allocating/freeing a lot of memory on the stack every loop. Please also move those outside the loop and compare again. — KompjoeFriek
– KompjoeFriek, Commented Nov 6, 2022 at 13:35
Also remember to to tell us how you compiled the test, how you measured and that they were both release builds. — Richard Critten
– Richard Critten, Commented Nov 6, 2022 at 13:37
I found that (i) is much faster than (ii). (i) requires ~1.9s while (ii) requires ~33.4s -- Are you timing a non-optimized build (debug build), or an optimized, release build? If it is an unoptimized build, then the timings you are showing are meaningless. Please post the build settings for your application. — PaulMcKenzie
– PaulMcKenzie, Commented Nov 6, 2022 at 13:45
No wonder the second approach is that slow. std::discrete_distribution is not supposed to be created each time a random number is needed, it is supposed to be created only once. — Evg
– Evg, Commented Nov 6, 2022 at 13:50

Nelfeal · Accepted Answer · 2022-11-06 14:32:57Z

Use the random library correctly. In the C version, you put the call to srand outside of the loop, so do the same in the C++ version for the engine and the distribution.

std::vector<int> res(100000000); std::vector<double> weights{0.1, 0.2, 0.3, 0.4}; std::default_random_engine randGen(seed); std::discrete_distribution<int> thisDistribution(weights.begin(), weights.end()); for (int i = 0; i < N; ++i) { res[i] = thisDistribution(randGen); }

Demo

Timing this code (online, so it might not be accurate), I find the C++ version to be only slightly slower than the C version.

From https://quick-bench.com/, it is 4.4 slower with clang (gcc does better, 1.3 slower Demo) :-/ (I don't know if quality of result differs though).
@Jarod42 Thanks for the links. Clang with its own libc++ seems to perform best (demo).

Collectives™ on Stack Overflow

Efficient way to generate random numbers with weights

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related