Selecting from a matrix according to elements of a column -- efficiency and speed?

Question

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.

Answer 1

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).