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

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 2

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 3

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 4

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();
 */

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

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 7

Maybe we can...

1. insert a random key
2. then we got the iterator of this random key
3. delete this random key
4. then we got the next iterator of this random key

    #include <iostream>
    #include <ctime>
    #include <unordered_map>
    
    struct Edge{
        int x;
        int y;
    };
    using EdgeMap = std::unordered_map<std::string, Edge>;
    EdgeMap edges;
    
    EdgeMap::iterator make_random_iterator(EdgeMap *map) {
      // make sure that random_key is not conflict with existing keys
      std::string random_key = "mock_key:" + std::to_string(std::rand());
      EdgeMap::iterator iter =
          map->insert(std::make_pair(random_key, Edge())).first;
      //now we got an random iterator
      iter = map->erase(iter);
      return iter;
    }
    
    int main(int, char**){
         std::srand(std::time(nullptr));
        //insert some keys
        for (int i=0;i<1000;i++) {
            edges[std::to_string(std::rand())] = Edge();
        }
        //visit 10 keys randomly
        for (int i=0;i<10;i++) {
            auto iter = make_random_iterator(&edges);
            std::cout << "i:" << i << " pick_key:" << iter->first << std::endl;
        }
        return 0;
    }