Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя snowmanonahoe

Автор snowmanonahoe, история, 15 месяцев назад, По-английски

It's well known that rand() is evil. The consensus appears to be to use the STL Mersenne twister, and the STL millisecond(?) precision clock as a seed. This is all fine and dandy, but there's a problem, as appears in the linked blog:

for (int i = 1; i < N; i++)
        swap(permutation[i], permutation[uniform_int_distribution<int>(0, i)(rng)]);

There's so many words. uniform_int_distribution is like, 2 really big words. And I hate big words. Fortunately, there's a solution:

#include <bits/stdc++.h>
#include <experimental/random>
// Note: experimental headers are not included by bits/stdc++.h
using namespace std;
int main() {
    experimental::reseed(chrono::steady_clock::now().time_since_epoch().count());
    for (int i = 0; i < 10; i++)
        cout << experimental::randint(0, 10) << '\n';
}

Try it

randint uses an STL PRNG to return a number in the range of the 2 arguments, inclusive. The PRNG used appears to be implementation-defined (meaning it might be the subtract-with-carry or linear congruential generator), but that's ok, because what we may lose in RNG quality is made up for by the fact that a hacker won't know which generator is being used. (Note: the documentation says the state of the "per-thread" RNG is unpredictable at the beginning of execution. This does not appear to be the case on Codeforces after some cursory testing. Calling reseed() is still necessary.)

Defined in the experimental/random header is also experimental::shuffle() and experimental::sample(), which both work like their non-experimental counterparts, using the implementation-defined RNG instead of having to make one to pass as argument.

This does have some drawbacks.

  • Isn't a function object, can't be passed to one of the couple of STL functions that want one

  • PRNG used is implementation-defined

  • Experimental header

For these reasons, I see it as a convenient middle ground to a Mersenne twister, when you really just need one number for, say, a hash function.

Documentation

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

I personally added the following in my template:

mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  return uniform_int_distribution<int>(x, y)(rng);
}

Then I just call rnd(l, r) to get a random integer between $$$l$$$ and $$$r$$$ inclusive.

»
15 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Are there any problems with this?

mt19937 rnd(time(NULL));

for(int i = 0; i < 10; i++)
    cout << rnd() % 10 << ' ';

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    time(NULL) is hackable if someone puts a lot of effort in. In addition, modulo is more likely to give lower vs. higher numbers. Pretend rnd() returns a number between 0 and 11. It is easy to see why 0 and 1 are twice as likely a result than the other numbers.