1
$\begingroup$

I need to select all elements from matrix M that have in their 3rd column elements from some given list L (3rd column and L are real numbers). I have written the most obvious (to me) command to select this subset:

S = Select[M, MemberQ[L, #[[3]]] &];    

The problem is that my matrix has 15 millions rows (and 30 columns), L has 500 000 elements and this operation takes ages (on my PC with 32 GB Ram it is running already for more than 24h).

Before I started, my only thought on how to improve the speed was to sort both M and L in increasing order (I mean sort M according to the increasing order of elements of its 3rd column). However it does not seem to help.

I will be grateful for any suggestions.

$\endgroup$
  • $\begingroup$ Dense matrix or sparse matrix? What kind of data? $\endgroup$ – Henrik Schumacher Jan 18 at 17:19
  • $\begingroup$ Hi, it is a dense matrix. The relevant column and the list contain only integers. Other columns contain all types -- bytes, longs, doubles, strings etc. $\endgroup$ – Kass Jan 18 at 17:23
2
$\begingroup$

This does the job for pure integer matrices (hence for packed arrays) in less than 10 seconds on my machine.

n = 500000;
L = RandomInteger[{1, 2 n}, n];
M = RandomInteger[{1, 2 n}, {30 n, 30}];
nf = Nearest[L -> Automatic]; // AbsoluteTiming // First
column = Developer`ToPackedArray[M[[All, 3]]];
rowidx = Random`Private`PositionsOf[
     Developer`ToPackedArray[Length /@ nf[column, {1, 0}]],
     1
     ]; // AbsoluteTiming // First
subM = M[[rowidx]]; // AbsoluteTiming // First

0.065254

8.17927

0.925655

The same strategy applies for purely real matrices. If M is of mixed type, the final read operation may take significantly longer, but looking up the row indices should take essentially the same time.

The key ingredient is to use Nearest. This will internally create a binary(?) search tree that speeds up the search tremendously. With nf[column, {1, 0}], I specify that I want to fine at most 1 entry in L and only if I have a perfect match (distance 0).

$\endgroup$
  • $\begingroup$ Nearest[ ] is definitely a powerful search tool. $\endgroup$ – MikeY Jan 18 at 18:17
  • $\begingroup$ Fantastic -- it sorted out even a bigger file of 25 millions rows in less than 15 seconds. Thanks a lot!! $\endgroup$ – Kass Jan 21 at 14:28
  • $\begingroup$ You're welcome! $\endgroup$ – Henrik Schumacher Jan 21 at 15:10

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.