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.sparse

Sparse Tensors

Authors:
Ilya Yaroshenko
Sparse!(Lengths.length, T) sparse(T, Lengths...)(Lengths lengths)
if (allSatisfy!(isIndex, Lengths));

Sparse!(N, T) sparse(T, size_t N)(auto ref size_t[N] lengths);
Sparse tensors represented in Dictionary of Keys (DOK) format.
Parameters:
N dimension count
Lengths lengths list of dimension lengths
Returns:
N-dimensional slice composed of indexes
See Also:
Examples:
auto slice = sparse!double(2, 3);
slice[0][] = 1;
slice[0, 1] = 2;
--slice[0, 0];
slice[1, 2] += 4;

assert(slice == [[0, 2, 1], [0, 0, 4]]);

import std.range.primitives: isRandomAccessRange;
static assert(isRandomAccessRange!(Sparse!(2, double)));

import mir.ndslice.slice: Slice, DeepElementType;
static assert(is(Sparse!(2, double) : Slice!(Universal, [2], FieldIterator!(SparseField!double))));
static assert(is(DeepElementType!(Sparse!(2, double)) == double));
template Sparse(size_t N, T)
Sparse Slice in Dictionary of Keys (DOK) format.
struct SparseField(T);
SparseField is used internally by Slice type to represent Sparse.
T[size_t] table;
@property auto save();
T opIndex(size_t index);
T opIndexAssign(T value, size_t index);
T opIndexUnary(string op)(size_t index)
if (op == "++" || op == "--");
T opIndexOpAssign(string op)(T value, size_t index)
if (op == "+" || op == "-");
struct CoordinateValue(size_t N, T);
Combination of coordinate(s) and value.
size_t[N] index;
T value;
const sizediff_t opCmp()(auto ref const typeof(this) rht);
auto byCoordinateValue(S : Slice!(Universal, packs, Iterator), size_t[] packs, size_t N = packs[0], Iterator : FieldIterator!(SparseField!T), T)(S slice);
Returns unsorted forward range of (coordinate, value) pairs.
Parameters:
S slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.
Examples:
import std.array: array;
import std.algorithm.sorting: sort;
alias CV = CoordinateValue!(2, double);

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.byCoordinateValue.array.sort().release == [
    CV([0, 1], 2),
    CV([0, 2], 1),
    CV([1, 2], 4),
    CV([2, 0], 6),
    CV([2, 1], 7)]);
auto byCoordinate(S : Slice!(Universal, packs, Iterator), size_t[] packs, size_t N = packs[0], Iterator : FieldIterator!(SparseField!T), T)(S slice);
Returns unsorted forward range of coordinates.
Parameters:
S slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.
Examples:
import std.array: array;
import std.algorithm.sorting: sort;

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.byCoordinate.array.sort().release == [
    [0, 1],
    [0, 2],
    [1, 2],
    [2, 0],
    [2, 1]]);
auto byValueOnly(S : Slice!(Universal, packs, Iterator), size_t[] packs, size_t N = packs[0], Iterator : FieldIterator!(SparseField!T), T)(S slice);
Returns unsorted forward range of values.
Parameters:
S slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.
Examples:
import std.array: array;
import std.algorithm.sorting: sort;

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.byValueOnly.array.sort().release == [1, 2, 4, 6, 7]);
auto compress(I = uint, J = uint, SliceKind kind, size_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice)
if (packs[0] > 1);
Returns compressed tensor
Examples:
Sparse tensor compression
auto sparse = sparse!double(5, 3);
sparse[] =
    [[0, 2, 1],
     [0, 0, 4],
     [0, 0, 0],
     [6, 0, 9],
     [0, 0, 5]];

auto crs = sparse.compress;
assert(crs.iterator._field == CompressedField!(double, uint, uint)(
     3,
    [2, 1, 4, 6, 9, 5],
    [1, 2, 2, 0, 2, 2],
    [0, 2, 3, 3, 5, 6]));
Examples:
Sparse tensor compression
auto sparse = sparse!double(5, 8);
sparse[] =
    [[0, 2, 0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 0, 0, 0, 4],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [6, 0, 0, 0, 0, 0, 0, 9],
     [0, 0, 0, 0, 0, 0, 0, 5]];

