# How to populate a large sparse array efficiently

I am trying to populate a large 2D sparse array and sum up all the columns at the end. I tried generating a set of rules and then generate a matrix using SparseArray or break the data into chunks but all of them were really slow!

So, let me explain what I am trying to do in a very simple code:

length = RandomInteger[{3, 6}, 4]
{3, 3, 3, 4}

value = Table[RandomReal[{}, length[[i]]], {i, 4}]
{{0.0854215, 0.281442, 0.224208}, {0.48975, 0.785775, 0.236305},{0.442947, 0.138147, 0.280603}, {0.434875, 0.0462578, 0.0704228, 0.494674}}

start = RandomInteger[{1, 6}, 4]
{2, 5, 1, 5}

sparseA = ConstantArray[0., {4, 20}];

Do[
sparseA[[i, start[[i]] + j - 1]] = value[[i, j]],
{i, 4},
{j, length[[i]]}]

sparseA
{
{0., 0.0854215, 0.281442, 0.224208, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.},
{0., 0., 0., 0., 0.48975, 0.785775, 0.236305, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.},
{0.442947, 0.138147, 0.280603, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.},
{0., 0., 0., 0., 0.434875, 0.0462578, 0.0704228, 0.494674, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}}

Total /@ Transpose[sparseA]
{0.442947, 0.223568, 0.562045, 0.224208, 0.924625, 0.832032, 0.306728, 0.494674, 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}


In the real code though 'length' contains 30,000 values ranging from 1500 to 2000,

'start' components are integers smaller than 120,000, and

'sparsA' is a 30,000 by 120,000 matrix.

Using the following to sim data of the actual size in your example:

length = RandomInteger[{1500, 2000}, 30000];

value = Table[RandomReal[{}, length[[i]]], {i, 30000}];

start = RandomInteger[{1, 118000}, 30000];


This takes a few seconds on a friggin' loungebook so I'd venture under a second on real hardware:

totLen = 120000;
accum = ConstantArray[0., totLen];
scanset = Transpose[{start, start + length - 1, value}];
Scan[(accum[[#[[1]] ;; #[[2]]]] += #[[3]]) &, scanset];


The end result is in accum obviously.

First of all, as a thumb rule - if you're using loops in Mathematica, you're probably not doing it right. See here and here for more details.

Second, the whole point of a sparse array is that you don't need to allocate all the memory for all the entries in advance, like you do with the command sparseA = ConstantArray[...].

Here's how it should be done:

rules = Flatten@
Table[{i, start[[i]] + j - 1} -> value[[i, j]], {i, 4}, {j, length[[i]]}];
sparseA = SparseArray[rules];


Lastly - if you only need the sum of each column, why do you bother generating a matrix, and not summing up your random numbers?

• For a very small dataset what you suggested works quite well. I have already tried this, generating 'rules' by Table is a very slow process. – Mahdi Razaz Sep 16 '15 at 14:18

If all you need is the sum at the end, why construct the matrix at all?

result = ConstantArray[0, 20];
Do[
result[[start[[i]] - 1 + Range[Length@value[[i]]]]] += value[[i]],
{i, 4}];
result


For such a sparse operation such a loop might just be the most efficient thing you can do.

Edit, a more mathematia-esque approach:

Fold[#1 +
SparseArray[ #2[[1]] - 1 +
Range[Length@#2[[2]]] -> #2[[2]] , {20}] &,
ConstantArray[0, 20], Transpose[{start, value}]]


If you do want to construct the whole sparse array try this:

sparseA = Fold[#1 + SparseArray[
Function[{row}, {row, #} & /@
(#2[[2]] - 1 + Range[Length@#2[[3]]])]@#2[[1]]
-> #2[[3]], Dimensions@#1] &,
SparseArray[{1, 1} -> 0, {Length@value, 20}],
Transpose[{Range@Length@value, start, value}]]


This puts each value in its own SparseArray and sums them up. I cant say if this will beat your loop for performance.

• I incorporated Fold in my code. it's the 2nd fastest way among the 3 methods I have tested. – Mahdi Razaz Sep 17 '15 at 12:56
• On the large set @ciao 's Scan is by far the fastest. My Do is 10x slower. My Fold is really slow. – george2079 Sep 17 '15 at 14:01