6
$\begingroup$

I have a sparse matrix, and I am interested in find k largest elements and their positions in the matrix. I do it in the following manner:

matrix=SparseArray[Automatic, {4, 4}, 0, {
 1, {{0, 2, 5, 8, 10}, {{2}, {3}, {1}, {3}, {4}, {1}, {2}, {4}, {2}, {
   3}}}, {1.6608834828359216`, 1.3176250784021715`, 
  1.6608834828359216`, 3.8979590937707167`, 2.058499550409593, 
  1.3176250784021715`, 3.8979590937707167`, 1.0569052092863416`, 
  2.058499550409593, 1.0569052092863416`}}];
k = 2;
TakeLargest[Association@Most[ArrayRules[matrix]], k]

I look for a more efficient way to do it, any suggestion on how to speed up this calculation in huge matrices are welcome.

Improve this question
$\endgroup$
2
  • $\begingroup$ @kglr I did not mean to diss you away. Your methods are still viable for dense matrices. $\endgroup$
    – Henrik Schumacher
    Jul 15, 2018 at 14:19
  • $\begingroup$ @HenrikSchumacher, not to worry:) I deleted it because the question is explicitly about sparse arrays. $\endgroup$
    – kglr
    Jul 15, 2018 at 14:24

1 Answer 1

Reset to default
10
$\begingroup$

For sparse matrices, the key is to perform the search only on the list of nonzero values.

With[{idx = Ordering[matrix["NonzeroValues"], -k]},
 AssociationThread[
  matrix["NonzeroPositions"][[idx]],
  matrix["NonzeroValues"][[idx]]
  ]
]

Beware that this completely neglects the zero valued entries.

Remark

This will take postive effect only for really large and sparse matrices. For example, the following matrix would need 745 GB(!) of memory if it was stored (and sorted) as a dense array.

n = 100000;
m = 600000;
A = SparseArray[RandomInteger[{1, n}, {m, 2}] -> RandomReal[{0, 1}, m], {n, n}];
k = 100;

But still, finding the 100 largest nonzero elements needs about an 8th part of a second.

a = With[{idx = Ordering[A["NonzeroValues"], -k]},
    AssociationThread[A["NonzeroPositions"][[idx]], 
     A["NonzeroValues"][[idx]]]
    ]; // RepeatedTiming

0.124

Edit

Incorporating Carl's and kglr's suggestion to use Nearest like in this post, we can get even faster:

a = With[{idx = Nearest[A["NonzeroValues"] -> Automatic, Max[A], k]},
     AssociationThread[
      A["NonzeroPositions"][[idx]],
      A["NonzeroValues"][[idx]]
      ]
     ]; // RepeatedTiming // First

0.0051

Note that this returns the largest value first. Of course, we can Reverse the output of Nearest, if needed.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Where are these properties documented as I don't see them in the SparseArray documentation. $\endgroup$
    – Edmund
    Jul 15, 2018 at 11:53
  • 1
    $\begingroup$ @Edmund Sadly, they are documented nowhere. The more important are SE posts like this and this. I learnt these things solely from this site. What a shame! $\endgroup$
    – Henrik Schumacher
    Jul 15, 2018 at 12:46
  • 2
    $\begingroup$ Ordering[matrix["NonzeroValues"], -k] with k greater than 1 will sort the data, and so it is quite slow. You could instead use Nearest[matrix["NonzeroValues"]->"Index", Max[data], k] as in my answer to (154944), which will be much faster when the nonzero length is large. $\endgroup$
    – Carl Woll
    Jul 15, 2018 at 12:53
  • 1
    $\begingroup$ Carl, very good point! Wouldn't that suggest the reimplementation of the two-argument version of Ordering, at least for vectors? $\endgroup$
    – Henrik Schumacher
    Jul 15, 2018 at 13:06

Your Answer

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

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