Single use C++ random engine

Normally if I wanted a single use random engine, say for use in std::shuffle on a container and no other use for the rng elsewhere in the code, I might do
1
2
std::default_random_engine rng(std::random_device {}());
std::shuffle(words.begin(), words.end(), rng);

I know I could use a temporary instance of std::random_engine for that one time use:
std::shuffle(words.begin(), words.end(), std::random_device {});

Is there any major difference between the two snippets, other than not creating a random engine seeded by std::random_device? Is one version at the machine code level more efficient than the other?
Last edited on
Try the code using godbolt.org. You can see the generated assembler code.
creating the engine over and over probably has a tiny cost. It will pale compared to the work done in shuffle, esp if the things in the container are heavy to swap (consider a side by side vector of pointers or ints/indices into vector if they are fat). Swapping 'words' which sound suspiciously like stings needs this kind of help if you care about speed.
Last edited on
(deleted, as I was wrong here)
Last edited on
1
2
std::default_random_engine rng(std::random_device {}());
std::shuffle(words.begin(), words.end(), rng);

std::shuffle(words.begin(), words.end(), std::random_device {});
Is there any major difference between the two snippets

In your first snippet you create an instance of std::default_random_engine, i.e. a PRNG implemented in the C++ standard library – which is seeded from std::random_device, but doesn't use std::random_device afterwards. But, in the second snippet, shuffle() reads the "random" data directly from std::random_device, i.e. the system's entropy source – usually /dev/[u]random on Unix, or RtlGenRandom() on Windows.

Generally, if you need large amounts of "random" data, using a PRNG, such as std::default_random_engine or std::mt19937, can be many times faster than reading directly from the system's entropy source.

Furthermore, in your first snippet, rng is a local variable (automatic storage duration) and thus the std::default_random_engine object is destroyed as soon as variable rng goes out of scope! This means that the std::default_random_engine is re-created (and re-seeded!) every time the code is called...

You could use something like this to ensure the object is only created once (per thread) and then re-used:
1
2
static thread_local std::default_random_engine rng(std::random_device {}());
std::shuffle(words.begin(), words.end(), rng);


BTW: I see a lot of people recommend to prefer std::mt19937 over std::default_random_engine, as the latter may not use a "strong" PRNG algorithm and thus may not produce "high quality" random numbers.
Last edited on
The question was based on the following snippet of code using old, outdated methods of generating random numbers:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

int main()
{
    // set-up
    const int MAX_WRONG = 8;  // maximum number of incorrect guesses allowed

    vector<string> words;  // collection of possible words to guess
    words.push_back("GUESS");
    words.push_back("HANGMAN");
    words.push_back("DIFFICULT");

    srand(static_cast<unsigned int>(time(0)));

    random_shuffle(words.begin(), words.end());
    
    const string THE_WORD = words[0];   // word to guess
    int wrong             = 0;          // number of incorrect guesses
    string soFar(THE_WORD.size(), '-'); // word guessed so far
    string used           = "";         // letters already guessed

    // the rest of the code to play the game one time.......
}


As I said, ONE TIME use of a random generator, used to shuffle a vector of strings. Grossly inefficient

1. Oh, ick, push_back strings is IMO really only useful for adding to a vector when reading data from a file. Why not use an initializer list?

2. random_shuffle?!? That uses the C random library, something even of lesser quality than using any C++ random engine. Ick, ick, and ick. Why not use std::shuffle? That at least uses a C++ random engine.

The closest C++ crossover might be something like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <random>

int main()
{
   const int MAX_WRONG { 8 };

   std::vector<std::string> words { "GUESS", "HANGMAN", "DIFFICULT" };

   std::default_random_engine rng(std::random_device {}());
   std::shuffle(words.begin(), words.end(), rng);

   const std::string THE_WORD { words[0] };
   int wrong { };
   std::string soFar(THE_WORD.size(), '-');
   std::string used;

   // the rest of the code to play the game one time.......
}


Still rather clunky and bad smelling, shuffling a vector to get a one time string. While the use of a C++ random engine in std::shuffle is "a one time use" the implementation is likely gonna use the random engine multiple times.

Shuffling a 3 element vector is a trivial action, so doubtful std::random_engine's entropy is going to be a factor even when use in std::shuffle.

A "better" C to C++ rewrite might be:

13
14
15
16
   std::default_random_engine rng(std::random_device {}());
   std::uniform_int_distribution<size_t> dis(0, words.size() - 1);

   const std::string THE_WORD { words[dis(rng)] };

Now no shuffling, a simple one time random number generated used to retrieve an index into the vector. The code is now smelling more like roses.

I asked my question AFTER I had gone the "generate an index, ignoring shuffling a vector" route, but was curious about the implications of the first blush C++ rewrite.

I see a lot of people recommend to prefer std::mt19937

A lot of people recommend a lot of things that don't really matter for TRIVIAL USES. The need for a one time random number is a trivial use scenario IMO.

Yes, std::default_random_engine and std::random_engine have some issues, not least being implementation dependent defined so exact behavior might change from compiler to compiler. *shrug* For trivial uses not a deal-breaker IMO.

For that matter ALL of the random engines C++ provides have minor issues that make choosing which one to use in any application other than trivial uses something to carefully select one that suits the particular needs of the application.

std::default_random_engine is far and away a better choice than using the C library random generator. Hands down, no questions asked.


Last edited on
The standard library has std::sample for this purpose:

1
2
3
4
5
6
7
8
int main()
{
  std::vector<std::string> words { "GUESS", "HANGMAN", "DIFFICULT" };
  std::default_random_engine rng(std::random_device {}());

  std::string the_word; 
  std::sample(words.begin(), words.end(), &the_word, 1, rng);  
}
Now THAT is a suggestion I hadn't considered, because I didn't know it existed. I'm still not "up" on all that C++17 added to the toolbox.

It resides in <algorithm> so an equitable swap for std::shuffle and the rest of the "choose a random word" folderol.

Thanks for the clue, mbozzi. :)
Topic archived. No new replies allowed.