Home > Back-end >  Efficient way to generate random numbers with weights
Efficient way to generate random numbers with weights

Time:11-07

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
    }

CodePudding user response:

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.

  • Related