Geek Answers Handbook

Efficient random selection of all std :: vector elements exactly once without rearrangement

I am looking for an effective method to select access to each element std::vector<T>at random without shuffling or copying them. Do not use std::random_shuffleand make sure that each item is selected only once.

I do not want to copy or shuffle, because a) each instance Tis likely to be a very large object, and b) for other operations that I will do on the elements of the vector, so that they remain in the same order.

In addition, I really do not want to go down the street, constantly collecting and rejecting duplicates. I will probably have many of these large objects stored in a vector, and efficiency is key, as I will look for a call to this random method many times per second.

+5
source share
3 answers

You did not tell us whether you want to randomly iterate over the entire array, or if you only need some elements.

I guess the first case. You will need additional storage for accounting, and you still need time to shuffle. Therefore, create a permutation and save its memory so that you can shuffle it as you wish. C ++ 11:

#include <algorithm>
#include <random>
#include <numeric>

struct permutation
{
    permutation(size_t n) 
        : perm(n), g(std::random_device())
    {
        std::iota(perm.begin(), perm.end(), size_t(0));
    }

    void shuffle() { std::shuffle(perm.begin(), perm.end(), g); }

    size_t operator[](size_t n) const { return perm[n]; }

private:
    std::vector<size_t> perm;
    std::mt19937 g;
};

Using:

std::vector<huge_t> v;
...

permutation sigma(v.size());
sigma.shuffle();

const huge_t& x = v[sigma[0]];

...
sigma.shuffle(); // No extra allocation
const huge_t& y = v[sigma[0]];

++ 03 std::random_shuffle, , .

+4

, , . - .

+6

I think that the simplest (and one of the more efficient) solution would be to either create indexes std::vector<size_t>to store in yours vector<T>, or std::vector<T*>by holding pointers in yours vector. Then you can shuffle this one using std::random_shuffleiterate over it and select the appropriate elements from your original vector. This way you don't change the order of your original shuffle vectors and pointers, or size_tpretty cheaply

+2
source

More articles:


All Articles