If you spot a problem with this page, click here to create a GitHub issue.

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

License:

Boost License 1.0.

Authors:

Ilya Yaroshenko

Sparse!(T, N) sparse(T, size_t N)(size_t[N] lengths...);

Sparse tensors represented in Dictionary of Keys (DOK) format.

Parameters:

N	dimension count
size_t[N] `lengths`	list of dimension lengths

Returns:

N-dimensional slice composed of indeces

See Also:

Sparse

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!(double, 2)));

import mir.ndslice.slice: Slice, DeepElementType;
static assert(is(Sparse!(double, 2) : Slice!(FieldIterator!(SparseField!double), 2)));
static assert(is(DeepElementType!(Sparse!(double, 2)) == double));

auto byCoordinateValue(size_t N, T)(Slice!(FieldIterator!(SparseField!T), N) slice);

Returns unsorted forward range of (coordinate, value) pairs.

Parameters:

Slice!(FieldIterator!(SparseField!T), N) slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.

Examples:

import mir.array.allocation: array;
import mir.ndslice.sorting: sort;
alias CV = CoordinateValue!(double, 2);

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.byCoordinateValue.array.sort() == [
    CV([0, 1], 2),
    CV([0, 2], 1),
    CV([1, 2], 4),
    CV([2, 0], 6),
    CV([2, 1], 7)]);

auto byCoordinate(T, size_t N)(Slice!(FieldIterator!(SparseField!T), N) slice);

Returns unsorted forward range of coordinates.

Parameters:

Slice!(FieldIterator!(SparseField!T), N) slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.

Examples:

import mir.array.allocation: array;
import mir.ndslice.sorting: sort;

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.byCoordinate.array.sort() == [
    [0, 1],
    [0, 2],
    [1, 2],
    [2, 0],
    [2, 1]]);

auto onlyByValue(T, size_t N)(Slice!(FieldIterator!(SparseField!T), N) slice);

Returns unsorted forward range of values.

Parameters:

Slice!(FieldIterator!(SparseField!T), N) slice sparse slice with pure structure. Any operations on structure of a slice are not allowed.

Examples:

import mir.array.allocation: array;
import mir.ndslice.sorting: sort;

auto slice = sparse!double(3, 3);
slice[] = [[0, 2, 1], [0, 0, 4], [6, 7, 0]];
assert(slice.onlyByValue.array.sort() == [1, 2, 4, 6, 7]);

auto compress(I = uint, J = size_t, SliceKind kind, size_t N, Iterator)(Slice!(Iterator, N, kind) slice) if (N > 1);

Returns compressed tensor.

Note allocates using GC.

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.compressWithType!double;
// 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.compressWithType!double;
// 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.compressWithType!double;

// 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]));

Slice!(ChopIterator!(J*, Series!(I*, V*)), N - 1) compressWithType(V, I = uint, J = size_t, T, size_t N)(Slice!(FieldIterator!(SparseField!T), N) slice) if (is(T : V) && (N > 1) && isUnsigned!I); Slice!(ChopIterator!(J*, Series!(I*, V*)), N - 1) compressWithType(V, I = uint, J = size_t, Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) slice) if (!is(Iterator : FieldIterator!(SparseField!ST), ST) && is(DeepElementType!(Slice!(Iterator, N, kind)) : V) && (N > 1) && isUnsigned!I);

Returns compressed tensor with different element type.

Note allocates using GC.

Slice!(ChopIterator!(J*, Series!(I*, V*)), N) recompress(V, I = uint, J = size_t, Iterator, size_t N, SliceKind kind)(Slice!(Iterator, N, kind) sparseSlice) if (isSeries!(DeepElementType!(Slice!(Iterator, N, kind))));

Re-compresses a compressed tensor. Makes all values, indeces and pointers consequent in memory.

Sparse slice is iterated twice. The first tine it is iterated to get length of each sparse row, the second time - to copy the data.

Note allocates using GC.

Examples:

import mir.ndslice.topology: universal;
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.indeces  == rec.iterator._field.indeces);
// assert(rev.iterator._field.pointers == rec.iterator._field.pointers);

template Sparse(T, size_t N = 1)

Sparse Slice in Dictionary of Keys (DOK) format.

template CompressedVector(T, I = uint)

template CompressedMatrix(T, I = uint)

template CompressedTensor(T, size_t N, I = uint, J = size_t) template CompressedTensor(T, size_t N : 1, I = uint)

Library Reference

mir.sparse

Sparse Tensors