std.random.RandomSample/randomSample
- multiple declarations
Function 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
.
auto randomSample(Range)
(
Range r,
size_t n,
size_t total
)
if (isInputRange!Range);
auto randomSample(Range)
(
Range r,
size_t n
)
if (isInputRange!Range && hasLength!Range);
auto randomSample(Range, UniformRNG)
(
Range r,
size_t n,
size_t total,
auto ref UniformRNG rng
)
if (isInputRange!Range && isUniformRNG!UniformRNG);
auto randomSample(Range, UniformRNG)
(
Range r,
size_t n,
auto ref UniformRNG rng
)
if (isInputRange!Range && hasLength!Range && isUniformRNG!UniformRNG);
Parameters
Name | Description |
---|---|
r | range to sample from |
n | number of elements to include in the sample;
must be less than or equal to the total number
of elements in r and/or the parameter
total (if provided) |
total | (semi-optional) number of elements of r
from which to select the sample (counting from
the beginning); must be less than or equal to
the total number of elements in r itself.
May be omitted if r has the
property and the sample is to be drawn from
all elements of r . |
rng | (optional) random number generator to use;
if not specified, defaults to rndGen |
Returns
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.
Example
import std .algorithm .comparison : equal;
import std .range : iota;
auto rnd = MinstdRand0(42);
assert(10 .iota .randomSample(3, rnd) .equal([7, 8, 9]));
Struct 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
.
struct RandomSample(Range, UniformRNG)
if (isInputRange!Range && (isUniformRNG!UniformRNG || is(UniformRNG == void)));
Properties
Name | Type | Description |
---|---|---|
empty [get]
|
bool | Range primitives. |
front [get]
|
auto | Range primitives. |
index [get]
|
size_t | Returns the index of the visited record. |
length [get]
|
size_t | Range primitives. |
save [get]
|
typeof(this) | Range primitives. |
Methods
Name | Description |
---|---|
popFront
()
|
Range primitives. |
Parameters
Name | Description |
---|---|
r | range to sample from |
n | number of elements to include in the sample;
must be less than or equal to the total number
of elements in r and/or the parameter
total (if provided) |
total | (semi-optional) number of elements of r
from which to select the sample (counting from
the beginning); must be less than or equal to
the total number of elements in r itself.
May be omitted if r has the
property and the sample is to be drawn from
all elements of r . |
rng | (optional) random number generator to use;
if not specified, defaults to rndGen |
Returns
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.
Example
import std .algorithm .comparison : equal;
import std .range : iota;
auto rnd = MinstdRand0(42);
assert(10 .iota .randomSample(3, rnd) .equal([7, 8, 9]));
Authors
Andrei Alexandrescu Masahiro Nakagawa (Xorshift random generator) Joseph Rushton Wakeling (Algorithm D for random sampling) Ilya Yaroshenko (Mersenne Twister implementation, adapted from mir-random)