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.
struct RandomField(G, D, T) if (isSaturatedRandomEngine!G);

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

RandomField!(G, D, T) field(T, G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G);

auto field(G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G);

RandomField!G field(G)(ref G gen)
if (isSaturatedRandomEngine!G);
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;
import mir.random.variable: NormalVariable;

auto var = NormalVariable!double(0, 1);
auto rng = Random(unpredictableSeed);
auto sample = rng      // passed by reference
    .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

//import std.stdio;
//writeln(sample);
Examples:
Normal distribution for complex numbers
import mir.ndslice: slicedField, slice;
import mir.random;
import mir.random.variable: NormalVariable;

auto var = NormalVariable!double(0, 1);
auto rng = Random(unpredictableSeed);
auto sample = rng      // passed by reference
    .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

//import std.stdio;
//writeln(sample);
Examples:
Bi
import mir.ndslice: slicedField, slice;
import mir.random.engine.xorshift;

auto rng = Xorshift(1);
auto bitSample = rng    // passed by reference
    .field              // construct random field
    .slicedField(5, 3)  // construct random matrix 5 row x 3 col (lazy, without allocation)
    .slice;             // allocates data of random matrix
this()(ref G gen, D var);
Constructor. Stores the pointer to the gen engine.
T opIndex()(size_t);
struct RandomRange(G, D) if (isSaturatedRandomEngine!G);

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

RandomRange!(G, D) range(G, D)(ref G gen, D var)
if (isSaturatedRandomEngine!G);

RandomRange!G range(G)(ref G gen)
if (isSaturatedRandomEngine!G);
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;

auto rng = Random(unpredictableSeed);
auto sample = rng // by reference
    .range(NormalVariable!double(0, 1))
    .take(1000)
    .array;

//import std.stdio;
//writeln(sample);
Examples:
Uniform random bit generation
import std.range, std.algorithm;
import mir.random.engine.xorshift;
auto rng = Xorshift(1);
auto bitSample = rng // by reference
    .range
    .filter!"a % 2 == 0"
    .map!"a % 100"
    .take(5)
    .array;
assert(bitSample == [58, 30, 86, 16, 76]);
this()(ref G gen, D var);
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);
}
this(size_t N, size_t n);
Parameters:
size_t N range length
size_t n sample length
@property bool empty();
Returns:
true if sample length equals to 0.
@property size_t length();
Returns:
N (remaining sample length)
@property size_t tail();
Returns:
n (remaining range length)
sizediff_t opCall(G)(ref 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, ref G gen, size_t n)
if (isInputRange!Range && hasLength!Range && isSaturatedRandomEngine!G);
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;
auto gen = Xorshift(112);
auto sample = iota(100).sample(gen, 7);
foreach(elem; sample)
{
    //import std.stdio;
    //writeln(elem);
}
struct RandomSample(Range, G);
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, ref G gen, size_t n);
@property size_t length();

@property bool empty();

@property ref auto front();

void popFront();

@property auto save();
Range primitives
void shuffle(Range, G)(ref G gen, Range range)
if (isSaturatedRandomEngine!G && 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 gen = Random(unpredictableSeed);
auto a = iota(10).slice;

gen.shuffle(a);

sort(a);
assert(a == iota(10));
void shuffle(Range, G)(ref G gen, Range range, size_t n)
if (isSaturatedRandomEngine!G && 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 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 gen = Random(unpredictableSeed);
auto a = iota(10).slice;

gen.shuffle(a, 4);

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