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.
auto randomSlice(T, G, D, size_t N)(G gen, D var, size_t[N] lengths...)
if (isSaturatedRandomEngine!G && isRandomVariable!D && (is(G == class) || is(G == interface)));

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

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

auto randomSlice(T, alias gen = rne, D, size_t N)(D var, size_t[N] lengths...)
if (isSaturatedRandomEngine!(typeof(gen)) && isRandomVariable!D);

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

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

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

auto randomSlice(alias gen = rne, D, size_t N)(D var, size_t[N] lengths...)
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ) && isRandomVariable!D);

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

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

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

auto randomSlice(alias gen = rne, size_t N)(size_t[N] lengths...)
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));
Allocates ndslice (vector, matrix, or tensor) and fills it with random numbers.
Parameters:
G gen random engine (optional, param or template param)
D var random variable (optional)
size_t[N] lengths one or more lengths
Examples:
Normal distribution
import mir.ndslice: slicedField, slice;
import mir.random.variable: NormalVariable;
auto sample = NormalVariable!double(0, 1).randomSlice(100);

assert(sample.shape == [100]);

import mir.ndslice.slice;
assert(is(typeof(sample) == ContiguousVector!double));
Examples:
Normal distribution for complex numbers
import mir.ndslice: slicedField, slice;
import mir.random;
import mir.random.variable: NormalVariable;

//Using pointer to RNG:
auto var = NormalVariable!double(0, 1);
auto sample1 = threadLocalPtr!Random.randomSlice(var, 5, 3);

//Using alias of default thread local Random Engine (`rne`):
auto sample2 = randomSlice!cdouble(var, 5, 3);

Random rng = Random(12345);
auto sample3 = rng.randomSlice!cdouble(var, 5, 3); //rng safely passed by ref
Examples:
Normal distribution for complex numbers
import mir.ndslice: slicedField, slice;
import mir.random;
import mir.random.variable: NormalVariable;

//Using pointer to RNG:
auto var = NormalVariable!double(0, 1);
auto sample1 = threadLocalPtr!Random.randomSlice(var, 5, 3);

//Using alias of default thread local Random Engine (`rne`):
auto sample2 = randomSlice!cdouble(var, 5, 3);

Random rng = Random(12345);
auto sample3 = rng.randomSlice!cdouble(var, 5, 3); //rng safely passed by ref
Examples:
Random binary data
import mir.ndslice: slicedField, slice;
import mir.random.engine.xorshift;

//Using pointer to RNG:
auto bitSample1 = randomSlice(threadLocalPtr!Random, 15);

//Using alias of RNG:
auto rng = Random(12345);
auto bitSample2 = randomSlice!rng(15);
struct RandomField(G, D, T) if (isSaturatedRandomEngine!G && isRandomVariable!D);

struct RandomField(alias gen, D, T) if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ) && isRandomVariable!D);

struct RandomField(G) if (isSaturatedRandomEngine!G);

struct RandomField(alias gen) if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));

RandomField!(G, D, T) field(T, G, D)(G gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && (is(G == class) || is(G == interface)));

