Report a bug
If you spot a problem with this page, click here to create a Github issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

mir.random.algorithm

Authors:
Ilya Yaroshenko, documentation is partially based on Phobos.
License:
Boost License 1.0.
This module is available in the extended configuration.
auto randomSlice(G, D, size_t N)(G gen, D var, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && isRandomVariable!D && (is(G == class) || is(G == interface)));

auto randomSlice(G, D, size_t N)(ref scope G gen, D var, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && isRandomVariable!D && is(G == struct));

auto randomSlice(G, D, size_t N)(scope G* gen, D var, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && isRandomVariable!D && is(G == struct));

auto randomSlice(D, size_t N)(D var, size_t[N] lengths...)
if (N && isRandomVariable!D);

auto randomSlice(G, D, size_t N)(G gen, D var, size_t[N] lengths...)
if (N > 1 && isSaturatedRandomEngine!G && isNdRandomVariable!D && (is(G == class) || is(G == interface)));

auto randomSlice(G, D, size_t N)(ref scope G gen, D var, size_t[N] lengths...)
if (N > 1 && isSaturatedRandomEngine!G && isNdRandomVariable!D && is(G == struct));

auto randomSlice(G, D, size_t N)(scope G* gen, D var, size_t[N] lengths...)
if (N > 1 && isSaturatedRandomEngine!G && isNdRandomVariable!D && is(G == struct));

auto randomSlice(D, size_t N)(D var, size_t[N] lengths...)
if (N > 1 && isNdRandomVariable!D);

auto randomSlice(T, G, size_t N)(G gen, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

auto randomSlice(T, G, size_t N)(ref scope G gen, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && is(G == struct));

auto randomSlice(T, G, size_t N)(scope G* gen, size_t[N] lengths...)
if (N && isSaturatedRandomEngine!G && is(G == struct));

auto randomSlice(T, alias gen = rne, size_t N)(size_t[N] lengths...)
if (N && isSaturatedRandomEngine!(typeof(gen)));
Allocates ndslice (vector, matrix, or tensor) and fills it with random numbers. If no variable is specified each element e is generated per rand!(typeof(e)).
Parameters:
G gen random engine (optional, param or template param)
D var random variable (optional)
size_t[N] lengths one or more lengths
Examples:
Random sample from Normal distribution
// mir.ndslice package is required for 'randomSlice', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.random.variable: normalVar;
    // Using default RNE:
    auto sample = normalVar.randomSlice(10);
    assert(sample.shape == [10]);

    import mir.ndslice.slice: Slice;
    assert(is(typeof(sample) == Slice!(double*)));

    // Using pointer to RNE:
    sample = threadLocalPtr!Random.randomSlice(normalVar, 15);

    // Using local RNE:
    auto rng = Random(12345);
    sample = rng.randomSlice(normalVar, 15);
}
Examples:
Random sample from uniform distribution strictly in the interval (-1, 1).
// mir.ndslice package is required for 'randomSlice', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.algorithm.iteration: all;
    import mir.math.common: fabs;
    // Using default RNE:
    auto sample = randomSlice!double(10);
    assert(sample.shape == [10]);

    import mir.ndslice.slice: Slice;
    assert(is(typeof(sample) == Slice!(double*)));
    assert(sample.all!(a => a.fabs < 1));

    // Using pointer to RNE:
    sample = threadLocalPtr!Random.randomSlice!double(15);

    // Using local RNE:
    auto rng = Random(12345);
    sample = rng.randomSlice!double(15);

    // For complex numbers:
    auto csample = randomSlice!cdouble(10);
}
Examples:
Random sample from 3D-sphere distribution
// mir.ndslice package is required for 'randomSlice', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.random.ndvariable: sphereVar;
    // Using default RNE:
    auto sample = sphereVar.randomSlice(10, 3);
    assert(sample.shape == [10, 3]);
    // 10 observations from R_3

    import mir.ndslice.slice: Slice;
    assert(is(typeof(sample) == Slice!(double*, 2)));

    // Using pointer to RNE:
    sample = threadLocalPtr!Random.randomSlice(sphereVar, 15, 3);

    // Using local RNE:
    auto rng = Random(12345);
    sample = rng.randomSlice(sphereVar, 15, 3);
}
Examples:
Random binary data
// mir.ndslice package is required for 'randomSlice', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    // Using default RNE:
    auto sample = randomSlice!ulong(15);
    assert(sample.shape == [15]);

    import mir.ndslice.slice: Slice;
    assert(is(typeof(sample) == Slice!(ulong*)));

    // Using pointer to RNE:
    sample = randomSlice!ulong(threadLocalPtr!Random, 15);

    // Using local RNE:
    auto rng = Random(12345);
    sample = randomSlice!ulong(rng, 15);
}
struct VitterStrides;
Random sampling utility.

Complexity O(n)

References Jeffrey Scott Vitter, An efficient algorithm for sequential random sampling

