# How to speed up Select with MemberQ for large lists?

I have two large lists: list1 and list2. I would like to select elements of list1 only if they appear in list2. Since the list1 has dimensions of (335000, 2) and list2 : (122000, 4), it's taking a very long time.

How could I speed up the process?

Select[list1, MemberQ[list2[[All, 2]], #[[1]]] &]

• – shrx Jun 6 '15 at 13:11
• well Intersection helps but doesn't quite do it because I want to keep the whole element, not only the key that is to be found in list2... – Cancan Jun 6 '15 at 13:27
• One should not have to decode your code to figure out format of lists - please add some simple list1/2 examples. – ciao Jun 6 '15 at 22:20
• @ciao would you consider adding examples yourself, please? – Mr.Wizard Sep 5 '17 at 6:57
• @Mr.Wizard - I don't know what you mean. – ciao Sep 5 '17 at 7:04

This should be pretty snappy:

With[{t = First@Transpose@#1, t2 = Transpose[#2][[2]]},
Pick[#1, Replace[t, Dispatch[Thread[Rule[Intersection[t, t2], True]]], {1}]]] &[list1, list2]

• thanks ciao, it is really fast! – Cancan Jun 8 '15 at 20:38
• What would I have change where if I wanted to match column 2 of list1 with column 3 of list2? – Cancan Jun 8 '15 at 20:40
• @Cancan: ...Transpose[#1][[2]], t2 = Transpose[#2][[3]]..., etc. – ciao Jun 8 '15 at 20:59
• @Cancan: Or perhaps more useful : With[{t = Transpose[#1][[#3]], t2 = Transpose[#2][[#4]]}, Pick[#1, Replace[t, Dispatch[ Thread[Rule[Intersection[t, t2], True]]], {1}]]] &[list1, list2, 2, 3] - so this has last two arguments being the cols. for lists 1/2... this form also can be used obviously for any size sublists pair of lists... – ciao Jun 8 '15 at 21:02
• Thanks, this form is great! I tried to use it for selection based on 2 columns together but it didn't work: ...[list1, list2, {1,2},{2,4}], what would you recommend? Also, I tried to use it for selection based on a ! MemberQ pattern but it didn't work, how would you do it with this form? – Cancan Jun 13 '15 at 20:51

Perhaps not the fastest, but reasonably fast (requires V10+):

Select[Association[Thread[list2[[All, 2]] -> True]] @* First][list1]


A slightly slower version of this to use for earlier versions:

With[{rules = Dispatch[Thread[list2[[All, 2]] -> True]]},
Select[list1, Replace[First[#], rules] &]
]

• thanks but I use V9... :( – Cancan Jun 6 '15 at 13:25
• @Cancan I updated the answer with code that should work for you. – Leonid Shifrin Jun 6 '15 at 13:30
• This was similar to my option!.. I lost by few minutes. :) +1 – Murta Jun 8 '15 at 11:59
• thanks Leonid! it works but it is not as fast than ciao's answer, which is why I accepted his answer. – Cancan Jun 8 '15 at 20:41
• @Cancan Sure, it is always proper to accept the best answer. I voted for that one, too. – Leonid Shifrin Jun 8 '15 at 21:37

One can make use of Nearest for this purpose (I should mention that the speed improvement may only occur in M11.1+). Here is a function that does this:

carl[l1_,l2_] := With[{nf = Nearest[l2[[All, 2]] -> "Index"]},
Pick[
l1,
Unitize[Length /@ nf[l1[[All, 1]], {All, 0}]],
1
]
]


The key idea is the use of the {All, 0} spec for the NearestFunction nf, that only returns a result for exact hits. Let's compare this to @ciao's approach (modified to be a function):

ciao[l1_, l2_] := With[{t = First@Transpose@l1, t2 = Transpose[l2][[2]]},
Pick[
l1,
Replace[t, Dispatch[Thread[Rule[Intersection[t, t2],True]]], {1}]
]
]

data1 = RandomInteger[10^6, {335000,2}];
data2 = RandomInteger[10^6, {122000,4}];

r1 = ciao[data1, data2]; //RepeatedTiming
r2 = carl[data1, data2]; //RepeatedTiming

r1 === r2


{0.41, Null}

{0.17, Null}

True

So, a speed up of about 2.5.

Update

After further thought, it makes sense to apply NearestFunction to the other data list. So, here is a version that uses this approach:

carl2[l1_, l2_] := With[{nf = Nearest[l1[[All,1]]->"Index"]},
l1[[Union @@ nf[l2[[All, 2]], {All, 0}]]]
]


Here is another speed comparison:

data1 = RandomInteger[10^6, {335000,2}];
data2 = RandomInteger[10^6, {122000,4}];

r1 = ciao[data1, data2]; //RepeatedTiming
r2 = carl[data1, data2]; //RepeatedTiming
r3 = carl2[data1, data2]; //RepeatedTiming

r1 === r2 === r3


{0.37, Null}

{0.17, Null}

{0.10, Null}

True

A nice speed up!

• Nice. +1 $\phantom{}$ – ciao Sep 5 '17 at 6:18