RandomField!(G, D, T) field(T, G, D)(G* gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

@system RandomField!(G, D, T) field(T, G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

RandomField!(gen, D, T) field(T, alias gen = rne, D)(D var)
if (isSaturatedRandomEngine!(typeof(gen)) && isRandomVariable!D);

auto field(G, D)(G gen, D var)
if (isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

auto field(G, D)(G* gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

@system auto field(G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

auto field(alias gen = rne, D)(D var)
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ) && isRandomVariable!D);

RandomField!G field(G)(G gen)
if (isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

RandomField!G field(G)(G* gen)
if (isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

@system RandomField!G field(G)(ref G gen)
if (isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

RandomField!gen field(alias gen = rne)()
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));
Field interface for random distributions and uniform random bit generators. It used to construct ndslices in combination with slicedField and slice.

Note:

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

Examples:
Normal distribution
import mir.ndslice: slicedField, slice;
import mir.random.variable: NormalVariable;
auto sample1 = NormalVariable!double(0, 1)
        .field             // construct random field from standard normal distribution
        .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
        .slice;            // allocates data of random matrix
Examples:
import mir.ndslice: slicedField, slice;
import mir.random;
import mir.random.variable: NormalVariable;

//Using pointer to RNG:
auto var = NormalVariable!double(0, 1);
auto sample1 = threadLocalPtr!Random
    .field(var)        // construct random field from standard normal distribution
    .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;            // allocates data of random matrix

//Using alias of default thread local Random Engine (`rne`):
auto sample2 = var
    .field    // construct random field from standard normal distribution
    .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;            // allocates data of random matrix    }


// Can write using old syntax but it isn't @safe
// due to lack of escape analysis.
() @trusted
{
    Random rng2 = Random(12345);
    auto sample3 = rng2
        .field(var)        // construct random field from standard normal distribution
        .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
        .slice;            // allocates data of random matrix    }
}();
Examples:
Normal distribution for complex numbers
import mir.ndslice: slicedField, slice;
import mir.random;
import mir.random.variable: NormalVariable;

immutable seed = unpredictableSeed;

//Using pointer to RNG:
auto var = NormalVariable!double(0, 1);

auto sample1 = threadLocalPtr!Random
    .field!cdouble(var)// construct random field from standard normal distribution
    .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;            // allocates data of random matrix

//Using alias of default thread local Random Engine (`rne`):
auto sample2 = var
    .field!(cdouble, rne) // construct random field from standard normal distribution
    .slicedField(5, 3) // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;            // allocates data of random matrix
Examples:
Random binary data
import mir.ndslice: slicedField, slice;
import mir.random.engine.xorshift;

//Using pointer to RNG:
setThreadLocalSeed!Xorshift(1);//Use a known seed instead of a random seed.
Xorshift* rng_ptr = threadLocalPtr!Xorshift;
auto bitSample1 = rng_ptr
    .field              // construct random field
    .slicedField(5, 3)  // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;             // allocates data of random matrix

//Using alias of local RNG:
Xorshift rng = Xorshift(1);
auto bitSample2 =
     field!rng          // construct random field
    .slicedField(5, 3)  // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;             // allocates data of random matrix

assert(bitSample1 == bitSample2);
this()(G gen, D var)
if (is(G == class) || is(G == interface));

this()(G* gen, D var)
if (!is(G == class) && !is(G == interface));

@system this()(ref G gen, D var)
if (!is(G == class) && !is(G == interface));
Constructor. Stores the pointer to the gen engine.
T opIndex()(size_t);
struct RandomRange(G, D) if (isSaturatedRandomEngine!G && isRandomVariable!D);

struct RandomRange(alias gen, D) if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ) && isRandomVariable!D);

struct RandomRange(G) if (isSaturatedRandomEngine!G);

struct RandomRange(alias gen) if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));

RandomRange!(G, D) range(G, D)(G gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && (is(G == class) || is(G == interface)));

RandomRange!(G, D) range(G, D)(G* gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

@system RandomRange!(G, D) range(G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G && isRandomVariable!D && !is(G == class) && !is(G == interface));

RandomRange!(gen, D) range(alias gen = rne, D)(D var)
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ) && isRandomVariable!D);

