RandomSample

Selects a random subsample out of r, containing exactly n elements. The order of elements is the same as in the original range. The total length of r must be known. If total is passed in, the total number of sample is considered to be total. Otherwise, RandomSample uses r.length.

struct RandomSample (

Range

UniformRNG = void

) if (

isInputRange!Range &&

(

isUniformRNG!UniformRNG ||

is(UniformRNG == void)

)

) {

static if(!(is(UniformRNG == void)))

UniformRNG _rng;

bool empty [@property getter];

auto ref front [@property getter];

void popFront();

size_t length [@property getter];

size_t index [@property getter];

}

Members

Functions

popFront void popFront(): Range primitives.

Properties

empty bool empty [@property getter]
front auto ref front [@property getter]: Range primitives.
index size_t index [@property getter]: Returns the index of the visited record.
length size_t length [@property getter]: Range primitives.

Return Value

Range whose elements consist of a randomly selected subset of the elements of r, in the same order as these elements appear in r itself. Will be a forward range if both r and rng are forward ranges, an input range otherwise.

RandomSample implements Jeffrey Scott Vitter's Algorithm D (see Vitter 1984, 1987), which selects a sample of size n in O(n) steps and requiring O(n) random variates, regardless of the size of the data being sampled. The exception to this is if traversing k elements on the input range is itself an O(k) operation (e.g. when sampling lines from an input file), in which case the sampling calculation will inevitably be of O(total).

RandomSample will throw an exception if total is verifiably less than the total number of elements available in the input, or if n > total.

If no random number generator is passed to randomSample, the thread-global RNG rndGen will be used internally.

Examples

import std.algorithm.comparison : equal;
import std.range : iota;
auto rnd = MinstdRand0(42);
assert(10.iota.randomSample(3, rnd).equal([7, 8, 9]));