Examples:
import mir.random.engine.xorshift;
auto gen = Xorshift(112);
auto strides = VitterStrides(20, 3);
size_t s;
foreach(_; 0..3)
{
    s += strides(gen) + 1;
    assert(s + strides.tail == 20);
}
this()(size_t N, size_t n);
Parameters:
size_t N range length
size_t n sample length
const @property bool empty()();
Returns:
true if sample length equals to 0.
const @property size_t length()();
Returns:
N (remaining sample length)
const @property size_t tail()();
Returns:
n (remaining range length)
sizediff_t opCall(G)(ref scope G gen);
Returns:
random stride step (S). After each call N decreases by S + 1 and n decreases by 1.
Parameters:
G gen random number engine to use
auto sample(G, Range)(G gen, Range range, size_t n)
if (isInputRange!Range && hasLength!Range && (__traits(hasMember, Range, "popFrontExactly") || hasSlicing!Range) && isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

auto sample(G, Range)(G* gen, Range range, size_t n)
if (isInputRange!Range && hasLength!Range && (__traits(hasMember, Range, "popFrontExactly") || hasSlicing!Range) && isSaturatedRandomEngine!G && is(G == struct));

@system auto sample(G, Range)(ref G gen, Range range, size_t n)
if (isInputRange!Range && hasLength!Range && (__traits(hasMember, Range, "popFrontExactly") || hasSlicing!Range) && isSaturatedRandomEngine!G && is(G == struct));

auto sample(alias gen = rne, Range)(Range range, size_t n)
if (isInputRange!Range && hasLength!Range && (__traits(hasMember, Range, "popFrontExactly") || hasSlicing!Range) && __traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));
Selects a random subsample out of range, containing exactly n elements. The order of elements is the same as in the original range.
Returns:
RandomSample over the range.
Parameters:
Range range range to sample from
G gen random number engine to use
size_t n number of elements to include in the sample; must be less than or equal to the range.length

Complexity O(n)

Examples:
Default RNE
// mir.ndslice package is required for 'iota', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.ndslice.topology: iota;

    auto sample = 100.iota.sample(7);
    assert(sample.length == 7);
}
Examples:
// mir.ndslice package is required for 'iota', it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.algorithm.iteration: equal;
    import mir.ndslice.topology: iota;
    import mir.random.engine.xorshift;

    // Using pointer to RNE:
    setThreadLocalSeed!Xorshift(112); //Use a known seed instead of a random seed.
    Xorshift* gen_ptr = threadLocalPtr!Xorshift;
    auto sample1 = gen_ptr.sample(100.iota, 7);

    // Using alias of local RNE:
    Xorshift gen = Xorshift(112);
    auto sample2 = 100.iota.sample!gen(7);

    assert(sample1.equal(sample2));
}
struct RandomSample(G, Range);

struct RandomSample(Range, alias gen);
Lazy input or forward range containing a random sample. VitterStrides is used to skip elements.

Complexity O(n)

Note

  • The structure holds a pointer to a generator.
  • The structure must not be copied (explicitly or implicitly) outside from a function.

this()(Range range, G gen, size_t n)
if (is(G == class) || is(G == interface));

this()(Range range, G* gen, size_t n)
if (is(G == struct));

@system this()(Range range, ref G gen, size_t n)
if (is(G == struct));
const @property size_t length();

const @property bool empty()();

@property ref auto front()();

void popFront()();

@property auto save()();
Range primitives
void shuffle(G, Iterator)(ref scope G gen, Slice!Iterator range)
if (isSaturatedRandomEngine!G);

void shuffle(G, Iterator)(scope G* gen, Slice!Iterator range)
if (isSaturatedRandomEngine!G);

void shuffle(Iterator)(Slice!Iterator range);
Shuffles elements of range.
Parameters:
G gen random number engine to use
Slice!Iterator range random-access range whose elements are to be shuffled

Complexity O(range.length)

Examples:
// mir.ndslice package is required, it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.ndslice.allocation: slice;
    import mir.ndslice.topology: iota;
    import mir.ndslice.sorting;

    auto a = iota(10).slice;

    shuffle(a);

    sort(a);
    assert(a == iota(10));
}
Examples:
// mir.ndslice package is required, it can be found in 'mir-algorithm'
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.ndslice.slice: sliced;
    import mir.ndslice.sorting;

    auto a = [1, 2, 3, 4];
    a.sliced.shuffle;

    sort(a);
    assert(a == [1, 2, 3, 4]);
}
void shuffle(G, Iterator)(ref scope G gen, Slice!Iterator range, size_t n)
if (isSaturatedRandomEngine!G);

void shuffle(G, Iterator)(scope G* gen, Slice!Iterator range, size_t n)
if (isSaturatedRandomEngine!G);

void shuffle(Iterator)(Slice!Iterator range, size_t n);
Partially shuffles the elements of range such that upon returning range[0..n] is a random subset of range and is randomly ordered. range[n..r.length] will contain the elements not in range[0..n]. These will be in an undefined order, but will not be random in the sense that their order after shuffle returns will not be independent of their order before shuffle was called.
Parameters:
G gen (optional) random number engine to use
Slice!Iterator range random-access range with length whose elements are to be shuffled
size_t n number of elements of r to shuffle (counting from the beginning); must be less than r.length

Complexity O(n)

Examples:
static if (is(typeof({ import mir.ndslice.slice; })))
{
    import mir.ndslice.allocation: slice;
    import mir.ndslice.topology: iota;
    import mir.ndslice.sorting;

    auto a = iota(10).slice;

    shuffle(a, 4);

    sort(a);
    assert(a == iota(10));
}