RandomRange!G range(G)(G gen)
if (isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

RandomRange!G range(G)(G* gen)
if (isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

@system RandomRange!G range(G)(ref G gen)
if (isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

auto range(alias gen)()
if (__traits(compiles, () { static assert(isSaturatedRandomEngine!(typeof(gen))); } ));
Range interface for random distributions and uniform random bit generators.

Note:

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

Examples:
import std.range : take, array;

import mir.random;
import mir.random.variable: NormalVariable;

immutable seed = unpredictableSeed;

//Using pointer to RNG:
setThreadLocalSeed!Random(seed);//Use a known seed instead of a random seed.
Random* rng_ptr = threadLocalPtr!Random;
auto sample1 = rng_ptr
    .range(NormalVariable!double(0, 1))
    .take(1000)
    .array;

//Using alias of local RNG:
Random rng = Random(seed);
auto sample2 =
     range!rng(NormalVariable!double(0, 1))
    .take(1000)
    .array;

assert(sample1 == sample2);

/// using default threadlocal Random Engine
auto sample3 = NormalVariable!double(0, 1)
    .range
    .take(1000)
    .array;
Examples:
Uniform random bit generation
import std.stdio;
import std.range, std.algorithm;
import std.algorithm: filter;
import mir.random.engine.xorshift;
//Using pointer to RNG:
setThreadLocalSeed!Xorshift(1);//Use a known seed instead of a random seed.
Xorshift* rng_ptr = threadLocalPtr!Xorshift;
auto bitSample1 = rng_ptr
    .range
    .filter!"a % 2 == 0"
    .map!"a % 100"
    .take(5)
    .array;
assert(bitSample1 == [58, 30, 86, 16, 76]);

//Using alias of RNG:
Xorshift rng = Xorshift(1);
auto bitSample2 =
    .range!rng
    .filter!"a % 2 == 0"
    .map!"a % 100"
    .take(5)
    .array;
assert(bitSample2 == [58, 30, 86, 16, 76]);
this()(G gen, D var)
if (is(G == class) || is(G == interface));

this()(G* gen, D var)
if (!is(G == class) && !is(G == interface));

@system this()(ref G gen, D var)
if (!is(G == class) && !is(G == interface));
Constructor. Stores the pointer to the gen engine.
enum auto empty;

@property auto front()();

void popFront()();
Infinity Input Range primitives
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);
}
pure nothrow @nogc @safe this(size_t N, size_t n);
Parameters:
size_t N range length
size_t n sample length
pure nothrow @nogc @property @safe bool empty();
Returns:
true if sample length equals to 0.
pure nothrow @nogc @property @safe size_t length();
Returns:
N (remaining sample length)
pure nothrow @nogc @property @safe 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(Range, G)(Range range, G gen, size_t n)
if (isInputRange!Range && hasLength!Range && isSaturatedRandomEngine!G && (is(G == class) || is(G == interface)));

auto sample(Range, G)(Range range, G* gen, size_t n)
if (isInputRange!Range && hasLength!Range && isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

@system auto sample(Range, G)(Range range, ref G gen, size_t n)
if (isInputRange!Range && hasLength!Range && isSaturatedRandomEngine!G && !is(G == class) && !is(G == interface));

auto sample(Range, alias gen)(Range range, size_t n)
if (isInputRange!Range && hasLength!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:
import std.range;
import mir.random.engine.xorshift;
//Using pointer to RNG:
setThreadLocalSeed!Xorshift(112);//Use a known seed instead of a random seed.
Xorshift* gen_ptr = threadLocalPtr!Xorshift;
auto sample1 = iota(100).sample(gen_ptr, 7);
size_t sum1 = 0;
foreach(elem; sample1)
{
    sum1 += elem;
}
//Using alias of local RNG:
Xorshift gen = Xorshift(112);
auto sample2 = iota(100).sample!(typeof(iota(100)),gen)(7);
size_t sum2 = 0;
foreach(elem; sample2)
{
    sum2 += elem;
}

assert(sum1 == sum2);
struct RandomSample(Range, G);

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 == class) && !is(G == interface));

@system this()(Range range, ref G gen, size_t n)
if (!is(G == class) && !is(G == interface));
@property size_t length();

@property bool empty();

@property ref auto front();

void popFront();

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

void shuffle(Range, G)(scope G* gen, scope Range range)
if (isSaturatedRandomEngine!G && isRandomAccessRange!Range && hasLength!Range);

void shuffle(Range)(scope Range range)
if (isRandomAccessRange!Range && hasLength!Range);
Shuffles elements of range.
Parameters:
G gen random number engine to use
Range range random-access range whose elements are to be shuffled

Complexity: O(range.length)

Examples:
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));
void shuffle(Range, G)(ref scope G gen, scope Range range, size_t n)
if (isSaturatedRandomEngine!G && isRandomAccessRange!Range && hasLength!Range);

void shuffle(Range, G)(scope G* gen, scope Range range, size_t n)
if (isSaturatedRandomEngine!G && isRandomAccessRange!Range && hasLength!Range);

void shuffle(Range)(scope Range range, size_t n)
if (isRandomAccessRange!Range && hasLength!Range);
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
Range 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:
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));