dimanche 6 novembre 2022

Efficient way to generate random numbers with weights

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
    }



Aucun commentaire:

Enregistrer un commentaire