6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mahdi Razaz Sep 16 '15 at 14:18
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.