-1

I need to create a set of random numbers between 0 and 800. The problem is at the moment that I need to do this fast and each number shall be returned only once.

My current approach is:

  • Create a std::vector containing the numbers from 0 to 800
  • Pick a number using numberVector[rand() % numberVector.length()]
  • Delete this number from the vector

I have to do this very often and my current approach is slow. Is there some way to speed things up here?

Nidhoegger
  • 4,973
  • 4
  • 36
  • 81

3 Answers3

4
  1. Create a std::vector containing the numbers from 0 to 800
  2. Shuffle the vector.
    This should be useful: c++ - How to shuffle a std::vector? - Stack Overflow
  3. Take the elements of the vector one by one, from the head to the tail. You don't have to delete the element: just store the index of last used element.
Community
  • 1
  • 1
MikeCAT
  • 73,922
  • 11
  • 45
  • 70
  • Thanks for that approach! I like it! But wouldnt it be better for speed to use this approach with a normal array? – Nidhoegger Nov 01 '15 at 14:54
  • @Nidhoegger: Vectors *are* normal arrays underneath the hood. –  Nov 01 '15 at 14:56
  • Yes, but by filling it up with 800 values, I would have 800 allocations, right? I could create an array with 800 values in one allocation. Thats my thought. But I dont know, I guess Ill make a benchmark :) – Nidhoegger Nov 01 '15 at 14:57
  • @Nidhoegger: If 800 is known at compile-time, then you can also use `std::array`. But I don't think you will notice a speed difference. – Christian Hackl Nov 01 '15 at 14:57
  • @Nidhoegger: With `std::vector`, you don't have 800 allocations. You can have as little as 1 allocation if you reserve all memory in advance. Even if you `push_back` one element after the other starting with an empty vector, the vector would grow more intelligently, resulting in only a few allocations in total. – Christian Hackl Nov 01 '15 at 14:59
  • You can use `reserve()` to allocate enough memory to `std::vector`. Note that this differs from resizing (adding/removing elements). – MikeCAT Nov 01 '15 at 14:59
1
  1. std::shuffle (std::random_shuffle) your std::vector
  2. pop_back elements
Filip Czaplicki
  • 189
  • 3
  • 12
1

Delete this number from the vector

You're probably doing too much work for this. Remember, for example, that deleting from the end of the vector is a lot faster than deleting from the front of the vector.

Since you don't care where in the vector your numbers are, you can speed things up by moving the number you want to delete to the end of the vector; e.g.

int take_from_vector(vector<int> &vec, size_t pos)
{
    int rv = vec[pos];
    swap(vec[pos], vec.back());
    vec.pop_back();
    return rv;
}

However, if you're generating just a few things, it is probably faster to use rejection sampling: you keep track of which numbers you've generated, then reject any repeats. e.g.

int generate_another_number(set<int> &already_generated, int bound)
{
    while (true) {
        int rv = rand() % bound;
        auto pos = already_generated.insert(rv);
        if (pos.second) { return rv; }
    }
}

Depending on how many things you're generating, you might want to use unordered_set<int> instead of set. Or maybe even use vector and just iterate over the vector to see if it contains the generated number.

P.S. consider using C++'s random number generation features, rather than the ancient rand() function.