C++: roulette wheel selection using map or boost

Well, the task is neither new nor unsolved. I was particularly interested in the fancy possibility to use a map container for binary search. Of course, boost offers better (read: faster and shorter) ways. Both of them can be implemented in a few lines.

#include <map>
#include <boost/random.hpp>

#define CHOICES 10000
#define SPINS 10000000
using namespace std;

struct wheelcomp {
    bool operator()(const pair<double, double> &a, const pair<double, double> &b) {
        if (b.first == -1) {
            if (b.second >= a.first && b.second < a.second)
                return false;
            return (b.second >= a.second);
        }
        if (a.first == -1) {
            if (a.second >= b.first && a.second < b.second)
                return false;
            return (a.second >= b.second);
        }
        return a.first < b.first;
    }
};

class wheel {
    double sum;
    map<pair<double, double>, int, wheelcomp> ranges;

public:
    wheel(double * p, int l) {
        sum = 0;
        for (int i = 0; i < l; i++) {
            ranges[pair<double, double>(sum, p[i]+sum)] = i;
            sum += p[i];
        }
    }

    int spin(double random) {
        return ranges.find(pair<double, double>(-1, random*sum))->second;
    }
};

int main(void) {
    // init random numbers
    boost::mt19937 mt;
    boost::uniform_real<> uniform(0,1);
    boost::variate_generator<boost::mt19937&,boost::uniform_real<> > rng(mt, uniform);

    // build_probabilities
    vector<double> p(CHOICES, 0);
    for (int i = 0; i < CHOICES; i++)
        p[i] = rng();

    // perform selections
    int k;
    wheel w(&p[0], CHOICES);
    for (int i = 0; i < SPINS; i++) 
        k = w.spin(rng());

    // the boost way
    boost::random::discrete_distribution<> dist(p);
    for (int i = 0; i < SPINS; i++) 
        k= dist(mt);

    return k;
}

Without any further optimization, the code has been compiled with gcc. The boost version takes 2 seconds for 1E7 selections, whereas the std::map version needs 6.1 seconds for 1E7 selections.

Leave a comment

Your email address will not be published.