Select random element in an unordered_map

Question

I define an unordered_map like this:

std::unordered_map<std::string, Edge> edges;

Is there a efficient way to choose a random Edge from the unordered_map edges ?

Answer 1

This is not an O(1) solution (unless you got only one edge):

Pre-C++11 solution:

std::tr1::unordered_map<std::string, Edge> edges;
std::tr1::unordered_map<std::string, Edge>::iterator random_it = edges.begin();
std::advance(random_it, rand_between(0, edges.size()));

C++11 onward solution:

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

The function that selects a valid random number is up to your choice, but be sure it returns a number in range [0 ; edges.size() - 1] when edges is not empty.

The std::next function simply wraps the std::advance function in a way that permits direct assignation.

Answer 2

Is there a efficient way to choose a random Edge from the unordered_map edges ?

If by efficient you mean O(1), then no, it is not possible.

Since the iterators returned by unordered_map::begin / end are ForwardIterators, the approaches that simply use std::advance are O(n) in the number of elements.

If your specific use allows it, you can trade some randomness for efficiency:

You can select a random bucket (that can be accessed in O(1)), and then a random element inside that bucket.

int bucket, bucket_size;
do
{ 
    bucket = rnd(edges.bucket_count());
}
while ( (bucket_size = edges.bucket_size(bucket)) == 0 );

auto element = std::next(edges.begin(bucket), rnd(bucket_size));

Where rnd(n) returns a random number in the [0,n) range.

In practice if you have a decent hash most of the buckets will contain exactly one element, otherwise this function will slightly privilege the elements that are alone in their buckets.

Answer 3

Strict O(1) solution without buckets:

1. Keep a vector of keys, when you need to get a random element from your map, select a random key from the vector and return corresponding value from the map - takes constant time
2. If you insert a key-value pair into your map, check if such key is already present, and if it's not the case, add that key to your key vector - takes constant time
3. If you want to remove an element from the map after it was selected, swap the key you selected with the back() element of your key vector and call pop_back(), after that erase the element from the map and return the value - takes constant time

However, there is a limitation: if you want to delete elements from the map aside from random picking, you need to fix your key vector, this takes O(n) with naive approach. But still there is a way to get O(1) performance: keep a map that tells you where the key is in the key vector and update it with swap :)

Answer 4

This is how you can get random element from a map:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
int random_index = rand() % edges.size();
std::advance(item, random_index);

Or take a look at this answer, which provides the following solution:

std::unordered_map<std::string, Edge> edges;
iterator item = edges.begin();
std::advance( item, random_0_to_n(edges.size()) );

Answer 5

The solution of

std::unordered_map<std::string, Edge> edges;
auto random_it = std::next(std::begin(edges), rand_between(0, edges.size()));

is extremely slow....

A much faster solution will be:

• when assigning edges, simutaneously emplaces its keys to std::vector<std::string> vec
• random an int index ranging from 0 to vec.size() - 1
• then get edges[vec[index]]

Answer 6

you can see this problem:

problem 380. Insert Delete GetRandom O(1) you can build a vector to use vector random iterators, get random values more efficiently. Like this:

    class RandomizedSet {
public:
    unordered_map<int, int> m;
    vector<int> data;
    RandomizedSet() {

    }
    
    bool insert(int val) {
        if(m.count(val)){
            return false;
        } else{
            int index = data.size();
            data.push_back(val);
            m[val] = index;
            return true;
        }
    }
    
    bool remove(int val) {
        if(m.count(val)){
            int curr_index = m[val];
            int max_index = data.size()-1;
            m[data[max_index]] = curr_index;

            swap(data[curr_index], data[max_index]);
            data.pop_back();
            m.erase(val);
            return true;
        } else{
            return false;
        }
    }
    
    int getRandom() {
        return data[rand() % data.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */