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$
  • 1
    $\begingroup$ Like Table[SparseArray[Band[{1, 1}] -> 1, {4, 4}][[k]], {k, 4}]? $\endgroup$ – J. M.'s discontentment Feb 23 '16 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$ – becko Feb 23 '16 at 13:14
  • $\begingroup$ Well, you could replace the SparseArray[] in my snippet with yours, for example. $\endgroup$ – J. M.'s discontentment Feb 23 '16 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$ – becko Feb 23 '16 at 13:43
  • $\begingroup$ Can you give a (minimal?) example of a sparse matrix where this goes slow? $\endgroup$ – J. M.'s discontentment Feb 23 '16 at 13:48
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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Simple and fast! $\endgroup$ – becko Feb 23 '16 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 '16 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$ – becko Feb 23 '16 at 16:55
  • 3
    $\begingroup$ @rhermans I added the section Why Does This Work? $\endgroup$ – WReach Feb 23 '16 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.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hah, I'd done it as Identity /@ smat myself, but I wasn't sure if it was faster or slower than Table[]. $\endgroup$ – J. M.'s discontentment Feb 23 '16 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$ – Anton Antonov Feb 23 '16 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 *)
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ With the Table form dont'you extract only the first 9999 rows? $\endgroup$ – unlikely Feb 23 '16 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$ – becko Feb 23 '16 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 '16 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 '16 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.

| improve this answer | |
$\endgroup$

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.