auto crs = sparse.compress;
assert(crs.iterator._field == CompressedField!(double, uint, uint)(
     8,
    [2, 1, 4, 6, 9, 5],
    [1, 7, 7, 0, 7, 7],
    [0, 2, 3, 3, 5, 6]));
Examples:
Dense tensor compression
import mir.ndslice.allocation: slice;

auto sl = slice!double(5, 3);
sl[] =
    [[0, 2, 1],
     [0, 0, 4],
     [0, 0, 0],
     [6, 0, 9],
     [0, 0, 5]];

auto crs = sl.compress;

assert(crs.iterator._field == CompressedField!(double, uint, uint)(
     3,
    [2, 1, 4, 6, 9, 5],
    [1, 2, 2, 0, 2, 2],
    [0, 2, 3, 3, 5, 6]));
Examples:
Dense tensor compression
import mir.ndslice.allocation: slice;

auto sl = slice!double(5, 8);
sl[] =
    [[0, 2, 0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 0, 0, 0, 4],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [6, 0, 0, 0, 0, 0, 0, 9],
     [0, 0, 0, 0, 0, 0, 0, 5]];

auto crs = sl.compress;
assert(crs.iterator._field == CompressedField!(double, uint, uint)(
     8,
    [2, 1, 4, 6, 9, 5],
    [1, 7, 7, 0, 7, 7],
    [0, 2, 3, 3, 5, 6]));
CompressedTensor!(packs[0], V, I, J) compressWithType(V, I = uint, J = uint, SliceKind kind, size_t[] packs, Iterator : FieldIterator!(SparseField!T), T)(Slice!(kind, packs, Iterator) slice)
if (is(T : V) && packs[0] > 1);

CompressedTensor!(packs[0], V, I, J) compressWithType(V, I = uint, J = uint, SliceKind kind, size_t[] packs, Iterator)(Slice!(kind, packs, Iterator) slice)
if (!is(Iterator : FieldIterator!(SparseField!ST), ST) && is(DeepElementType!(Slice!(Universal, packs, Iterator)) : V) && packs[0] > 1);
Returns compressed tensor with different element type.
CompressedTensor!(packs[0] + 1, V, I, J) recompress(V, I = uint, J = size_t, SliceKind kind, size_t[] packs, Iterator : FieldIterator!(CompressedField!(RV, RI, RJ)), RV, RI, RJ)(Slice!(kind, packs, Iterator) slice);
Re-compresses a compressed tensor. Makes all values, indexes and pointers consequent in memory.
Examples:
import mir.ndslice.allocation: slice;

auto sl = slice!double(5, 8);
sl[] =
    [[0, 2, 0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 0, 0, 0, 4],
     [0, 0, 0, 0, 0, 0, 0, 0],
     [6, 0, 0, 0, 0, 0, 0, 9],
     [0, 0, 0, 0, 0, 0, 0, 5]];

auto crs = sl.compress;
assert(crs.iterator._field == CompressedField!(double, uint, uint)(
     8,
    [2, 1, 4, 6, 9, 5],
    [1, 7, 7, 0, 7, 7],
    [0, 2, 3, 3, 5, 6]));

import mir.ndslice.dynamic: reversed;
auto rec = crs.reversed.recompress!real;
auto rev = sl.universal.reversed.compressWithType!real;
assert(rev.structure == rec.structure);
assert(rev.iterator._field.values   == rec.iterator._field.values);
assert(rev.iterator._field.indexes  == rec.iterator._field.indexes);
assert(rev.iterator._field.pointers == rec.iterator._field.pointers);
template CompressedTensor(size_t N, T, I = uint, J = size_t)
CompressedTensor!(N, T, I, J) is Slice!(N - 1, CompressedField!(T, I, J)).
See Also:
struct CompressedArray(T, I = uint) if (is(I : size_t) && isUnsigned!I);
Compressed array is just a structure of values array and indexes array.
T[] values;
I[] indexes;
struct CompressedField(T, I = uint, J = size_t) if (is(I : size_t) && isUnsigned!I && is(J : size_t) && isUnsigned!J && I.sizeof <= J.sizeof);
CompressedField is used internally by Slice type to represent CompressedTensor.
size_t compressedLength;
T[] values;
I[] indexes;
J[] pointers;
inout inout(CompressedArray!(T, I)) opIndex(size_t index);