LABTITLE=: 'Sparse Arrays'
LABFOCUS=: 0

NB. =========================================================
Lab Section Overview
Sparse arrays provide a compact and efficient storage form for very large arrays where most elements are zero or some other "sparse element". The sparse array represention does not store extra copies of the sparse element. J primitives work directly on sparse arrays.

The verb $. converts between sparse and dense representations of arrays.
)

NB. =========================================================
Lab Section
A sparse array has a single sparse element, plus an array of other values and a matrix of their corresponding indices.

The sparse attribute can be assigned to axes individually. Non-sparse axes are known as dense axes.

The index matrix has entries for the sparse axes, and the values array has entries for the dense axes.

A scalar is always dense.
)

NB. =========================================================
Lab Section $.
The verb $. creates and manipulates sparse arrays.

For example, "1 $. shape" creates a sparse array of the given shape, with all axes sparse, and a sparse element of 0. Here, we create a sparse array of shape:

    100 x 1,000 x 10,000    (1e9 elements)

Note that this array is too large to be represented normally. To see this, trying entering:

   T=: 100 1000 10000 $ 0
)
S=: 1 $. 100 1000 1000

$S           NB. shape of S

NB. =========================================================
Lab Section Display
The default display of a sparse array shows only the non-sparse values.

Since none have yet been assigned, the display is empty.
)
S            NB. display S (empty)

+/ , S       NB. sum all elements of S

NB. =========================================================
Lab Section Sparse Element
The sparse element is set as appropriate, for example if you add a scalar to an array, the sparse element is incremented by that scalar.
)
T=: S + 4    NB. add 4 to each element of S
             NB. sets sparse element of result to 4

T            NB. display is still empty

+/ , T       NB. sum is non-zero

3 $. T       NB. query sparse element

NB. =========================================================
Lab Section Amend
Now lets amend S with some non-sparse data. The display shows the index matrix and the corresponding value cells.

Since all axes are sparse, the index matrix has 3 columns (one for each axis), and the values array has a scalar value for each row.
)
PREPARE
S=: 1 $. 100 1000 10000
PREPARE
  [dat=: 100+i.6

  [ndx=: ?.6#,:$S

   S=: dat (<"1 ndx)} S

   S       NB. shows index matrix and values array

NB. =========================================================
Lab Section Index Matrix
The following examples use entries in the index matrix to index S directly:
)
PREPARE
S=: 1 $. 100 1000 10000
dat=: 100+i.6
ndx=: ?.6#,:$S
S=: dat (<"1 ndx)} S
PREPARE
S

(<38 519 8309) { S

[ndx=: 4 $. S         NB. get the index matrix

[T=: (<"1 ndx) { S    NB. T is a 6-element sparse vector

$T

NB. =========================================================
Lab Section Array Operations
Some typical array operations:
)
PREPARE
S=: 1 $. 100 1000 10000
dat=: 100+i.6
ndx=: ?.6#,:$S
S=: dat (<"1 ndx)} S
PREPARE
67 { S

+/"1 S

|: S

S * S

NB. =========================================================
Lab Section To Dense
For the next few sections, we will work with a much smaller sparse array, so that we can easily compare sparse and dense representations.

The monad $. converts a dense array to sparse, and the inverse $. ^:_1 converts a sparse array to dense
)
[A=: (1=?.2 3 4$4) * ?.2 3 4$100

[S=: $. A

todense=: $. ^:_1

todense S

NB. =========================================================
Lab Section Add Scalar
Adding a scalar to S changes the sparse element. This is noticeable when you display the dense representation of the array:
)
PREPARE
[S=: $. (1=?.2 3 4$4) * ?.2 3 4$100
todense=: $. ^:_1
PREPARE
S + 1

todense S + 1

NB. =========================================================
Lab Section Sparse Axes
The sparse attribute can be assigned to axes individually.

The index matrix has one column for each sparse axis; the values array has one item for each dense axis.
)
PREPARE
[S=: $. (1=?.2 3 4$4) * ?.2 3 4$100
todense=: $. ^:_1
PREPARE
S              NB. all axes are sparse

(2;1 2) $. S   NB. set axes 1 2 as sparse (0 is dense)

(2;2) $. S     NB. set axis 2 as sparse (0 and 1 are dense)

(2;'') $. S    NB. set no axes as sparse (all are dense)

NB. =========================================================
Lab Section Sparse Element
The sparse element can be reassigned. Note that this does not change the non-sparse values in the array.
)
PREPARE
[S=: $. (1=?.2 3 4$4) * ?.2 3 4$100
todense=: $. ^:_1
PREPARE
S                 NB. display S

T=: (3;1) $. S    NB. T is S with a sparse element of 1

T                 NB. same display as S

(todense S) ; todense T

NB. =========================================================
Lab Section Sparse Axes
If an operation on a sparse array changes a non-sparse value into the sparse element, it nevertheless is still stored as a non-sparse value. This is for efficiency reasons - since otherwise after every operation, the system would have to check for new sparse values, and if necessary, rebuild the index and value arrays.

The operation "8 $. array" rebuilds the sparse array.
)
PREPARE
[S=: $. (1=?.2 3 4$4) * ?.2 3 4$100
todense=: $. ^:_1
PREPARE
T=: 0 (<1;1)} S

(todense S) ; todense T

S

T                NB. T has non-sparse values of 0

T=: 8 $. T       NB. rebuild T

T

NB. =========================================================
Lab Section Efficiency
When applying a dyadic scalar verb, if one array has sparse axes SX and the other has sparse axes SY, then the result has sparse axes of the union of SX and SY.
)
PREPARE
[S=: $. (1=?.2 3 4$4) * ?.2 3 4$100
todense=: $. ^:_1
PREPARE
[T=: (2;0) $. S     NB. T is S with sparse axis 0

[U=: (2;2) $. S     NB. U is S with sparse axis 2

[W=: T + U          NB. W has sparse axes 0 and 2

2 $. W

NB. =========================================================
Lab Section
In the examples used so far, S was either an array so large (with 1e9 elements) that it could not be represented as a dense array, or a small array for which the sparse representation would not be worthwhile.

In general, there is a trade-off between the memory usage and CPU efficiency of sparse and dense representations.

In the following example, S is a sparse array with 1 million elements, of which 6 are non-sparse. The sparse representation is much more efficient than the dense representation:
)
S=: <. 1 $. 10 100 1000  NB. S is an integer array

dat=: 100+i.6

ndx=: ?.(#dat)#,:$S

S=: dat (<"1 ndx)} S

T=: todense S

($ 3!:1 S) ; ($ 3!:1 T)   NB. internal storage size

timespacex=: 6!:2 , 7!:2@]

(timespacex '+/ ,S') ; (timespacex '+/ ,T')

NB. =========================================================
Lab Section Summary
Here is the same example, where there are now 100,000 non-sparse elements:
)
PREPARE
timespacex=: 6!:2 , 7!:2@]
todense=: $. ^:_1
PREPARE
S=: <. 1 $. 10 100 1000

dat=: 100+i.1e5

ndx=: ?.(#dat)#,:$S

S=: dat (<"1 ndx)} S

T=: todense S

($ 3!:1 S) ; ($ 3!:1 T)

(timespacex '+/ ,S') ; (timespacex '+/ ,T')

NB. =========================================================
Lab Section
Sparse arrays are useful when you have large arrays, with most values being a common "sparse element". Ordinary J primitives work directly on sparse arrays. The $. verb converts to and from the sparse representation.

For more information about sparse arrays, see the entry for $. in the Vocabulary Help.
)
