11
$\begingroup$

I have a matrix stored as a SparseArray. How can I convert it to a List of its rows, where each row is stored as a SparseArray?

Note that the matrix is huge, so the conversion should use as little memory as possible (the lower bound being the memory of the final List object).

$\endgroup$
5
  • 1
    $\begingroup$ Like Table[SparseArray[Band[{1, 1}] -> 1, {4, 4}][[k]], {k, 4}]? $\endgroup$ Feb 23, 2016 at 13:13
  • $\begingroup$ @J.M. Yes, that is the final representation I want. How do I convert an input sparse matrix to this form? $\endgroup$
    – a06e
    Feb 23, 2016 at 13:14
  • $\begingroup$ Well, you could replace the SparseArray[] in my snippet with yours, for example. $\endgroup$ Feb 23, 2016 at 13:16
  • $\begingroup$ @J.M. This works and gives the result that I want. However, for some reason it is very slow for me. Maybe there is a faster way? $\endgroup$
    – a06e
    Feb 23, 2016 at 13:43
  • $\begingroup$ Can you give a (minimal?) example of a sparse matrix where this goes slow? $\endgroup$ Feb 23, 2016 at 13:48

4 Answers 4

14
$\begingroup$

List @@ s will do the trick:

s = 1000000 // RandomInteger[{1, 1000000}, {#, 2}] -> RandomReal[1, #]& // SparseArray;

s // Head
(* SparseArray *)

s // Dimensions
(* {1000000, 1000000} *)

l = List @@ s;

l // Head
(* List *)

l // Dimensions
(* {1000000, 1000000} *)

l // First // Head
(* SparseArray *)

Take[l, 4]

sparse array screenshot

Why Does This Work?

Commentators observe that replacing the head of the (apparent) FullForm of a SparseArray ought to produce a nonsensical result. Why, then, does this work?

Despite appearances, a SparseArray is an atom:

SparseArray[Range[10]] // AtomQ
(* True *)

The full-form is therefore synthetic. Any operations that operate upon the (notionally non-existent) subparts of these atoms are implemented as special definitions. The documentation strongly implies that a SparseArray is meant to act virtually interchangeably with a regular List.

The Details section gives explicit examples where the parts of a multidimensional sparse array themselves appear as sparse arrays to operations like Map, Part, Listable, etc. In light of this, it stands to reason that replacing the notional head of a multidimensional sparse array with List would result in a list of sparse arrays. It is likely that the implementation has explicit code to handle this case.

I cannot point to a definitive statement in the documentation that guarantees the behaviour of List @@ s. But I would argue that it is so strongly implied that it would be a regression if it were changed in some future release.

$\endgroup$
4
  • $\begingroup$ Simple and fast! $\endgroup$
    – a06e
    Feb 23, 2016 at 16:24
  • 4
    $\begingroup$ Brilliant, but I don't understand why doest it work considering what is the FullForm of a SparseArray. Can you comment on the rationale behind? $\endgroup$
    – rhermans
    Feb 23, 2016 at 16:33
  • 3
    $\begingroup$ Actually I didn't understand either, I was just happy it worked. I second @rhermans request for further explanation. $\endgroup$
    – a06e
    Feb 23, 2016 at 16:55
  • 3
    $\begingroup$ @rhermans I added the section Why Does This Work? $\endgroup$
    – WReach
    Feb 23, 2016 at 18:33
3
$\begingroup$

Easy to do with Map.

This generates a random sparse matrix(array):

{m, n} = {1000, 2000};
pairs = Flatten[
   Outer[List, RandomInteger[{1, m}, Floor[0.7 m]], 
    RandomInteger[{1, n}, Floor[0.7 n]]], 1];
smat = SparseArray[
  Thread[pairs -> RandomReal[{0, 1}, Length[pairs]]], {m, n}]

enter image description here

Get the rows:

vecs = Map[# &, smat];

Verify it is all sparse arrays:

Shallow[Head /@ vecs]

(* Out[170]//Shallow= {SparseArray, SparseArray, SparseArray, \
SparseArray, SparseArray, SparseArray, SparseArray, SparseArray, \
SparseArray, SparseArray, <<990>>} *)

Here is some profiling code:

Profiling code:

memOld = MemoryInUse[];
timeOld = Date[];
vecs = Map[# &, smat];
memNew = MemoryInUse[];
timeNew = Date[];

(memNew - memOld)
(memNew - memOld)/memOld // N
timeNew - timeOld  

(* 12172576

   0.170369

  {0, 0, 0, 0, 0, 0.021384} *)

(I got the output on a 2.3 GHz Intel Core i7 MacBook Pro laptop with Mathematica 10.3.2.)

$\endgroup$
2
  • $\begingroup$ Hah, I'd done it as Identity /@ smat myself, but I wasn't sure if it was faster or slower than Table[]. $\endgroup$ Feb 23, 2016 at 14:19
  • 2
    $\begingroup$ I did some profiling: Identity /@ smat does not seem faster than #& /@ smat and it seems to be 10-20% less memory consuming. Of course the comparison should be done on a collection of sparse matrices with different sizes and densities. $\endgroup$ Feb 23, 2016 at 14:32
2
$\begingroup$

@WReach has provided the ultimate answer. Consider this an extended comment about the performance of ArrayRules


A large SparseArray

sa = SparseArray[
   Table[
    RandomInteger[{1, 99999}, 2] -> RandomReal[1]
    , 9999]
   ];

An example with Table that takes some time even for a subset of the rows (some list will be empty).

First@AbsoluteTiming[Table[sa[[k]], {k, 9999}]]
(* 2.68629 *)

But if you can get away with ArrayRules instead of SparseArray

First@AbsoluteTiming[GatherBy[Most@ArrayRules[sa], First@*First]]
(* 0.0172612 *)
$\endgroup$
4
  • 1
    $\begingroup$ With the Table form dont'you extract only the first 9999 rows? $\endgroup$
    – unlikely
    Feb 23, 2016 at 15:45
  • 1
    $\begingroup$ Yes, in the Table form you are missing most rows, that's why the timing is so small I think. $\endgroup$
    – a06e
    Feb 23, 2016 at 15:47
  • 1
    $\begingroup$ not a fair timing comparison unless you add the code to reconstruct the individual sparse arrays. $\endgroup$
    – george2079
    Feb 23, 2016 at 16:21
  • $\begingroup$ Yes, this of not for benchmark, times here are only to show that what is almost impossibly slow even for a subsection of a SparseArray becomes trivial with ArrayRules for the whole set. This may or may not be of use to the OP. $\endgroup$
    – rhermans
    Feb 23, 2016 at 16:25
1
$\begingroup$

If m contains your SparseArray

m = SparseArray[{{1, 2} -> a, {3, 2} -> b, {3, 3} -> c}];

enter image description here

then the following will return its list of sparse array rows.

m[[#]] & /@ Range[First@Dimensions@m]

enter image description here

Hope this helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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