On Thursday, 25 February 2016 at 17:27:25 UTC, Andrei
Alexandrescu wrote:
So we have
https://dlang.org/phobos/std_random.html#.randomCover which
needs to awkwardly allocate memory to keep track of the
portions of the array already covered.
Yes, this is definitely a standout in terms of being an
unpleasant solution. It means that you require o(N) memory even
when you're dealing with a lazily-evaluated range -- it would
probably be more efficient in practice to just write the input
into an array and do an in-place shuffle. :-(
This could be fixed by devising a PRNG that takes a given
period n and generates all numbers in [0, n) in exactly n steps.
However, I've had difficulty finding such PRNGs. Most want the
maximum period possible so they're not concerned with a given
period. Any insights?
I'll try to see what I can find. This must be something that
other lazy/functional communities (Haskell, Clojure, ...) have
had to contend with.
BTW I would caution that with pseudo-RNGs per se, the problem is
not so much the size of the period per se, as the fact that it's
not very random (in the sense that a PRNG is aiming for) to visit
every possible value within the range of the RNG exactly once
before repeating ... ;-)
BTW I found this statement in the documentation rather odd:
"These issues will be resolved in a second-generation
std.random that re-implements random number generators as
reference types." The documentation is not a place for making
vague promises and speculations about future developments. I
think it should be removed.
Yes, I agree. That was written at a time when those of us
focused on std.random had great hope that a new design was
immediately on the cards. I can probably find the PRs if you
want to see the context.
