RandomSample with specified random number generator

[Jonathan M Davis]

On Friday, June 15, 2012 01:04:15 Joseph Rushton Wakeling wrote:
> On Thursday, 14 June 2012 at 22:17:44 UTC, Jonathan M Davis wrote:
> > On Thursday, June 14, 2012 23:37:05 jerro wrote:
> >> Issues with copying rngs are not unique to randomSample -
> >> anyone
> >> who uses random number generators will run into them
> >> sooner or later. So the problem is not that randomSample takes
> >> a rng as a parameter - it's that rngs are value types. The
> >> proper solution would be to make them reference types.
> > 
> > Exactly. This has been discussed before (IIRC, there's a bug
> > report which
> > discusses it). The most straightforward solution is to change
> > the random
> > number generator ranges to classes, but that _will_ break code,
> > because
> > they're constructed completely differently.
> 
> I don't think the solution is to pass the RNGs as refs.

I'm not talking about passing them as refs. I'm talking about making them 
reference types. It arguably makes no sense for random number generators to be 
passed around by value. It makes it ludicrously easy to get the same value 
multiple times simply because you passed it around. If you want to guarantee 
that you get the same value multiple times, then you should have to use save.

> I'm not
> familiar with the precise bug report you mention, but the
> reasoning is clear:it's because if you do something like,
> 
> auto getRandomSample(size_t N, size_t n)
> {
> auto rng = Random(unpredictableSeed);
> auto sample = randomSample(iota(0, N), n, rng);
> }
> 
> void main()
> {
> writeln(getRandomSample(100, 5));
> }
> 
> ... then if the RNG were stored in RandomSample by ref rather
> than value, this will fail, because the variable rng will no
> longer exist when the sample is evaluated in main().

I don't believe that the bug report had anything to do with randomSample. It 
had to do with using random number generator ranges in general. The problem is 
that if do something like

auto func(R)(R r)
{
 r.popFront();
 auto value = r.front;
 ///...
}

func(generator);
generator.popFront();
auto value = generator.front;

then both of those values will be the same, because the generator was passed 
by value. You don't have that problem if the generator is a reference type. 
And if you really want the same value twice, then you can use save.

> As far as I can see the only _safe_ option is that randomSample
> must always be passed a uniquely seeded RNG. And if you take
> that line then it's a small step to conclude that you can
> dispense with passing an RNG at all and just pass the seed, with
> the RNG type passed as a template parameter.

You need to be able to pass a random number generator range, because 
otherwise, you can't use any number generator other than the default. But you 
could just reseed the thing at the beginning of randomSample as long as 
isSeedable!R is true if you really want to ensure that it's seeded right 
before randomSample does its thing.

- Jonathan M Davis