Random element from a collection

#1

Following code returns a random element from a collection. Here I put a special condition when the collection only contains one element. Although, uniform_int_distribution di(0,(int)mSet.size()-1) will cover this case. I’m thinking if this gets called thousands of time, the extra processing although theoretically O(1) will be done unnecessarily. In an interview setting (or real work) would this be considered messy?

 experimental::optional<T> random(default_random_engine& dre,uniform_int_distribution<int> di) {

    if(mSet.size() == 0) {
        return {};
    }
    
    if(mSet.size() == 1) {
        return {
            *mSet.begin()
        };
    }

    
    size_t adv = (size_t) di(dre);
    auto randomIt = next(mSet.begin(),adv);
    return {*randomIt};
}

I did a quick simulation:

Iterations User
5000 0m0.002s
90000 0m0.012s
200000 0m0.023s
400000 0m0.044s
500000 0m0.052s

First Col is number of times the getRandom method was called. Second col is time spent in executing user space code, collected using the time utility on Mac. This compared to a fake getRandom which mostly stays around 0m0.02s

0m0.001s
0m0.002s
0m0.002s
0m0.002s
0m0.003s

I changed the code to bare minimum:

int getRandom(default_random_engine& engine, uniform_int_distribution& dist) {
return dist(engine);
}

int getRandomFake(default_random_engine& engine, uniform_int_distribution& dist) {
return 1;
}

int main(int argc, const char * argv[]) {
// insert code here…

default_random_engine dre((unsigned int)time(0));
uniform_int_distribution<int> di(0,numeric_limits<int>::max()-1);

for(size_t i = 0; i < 90000 ;i++) {
    getRandom(dre, di);
}

return 0;

}

0 Likes
#2

I think the code itself is OK (coding style is weird in my opinion but it is really reabable to me). If you want to use C++17 feature, you might want to take a look at http://en.cppreference.com/w/cpp/experimental/sample for more information.

Let me know if you have any other questions.

0 Likes